ric*_*ree 263 python dictionary data-structures
有谁知道如何实现python的内置字典类型？我的理解是它是某种哈希表,但我无法找到任何确定的答案.
Pra*_*ota 446
以下是我能够整理的Python dicts的所有内容(可能比任何人都想知道的更多;但答案是全面的).
dict使用开放式寻址来解决哈希冲突(如下所述)(参见dictobject.c:296-297).O(1)通过索引进行查找).下图是Python哈希表的逻辑表示.在下图中,0, 1, ..., i, ...左边是哈希表中的槽的索引(它们仅用于说明目的,并且不会与表一起存储!).
# Logical model of Python Hash table
-+-----------------+
0| <hash|key|value>|
-+-----------------+
1| ... |
-+-----------------+
.| ... |
-+-----------------+
i| ... |
-+-----------------+
.| ... |
-+-----------------+
n| ... |
-+-----------------+
初始化新的dict时,它以8 个插槽开始.(见dictobject.h:49)
i,这是基于密钥的散列.CPython最初使用i = hash(key) & mask(在哪里mask = PyDictMINSIZE - 1,但这并不重要).请注意,i检查的初始插槽取决于密钥的哈希值.<hash|key|value>).但如果那个插槽被占用怎么办？很可能是因为另一个条目具有相同的哈希值(哈希冲突!)==比较不is比较)在对哈希和当前项目的关键插槽的条目要插入(dictobject.c :分别为337,344-345.如果两者都匹配,则认为该条目已存在,放弃并继续下一个要插入的条目.如果散列或密钥不匹配,则开始探测.i+1, i+2, ...并使用第一个可用的(线性探测).但是由于在评论中精美解释的原因(参见dictobject.c:33-126),CPython使用随机探测.在随机探测中,以伪随机顺序拾取下一个时隙.该条目将添加到第一个空槽中.对于这个讨论,用于选择下一个槽的实际算法并不重要(参见dictobject.c:33-126,用于探测算法).重要的是探测插槽直到找到第一个空插槽.dict如果三分之二满,将重新调整大小.这可以避免减慢查找速度.(见dictobject.h:64-65)注意:我对Python Dict实现进行了研究,以回应我自己的问题,即dict中的多个条目如何具有相同的哈希值.我在这里发布了一个略微编辑的回复版本,因为所有的研究都与这个问题非常相关.
Aar*_*all 48
Python的内置词典是如何实现的？
这是短期课程:
从Python 3.6开始,有序方面是非官方的,但在Python 3.7中是官方的.
很长一段时间,它的工作原理与此类似.Python将预先分配8个空行并使用哈希来确定键值对的位置.例如,如果键的哈希值以001结尾,则会将其粘贴在1索引中(如下例所示).
<hash> <key> <value>
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]
我们的表只是通过插入顺序填充:
<hash> <key> <value>
...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__,请在此处查看我的答案.
**kwargs函数的顺序.