有人知道Python内置字典类型是如何实现的吗？我的理解是它是一种哈希表，但我还没有找到任何明确的答案。
4个回答
727
编辑：
这个答案适用于Python 3.6之前的版本。对于Python 3.6及以上版本，请参考下面的russia-must-remove-putin's answer。
原文：
这里是关于Python字典的所有内容，我尽力整理了一切（可能比任何人想知道的都多；但这个答案是全面的）。
哈希表必须允许哈希冲突，即使两个不同的键具有相同的哈希值，表的实现也必须有一种策略来明确地插入和检索键值对。
Python的dict使用开放寻址来解决哈希冲突（下面会解释）（参见dictobject.c:296-297）。
Python的哈希表只是一个连续的内存块（类似于数组），因此可以通过索引进行O(1)的查找。
表中的每个槽位只能存储一个条目。这很重要。
表中的每个条目实际上是三个值的组合：<哈希，键，值>。这是作为C结构实现的（参见dictobject.h:51-56）。
下图是Python哈希表的逻辑表示。在下图中，左侧的0、1、...、i等是哈希表中槽位的索引（它们仅用于说明目的，显然不与表一起存储）。
# Python哈希表的逻辑模型 -+-----------------+ 0| | -+-----------------+ 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）。重要的是，直到找到第一个空槽位为止，都会进行探测。
查找时也是同样的情况
注意：我对Python字典实现进行了研究，以回答我自己关于字典中多个条目如何具有相同哈希值的问题。我在这里发布了略微编辑过的回答版本，因为所有的研究对这个问题也非常相关。
- Praveen Gollakota
6
25当哈希和键都匹配时，插入操作会放弃并继续执行。在这种情况下，插入不会覆盖现有的条目吗？ - 0xc0de
2感谢@Praveen的精彩解释。
如果您还能提供一个字典插入、查找和删除的示例，那就更好了。 - Underoos
@PraveenGollakota，感谢您的回答...我的一个朋友在今天的CS直播课上讨论字典时提出了同样的问题，当他看到错误提示不可哈希类型被传递为键值时...我幸运地找到了您的答案并将其传递给了他。 - Sam Ruben Abraham
一个条目中的键和值是指向PyObjects（即PyObject *）的指针吗？ - Fırat Kıyak
非常感谢。但是，对象的哈希被转换为索引。所以显然，在索引内部，哈希应该与对象中的哈希匹配。如果键不匹配，那就意味着发生了哈希冲突，然后需要进行探测。 - Apurva Singh
调整字典的大小是不是非常昂贵？ - user129393192
124
这里是简短的介绍：
每一行在64位架构上占用24个字节，在32位上则占用12个字节。（请注意，列标题只是我们在此处使用的标签 - 它们实际上不存在于内存中。）
如果哈希值与先前存在的键的哈希值相同，则会发生冲突，然后将键-值对粘贴到另一个位置。
存储5个键值后，当添加另一个键值对时，哈希冲突的概率太大，因此字典的大小加倍。在64位进程中，在调整大小之前，我们有72个空字节，在之后，由于10个空行，我们浪费了240个字节。
这需要很多空间，但查找时间相当恒定。关键比较算法是计算哈希值，转到预期位置，比较键的id - 如果它们是同一个对象，则它们相等。如果不是，则比较哈希值，如果它们不相同，则它们不相等。否则，我们最终比较键是否相等，如果它们相等，则返回值。最终的相等比较可能非常缓慢，但是早期检查通常会捷径最终比较，使查找非常快速。
Collisions slow things down, and an attacker could theoretically use hash collisions to perform a denial of service attack, so we randomized the initialization of the hash function such that it computes different hashes for each new Python process.
The wasted space described above has led us to modify the implementation of dictionaries, with an exciting new feature that dictionaries are now ordered by insertion.
The New Compact Hash Tables
We start, instead, by preallocating an array for the index of the insertion.
Since our first key-value pair goes in the second slot, we index like this:
因此，当我们查找一个键时，我们使用哈希来检查我们期望的位置（在这种情况下，我们直接转到数组的索引1），然后转到哈希表中的该索引（例如，索引0），使用之前描述的相同算法检查键是否相等，如果是，则返回值。
我们保持常数查找时间，在某些情况下会有轻微的速度损失和其他情况下会有收益，好处是我们节省了相当多的空间，并且保留了插入顺序。唯一浪费的空间是索引数组中的空字节。
Raymond Hettinger于2012年12月在python-dev上介绍了这个方法。它最终在Python 3.6中加入了CPython。按插入顺序排序被认为是3.6的实现细节，以便让其他Python实现有机会赶上。
- 它们是哈希表（hash tables）。（有关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 - 如果它们是同一个对象，则它们相等。如果不是，则比较哈希值，如果它们不相同，则它们不相等。否则，我们最终比较键是否相等，如果它们相等，则返回值。最终的相等比较可能非常缓慢，但是早期检查通常会捷径最终比较，使查找非常快速。
Collisions slow things down, and an attacker could theoretically use hash collisions to perform a denial of service attack, so we randomized the initialization of the hash function such that it computes different hashes for each new Python process.
The wasted space described above has led us to modify the implementation of dictionaries, with an exciting new feature that dictionaries are now ordered by insertion.
The New Compact Hash Tables
We start, instead, by preallocating an array for the index of the insertion.
Since our first key-value pair goes in the second slot, we index like this:
[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__。为了获得这种行为，我认为您需要在实例化下一个对象之前完成填充__dict__（参见PEP 412）。这意味着您应该在__init__或__new__中分配所有属性，否则可能无法获得空间节省。
然而，如果您在执行__init__时知道所有属性，还可以为对象提供__slots__，并保证根本不创建__dict__（如果在父级中不可用），甚至允许__dict__但保证您预见到的属性仍存储在插槽中。有关__slots__的更多信息，请查看我的答案。
参见：
- PEP 509 -- 向字典添加私有版本
- PEP 468 -- 保留函数中
**kwargs的顺序。 - PEP 520 -- 保留类属性定义顺序
- PyCon 2010: The Might Dictionary - Brandon Rhodes
- PyCon 2017: The Dictionary Even Mightier - Brandon Rhodes
- PyCon 2017: Modern Python Dictionaries A confluence of a dozen great ideas - Raymond Hettinger
- dictobject.c - CPython实际的字典C实现。
- Russia Must Remove Putin
7
1你说“我们”，并且“为了让其他Python实现有机会赶上” - 这意味着你“知道一些事情”，而且那可能会成为一个永久的功能吗？字典按规范排序是否有任何缺点？ - toonarmycaptain
1有序的缺点是，如果期望字典是有序的，它们就不能轻松地切换到更好/更快的未排序实现。虽然这似乎不太可能发生。我“知道事情”的原因是我观看了许多核心成员和其他声誉比我更好的人编写的演讲和文章，因此即使我没有立即可用的引用来源，我通常也知道自己在谈论什么。但我认为你可以从雷蒙德·赫廷格(Raymond Hettinger)的其中一次演讲中得到这个观点。 - Russia Must Remove Putin
2你有点含糊地解释了插入的工作原理（“如果哈希值与已存在的键的哈希值相同，...那么它会将键值对粘贴到另一个位置” - 是吗？），但你没有解释查找和成员测试的工作原理。也不太清楚哈希如何确定位置，但我想大小总是2的幂，并且您取哈希的最后几位... - Alexey
在存储了五个键值对之后，字典的大小会翻倍。在64位进程中，在调整大小之前，我们有72个空字节，在调整大小之后，由于有10行为空，我们浪费了240个字节。
为什么不是264？8-5+8=11，11*24=264。 - filler36
清晰明了的解释。谢谢。您能否确认在冲突的情况下，Python仍然使用线性探测来压缩字典？ - S.B
显示剩余2条评论
1
Python字典现在维护两个索引。当第一个元素插入字典时，它的操作如下：
- 插入键值对 - 字典找到键的哈希值 - 字典将哈希值映射到一个索引 - 在稀疏数组中，找到该索引并输入数字0（第一次进行插入）
第二个数组是一个密集数组。它的操作如下：
- 在索引0处输入值
因此，第二个数组是紧凑且内存高效的。对于后续的插入操作，会递增第二个数组的插入索引。这样可以节省内存，并保持插入顺序。在向第一个稀疏数组插入索引时，可能会发生哈希冲突。这通过伪随机探测算法来处理，即在数组中以可预测但伪随机的方式向前查找空槽位。第二个数组始终是紧凑的。
- 插入键值对 - 字典找到键的哈希值 - 字典将哈希值映射到一个索引 - 在稀疏数组中，找到该索引并输入数字0（第一次进行插入）
第二个数组是一个密集数组。它的操作如下：
- 在索引0处输入值
因此，第二个数组是紧凑且内存高效的。对于后续的插入操作，会递增第二个数组的插入索引。这样可以节省内存，并保持插入顺序。在向第一个稀疏数组插入索引时，可能会发生哈希冲突。这通过伪随机探测算法来处理，即在数组中以可预测但伪随机的方式向前查找空槽位。第二个数组始终是紧凑的。
- Apurva Singh
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接