Python 中的哈希表（dict/set）底层数据结构与性能优化深度剖析

在 Python 的日常开发中，字典（dict） 和 集合（set） 是使用频次最高的核心数据结构。无论是存储配置、映射关系，还是进行海量数据的快速去重，它们都以 $O(1)$ 的近乎瞬时的检索速度支撑着业务逻辑的高效运行。

然而，优秀的性能并不是凭空产生的。在底层的 CPython 实现中，为了追求极致的内存利用率和查找效率，字典的设计经历过数次重大的架构演进，最具代表性的就是 Python 3.6 引入的 紧凑字典（Compact Dict） 内存布局。

本文将带你深入 CPython 源码空间，解密 Python 哈希表的底层运转细节、冲突解决算法、以及为什么现代 Python 字典能天然保持“插入顺序”。

一、 经典哈希表的核心挑战：哈希冲突

字典的底层是基于哈希表（Hash Table） 实现的。其查找的基本流程是：通过对键（Key）进行哈希运算（hash(key)），将结果映射为数组的索引，从而直接通过下标以 $O(1)$ 的时间复杂度读取对应的值（Value）。

然而，哈希表的槽位（Slot）是有限的，而不同的 Key 的哈希值可能会映射到同一个数组索引上，这就是哈希冲突（Hash Collision）。

1. 冲突解决流派：链地址法 vs 开放寻址法

• 链地址法（如 Java 的 HashMap）：在冲突的槽位上挂载一个单向链表（或红黑树），冲突的数据顺次挂在链表节点中。
• 开放寻址法（Python 的选择）：所有的元素都直接存储在哈希表数组本身中。一旦发生冲突，引擎会通过某种探查算法去寻找下一个空闲的槽位。

2. Python 独特的探查公式（Quadratic Probing + Perturbation）

Python 采用的是开放寻址法。为了快速打破哈希冲突，Python 并没有使用简单的线性探测（即 +1，+2），因为那会导致严重的“聚集效应”（大量冲突堆积在一起）。

Python 采用了一套带有扰动（Perturbation）因子的探查公式： idx = (5 * idx + 1 + perturbation) % size * 每次冲突后，扰动因子 perturbation 会右移 5 位（perturbation >>= 5），逐渐引入哈希值的高位比特进行重新计算。这使得探查轨迹极具随机性，能瞬间打散冲突数据，将其均匀分布在哈希表各处。

二、 划时代的技术飞跃：紧凑字典（Compact Dict）

在 Python 3.6 之前，字典的内存开销非常庞大。当时的底层结构体数组中，每个槽位不仅存储了 Hash 值，还物理存储了 Key 的指针和 Value 的指针。

旧版字典内存布局：

[Entries Array]
┌─────────┬─────────┬─────────┐
│  Hash   │ Key_Ptr │ Val_Ptr │  <-- 槽位 0 (24 字节)
├─────────┼─────────┼─────────┤
│  Empty  │  None   │  None   │  <-- 空闲槽位 (24 字节，浪费严重)
├─────────┼─────────┼─────────┤
│  Hash   │ Key_Ptr │ Val_Ptr │  <-- 槽位 2 (24 字节)
└─────────┴─────────┴─────────┘

在 64 位系统下，每个槽位占据 24 字节。由于开放寻址法要求哈希表必须保持至少 1/3 的空闲率以防查找性能退化，这意味着有大量的 24 字节槽位被白白荒废。

现代 Python（>=3.6）的紧凑字典布局：

为了节约内存，Raymond Hettinger 提出了分离式结构。将原本的一个大数组拆分为：一个紧凑的键值存储数组（Entries） 和 一个稀疏的索引数组（Indices）。

1. 【 索引数组 Indices 】 (只存 Entries 数组的下标，可以是 1 字节的 int8)
   ┌───┬───┬───┬───┬───┬───┐
   │ 0 │-1 │ 1 │-1 │ 2 │-1 │   ( -1 代表该槽位空闲 )
   └───┴───┴───┴───┴───┴───┘
                 │
                 ▼
2. 【 键值数组 Entries 】 (紧凑存储，不预留空槽，仅 24 字节 * 实际元素数)
   ┌─────────┬─────────┬─────────┐
   │  Hash   │ Key_Ptr │ Val_Ptr │  <-- 索引 0 (实际插入的第1个元素)
   ├─────────┼─────────┼─────────┤
   │  Hash   │ Key_Ptr │ Val_Ptr │  <-- 索引 1 (实际插入的第2个元素)
   ├─────────┼─────────┼─────────┤
   │  Hash   │ Key_Ptr │ Val_Ptr │  <-- 索引 2 (实际插入的第3个元素)
   └─────────┴─────────┴─────────┘

这一改进带来的巨大收益：

1. 极高的内存压缩率：空闲槽位在 Indices 数组中只需占用 1 个字节（若哈希表容量在 128 以内），而高消耗的 24 字节 Entries 结构体则被紧凑塞满，整体内存开销缩减了 20% ~ 25%。
2. 字典天然有序性：由于数据是按实际插入顺序追加写入 Entries 数组的，这使得 Python 3.6 之后的字典默认保持了元素的插入顺序。

三、 集合（set）的底层实现

集合（set）在底层其实是一个“没有值的字典”。 * 它和 dict 共享几乎完全相同的哈希查找、哈希冲突、以及扩容和稀疏化逻辑。 * 区别在于，set 的底层表项中只有 Hash 和 Key_Ptr 指针，去除了 Val_Ptr。 * 集合的去重操作（set.add(x)）效率之所以极高，就是因为在后台执行了一次 $O(1)$ 的哈希键查找，如果哈希冲突探查证明该 Key 已在表中，则直接跳过。

四、 核心协议：如何让你的自定义类对象“可哈希”？

只有可哈希（Hashable）的对象才能作为字典的 Key 或者集合的元素。

1. 什么是 Hashable？

一个对象如果满足以下条件，就是可哈希的： * 在它的生命周期内，其哈希值必须保持不变（通常这意味着它必须是不可变对象，如数字、字符串、元组）。 * 必须实现了 __hash__() 方法。 * 必须实现了 __eq__() 方法，且当 a == b 时，hash(a) == hash(b)。

2. 自定义可哈希对象实战：

如果你需要自定义一个坐标类 Point 作为字典的 Key，你必须同时重写 __eq__ 和 __hash__：

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    # 1. 重写相等比较契约
    def __eq__(self, other):
        if not isinstance(other, Point):
            return NotImplemented
        return self.x == other.x and self.y == other.y

    # 2. 重写哈希契约 (利用内部不可变元组计算哈希值)
    def __hash__(self):
        return hash((self.x, self.y))

# 测试
points_map = {}
p1 = Point(1, 2)
p2 = Point(1, 2)

points_map[p1] = "Base_A"
print(points_map.get(p2))  # 输出: Base_A (尽管 p1 和 p2 是两个不同实例，但由于 __eq__ 和 __hash__ 相同，被成功判定为同一个 Key！)

五、 哈希表性能调优与避坑指南

1. 扩容与性能退化：避免在循环中频繁扩容

当哈希表利用率超过 2/3 时，为了防止哈希冲突急剧增加导致退化成 $O(N)$ 的查找，CPython 会自动对字典进行扩容（通常是翻倍扩容，并重新计算所有 Key 的索引）。 * 优化方案：在需要合并超大字典时，直接使用 dict.update() 或者是 Python 3.9 的合并运算符 dict_a | dict_b 一次性完成，避免在 for 循环中反复追加导致频繁触发重绘和重新哈希。

2. 严禁在遍历字典时修改字典的 Size

在遍历 dict 时（如 for k in my_dict:），如果在循环体内部执行了 my_dict[new_key] = val 或 del my_dict[k]，Python 会直接抛出 RuntimeError: dictionary changed size during iteration。 * 原因：因为遍历字典是基于 Entries 数组的索引进行的，如果在遍历中改变容量，可能会导致哈希重组，从而让遍历指针失控。 * 解决方法：在遍历前先拷贝一份 Keys 列表：for k in list(my_dict.keys()):。

总结

Python 的 dict 和 set 是工程调优与算法设计的结晶。从解决哈希冲突的扰动探查公式，到 3.6 引入的紧凑稀疏数组双重布局，这些巧妙的设计在保障 $O(1)$ 高速读取的同时，完成了极高的内存压缩，并顺理成章地确保了键值对的插入顺序。理解哈希表的底层运转以及可哈希协议的强要求，能够帮助我们更理性地设计对象关系映射、排查遍历修改 Bug，并编写出高响应度的核心业务代码。