再次解释一下 Python 字典使用的哈希表
我们在上一篇文章中分析了 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 数组的，因而元素的输出顺序和插入顺序是一致的。
【使用这种结构的好处】
首先，使用连续的内存可充分利用数组随机访问的特性，保证了 dict 的访问效率。
其次，Slots 数组只保存元素的索引，每个 slot 只占用少量固定长度的内存，可大大节省内存空间。
我们可以想象，当 dict 比较大时，如果其中只包含少量有效的（Active） slot，此时的 Slots 就是一个稀疏的数组。如果 Slots 中存储的是元素对象，每个元素对象的 size 要远大于一个 int 索引值占用的空间，这个稀疏数组会造成比较严重的内存浪费。
因此，CPython 所采用的这种哈希表内存结构的确是一种高效紧凑的数据存储方式，具有很高的时间和空间效率。
【相关文章】
我埋头写作，就像在努力爬坡
你在看和分享，无形中推了我一把
多希望你可以一直关注着我
那是我不懈前行的力量