Python的内置字典是如何实现的
有没有人知道如何在python内置的字典types实现？ 我的理解是这是一个哈希表，但我一直没能find任何明确的答案。
这里是关于我可以放在一起的Python字典的一切（可能比任何人都想知道的更多;但答案是全面的）。
- Python字典被实现为散列表 。
- 散列表必须允许散列冲突，即使两个不同的键具有相同的散列值，表的实现也必须具有明确插入和检索键和值对的策略。
- Python
dict使用开放寻址来解决散列冲突（下面解释）（参见dictobject.c：296-297 ）。 - Python哈希表只是一个连续的内存块（有点像一个数组，所以你可以通过索引进行
O(1)查找）。 - 表格中的每个插槽可以存储一个且只有一个条目。 这个很重要。
- 表中的每个条目实际上是三个值的组合： <hash，key，value> 。 这是作为C结构实现的（请参阅dictobject.h：51-56 ）。
-
下图是一个Python哈希表的逻辑表示。 在下面的图中，左边的
0, 1, ..., i, ...是散列表中的槽的索引（它们仅仅是用于说明的目的，并不明显与表一起存储）。# Logical model of Python Hash table -+-----------------+ 0| <hash|key|value>| -+-----------------+ 1| ... | -+-----------------+ .| ... | -+-----------------+ i| ... | -+-----------------+ .| ... | -+-----------------+ n| ... | -+-----------------+ -
当一个新的字典被初始化时，它从8 个插槽开始。 （见dictobject.h：49 ）
- 当向表中添加条目时，我们从基于密钥哈希的某个时隙开始。 CPython最初使用
i = hash(key) & mask（其中mask = PyDictMINSIZE - 1，但这并不重要）。 只要注意，被检查的最初的插槽i取决于密钥的散列 。 - 如果该槽为空，则将该条目添加到槽（通过条目，我的意思是
<hash|key|value>）。 但是，如果这个插槽被占用了！ 很可能是因为另一个条目具有相同的散列（散列冲突！） - 如果该槽被占用，则CPython（甚至PyPy）比较该槽中的条目与要插入的当前条目的散列和键的散列和键（通过比较我的意思是比较而不是比较） dictobject.c：337,344-345 ）。 如果两者匹配，则认为该条目已经存在，放弃并移动到下一个要插入的条目。 如果散列或密钥不匹配，则开始探测 。
- 探测只是意味着它通过插槽search插槽来查找空插槽。 从技术上讲，我们可以一个接一个，
i+1, i+2, ...并使用第一个可用的（即线性探测）。 但是，由于在评论中精美的解释（见dictobject.c：33-126 ），CPython使用随机探测 。 在随机探测中，下一个时隙是以伪随机顺序选取的。 该条目被添加到第一个空插槽。 对于这个讨论，用于select下一个时隙的实际algorithm并不重要（有关探测algorithm，请参见dictobject.c：33-126 ）。 重要的是插槽被探测，直到find第一个空插槽。 - 同样的事情发生的查找，只是从最初的槽我（我在哪里取决于密钥的散列）开始。 如果散列和密钥都与时隙中的条目不匹配，则开始探测，直到find一个匹配的时隙。 如果所有插槽都耗尽，则报告失败。
- 顺便说一句，如果
dict是三分之二，dict将会被调整。 这可以避免查找速度变慢。 （见dictobject.h：64-65 ）
注：我做了关于Python Dict实现的研究，以回应我自己关于字典中多个条目可以具有相同散列值的问题。 我在这里发布了一个稍微修改过的版本，因为所有的研究都是针对这个问题的。
Python字典使用开放寻址 （ 参考美丽的代码 ）
NB！ 开放寻址 ，也叫做封闭散列 ，正如维基百科所指出的那样，不要把它与对面的开放散列相混淆！
开放寻址意味着字典使用数组槽，当在字典中使用对象的主要位置时，使用“扰动”scheme在同一数组的不同索引处寻找对象的斑点，其中对象的散列值扮演angular色。
Python的内置字典是如何实现的？
以下是短期课程：
- 他们是哈希表。
- 从Python 3.6开始，一个新的过程/algorithm使得它们成为可能
- 按键插入sorting，和
- 占用较less的空间，
- 在性能上几乎没有任何成本。
- 当字典共享密钥时（特殊情况下），另一个优化节省空间。
有序的方面可能会停留，但目前是非官方的，程序不应该像Python 3.6那样写出这样的期望。
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位的进程中，在resize之前，我们有72个字节是空的，之后，由于有10个空行，我们浪费了240个字节。
这占用了很多空间，但查找时间相当稳定。 关键比较algorithm是计算散列，到期望的位置，比较键的id – 如果它们是相同的对象，它们是相等的。 如果不是，那么比较散列值，如果它们不相同，则不相等。 否则，我们最后比较键的相等性，如果它们相等，则返回值。 对于平等的最后比较可能会很慢，但早期的检查通常会缩短最后的比较，从而使查找速度非常快。
（碰撞减慢了速度，攻击者理论上可以使用散列冲突来执行拒绝服务攻击，所以我们将散列函数进行了随机化，以便为每个新的Python进程计算不同的散列值。
上述浪费的空间导致我们修改词典的实施，并且现在（通过插入）订购字典的一个令人兴奋的新（如果非官方的）特征。
新的紧凑哈希表
我们开始，而是通过预先分配插入索引的数组。
由于我们的第一个键值对在第二个槽中，所以我们索引如下：
[null, 0, null, null, null, null, null, null]
而我们的表只是通过插入顺序填充：
hash key value ...010001 ffeb678c 633241c4 ... ... ...
所以当我们查找一个关键字时，我们使用散列来检查我们期望的位置（在这种情况下，我们直接去索引数组索引1），然后到散列表中的索引（例如索引0 ），检查键是否相等（使用前面所述的相同algorithm），如果是，则返回值。
我们保持不变的查找时间，在某些情况下速度损失较小，而在其他情况下则有一定的提升，相比之下，我们节省了相当多的空间。 唯一浪费的空间是索引数组中的空字节。
Raymond Hettinger于2012年12月向python-dev介绍了这个function，最后在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__ ，并保证不会创build__slots__ __init__ （如果父类不可用），或者甚至允许__dict__但保证无论如何，您预见的属性都存储在插槽中。 有关__slots__更多信息， 请参阅我的答案 。
也可以看看：
- PEP 509 – 添加一个私人版本的字典
- PEP 468 – 在函数中保存
**kwargs的顺序。 - PEP 520 – 保留类属性定义顺序
- PyCon 2010：可能字典 – 布兰登罗德斯
- PyCon 2017：词典甚至更强大 – 布兰登罗德斯
- PyCon 2017：现代Python字典十几个伟大的想法 – Raymond Hettinger的汇合
- dictobject.c – CPython在C中实际的dict实现
这是一个哈希表。 你可以在python wiki上阅读一些。 否则，代码写得很好，应该很容易理解。
