如何实现Python的内置词典？

如何实现Python的内置词典？

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

• 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|      ...        |-+-----------------+

• 初始化新字典时，它将以8 个插槽开始。（见dictobject.h：49）
• 在向表中添加条目时，我们从某个槽开始i，该槽基于键的哈希值。CPython最初使用

  i = hash(key) & mask（where mask = 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的实现进行了研究，以回答我自己的问题，即字典中的多个条目如何具有相同的哈希值。我在此处发布了对此回复的略作修改的版本，因为所有的研究也都与此问题相关。