Python字典哈希机制详解

Python字典远非传统哈希表，其底层采用自3.6起引入的紧凑哈希表设计——通过分离存储的entries数组（存键值对）与轻量级indices索引数组（用-1/-2标记空/已删槽位），配合used/fill计数器实现高效查找、低开销扩容和天然有序迭代；这种结构不仅大幅提升缓存友好性与遍历速度，还巧妙利用重哈希丢弃已删除项来回收空间，让字典在保持O(1)均摊性能的同时，兼具内存紧凑性与插入顺序稳定性。

Python字典的底层结构：不是简单的哈希表

Python字典（dict）在 CPython 中并非传统意义的开放寻址哈希表，而是一种**紧凑哈希表（compact hash table）**，自 Python 3.6 起成为正式实现（3.7+ 保证插入顺序），其核心是“键值分离”+“索引数组”设计。

核心三块内存布局

每个字典对象（PyDictObject）维护三个关键数组：

• entries 数组（ma_keys）：存储实际的 key-value-entry 结构体（PyDictKeyEntry），每个 entry 含 me_hash、me_key、me_value。空槽用 NULL 表示。
• indices 数组（ma_indices）：大小为 2**n 的有符号短整型数组，每个元素是 entries 中对应槽位的下标（或特殊标记：-1 空、-2 已删除）。这是“紧凑性”的关键——它允许 indices 比 entries 小得多（尤其在稀疏时）。
• used / fill 计数器：分别记录当前已插入的有效键数和已占用（含已删）的 slots 数，用于触发扩容。

哈希计算与索引定位过程

给定一个 key，查找流程如下：

• 调用 PyObject_Hash(key) 得到哈希值 h（若未定义 __hash__ 或返回不可哈希类型会报错）。
• 取模得到初始索引：i = h & (size-1)（因 size 总是 2 的幂，等价于位与，比取模快）。
• 查 indices[i]：
  • 若为 -1：该位置从未使用，直接返回未找到；
  • 若为 -2：曾被占用后删除，继续探测（线性探测）；
  • 若 ≥ 0：去 entries[indices[i]] 取 entry，先比哈希值（快速失败），再用 PyObject_RichCompareBool(key, entry->me_key, Py_EQ) 做全量相等判断。

注意：CPython 使用**伪随机探测序列**（基于哈希高比特扰动）而非简单线性探测，以缓解聚集问题，但实现仍属开放寻址变种。

扩容与重哈希的关键逻辑

当 fill * 3 >= size * 2（即装载因子 ≥ 2/3）时触发扩容。新 size 为首个 ≥ 当前 size * 2 的 2 的幂。

• 分配新的更大的 indices 和 entries；
• 遍历旧 entries 中所有非空项，对每个 key 重新计算哈希、重新定位插入到新表中；
• 已删除项（-2）不参与重哈希，自然被丢弃 —— 这是空间回收的核心机制。

扩容代价高，但通过延迟扩容 + 指数增长，均摊时间复杂度仍为 O(1)。

为什么“紧凑”能提速？

传统哈希表（如 Java HashMap）每个桶存一个链表头或树根，遍历时 cache 不友好。而 CPython 的紧凑布局使：

• 所有 key 和 value 在 entries 中连续存放，迭代时 CPU 缓存命中率高；
• indices 极小（常为 1/4 ~ 1/8 entries 大小），查找索引本身也快；
• 插入顺序天然保留在 entries 数组中，无需额外维护顺序链表。

这就是为何 dict.keys() 迭代比旧版快且稳定有序 —— 它本质就是按 entries 线性扫描非空项。

本篇关于《Python字典哈希机制详解》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！