问题描述：

有人知道 python 的内置字典类型是如何实现的吗？我的理解是它是某种哈希表，但我找不到任何明确的答案。

解决方案 1：

编辑：

此答案适用于 Python 3.6 之前的版本。对于 Python 3.6 及更高版本，请参阅下面russia-must-remove-putin 的答案。

原来的：

这是我整理的有关 Python 字典的所有内容（可能比任何人想知道的都多；但答案是全面的）。

• Python 字典以哈希表的形式实现。

• 哈希表必须允许哈希冲突，即，即使两个不同的键具有相同的哈希值，表的实现也必须具有明确地插入和检索键和值对的策略。

• Pythondict使用开放寻址来解决哈希冲突（如下所述）（参见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）

• 在向表中添加条目时，我们从某个i基于密钥哈希值的槽开始。CPython 最初使用i = hash(key) & mask（其中mask = PyDictMINSIZE - 1，但这并不重要）。只需注意，i检查的初始槽取决于密钥的哈希值。

• 如果该插槽为空，则将条目添加到插槽中（我指的是条目<hash|key|value>）。但是如果该插槽已被占用怎么办！？很可能是因为另一个条目具有相同的哈希值（哈希冲突！）

• 如果插槽已被占用，CPython（甚至 PyPy）会将插槽中条目的哈希值和键（比较是指==比较而不是比较）分别与要插入的当前条目的哈希值和键（ dictobject.c:337,344-345）进行比较。如果两者匹配，则它会认为该条目已经存在，放弃并转到下一个要插入的条目。如果哈希值或键不匹配，它会开始探测。is

• 探测只是意味着它会逐个搜索槽位以找到一个空槽位。从技术上讲，我们可以一个接一个地搜索，i+1, i+2, ...并使用第一个可用的槽位（即线性探测）。但由于注释中详细解释的原因（参见dictobject.c:33-126），CPython 使用随机探测。在随机探测中，下一个槽位以伪随机顺序挑选。条目将添加到第一个空槽位。对于本次讨论，用于挑选下一个槽位的实际算法并不重要（有关探测算法，请参阅dictobject.c:33-126）。重要的是探测槽位，直到找到第一个空槽位。

• 查找也会发生相同的情况，只是从初始槽位 i 开始（其中 i 取决于密钥的哈希值）。如果哈希值和密钥均与槽位中的条目不匹配，则开始探测，直到找到匹配的槽位。如果所有槽位都已用尽，则报告失败。

• 顺便说一句，dict如果已满三分之二，则会调整大小。这可以避免减慢查找速度。（请参阅dictobject.h:64-65）

注意：我针对我自己的问题（即字典中的多个条目如何具有相同的哈希值）研究了 Python Dict 实现。我在此处发布了略作修改的版本，因为所有研究也与此问题非常相关。

解决方案 2：

Python 的内置字典是如何实现的？

以下是简短的课程：

• 它们是哈希表。（请参阅下文了解 Python 实现的具体内容。）

• 从 Python 3.6 开始，新的布局和算法使它们

+ 按照按键插入顺序排列，
+ 占用更少的空间，
+ 且几乎不影响性能。

• 另一种优化是当字典共享键时（在特殊情况下）节省空间。

从 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 个键值后，再添加一个键值对时，发生哈希冲突的概率太大，因此字典的大小会加倍。在 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__ ）。这意味着您应该在或 中分配所有属性__new__，否则您可能无法节省空间。

__init__但是，如果您在执行时知道所有属性，那么您也可以__slots__为您的对象提供，并保证__dict__根本不会创建（如果父级中不可用），甚至允许__dict__但保证您预见的属性无论如何都存储在插槽中。有关更多信息__slots__，请参阅我的回答。

参见：

• PEP 509——为 dict 添加私有版本

• PEP 468——**kwargs保留函数中的顺序。

• PEP 520——保留类属性定义顺序

• PyCon 2010：强大的词典- Brandon Rhodes

• PyCon 2017：更强大的词典- Brandon Rhodes

• PyCon 2017：现代 Python 字典，十几个伟大想法的汇聚- Raymond Hettinger

• dictobject.c - CPython 用 C 语言实现的实际 dict。

解决方案 3：

Python 字典使用开放寻址（参考里面的Beautiful code）

注意！如 Wikipedia 所述， 开放寻址（又称封闭哈希）不应与其对立的开放哈希相混淆！

开放寻址意味着字典使用数组槽，并且当对象在字典中占据主要位置时，将使用“扰动”方案在同一数组中的不同索引处寻找该对象的位置，其中对象的哈希值起作用。

解决方案 4：

Python dict 现在维护两个索引。一个是稀疏数组。当第一个元素插入到 dict 中时，它执行的操作如下：

• 插入键值

• 字典查找键的哈希值

• 字典将哈希映射到索引

• 在稀疏数组中，定位此索引并输入数字零（第一次输入时）

第二个数组是密集数组。这就是那里发生的事情：

• 在零索引中输入值

因此第二个数组紧凑且内存高效。

对于后续插入，第二个数组的插入索引将递增。这样可以节省内存并保持插入顺序。

在第一个稀疏数组中插入索引时可能会发生哈希合谋。这由伪随机探测处理，即算法以可预测但伪随机的方式在数组内部进一步查找空槽。

第二个数组始终是紧凑的。