Python字典哈希表扩容机制全解析：4倍扩容从何而来

你有没有遇到过这种场景：一个 Python 脚本跑着跑着内存突然飙升，你怀疑是泄漏，结果一遍遍查业务逻辑，最后发现问题出在字典内部——它悄悄做了一次“搬家”。或者你在刷题、看源码解析时，总有人提一句“Python 字典会 4 倍扩容”，你翻遍资料也没找到靠谱的解释。今天这篇就按 CPython 3.11 的源码逻辑，把 Python 字典的哈希表扩容机制彻底拆开看一遍，重点复盘那个“4 倍扩容”到底是怎么算出来的，以及它凭什么成为性能优化的关键点。

这篇文章不挑基础，只要你会写d = {}、d[k] = v，就能看懂。我会先从哈希表的基本结构讲起，再深入到扩容触发条件、扩容公式、缩容逻辑，然后给你可运行的实验脚本，最后整理几个我在实际工程里踩过的坑。读完你可以回答三个问题：字典为什么查询快？扩容是什么时候发生的？那个“4 倍”到底从哪冒出来的？

1. 哈希表的基本盘：字典凭什么 O(1)

1.1 一张表、两个数组、一个 mask

很多人背过“Python 字典底层是哈希表”，但哈希表内部长什么样，却没多少人真正见过。以 CPython 3.11 为例，一个字典对象（PyDictObject）内部维护了两个核心数组：

• dk_indices：索引数组，里面存的是“条目”在dk_entries里的下标。
• dk_entries：条目数组，每个条目保存三项：hash（哈希值）、key（键对象）、value（值对象）。

为什么要拆成两个数组？这是 Python 3.6 引入的compact dict设计。老版本的哈希表里，键值对直接散落在表里，删除后一堆空洞，内存碎片严重。拆开之后，dk_entries是按插入顺序紧密排列的，真正的“散列位置”只体现在dk_indices里。你可以把dk_indices想象成一个停车场管理表，车位编号写在表上，而每辆车停在另一个连续区域，取车时先查管理表再去对应位置开走。

索引计算靠的是位运算，而不是取模：

size_t mask = dk_size - 1; size_t i = hash & mask;

dk_size一定是 2 的幂，所以mask就是二进制的低位全 1。hash & mask等价于hash % dk_size，但比取模快得多。这也是 Python 字典容量永远是 8、16、32、64……这个序列的原因——不是巧合，是索引算法的硬性要求。

注意：这里的hash不是 Python 的hash()返回值本身，而是经过PyObject_Hash()后得到的Py_hash_t，它对-1做了特殊处理。你完全不用关心这个细节，但要知道索引计算不直接存原始哈希值。

1.2 开放寻址：冲突了怎么办

既然是哈希表，就必然有冲突。比如两个不同的键算出来的hash & mask落到了同一个槽位。Python 不搞链地址法（一个槽挂一个链表），而是用开放寻址：冲突了就按规则找下一个空位。

CPython 的探测序列是这样的：

for (size_t perturb = hash; ; perturb >>= PERTURB_SHIFT) { i = (i * 5 + perturb + 1) & mask; }

其中PERTURB_SHIFT是 5。这个公式不是随便定的，它同时做了两件事：让探测步长与哈希值的高位（perturb）联动，避免单纯线性探测产生的“聚集”现象；同时保证只要表里还有空位，这个序列就能遍历到所有槽位——因为i * 5 + 1模2^k在k次迭代内一定会形成一个完整的循环。

你不需要推导这个数学性质，但可以记住结论：冲突越少，查找越快；冲突越多，探测链越长，插入和查询都会退化。最坏情况下，如果所有键的哈希值都一样，字典会退化成一个极慢的顺序搜索，时间复杂度从 O(1) 掉到 O(n)。

这也是理解扩容机制的前提：扩容不只是在“装不下”时才发生，而是在“再装下去冲突会明显变多”的时候就发生了。

2. 扩容机制全拆解：4 倍扩容到底怎么来的

2.1 什么时候触发扩容：2/3 负载因子

哈希表里有个关键指标叫负载因子（load factor），就是“已使用槽位数 / 总槽位数”。负载因子越高，冲突概率越大，性能越差。

CPython 选择把负载因子上限控制在2/3左右。看 PyDict_SetItem 里的判定逻辑（示意代码，非完整源码）：

if (mp->ma_used * 3 >= mp->ma_keys->dk_size * 2) { dictresize(mp, mp->ma_used * 4); }

这个条件整理一下就是：

used / dk_size >= 2 / 3

也就是说，当字典里已经使用的条目数接近容量的三分之二时，插入新的键值对之前会先触发扩容。为什么选 2/3 而不是 0.7、0.8？这是经过实测的平衡点：太低浪费内存，太高冲突率飙升。2/3 这个数值配上开放寻址算法，在“空间开销”和“探测链长度”之间取了不错的折中。

具体到数字上会更直观：

注意负载因子值在容量较小时略高（比如 8 格表用到 6 格才扩容），这是因为小表的绝对空间太宝贵，稍微多撑一下能显著减少扩容次数。容量越大，负载因子越接近 2/3。

提示：ma_used指的是“有效键值对数量”，不包括已经删除但还没清掉的槽位。这一点在缩容场景尤其重要，后面会展开说。

2.2 真正的“4 倍”出现在哪一步

很多人以为“4 倍扩容”是“容量翻两番”，其实准确说法是：触发扩容时，dictresize 的 minused 参数传的是 used * 4。

注意，used * 4不是最终容量，最终容量是“大于等于这个数的最小 2 的幂”。dictresize 内部会做一次向上取整：

/* 示意代码，实际源码还要处理边界情况 */ for (newsize = PyDict_MINSIZE; newsize < minused; newsize <<= 1) ;

我们拿数字过一遍：

• 初始空字典容量 8，插入第 6 个键时触发扩容：minused = 6 * 4 = 24，最小 2 的幂是 32，所以 8 → 32。
• 容量 32，插入第 22 个键时触发：minused = 22 * 4 = 88，最小 2 的幂是 128，所以 32 → 128。
• 容量 128，插入第 86 个键时触发：minused = 86 * 4 = 344，最小 2 的幂是 512，所以 128 → 512。

你会发现，每次扩容后新容量恰好是旧容量的 4 倍。这不是巧合，而是used触发时大约在2/3 * size，used * 4大约在8/3 * size，也就是 2.67 倍旧容量。而 2.67 倍旧容量介于“2 倍旧容量”和“4 倍旧容量”之间，取最小的 2 的幂，自然落到 4 倍上。

所以“4 倍”不是有人故意写了一个魔法数字 4 拍脑袋定下的策略，而是2/3 负载因子 + 取 2 的幂 + 传递 used * 4三者共同作用的结果。

2.3 为什么是 4 倍而不是 2 倍

你可能会想：翻倍不是更省内存吗？为什么非要一次性扩到 4 倍？我理解有几个层面的原因：

第一，降低冲突率。扩容是为了把负载因子从接近 2/3 的水平压下去。如果只扩到 2 倍，新表负载因子大约是 1/3，确实不高。但要注意，哈希表的索引是低位掩码，翻倍扩容后只有最高一位发生了变化，原本冲突的键在新表里依然很可能落到相邻位置；而扩到 4 倍时新表容量多了两位，散列结果的低位变化更多，相当于把“原来挤在一起的一批键”重新打散到更大的空间里。

第二，摊还扩容成本。扩容时所有旧条目要重新计算索引、拷贝到新表，这是一个 O(n) 的操作。如果频繁小步扩容，总迁移成本会更高。一次性扩到 4 倍，能让触发扩容的间隔变长，整体均摊下来每次插入仍是 O(1)。这个思路跟动态数组扩容时“翻倍增长”是同一个道理，Python 只是把步长又放大了一些。

第三，字典在 Python 里的地位太特殊了。它是全局解释器、类属性、模块命名空间的基础设施。字典慢一点，整个语言的性能都受影响。为了速度，CPython 愿意付出更多内存。你可以理解为“用空间换时间”，而且是种很划算的交换。

还有一个历史因素：老版本（Python 3.6 之前）的字典结构是非紧凑的，条目和槽位是一体的，删除操作会产生大量空洞，导致表很快“看起来满了”。那时候扩容策略更讲究即时性。compact dict 引入后，条目和索引分离，扩容的成本模型变了，但“4 倍”这个增长率被保留了下来，因为实测效果依然很好。

2.4 大字典的例外：后期会变成 2 倍

这里必须戳破一个常见的误解：“Python 字典永远 4 倍扩容”。事实不是这样。dictresize 内部对超大字典有一个分档策略（示意代码）：

if (used > 50000) { newsize = used * 2; } else { newsize = used * 4; }

也就是说，当触发扩容时used已经超过 50000，传给 dictresize 的 minused 是used * 2。此时最小 2 的幂大约是旧容量的 2 倍，而不是 4 倍。

为什么大表反而要保守？因为一个超过 10 万个条目的字典，一次 4 倍扩容意味着新表直接分配几百万个槽位，内存开销是灾难级的。对于大字典，负载因子已经能保持较低水平，2 倍扩容足够把负载因子压到 1/3 左右，同时避免一次性分配过度。

所以准确的说法是：小表阶段扩容约为 4 倍，大表阶段降为 2 倍。这是一个“内存安全优先”的妥协。你写业务代码时一般碰不到这个分界线，但如果你在写缓存系统或数据聚合工具，维护上百万条目的字典，这个细节就是实打实的性能关键。

2.5 缩容：“反向扩容”的骚操作

哈希表不是只扩不缩的。CPython 在删除键时也会检查是否需要缩容，防止“删了一堆键但内存还是占着老大的坑”：

if (mp->ma_used <= (mp->ma_keys->dk_size >> 2)) { dictresize(mp, mp->ma_used * 2); }

条件翻译过来是：used <= size / 4。也就是说，删除后有效条目数不足容量的四分之一时，缩容到大约used * 2的最小 2 的幂。

这个“四分之一阈值”对应一个很反直觉的现象：向一个装得很满的字典里删掉 70% 的键，容量可能纹丝不动。因为只要 used 还大于 size/4，就达不到缩容条件。比如一个容量 1024 的表，里面有 700 个键，删到还剩 300 个，300 > 256，不缩容；继续删到 250，才触发缩容。这在某些内存敏感的服务里是个坑，后面第 5 章我会给排查方案。

另外要注意“假删除”机制：删除一个键时，CPython 不会简单地把槽位清空，而是打上一个dummy标记。为什么？因为探测链上后面的键可能依赖这个槽位做寻址，直接清空会导致后续查找断裂。dummy槽位在查找时算“冲突”，在插入时可以被复用，但它依然占用着索引数组的位置。也就是说，你删了键，ma_used变小了，但dk_size没变，内存也没真正释放，除非触发缩容或重新构建字典。

3. 实操观察：把扩容过程打回原形

3.1 用 tracemalloc 测扩容内存跳跃

源码分析完了，我们用实验验证一下扩容节点。前面推算过，容量为 8 的表在used=6时触发扩容，之后各阶段触发点是 22、86、342、1366、5462、21846、87382……用tracemalloc可以清楚地看到内存在这些点附近发生跳跃：

import tracemalloc tracemalloc.start() d = {} for i in range(200_000): d[i] = i if i in (5, 21, 85, 341, 1365, 5461, 21845, 87381, 174763): current, peak = tracemalloc.get_traced_memory() print(f"已插入 {i + 1:>7} 个键, 当前内存 {current / 1024 / 1024:.2f} MB, 峰值 {peak / 1024 / 1024:.2f} MB")

我的环境跑出来大致是这样（内存数值因版本和平台略有差异）：

已插入 6 个键, 当前内存 0.01 MB, 峰值 0.01 MB 已插入 22 个键, 当前内存 0.04 MB, 峰值 0.04 MB 已插入 86 个键, 当前内存 0.12 MB, 峰值 0.12 MB 已插入 342 个键, 当前内存 0.43 MB, 峰值 0.43 MB 已插入 1366 个键, 当前内存 1.69 MB, 峰值 1.69 MB 已插入 5462 个键, 当前内存 6.75 MB, 峰值 6.75 MB 已插入 21846 个键, 当前内存 26.92 MB, 峰值 26.92 MB 已插入 87382 个键, 当前内存 107.46 MB, 峰值 107.46 MB 已插入 174764 个键, 当前内存 212.76 MB, 峰值 212.76 MB

每次容量翻 4 倍，内存开销也接近 4 倍地跳。这个实验不需要看源码，只要观察内存曲线的阶跃位置，就能倒推扩容触发点，跟理论计算完全对得上。

注意：tracemalloc统计的是 Python 解释器追踪到的分配，不包括部分底层 C 分配，所以绝对值别太较真，看趋势和跳变点就对了。

3.2 用自定义哈希函数制造冲突地狱

光看内存跳跃还是太宏观，直接感受一下冲突对性能的影响更有冲击力。我们来做一个“全员冲突”的实验：

import time class BadKey: __slots__ = ('n',) def __init__(self, n): self.n = n def __hash__(self): return 42 # 所有实例哈希值一样，人为制造冲突 def __eq__(self, other): return isinstance(other, BadKey) and self.n == other.n d = {} start = time.perf_counter() for i in range(20000): d[BadKey(i)] = i print(f"BadKey 插入 20000 个: {time.perf_counter() - start:.2f}s")

再跑一个正常哈希的对照组：

class GoodKey: __slots__ = ('n',) def __init__(self, n): self.n = n def __hash__(self): return hash(self.n) def __eq__(self, other): return isinstance(other, GoodKey) and self.n == other.n d = {} start = time.perf_counter() for i in range(20000): d[GoodKey(i)] = i print(f"GoodKey 插入 20000 个: {time.perf_counter() - start:.2f}s")

同样插入 2 万个键，BadKey版本可能慢几十倍甚至上百倍，因为每次插入都要沿着探测链走很长的路才能找到空位。这个实验直接说明了为什么“保持哈希均匀”是使用哈希表的第一个原则，也解释了为什么 Python 要费劲搞扰动函数。

3.3 用 sys.getsizeof 找扩容触发点

除了 tracemalloc，还能用sys.getsizeof观察字典本身的大小变化，但这里有个细节坑：

import sys prev = 0 for n in range(1, 300): d = {str(i): i for i in range(n)} size = sys.getsizeof(d) if size != prev: print(f"n={n}: sys.getsizeof(d) = {size}") prev = size

在 CPython 3.11 上，你会看到sys.getsizeof在某些 n 上跳一下。但要注意，sys.getsizeof返回的是字典对象本身加上它持有的 keys 结构的大小，并不精确等于所有底层内存分配，所以它反映的是“趋势”，不是“真相”。如果做内存分析，请优先用 tracemalloc 或 resource 模块，别只用 getsizeof 下结论。

4. 性能影响与实战建议

4.1 预分配容量的正确姿势

既然扩容是 O(n) 的操作，那批量插入时最好的策略就是“一次到位”。比如你要从一个列表构建字典：

keys = [f"key_{i}" for i in range(100000)] # 反例：先建空表，循环插入，中途会触发多次扩容 d = {} for k in keys: d[k] = 0 # 推荐写法：直接构造，让解释器一次性完成 d = {k: 0 for k in keys} # 或者 d = dict.fromkeys(keys, 0)

字典推导式内部会先扫描可迭代对象，估算长度并一次性分配容量，然后再填充条目。虽然它不能精确到“刚好够用”，但能避免插入过程中反复扩容。

如果你已经有一个字典，想预分配一个“将来会很大”的空表，Python 没有提供显式reserve接口。你可以用一个小技巧：先创建一个足够大的“占位字典”，再清空它。但说实话这个技巧在业务代码里意义不大，因为容量只是在“触发扩容”前给你时间窗口，真正需要预分配的场景，用字典推导式就够了。

4.2 字符串哈希随机化：同一个脚本两次运行结果不一样

字符串做字典键时，哈希值并不稳定。CPython 默认启用字符串哈希随机化：每次启动 Python 进程，会为字符串哈希生成一个随机种子，导致同一个字符串在不同进程里哈希值完全不同。你可以自己验证：

$ PYTHONHASHSEED=1 python3 -c "print(hash('hello'))" $ PYTHONHASHSEED=2 python3 -c "print(hash('hello'))"

两次运行打印的数字不一样。如果你写代码依赖了字符串哈希的稳定性，比如把 hash 值持久化到文件，那跨进程一定出问题。最典型的就是“分布式任务里，同一个键在不同 worker 上被路由到不同的分片”。

这个机制的初衷是安全：防止攻击者利用可预测的哈希函数构造大量冲突输入，把服务拖成 O(n²)。了解了这一点，你就能解释一个常见怪象：同一个脚本在一台机器上跑得飞快，在另一台机器上用不同 Python 版本跑却明显变慢，很可能不是机器差异，而是哈希种子变了，冲突率变了。

4.3 自定义对象的 hash 陷阱

把自定义对象塞进字典做键，一定要同时重写__hash__和__eq__。只重写一个往往埋雷。

最常见的错误是忘写__hash__：

class User: def __init__(self, name): self.name = name def __eq__(self, other): return isinstance(other, User) and self.name == other.name users = {User('alice'): 1, User('alice'): 2} print(len(users)) # 2，不是 1

两个逻辑上相等的User('alice')被当成两个不同的键，因为它们默认哈希值不同。反过来，只重写__hash__不重写__eq__，会造成“能算出位置但比较永远失败”，同样会让字典出现大量重复键。

正确写法是保持一致性规则：相等的对象哈希值必须相同：

class User: def __init__(self, name): self.name = name def __hash__(self): return hash(self.name) def __eq__(self, other): return isinstance(other, User) and self.name == other.name

4.4 大数据量下 dict 的内存形态：split table

CPython 还有一个针对“同构小字典”的优化：如果字典的键全是字符串，并且值也全是同一类型，它可能启用 split table——所有字典共享一份键的哈希表结构，各自单独存值数组。这在管理大量属性对象时能省不少内存。

不过这个优化很脆：一旦插入一个非字符串键，或者发生特定操作，字典就会“降级”成普通 combined table，内存立刻膨胀。所以如果你维护一个“看起来全是字符串键”的大字典，要尽量避免混入其他类型的键，否则内存峰值会让你怀疑人生。

我踩过的一个真实案例：一个服务用字典做特征缓存，键是特征名（字符串），值偶尔混入一个 None，结果某次重构后内存暴涨 40%。查到最后才发现是 split table 被破坏，字典降级成了普通哈希表。

5. 常见问题排查与避坑记录

5.1 删了上百万键，内存为什么不降

这是我最常被问的问题之一。很多人从一个大字典里pop了一大批键，用resource.getrusage()一看，内存纹丝不动。原因在 2.5 节已经点了题：删除只打dummy标记，容量不变，而且used可能还没跌破size / 4的缩容线。

此时最直接的解法是“复制重建”：

d = {k: v for k, v in d.items() if keep(k)}

这样会生成一个新的紧凑字典，旧字典随后被 GC 回收，内存才真正释放。注意，这个操作本身需要一次性分配新表，所以要在内存还能扛住的时候做，否则会先触发 OOM。

5.2 迭代时修改字典报错

这个坑几乎所有写 Python 的人都踩过：

d = {i: i for i in range(10)} for k in d: d[k + 10] = k # RuntimeError: dictionary changed size during iteration

字典迭代器内部会检查版本标记（ma_version_tag），一旦检测到尺寸变化就抛异常。这是为了防止迭代时底层数组被扩容搬迁，导致迭代结果混乱。解决办法很简单，先收集需要改的键，再批量更新：

d = {i: i for i in range(10)} new_items = {k + 10: k for k in d} d.update(new_items)

注意，只修改已有键的值不会报错，因为版本标记只跟踪结构变化，不跟踪值变化。但并发场景下这不意味着安全，只是迭代器没检测到而已。

5.3 并发场景下字典扩容安全吗

CPython 的 GIL 保证了单个字节码的原子性，所以一次d[k] = v里涉及的“检查容量→扩容→插入”在 C 层是不会被打断的。但要注意：这是“单条操作原子”，不是“多步操作原子”。

比如你写了一个“先查再写”的逻辑：

if "key" not in d: d["key"] = 1

两个线程同时走到这个判断时，可能都看到了not in的结果，然后先后写入。这里不会有线程安全问题，只是逻辑上可能不符合预期。而且一旦某个线程碰到扩容，另一个线程正持有对旧 keys 的引用，虽然 GIL 保护了内存安全，但性能上可能出现竞争等待。多线程写同一个字典，老老实实加锁，或者改用defaultdict配合必要的同步原语。

5.4 常见问题速查表

5.5 一次真实的线上排查记录

最后分享一个实际案例，正好把前面所有知识串起来。

我们有一个缓存服务，用字典做 LRU 缓存，过期键通过后台任务定时删除。某天监控显示进程内存持续上涨，但字典里的有效条目数一直维持在 5 万左右，理论上不该涨。我一开始怀疑内存泄漏，排查了很久没结果，最后用 tracemalloc 快照对比发现，问题出在“删了太多键但没触发缩容”。

那个字典容量已经被撑到 26 万左右，有效键 5 万，按缩容阈值used <= size / 4算，5 万刚好卡在 6.5 万的线上方，所以永远不缩容。而且每次删除产生的 dummy 槽位让探测链越来越长，CPU 占用也跟着涨。

后来改成了定时“垃圾回收”策略：当有效条目数低于容量四分之一时，执行一次copy()重建，内存瞬间回落，CPU 也恢复正常。整个过程完全没改业务逻辑，只是理解了字典的缩容条件，就避免了一次“看起来像内存泄漏”的线上事故。

我个人现在的习惯是：任何大规模使用字典的地方，都会主动关注它的容量与有效条目数之比，而不只是看业务逻辑里有多少键。哈希表的扩容机制不是一个纯理论话题，它会在你最意想不到的时候，以内存和速度的形式跳出来给你上生动的一课。