【原】再次解释一下 Python 字典使用的哈希表

RealPython 2021-03-28

展开全文

我们在上一篇文章中分析了 CPython 中是如何实现 dict 的。由于涉及内容较多，我可能并没有描述清楚 dict 所用的哈希表的具体结构。

如果你也对此有疑问，不妨来看一下本文对哈希表结构的进一步分析。

【dict 哈希表】

先看一张重新制作的图。

这张图描述的就是 CPython 中 PyDictKeysObject 结构中的成员变量 dk_indices。它的数据类型是 char[]，表明它是一块连续分配的内存。

dk_indices 在使用中被分割为两部分。

第一部分是图中的 Slots 数组，也就是我们之前文章中提到的哈希表索引内存块；第二部分是 KeyValues 数组，我们之前称之为哈希表键值对内存块。这两部分都是连续的内存，都可以当做数组来处理，从而能充分利用数组随机访问的特性，提高 dict 的访问效率。

Slots 数组有两个作用：

根据字典中元素 key 的哈希值为元素提供一个槽位（slot）。这是哈希表最一般的用途。
Slots 中存储的并非元素本身，而是元素在 KeyValues 数组中的索引。由于 Slots 本身就是一个数组，通过 Slots[KeySlot] 就可以直接获取元素在 KeyValues 数组中的位置，效率很高。

图中的 slot 有 3 种取值：-1、-2 和自然数。分别代表着 slot 的三种状态：

未曾使用（UnUsed）
这是每个 slot 的初始状态，表示 slot 从未被 key 命中过，从未存储过任何元素的索引。
回收备用（Dummy）
这类 slot 已存储过元素的索引，但元素已被删除，被标记为可再次使用。从这里也可以看到，执行删除操作时，哈希表并不会真正删除元素。这既能提高内存的使用效率，又可以避免物理删除导致的其他元素访问失效。
活动的（Active）
slot 中存储的是一个有效的元素的索引。

哈希表的 hash 算法和冲突算法都是运行在这个 Slots 数组上的。

计算 slot 的基本方法为：

slot = hash(key) & (dk_size - 1)

当发生 key 冲突时，会采用如下算法在 Slots 中查找下一个合适的 slot：

const size_t mask = DK_MASK(keys); // 计算初始 slot size_t i = hash & mask; //获取 slot 中的索引值 Py_ssize_t ix = dictkeys_get_index(keys, i); //循环检查索引值是否有效 for (size_t perturb = hash; ix >= 0;) { perturb >>= PERTURB_SHIFT; i = (i*5 + perturb + 1) & mask; ix = dictkeys_get_index(keys, i); }

KeyValues 数组用来存储键值对。键值对是以追加的方式添加到数组的尾部的，添加完成之后，将其位置索引保存在 key 对应的 slot 中。

dict.items()、dict.keys() 和 dict.values() 这三个方法就是直接访问 KeyValues 数组的，因而元素的输出顺序和插入顺序是一致的。