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

Question

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

Answer 1

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

• Python 字典被实现为 哈希表。

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

• Python dict使用开放寻址来解决哈希冲突(解释如下)(见dictobject.c:296-297)。

• Python 哈希表只是一个连续的内存块(有点像数组，因此您可以通过索引进行 O(1) 查找)。

• 表中的每个槽只能存储一个条目。这很重要。

• 表中的每一个entry实际上是三个值的组合: 。这是作为 C 结构实现的(参见 dictobject.h:51-56)。

• 下图是一个 Python 哈希表的逻辑表示。下图中，0, 1, ..., i, ...左边是哈希表中 slots 的索引(它们仅用于说明目的，显然不与表一起存储!)。

    # Logical model of Python Hash table
    -+-----------------+
    0| <hash|key|value>|
    -+-----------------+
    1|      ...        |
    -+-----------------+
    .|      ...        |
    -+-----------------+
    i|      ...        |
    -+-----------------+
    .|      ...        |
    -+-----------------+
    n|      ...        |
    -+-----------------+
  

• 当一个新的 dict 被初始化时，它以 8 个 slots 开始。 (见 dictobject.h:49)

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

• 如果该槽为空，则将条目添加到槽中(我的意思是，<hash|key|value>)。但是如果那个插槽被占用了怎么办!？很可能是因为另一个条目具有相同的哈希(哈希冲突!)

• 如果插槽被占用，CPython(甚至 PyPy)会比较条目的 哈希和键(比较我的意思是 == 比较而不是 is 比较)在插槽中分别针对要插入的当前条目的哈希和键( dictobject.c:337,344-345 )。如果 both 匹配，则认为该条目已经存在，放弃并继续插入下一个条目。如果哈希或 key 不匹配，则开始探测。

• 探测只是意味着它逐个插槽搜索插槽以找到一个空插槽。从技术上讲，我们可以一一进行，i+1, i+2, ...并使用第一个可用的(即线性探测)。但是由于注释中解释得很清楚的原因(参见 dictobject.c:33-126)，CPython 使用随机探测。在随机探测中，以伪随机顺序选择下一个槽。该条目被添加到第一个空槽。对于本次讨论，用于选择下一个插槽的实际算法并不重要(关于探测算法，请参见 dictobject.c:33-126)。重要的是探测槽直到找到第一个空槽。

• 查找也会发生同样的事情，只是从初始槽 i 开始(其中 i 取决于键的哈希值)。如果散列和键都与槽中的条目不匹配，它开始探测，直到找到匹配的槽。如果所有槽都用完，则报告失败。

• 顺便说一句，dict如果三分之二已满，将调整大小。这样可以避免减慢查找速度。 (见 dictobject.h:64-65)

注意:我对 Python Dict 实现进行了研究，以回应我自己的 question关于 dict 中的多个条目如何具有相同的哈希值。我在这里发布了经过稍微编辑的回复版本，因为所有研究都与这个问题非常相关。