有谁知道python的内置字典类型是如何实现的？我的理解是它是某种哈希表，但我无法找到任何明确的答案。
问问题
114869 次
3 回答
652
这是我能够汇总的有关 Python dicts 的所有内容（可能比任何人都想知道的要多；但答案很全面）。
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| ... | -+-----------------+当一个新的 dict 被初始化时，它以 8个 slot开始。（见dictobject.h:49）
在向表中添加条目时，我们从某个插槽 开始
i，它基于键的哈希值。CPython 最初使用i = hash(key) & mask(wheremask = PyDictMINSIZE - 1，但这并不重要)。请注意，i检查的初始插槽 取决于密钥的哈希值。如果该插槽为空，则将条目添加到插槽中（通过条目，我的意思是，
<hash|key|value>）。但是如果那个插槽被占用了怎么办！？很可能是因为另一个条目具有相同的哈希（哈希冲突！）如果插槽被占用，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 Dict 实现进行了研究，以回答我自己关于dict 中的多个条目如何具有相同的哈希值的问题。我在这里发布了一个稍微编辑过的回复版本，因为所有研究都与这个问题非常相关。
于 2012-01-26T17:52:00.447 回答
100
Python 的内置字典是如何实现的？
这是短期课程：
- 它们是哈希表。（有关 Python 实现的详细信息，请参见下文。）
- 从 Python 3.6 开始，一种新的布局和算法使它们
- 按插入键排序，和
- 占用更少的空间，
- 几乎没有性能成本。
- 当 dicts 共享键时（在特殊情况下），另一个优化可以节省空间。
从 Python 3.6 开始，有序方面是非官方的（让其他实现有机会跟上），但在 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__。要获得这种行为，我相信您需要__dict__在实例化下一个对象之前完成填充（参见 PEP 412）。这意味着您应该在__init__or中分配所有属性__new__，否则您可能无法节省空间。
但是，如果您在__init__执行时知道所有属性，您还可以提供__slots__您的对象，并保证__dict__根本没有创建它（如果在父母中不可用），甚至允许__dict__但保证您预见的属性是无论如何都存储在插槽中。有关更多信息__slots__，请在此处查看我的回答。
也可以看看：
- 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 实现。
于 2017-06-12T21:54:15.970 回答