你有没有遇到过这种场景一个 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 这个数值配上开放寻址算法在“空间开销”和“探测链长度”之间取了不错的折中。具体到数字上会更直观表容量 dk_size触发扩容时的 used触发时负载因子860.7532220.6875128860.6718755123420.66796875注意负载因子值在容量较小时略高比如 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 * sizeused * 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 的表在used6时触发扩容之后各阶段触发点是 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(fBadKey 插入 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(fGoodKey 插入 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(fn{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 [fkey_{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 进程会为字符串哈希生成一个随机种子导致同一个字符串在不同进程里哈希值完全不同。你可以自己验证$ PYTHONHASHSEED1 python3 -c print(hash(hello)) $ PYTHONHASHSEED2 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.name4.4 大数据量下 dict 的内存形态split tableCPython 还有一个针对“同构小字典”的优化如果字典的键全是字符串并且值也全是同一类型它可能启用 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 常见问题速查表现象原因解决办法内存居高不下删除键产生 dummy缩容未触发重建字典或用filter生成新表同样数据两次运行内存不同字符串哈希随机化影响冲突率用PYTHONHASHSEED固定种子做性能对比自定义对象做键出现重复__hash__和__eq__未同时重写重写两个方法且保持一致迭代中新增键报错字典结构变化被迭代器检测到先收集再 update插入大量数据很慢扩容频繁触发用字典推导式一次性构建字典查询慢到离谱键的哈希函数退化冲突过多检查自定义键的__hash__5.5 一次真实的线上排查记录最后分享一个实际案例正好把前面所有知识串起来。我们有一个缓存服务用字典做 LRU 缓存过期键通过后台任务定时删除。某天监控显示进程内存持续上涨但字典里的有效条目数一直维持在 5 万左右理论上不该涨。我一开始怀疑内存泄漏排查了很久没结果最后用 tracemalloc 快照对比发现问题出在“删了太多键但没触发缩容”。那个字典容量已经被撑到 26 万左右有效键 5 万按缩容阈值used size / 4算5 万刚好卡在 6.5 万的线上方所以永远不缩容。而且每次删除产生的 dummy 槽位让探测链越来越长CPU 占用也跟着涨。后来改成了定时“垃圾回收”策略当有效条目数低于容量四分之一时执行一次copy()重建内存瞬间回落CPU 也恢复正常。整个过程完全没改业务逻辑只是理解了字典的缩容条件就避免了一次“看起来像内存泄漏”的线上事故。我个人现在的习惯是任何大规模使用字典的地方都会主动关注它的容量与有效条目数之比而不只是看业务逻辑里有多少键。哈希表的扩容机制不是一个纯理论话题它会在你最意想不到的时候以内存和速度的形式跳出来给你上生动的一课。