Python内建字典是如何实现的？
有没有人知道Python内置的字典类型是怎么实现的？我了解到它是一种哈希表，但我一直找不到确切的答案。
4 个回答
Python 字典使用了一种叫做 开放寻址 的方法（在《优雅代码》中的参考）。
注意！ 开放寻址，也叫 闭合哈希，不要和它的相对概念 开放哈希 混淆！
开放寻址的意思是，字典使用数组的槽位。当一个对象的主要位置在字典中被占用时，系统会在同一个数组中寻找这个对象的其他位置，使用一种叫做“扰动”的方法，这个方法中对象的哈希值会起到作用。
Python的内置字典是怎么实现的？
简单来说：
- 它们是哈希表。（下面会具体讲Python的实现方式。）
- 从Python 3.6开始，新的布局和算法让它们变得
- 按键插入的顺序排列，
- 占用更少的空间，
- 几乎没有性能损失。
- 另一个优化是在特殊情况下，当字典共享键时，可以节省空间。
从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中得以实现。插入顺序在3.6中被视为实现细节，以便让其他Python实现有机会赶上。
共享键
另一个节省空间的优化是共享键的实现。因此，我们不再有冗余的字典占用大量空间，而是有字典重用共享的键和键的哈希值。你可以这样理解：
hash key dict_0 dict_1 dict_2...
...010001 ffeb678c 633241c4 fffad420 ...
... ... ... ... ...
对于64位机器，这可以为每个额外的字典节省最多16字节。
自定义对象的共享键和替代方案
这些共享键的字典是为了自定义对象的__dict__而设计的。为了实现这种行为，我认为你需要在实例化下一个对象之前完成填充你的__dict__（参见PEP 412）。这意味着你应该在__init__或__new__中分配所有属性，否则你可能无法节省空间。
不过，如果你在执行__init__时就知道所有属性，你也可以为你的对象提供__slots__，这样可以保证根本不创建__dict__（如果父类中没有的话），或者即使允许__dict__的存在，也能保证你预设的属性存储在槽中。关于__slots__的更多信息，请参见我的回答。
另见：
- PEP 509 -- 为字典添加一个私有版本
- PEP 468 -- 在函数中保留
**kwargs的顺序。 - PEP 520 -- 保留类属性定义的顺序
- PyCon 2010: 强大的字典 - Brandon Rhodes
- PyCon 2017: 字典更强大 - Brandon Rhodes
- PyCon 2017: 现代Python字典的汇聚 - Raymond Hettinger
- dictobject.c - CPython中字典的实际实现（C语言）。
编辑：
这个回答适用于 Python 3.6 之前的版本。对于 Python 3.6 及以后的版本，请查看下面的 russia-must-remove-putin 的回答。
原文：
这里是关于 Python 字典（dict）的所有信息，我尽量整理了一下（可能比大家想知道的还要多，但这个回答是全面的）。
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| <hash|key|value>| -+-----------------+ 1| ... | -+-----------------+ .| ... | -+-----------------+ i| ... | -+-----------------+ .| ... | -+-----------------+ n| ... | -+-----------------+当一个新的字典被初始化时，它会从 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 字典实现进行了研究，回应我自己的 问题，关于字典中多个条目如何可以有相同的哈希值。我在这里发布了稍微编辑过的版本，因为所有的研究对这个问题也非常相关。