Python的内置字典是如何实现的
有谁知道python的内置字典类型是如何实现的？ 我的理解是它是某种散列表，但我一直没能找到任何明确的答案。
以下是我能够放在一起的所有Python字典（可能比任何人都想知道的更多;但答案是全面的）。
dict使用开放寻址来解决散列冲突（如下所述）（请参阅dictobject.c：296-297）。 O(1)查找）。 下图是Python哈希表的逻辑表示。 在下面的图中，左边的0, 1, ..., i, ...是散列表中的槽的索引（它们仅用于说明的目的，并不明显与表一起存储）。
# Logical model of Python Hash table
-+-----------------+
0| <hash|key|value>|
-+-----------------+
1| ... |
-+-----------------+
.| ... |
-+-----------------+
i| ... |
-+-----------------+
.| ... |
-+-----------------+
n| ... |
-+-----------------+
当一个新的字典被初始化时，它从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实现的研究，以回应我自己关于字典中多个条目可以具有相同散列值的问题。 我在这里发布了一个稍微修改过的版本，因为所有的研究都与这个问题非常相关。
Python字典使用开放寻址（美丽代码中的引用）
NB！ 正如维基百科所指出的，开放寻址（又名封闭散列）应该不会与其相反的开放散列相混淆！
开放寻址意味着字典使用数组槽，当字典中使用对象的主要位置时，使用“扰动”方案在同一数组的不同索引处寻找对象的斑点，其中对象的散列值扮演角色。
Python的内置字典是如何实现的？
以下是短期课程：
有序的方面在Python 3.6中是非官方的，但是在Python 3.7中是官方的。
Python的字典是哈希表
很长一段时间，它的确如此。 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个字节。
自定义对象和替代方案的共享密钥
这些共享键字典旨在用于自定义对象__dict__ 。 为了得到这种行为，我相信你需要在实例化下一个对象之前完成填充你的__dict__ （见PEP 412）。 这意味着您应该在__init__或__new__分配所有属性，否则可能无法节省空间。
但是，如果您在执行__init__时知道所有属性，则还可以为对象提供__slots__ ，并确保__dict__不创建__slots__ __init__ （如果父项不可用），或者甚至允许__dict__但保证无论如何，您的预见属性都存储在插槽中。 有关__slots__更多信息，请参阅我的答案。
也可以看看：
**kwargs的顺序。 上一篇: How are Python's Built In Dictionaries Implemented
下一篇: Check existence of input argument in a Bash shell script