先问大家一个平时可能没想过的问题Python 的字典dict到底把键值对存在了哪里答案是一张哈希表。更冷门的是这张哈希表在扩容时并不像一般数据结构那样翻倍“4 倍扩容”这个说法在 Python 社区流传已久。我最早接触这个细节是在排查一个“删了大量键内存却不降、大字典插入又周期性卡顿”的问题时。翻了 CPython 源码才发现触发扩容的那一行其实很直白调用dictresize时传入的参数是mp-ma_used * 4。这篇就把哈希表的存储布局、扩容触发条件、4 倍扩容背后的原理以及对实际业务的影响一次性讲清楚最后附上可以自己动手验证的实验。适合准备面试、想要深入理解 Python 数据结构或者正在做性能调优时对字典内存有疑惑的读者。1. 字典的底层一张哈希表是怎么把键值对组织起来的1.1 键的位置由哈希值和掩码共同决定在写 Python 时d[key] value和d[key]看起来都没什么成本但背后做的事情很有意思。CPython 会先调用PyObject_Hash(key)得到哈希值再把这个哈希值和当前表的掩码mask等于容量减一做按位与得到初始槽位索引。比如容量为 8 的字典掩码就是 7二进制是 0b111所以任何哈希值被截取后都落在 0 到 7 之间。这里有一个关键前提表容量必须始终是 2 的幂。只有 2 的幂才能用hash (size - 1)这种按位与运算代替取模而取模运算比按位与慢一个数量级。所以 Python 扩容时总是在寻找“下一个不小于目标的 2 的幂”而不是随便定一个新容量。这个设计从底层决定了我们看到的 8、32、128、512 这些容量数字都有明确来源。还有一个容易忽略的点哈希值是整数但整数可能很大而我们只需要它的若干低位来定位。掩码位数越多参与定位的哈希比特就越多。扩容到 4 倍相当于一次多用了两个比特位这对键位置的分散程度影响很大后面讲 4 倍之谜时会再提到。1.2 冲突了怎么办开放寻址与二次探测两个不同的键哈希值低位相同就会映射到同一个槽位这就是冲突。Python 解决冲突的方式和 Java HashMap 那种“数组加链表”完全不同。CPython 用的是开放寻址法open addressing具体是二次探测quadratic probing如果槽位被占用不是简单往后挪一位而是尝试 pos01再试试 pos03、pos06偏移量按平方数递增。为什么不用线性探测线性探测在负载较高时容易形成聚集一旦某片区域连续被占用后来的键就要绕更远的路去找空位。二次探测的步长越拉越大让后续冲突的键不要挤在同一小片区域。当然二次探测对 CPU 缓存不算太友好因为它会跳到距离较远的内存位置。但 Python 在字典这个场景里选择了分布均匀优先因为键值对往往是随机访问的短探测链比连续内存更重要。对初学者来说可以先这样理解开放寻址就是“如果我的车位被占了就在附近找空位”。但这个“附近”不是死板地往后挪一个而是按一定规律跳跃目的是让整个表的占用分布更平滑。1.3 紧凑型布局从一层数组变成“索引 条目”两段式CPython 3.6 之前字典内部只有一层数组每个槽位都是完整的PyDictEntry里面存哈希值、键和值三项。即使某个槽位是空的内存也照样占着。所以老版本里一个空字典和只存 3 个键的字典底层数组都可能是 8 个完整 entry 在占位内存浪费明显。3.6 开始CPython 把字典改成了“索引 条目”两段式结构。indices数组只存整数索引表示某个哈希位置对应entries数组里的第几个条目entries数组才是真正连续存放键值对条目的地方。如果一个槽位没有对应条目索引值就是 -1。这个改动让空槽不再吃完整 entry 的内存字典整体占用大幅下降。这个布局变化和 4 倍扩容是有关联的。因为扩容时要重新分配indices和entries还要把entries里的空洞整理掉整个重新哈希过程比老版本更复杂。既然重建成本高就更应该一次把容量扩到位减少扩容次数。4 倍扩容正好符合这个思路。1.4 删除键不会真正释放Unused、Active、Dummy 三种状态哈希表里的槽位其实有三种状态未使用Unused、已占用Active、已删除Dummy。删除一个键时不能直接把槽位标成 Unused因为那样会截断后面键的探测链。举个例子键 A 本来落在槽 3因为冲突被放到了槽 4。如果槽 3 后来被清空成 Unused以后查找 A 时走到槽 3 看到“空”就会提前判定不存在再也找不到真正待在槽 4 的 A。所以删除时只能把槽位标成 Dummy。Dummy 槽在查找时被当作“占用过”会继续往后探测在插入时又可以被新键覆盖。这个概念听起来细但后果很实际字典执行很多pop或del之后容量并没有变小你删除的键只是变成了一个个 Dummy 标记。如果后续不再插入新键这些槽位就一直空着内存自然降不下来。2. 扩容的触发条件不是等到满了而是用到 2/3 就扩2.1 负载因子为什么卡在 2/3 附近哈希表有个关键指标叫负载因子也就是“已用槽位数 / 总容量”。CPython 字典把负载因子上限控制在 2/3 左右。一个容量为 8 的字典大约存到第 5 个键时就会触发扩容而不是等到塞满 8 个。为什么不能等满了再扩用停车场来解释最直观。开放寻址就是“我停在车位 3发现被占了就在附近找空闲车位”。如果停车场空位多找起来很快如果已经停到 95%一个新来的司机可能要绕大半个停车场才能找到空位而且在他找的过程中其他司机也在绕停车效率直线下降。保留 1/3 左右的空位是为了让绝大多数插入只需要尝试一到两次就能成功。在计算机里这个“尝试”的成本就是内存访问。哈希表访问是随机访问不能指望缓存。负载因子越高探测链越长平均每次插入和查找要访问的内存次数就越多。Python 选择 2/3是在“表太稀疏浪费内存”和“表太满拖慢性能”之间做的折中。2.2 插入路径上的扩容判断usused 这个参数到底怎么来的具体到源码扩容不是在“负载因子超标”那一刻立刻发生而是在插入过程中发现可用条目数不够时才触发。在紧凑布局下entries数组里有多少个可用空位是有明确记录的每个新键都必须占一个 entry。当可用条目数降到不够时就走进扩容分支。在较旧的 CPython 源码里这个分支写得很直接status dictresize(mp, mp-ma_used * 4);dictresize接收的参数叫 minused意思是“新容量至少要达到这么大”。它内部会把这个数向上取整到 2 的幂。举个例子容量 8 的字典在插入第 6 个键左右触发扩容此时已用数量大约是 5传入5 * 4 20向上取 2 的幂就是 32。8 到 32 正好是 4 倍这就是“4 倍扩容”最直接的出处。注意这里的 4 倍并不是“拿旧容量乘以 4”而是“新容量至少是当前已用数量的 4 倍”。这两者在大多数情况下结果相似但语义完全不同。2.3 扩容瞬间做了什么重新哈希的完整过程扩容不是把旧数组原样拷贝到新数组就结束。它要先根据新容量分配indices和entries的内存然后遍历旧表里每一个还存活的条目取出键重新计算hash (newsize - 1)判断新槽位是否冲突最终插入新表。如果旧表里存在大量 Dummy 槽位这次重建会顺手把它们全部丢弃相当于给字典做了一次彻底的大扫除。这个过程的复杂度是 O(n)n 是当前键的数量。想象一下一个已经存了 100 万个键的字典某次插入触发扩容要一次性重新处理这 100 万个键。这就是为什么大字典在特定插入点会突然卡一下。业务代码里如果存在周期性的大规模插入这个现象会非常明显。3. “4 倍扩容”之谜为什么偏偏是 4 倍而不是 2 倍3.1 减少重新哈希后的冲突连锁先回答最核心的问题只扩容 2 倍行不行表面上看容量从 8 变成 16负载率也会降下来重新哈希后的查找性能应该也好一些。但有一个隐蔽问题原来在旧表里被挤到相邻位置的键重新哈希后两个键的新位置大概率还是相邻因为新掩码只比旧掩码多了 1 个比特位键的落点分布其实没发生质变。如果旧表已经因为负载过高形成了较长的探测链2 倍扩容往往只是把问题从“比较挤”变成“还是有点挤”。4 倍扩容就不同了。容量从 8 变成 32掩码从 3 个比特变成 5 个比特相当于一次多用了 2 个哈希比特。原本聚集在同一区域的键会被这多出的两个二进制位切散到四个不同的大区块。你可以理解成原来一个班的学生座位只分前后两排4 倍扩容后变成了前后左右四大区域大家重新散开后续插入时撞到一起的概率明显下降。3.2 配合 2/3 负载因子的数学关系4 倍扩容还有一个隐藏好处扩容间隔被拉长了。假设旧表容量是 S已用数量 U 大约是 2/3 S。传入的参数是U * 4约等于8/3 S向上取整到 2 的幂后新容量很容易变成 4S。新表负载率从接近 2/3 一下子降到接近 1/6。这意味着字典要再写入大量键才会达到下一次扩容线。如果只扩 2 倍新表负载率降到大约 1/3它确实还能工作但很快又会达到 2/3 的负载上限触发下一次扩容。每次扩容都伴随一次全量重新哈希成本不低。与其频繁小幅扩容不如一次扩到位让字典安静运行更久。这个思路在很多大数据结构里都存在减少复制次数往往比省下一次性分配内存更重要。3.3 哈希函数的雪崩效应与位运算的收益前面提到2 的幂容量让索引计算可以用位运算。4 倍扩容让掩码多用了 2 个比特位而 Python 内置的字符串、整数、浮点数的哈希函数都经过精心设计具有很好的雪崩效应哪怕输入只差一个字节输出哈希值的多个位都会剧烈变化。所以扩容之后键的新位置能够充分散开而不是集中在几个固定区块。这个设计环环相扣哈希函数分布好掩码位参与得越多散列越均匀散列越均匀负载因子就能维持得更健康负载因子健康开放寻址的探测链就短。4 倍扩容正是为了让“多出来的掩码位”足够多从而充分发挥哈希函数的分布优势。3.4 4 倍不是绝对规则超大字典和内存上限下的妥协严格说Python 在字典规模极大时并不会永远 4 倍膨胀。dictresize内部会限制最大规模并且当已用数量接近可表示的范围上限时used * 4可能超出整数范围或可用内存限制。此时源码里会有针对大字典的特殊路径让扩容幅度退化为 2 倍甚至不再增加。不过这个细节对绝大多数业务代码来说基本见不到。把“4 倍扩容”当成 CPython 字典在中小规模下的主要行为不会有什么偏差。如果你真的在维护包含几千万键的巨型字典最靠谱的做法是直接去读你所用版本的dictresize源码以那份实现为准。3.5 代价瞬时内存峰值可能很高4 倍扩容不是免费的午餐。当字典从容量 128 扩到 512而里面已经存了大约 85 条存活数据时旧表内存还没释放新表内存已经分配出来。如果这个字典里存的是大字符串或者复杂对象瞬时内存峰值会非常可观。所以在处理大批量写入时我通常不会让一个字典无限膨胀。要么用已知长度预分配要么在数据量到达一定规模后换用其他存储方案。别让单个字典的内存波动成为进程内存峰值的罪魁祸首。4. 扩容机制对实际业务的影响几个可以直接落地的建议4.1 为什么删了 90% 的键内存却不见下降很多开发者第一次踩坑就是处理完一个大数据字典后用pop或del清理了绝大部分键结果发现进程内存毫无变化。原因前面已经讲了删除只是把槽位标记成 Dummy哈希表的容量仍然保持在高峰期的状态。如果之后不再插入新键这些 Dummy 槽就一直空着。如果你确定后续不再用这个字典最干净的做法是调用clear()它会直接释放整张表。注意clear()释放的是整张表的底层内存而不是保留一个空表这一点和逐个删除键完全不同。如果还想保留部分数据就用字典推导式重新构建一个新字典只拷贝需要保留的键然后把旧字典引用置空交给垃圾回收处理。4.2 大批量插入时的周期性卡顿预分配的思路当你写这样一个循环data {} for item in huge_iterable: data[key(item)] process(item)随着字典越来越大你会注意到在特定插入次数时某一次插入明显变慢。这正是扩容瞬间的 O(n) 重新哈希。数据量小的时候完全无感到了百万级就会变成肉眼可见的卡顿点。处理办法有两个方向。第一预分配足够容量第二把字典拆成多个子字典让每个子字典规模可控。预分配在 Python 里没有类似dict(capacity100000)这种公开参数但不代表完全做不到。当你已经知道总条数 N 时可以这样写data dict.fromkeys(iterable_of_keys, default_value)或者使用后端支持长度推断的zip构建data dict(zip(key_list, value_list))dict.fromkeys在内部会根据传入序列的长度估算预分配容量比逐个插入少经历多次扩容。4.3 预分配的限制与误解预分配不是万能的。如果传给fromkeys的是一个生成器CPython 无法提前知道元素数量预分配效果会大打折扣。所以想真正受益就得传列表、元组这类明确知道长度的可迭代对象。另外预分配只是减少扩容次数并不能消除扩容。后续插入量如果超过预估照样会触发扩容。还有一个容易被忽略的点字典的最小容量是 8。也就是说一个只放 1 个键的字典底层也是容量 8 的哈希表。如果创建上万个微型的、每个只存几个键的字典内存浪费会非常可观。遇到这种场景可以考虑改用dataclass或者设计上的“字典池”不要指望原生 dict 在极小规模下也很省。4.4 数据稀疏时的备选方案原生 dict 不适合充当稀疏矩阵。当键的数量可能达到千万级但真正有值的位置很少时哈希表的容量会随着负载因子预先膨胀造成大量内存浪费。这类需求更适合用布隆过滤器之类的概率性结构先做存在性判断或者把数据落到 SQLite、本地文件索引里避免让 Python 堆内存一次性吃掉所有键的哈希表开销。如果你的场景只是“偶尔查一下某个键是否存在并不需要随机访问”也可以考虑用有序外部存储加二分查找。理解 dict 的扩容机制之后你就不会再天真地看着一百万个键的字典说“反正 Python 会自动管理内存”。5. 实测与排查用代码和数据把这个机制看清楚5.1 打印字典大小的跳跃点验证 4 倍扩容最直接的方法是观察sys.getsizeof的变化。这个函数返回对象自身占用的内存字节数会随着字典容量的变化而跳变。import sys d {} prev sys.getsizeof(d) for i in range(1000): d[i] i cur sys.getsizeof(d) if cur ! prev: print(f插入 {i 1:4d} 个键之后大小: {prev} - {cur} 字节) prev cur在不同版本的 CPython 里具体字节数会有差异但能明显看到几个跳跃点。第一次跳跃通常发生在插入第 5 到 6 个键时对应容量从 8 到 32后面还有 32 到 128、128 到 512 的跳跃间隔呈现约 4 倍的规律。你可以拿输出结果和自己版本的源码对照这比任何解释都直观。如果看不到这个规律先确认解释器是不是 CPython。PyPy 或者 Jython 的字典实现完全不同不能拿 CPython 的规则去套。5.2 故意制造哈希冲突看负载因子怎么救场自定义一个哈希永远返回 1 的对象把它塞进字典所有键都会被映射到同一条探测链上。虽然二次探测仍然能保证插入成功但查找和插入的时间会从 O(1) 劣化到 O(n)。import time class AlwaysCollide: def __init__(self, x): self.x x def __hash__(self): return 1 def __eq__(self, other): return self.x other.x normal {i: i for i in range(5000)} bad {AlwaysCollide(i): i for i in range(5000)} start time.perf_counter() for i in range(5000): _ normal.get(i) print(正常哈希耗时, time.perf_counter() - start) start time.perf_counter() for obj in bad: _ bad.get(obj) print(冲突哈希耗时, time.perf_counter() - start)你会看到冲突字典的耗时比正常字典高一个数量级以上。这个实验说明扩容机制再强也救不了劣质哈希函数。反过来说正因为 Python 的哈希函数质量高4 倍扩容多引入的那两个掩码位才有意义。5.3 常见问题速查表下面这张表是我在实际排查中总结出来的可以直接当排查手册用现象可能原因排查方向删掉大量键后内存不降哈希表只扩不缩删除只标记 Dummy用 clear 或重建新字典大字典插入时周期性卡顿扩容瞬间在做 O(n) 重新哈希预分配或拆分字典查不到已插入的自定义对象hash依赖可变字段哈希值变化让对象不可变或不用自定义对象作键字典内存比预期大容量始终是 2 的幂且只扩不缩用 sys.getsizeof 观察跳跃点预分配没有效果传入了生成器长度未知改用已知长度的列表或元组5.4 自定义对象作键时最容易踩的坑除了哈希冲突还有一个隐蔽问题对象的哈希值在放入字典之后发生改变。比如class Key: def __init__(self): self.name a def __hash__(self): return hash(self.name) k Key() d {k: 1} k.name b # 危险 print(d.get(Key()))一旦k.name被改变hash(k)就变了。哈希表扩容或者下一次查询时Python 会按新的哈希值去定位大概率找不到原来的条目。更危险的是这个条目还残留在旧哈希桶里可能破坏整个表的完整状态。所以字典键必须使用不可变对象或者确保__hash__只依赖不会变化的属性。这个坑我遇过不止一次。排查时可以把自定义类的__hash__临时注释掉看看字典行为是否恢复或者观察报错里有没有出现unhashable type。最稳妥的规范是一个类只要被当字典键使用就不要提供可能随状态变化的哈希逻辑。最后聊一点我自己的体会。查 CPython 源码理解字典扩容不是为了在面试里背一个“4 倍”的结论而是为了理解它为什么要这么设计。4 倍扩容的本质是用更多的一次性分配换取更少的重哈希次数和更短的探测路径代价是内存峰值上升以及删除后容量不收缩。搞懂这个权衡之后我在处理大数据量程序时多了一个判断维度什么时候该预分配、什么时候该重建字典、什么时候该换用其他数据结构。建议你动手把 5.1 和 5.2 两个小实验跑一遍再打印一下每次扩容前后的sys.getsizeof那种“原来底层是这样走”的感觉比单纯看文章要来得实在得多。
