有谁知道如何实现python的内置字典类型？我的理解是它是某种哈希表,但我无法找到任何确定的答案.
1> Praveen Goll..：
以下是我能够整理的Python dicts的所有内容(可能比任何人都想知道的更多;但答案是全面的).
Python字典作为哈希表实现.
散列表必须允许散列冲突,即使两个不同的键具有相同的散列值,表的实现必须具有明确插入和检索键和值对的策略.
Python dict使用开放式寻址来解决哈希冲突(如下所述)(参见dictobject.c:296-297).
Python哈希表只是一个连续的内存块(有点像数组,所以你可以O(1)通过索引进行查找).
表中的每个插槽可以存储一个且仅存储一个条目.这个很重要.
表中的每个条目实际上是三个值的组合:.这是作为C结构实现的(参见dictobject.h:51-56).
下图是Python哈希表的逻辑表示.在下图中,0, 1, ..., i, ...左边是哈希表中的槽的索引(它们仅用于说明目的,并且不会与表一起存储!).
# Logical model of Python Hash table
-+-----------------+
0| |
-+-----------------+
1| ... |
-+-----------------+
.| ... |
-+-----------------+
i| ... |
-+-----------------+
.| ... |
-+-----------------+
n| ... |
-+-----------------+
初始化新的dict时,它以8 个插槽开始.(见dictobject.h:49)
在向表中添加条目时,我们从一些插槽开始i,这是基于密钥的散列.CPython最初使用i = hash(key) & mask(在哪里mask = PyDictMINSIZE - 1,但这并不重要).请注意,i检查的初始插槽取决于密钥的哈希值.
如果该插槽为空,则该条目将添加到插槽中(通过条目,我的意思是
如果插槽被占用,CPython的(甚至PyPy)比较哈希和密钥(通过比较我的意思是==比较不is比较)在对哈希和当前项目的关键插槽的条目要插入(dictobject.c :分别为337,344-345.如果两者都匹配,则认为该条目已存在,放弃并继续下一个要插入的条目.如果散列或密钥不匹配,则开始探测.
探测只是意味着它按插槽搜索一个空槽.从技术上讲,我们可以逐个进行,i+1, i+2, ...并使用第一个可用的(线性探测).但是由于在评论中精美解释的原因(参见dictobject.c:33-126),CPython使用随机探测.在随机探测中,以伪随机顺序拾取下一个时隙.该条目将添加到第一个空槽中.对于这个讨论,用于选择下一个槽的实际算法并不重要(参见dictobject.c:33-126,用于探测算法).重要的是探测插槽直到找到第一个空插槽.
同样的事情发生在查找中,只是从初始插槽i开始(其中i取决于密钥的散列).如果散列和密钥都与插槽中的条目不匹配,则它开始探测,直到找到具有匹配的插槽.如果所有插槽都耗尽,则报告失败.
顺便说一句,dict如果三分之二满,将重新调整大小.这可以避免减慢查找速度.(见dictobject.h:64-65)
注意:我对Python Dict实现进行了研究,以回应我自己的问题,即dict中的多个条目如何具有相同的哈希值.我在这里发布了一个略微编辑的回复版本,因为所有的研究都与这个问题非常相关.
您说过，当哈希和密钥都匹配时，它（插入op）就放弃并继续前进。在这种情况下不插入覆盖现有条目吗？
2> Aaron Hall..：
Python的内置词典是如何实现的？
这是短期课程:
它们是哈希表.
从Python 3.6开始,新的过程/算法就是这样做的
按键插入排序,和
占用更少的空间,
几乎没有性能成本.
当dicts共享密钥时(在特殊情况下),另一个优化节省了空间.
从Python 3.6开始,有序方面是非官方的,但在Python 3.7中是官方的.
Python的字典是哈希表
很长一段时间,它的工作原理与此类似.Python将预先分配8个空行并使用哈希来确定键值对的位置.例如,如果键的哈希值以001结尾,则会将其粘贴在1索引中(如下例所示).
null null null
...010001 ffeb678c 633241c4 # addresses of the keys and values
null null null
... ... ...
每行在64位架构上占用24个字节,在32位上占用12个字节.(请注意,列标题只是标签 - 它们实际上并不存在于内存中.)
如果散列与预先存在的键的散列结束相同,则这是一个冲突,然后它会将键值对粘贴在不同的位置.
存储5个键值后,当添加另一个键值对时,哈希冲突的概率太大,因此字典的大小加倍.在64位进程中,在调整大小之前,我们有72个字节为空,之后,由于10个空行,我们浪费了240个字节.
这需要很大的空间,但查找时间相当稳定.关键比较算法是计算哈希值,转到预期位置,比较密钥的id - 如果它们是同一个对象,它们是相等的.如果没有那么比较哈希值,如果它们不相同,它们就不相等.否则,我们最后比较密钥的相等性,如果它们相等,则返回值.相等的最终比较可能非常慢,但早期检查通常会使最终比较快捷,使查找速度非常快.
(冲突会减慢速度,理论上攻击者可以使用哈希冲突来执行拒绝服务攻击,因此我们将哈希函数随机化,以便为每个新的Python进程计算不同的哈希值.)
上面描述的浪费的空间使我们修改了字典的实现,带有一个令人兴奋的新(如果是非官方的)功能,字典现在被排序(通过插入).
新的紧凑哈希表
相反,我们通过为插入索引预分配数组来启动.
由于我们的第一个键值对进入第二个插槽,我们的索引如下:
[null, 0, null, null, null, null, null, null]
我们的表只是通过插入顺序填充:
...010001 ffeb678c 633241c4
... ... ...
所以当我们查找一个键时,我们使用哈希来检查我们期望的位置(在这种情况下,我们直接指向数组的索引1),然后转到哈希表中的那个索引(例如索引0) ),检查密钥是否相等(使用前面描述的相同算法),如果是,则返回值.
我们保持不变的查找时间,在某些情况下会有轻微的速度损失,而在其他情况下会有所增加,我们可以在预先存在的实现中节省相当多的空间.浪费的唯一空间是索引数组中的空字节.
Raymond Hettinger 在2012年12月向python-dev介绍了它.它终于在Python 3.6中进入了CPython .通过插入排序仍然被认为是一个实现细节,以允许Python的其他实现有机会赶上.
共享密钥
节省空间的另一个优化是共享密钥的实现.因此,我们没有冗余字典占用所有空间,而是使用重用共享密钥和密钥哈希的字典.你可以这样想:
hash key dict_0 dict_1 dict_2...
...010001 ffeb678c 633241c4 fffad420 ...
... ... ... ... ...
对于64位计算机,每个额外字典每个密钥最多可以节省16个字节.
自定义对象和替代项的共享密钥
这些共享密钥dicts旨在用于自定义对象__dict__.为了得到这种行为,我相信你需要__dict__在实例化下一个对象之前完成填充(参见PEP 412).这意味着您应该在__init__或中分配所有属性__new__,否则您可能无法节省空间.
但是,如果您在执行时知道所有属性__init__,那么您也可以提供__slots__对象,并保证__dict__根本不创建(如果在父项中不可用),或者甚至允许__dict__但保证您的预见属性是无论如何都存储在插槽中.有关更多信息__slots__,请在此处查看我的答案.
也可以看看:
PEP 509 - 为dict添加私有版本
PEP 468 - 保留**kwargs函数的顺序.
PEP 520 - 保留类属性定义顺序
PyCon 2010:The Might Dictionary - Brandon Rhodes
PyCon 2017:字典甚至更强 - Brandon Rhodes
PyCon 2017:现代Python词典十几个伟大的想法汇集 - 雷蒙德Hettinger
dictobject.c - CPython在C中的实际dict实现.
3> u0b34a0f6ae..：
Python字典使用Open寻址(美丽代码中的引用)
NB! 如维基百科所述,开放式寻址,即封闭散列应该不会与其相反的开放散列相混淆!
开放寻址意味着dict使用数组槽,并且当在dict中获取对象的主要位置时,使用"扰动"方案在同一阵列中的不同索引处寻找对象的斑点,其中对象的散列值起作用.
*"不要与其相反的开放哈希相混淆!(我们在接受的答案中看到)."* - 我不确定当你写这个答案时接受了哪个答案,或者那个答案在当时说的是什么 - 但这个括号对于已接受的答案,评论目前不正确,最好将其删除.
京公网安备 11010802040832号