Python 的内置字典是如何实现的？
有谁知道python的内置字典类型是如何实现的？我的理解是它是某种哈希表，但我无法找到任何明确的答案。
这是我能够汇总的有关 Python dicts 的所有内容（可能比任何人都想知道的要多；但答案很全面）。
Python 字典被实现为哈希表。
散列表必须允许散列冲突，即即使两个不同的键具有相同的散列值，表的实现也必须具有明确地插入和检索键和值对的策略。
Python dict 使用开放寻址来解决哈希冲突（如下所述）（参见 dictobject.c:296-297）。
Python 哈希表只是一个连续的内存块（有点像一个数组，所以你可以按索引进行 O(1) 查找）。
表中的每个槽可以存储一个且仅一个条目。这个很重要。
表中的每个条目实际上是三个值的组合：
下图是 Python 哈希表的逻辑表示。在下图中，左边的 0, 1, ..., i, ... 是哈希表中槽的索引（它们仅用于说明目的，显然不与表一起存储！）。 # Python Hash表的逻辑模型-+-----------------+ 0| <散列|键|值>| -+-----------------+ 1| ... | -+-----------------+ .| ... | -+-----------------+ 我| ... | -+-----------------+ .| ... | -+-----------------+ n| ... | -+-----------------+
当一个新的字典被初始化时，它从 8 个插槽开始。 （见 dictobject.h:49）
当向表中添加条目时，我们从某个插槽 i 开始，它基于键的哈希值。 CPython 最初使用 i = hash(key) & mask（其中 mask = PyDictMINSIZE - 1，但这并不重要）。请注意，检查的初始槽 i 取决于密钥的哈希值。
如果该槽为空，则将条目添加到槽中（通过条目，我的意思是
如果插槽被占用，CPython（甚至 PyPy）会将插槽中条目的哈希和键（通过比较我的意思是 == 比较而不是比较）与要插入的当前条目的哈希和键进行比较（ dictobject.c:337,344-345) 分别。如果两者都匹配，则认为该条目已经存在，放弃并继续插入下一个条目。如果散列或密钥不匹配，则开始探测。
探测只是意味着它按插槽搜索插槽以找到一个空插槽。从技术上讲，我们可以一个一个地进行，i+1，i+2，...并使用第一个可用的（即线性探测）。但是由于注释中解释得很清楚的原因（参见 dictobject.c:33-126），CPython 使用随机探测。在随机探测中，以伪随机顺序选择下一个槽。该条目被添加到第一个空槽。对于本次讨论，用于选择下一个插槽的实际算法并不重要（有关探测算法，请参见 dictobject.c:33-126）。重要的是探测槽直到找到第一个空槽。
查找也会发生同样的事情，只是从初始槽 i 开始（其中 i 取决于键的哈希）。如果散列和键都与槽中的条目不匹配，它开始探测，直到找到匹配的槽。如果所有插槽都用尽，则报告失败。
顺便说一句，如果字典已满三分之二，它将调整大小。这样可以避免减慢查找速度。 （见 dictobject.h:64-65）
注意：我对 Python Dict 实现进行了研究，以回应我自己的 question，即 dict 中的多个条目如何具有相同的哈希值。我在这里发布了一个稍微编辑过的回复版本，因为所有研究都与这个问题非常相关。
Python 的内置字典是如何实现的？
这是短期课程：
它们是哈希表。 （有关 Python 实现的详细信息，请参见下文。）
从 Python 3.6 开始，一种新的布局和算法使它们按键插入排序，并且占用更少的空间，几乎没有性能成本。
按插入键排序，和
占用更少的空间，
几乎没有性能成本。
当 dicts 共享键时（在特殊情况下），另一个优化可以节省空间。
从 Python 3.6 开始，有序方面是非官方的（让其他实现有机会跟上），但是 official in Python 3.7。
Python 的字典是哈希表
很长一段时间，它的工作原理就是这样。 Python 将预先分配 8 个空行并使用哈希来确定键值对的粘贴位置。例如，如果键的散列以 001 结尾，它会将其粘贴在第 1（即第 2）索引中（如下例所示。）
<hash> <key> <value>
null null null
...010001 ffeb678c 633241c4 # addresses of the keys and values
null null null
... ... ...
在 64 位架构上，每行占用 24 个字节，在 32 位架构上占用 12 个字节。 （请注意，这里的列标题只是用于我们目的的标签 - 它们实际上并不存在于内存中。）
如果散列与先前存在的键的散列结束相同，则这是一个冲突，然后它将键值对粘贴在不同的位置。
存储5个key-value后，再添加一个key-value对时，hash冲突的概率太大，所以字典的大小翻了一番。在 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。按插入排序被认为是 3.6 的实现细节，以允许 Python 的其他实现有机会赶上。
共享密钥
另一个节省空间的优化是共享密钥的实现。因此，我们不再拥有占据所有空间的冗余字典，而是拥有重复使用共享键和键的哈希值的字典。你可以这样想：
hash key dict_0 dict_1 dict_2...
...010001 ffeb678c 633241c4 fffad420 ...
... ... ... ... ...
对于 64 位机器，这可以为每个额外字典的每个键节省多达 16 个字节。
自定义对象和替代品的共享密钥
这些共享密钥字典旨在用于自定义对象的 __dict__。要获得这种行为，我相信您需要在实例化下一个对象 (see PEP 412) 之前完成填充 __dict__。这意味着您应该在 __init__ 或 __new__ 中分配所有属性，否则您可能无法节省空间。
但是，如果您在执行 __init__ 时知道所有属性，您还可以为您的对象提供 __slots__，并保证根本不创建 __dict__（如果在父级中不可用），或者甚至允许 __dict__ 但保证您预见的属性无论如何都存储在插槽中。有关 __slots__ 的更多信息，see my answer here。
也可以看看：
PEP 509 -- 向 dict 添加私有版本
PEP 468 -- 在函数中保留 **kwargs 的顺序。
PEP 520 - 保留类属性定义顺序
PyCon 2010: The Might Dictionary - Brandon Rhodes
PyCon 2017：更强大的词典 - Brandon Rhodes
PyCon 2017：现代 Python 词典融合了十几个伟大的想法 - Raymond Hettinger
dictobject.c - CPython 在 C 中的实际 dict 实现。
find_empty_slot: github.com/python/cpython/blob/master/Objects/dictobject.c#L969 -从第 134 行开始，有一些散文描述它。
Python 字典使用 Open addressing (reference inside Beautiful code)
注意！正如维基百科中所指出的，开放寻址，又称封闭散列，不应与其相反的开放散列混淆！
开放寻址意味着字典使用数组槽，当对象的主要位置在字典中时，使用“扰动”方案在同一数组中的不同索引处寻找对象的位置，其中对象的哈希值起作用.
