平时写 Python我们默认set和dict是“快”的代名词去重、缓存、映射表、Union-Find、倒排索引……几乎哪里都有它们的身影。但很多开发者都经历过这种诡异情况同样是往一个set里塞 10 万个元素换了一批数据源之后代码从“毫秒级”直接变成“秒级”甚至卡到像死循环你反复检查循环、比较、IO最后才发现问题出在那些元素的哈希值上。这不是冷门知识而是一个被大量业务代码忽略的性能陷阱。set和dict的“平均 O(1)”有一个非常严格的前提元素的哈希值要足够分散。一旦这个前提被打破最坏情况下总操作复杂度会退化成 O(n²)。从毫秒到分钟往往只差一个糟糕的__hash__。这篇文章我会把这件事讲透先看 CPython 哈希表的底层机制搞清楚为什么“同哈希值”会带来灾难性的探测链然后用两个可复现的基准脚本让你亲眼看到 O(n²) 退化最后给出生产环境的排查路径和工程建议。无论你是在做爬虫去重、接口缓存、数据导入还是在准备 Python 面试这篇都值得收藏。1. 为什么 O(1) 只是一个“平均情况”承诺1.1 哈希表怎么做到“平均 O(1)”要理解退化先要理解为什么正常情况下哈希表很快。哈希表的核心是一个数组数组的每个位置可以看作一个“桶”。当我们往dict或set里放一个 key 时CPython 会调用hash(key)得到一个整数然后用这个整数定位到数组的某个位置直接在目标位置附近完成查找或写入。正常情况下一个设计良好的哈希函数会让不同的 key 尽量分散到不同的位置。这样插入和查找只需要常数次比较就能完成时间复杂度就是 O(1)。这里有个非常容易混淆的地方你听到的“O(1)”其实是平均情况而不是最坏情况。数据结构教科书里明确写过哈希表的理想复杂度是平均 O(1)、最坏 O(n)。但在业务代码里大家往往只记住了前半句导致遇到性能退化时完全没有排查方向。1.2 最坏情况到底坏在哪里最坏情况什么时候出现当大量 key 被哈希到同一个位置时。假设有 n 个 key它们的哈希值完全相同。第一个 key 插入时目标位置是空的1 次操作搞定第二个 key 发现目标位置被占了要顺着探测序列往后找第三个 key 要跳过的已占用位置更多…… 到第 n 个 key 时已经需要扫描大约 n 个位置。于是累计操作次数是1 2 3 ... n ≈ n² / 2这就是 O(n²) 的来历。如果你在一个循环里反复执行这样的插入或查找整体时间会随数据量平方级上升。数据量从 1 万变成 2 万理论上最坏耗时不是翻倍而是变成 4 倍。有些读者可能觉得这只是教科书上的极端情况。但关键在于这种“极端”在真实代码里并不少见尤其是当 key 是自定义对象、整数序列或来自不可信输入时。1.3 这篇文章能帮你解决什么理解了“平均 O(1)”和“最坏 O(n²)”的关系之后你需要的不只是概念而是一套可执行的方案。下面几个问题都会在本文得到答案CPython 的set和dict底层到底怎么处理哈希冲突为什么 Python 的开放寻址法对“同哈希值”格外敏感怎么用基准测试验证自己的代码是否正在退化生产环境出现可疑卡顿应该按什么顺序排查自定义类的__hash__怎么写才安全、高效2. CPython 中 set 与 dict 的哈希表设计2.1 开放寻址法而不是链地址法很多语言里的哈希表采用“数组 链表”的链地址法每个桶下面挂一个链表遇到哈希冲突就把新元素挂到链表尾部。Java 的HashMap在早期就是这样后来链表过长还会转成红黑树。但 CPython 的set和dict走的是另一条路开放寻址法。在开放寻址法里整个哈希表就是一块连续的大数组。没有链表。当目标位置已经被占用时不另开链表而是在数组里继续向后寻找下一个空位。找到空位就放进去查找时也从初始位置出发沿着同一条探测路径逐个比较直到找到目标或遇到空位。这种设计的优势是内存紧凑、缓存友好。缺点也很明显它对哈希值的多样性要求极高。如果大量 key 的哈希值相同它们会沿着几乎相同的路线“挤”在一起形成一条很长的探测链。这也是为什么 Python 的哈希表一旦遇到“垃圾哈希函数”性能雪崩得比链地址法还明显。2.2 探测序列伪随机也救不了相同哈希值CPython 的探测并不是简单的线性探测。实际代码里初始位置是i hash_value mask其中mask是容量减 1容量始终是 2 的幂所以这个操作等价于取哈希值的低若干位。如果初始位置被占用CPython 会进入一个循环更新位置的方式类似于i (i * 5 1 perturb) mask perturb 5这里的perturb初始就是哈希值本身每次循环右移 5 位。这种设计让探测序列能够快速覆盖整张表避免线性探测容易出现的“聚集”问题。但请注意一个关键事实**perturb从哈希值推导而初始位置也从哈希值推导**。如果两个 key 的哈希值完全相同那么它们的初始位置相同后续每一轮探测的位置也完全相同。伪随机扰动只会把同哈希值的元素送到同一条链上。所以对于哈希值完全相同的 n 个元素它们的行为就像排队进同一个坑时间复杂度不可避免地从 O(1) 退化到 O(n)。2.3 负载因子与扩容CPython 的哈希表不会等到数组塞满才扩容。它有一个负载因子大约是 2/3。也就是说当已使用槽位数超过容量的 2/3 时就会触发扩容分配一个更大的数组并重新安排元素位置。扩容会让每个元素重新计算自己在新数组里的位置这个操作本身均摊后是 O(1)所以正常的渐进构建复杂度依然是 O(n)。但这里有一个容易忽略的点如果哈希值本身分布很差扩容根本救不了你。因为无论数组多大所有元素的哈希值还是相同它们在新数组里依然会挤在同一条探测链上。扩容只会浪费内存不会改善查找效率。2.4 删除操作的隐性代价dummy 标记开放寻址法还有一个容易被忽视的细节删除元素时不能简单地清空槽位。假设 A、B、C 三个 key 哈希值相同依次落在位置 0、1、2。现在你把 B 的槽位清空下次查找 C 的时候从位置 0 开始探测位置 0 不是 C继续探测到位置 1 —— 如果这里被清空成“未使用”状态查找算法会认为探测链在这里断了直接判定 C 不存在。所以 CPython 会把被删除的槽位标记成特殊状态通常称为 dummy。dummy 槽位不能直接结束探测但可以被新元素重新使用。当一个哈希表里堆积了大量 dummy 槽位时负载计算会受影响甚至可能提前触发扩容。如果你在做一个高频“增删”操作的缓存表这个问题可能会在不知不觉中拖慢性能。3. 触发二次方退化的四类真实场景3.1 自定义对象的hash被写坏最典型、也最常见的退化来源是自定义类没有实现一个分散均匀的哈希函数。举个例子假设你在做一个订单系统把订单对象直接当作dict的 keyclass Order: def __init__(self, order_id, channel): self.order_id order_id self.channel channel def __hash__(self): return 1这个__hash__返回常量1。看起来荒唐但现实里真的有很多“简化版”代码随手return 1或return len(self.name)导致所有对象哈希值相同。结果就是上面说的构建一个 N 个元素的 set/dict代价从 O(n) 直接变成 O(n²)。即使不用常量如果__hash__只用了一个取值空间很小的字段比如只取channel的编号只有几个值也会造成严重的不均匀。代码不会崩但性能会以一种非常隐蔽的方式劣化。另外Python 3 中还有一个容易踩的坑如果你定义了__eq__但没有定义__hash__Python 会把__hash__自动设为None这个类的实例会变成不可哈希放入 set 会直接抛出TypeError: unhashable type。这是因为两个对象相等时哈希值必须相等Python 不敢替你默认实现。3.2 整数 key 的整除碰撞某些读者可能会觉得“我的 key 都是 int应该没问题吧” 其实 int 也有坑。CPython 中 int 的哈希值是它本身内部会按 2^61-1 取模处理大整数本身没问题。问题出在哈希表“初始位置取低位”这个设计上。哈希表容量是 2 的幂初始位置是hash mask。假设当前容量是 8mask是 7那么初始位置只取决于哈希值的低 3 位。如果你的数据是一批 8 的倍数比如i * 8在容量为 8 的阶段这些整数的低 3 位全是 0它们会争抢同一个起始槽位。随着扩容高位扰动逐渐生效情况会缓解但早期的长链已经造成了明显的额外开销。这种“整数 key 的隐蔽退化”在真实项目里最容易出现在从数据库读取一批有规律的 ID再批量去重或建索引的时候。需要说明的是这种情况不一定严格退化成 O(n²)但性能劣化是可感知的数据量越大越明显。3.3 恶意输入哈希拒绝服务Hash DoS哈希碰撞不只是性能问题还是安全问题的例子在历史上非常有名。2003 年 Perl 爆出哈希碰撞拒绝服务漏洞2011 年前后Java、Python、Ruby、Node.js 等主流语言也陆续爆出过类似问题。攻击原理很简单如果服务端把 HTTP 请求参数解析成一个dict而字符串哈希函数是固定的、可预测的攻击者就可以预先批量构造大量“哈希值相同”的 key。服务端在解析这些参数时哈希表退化成一条超长探测链CPU 被白白耗尽系统响应越来越慢最终达到拒绝服务的效果。Python 对此的应对是Python 3.3 起默认启用哈希随机化Python 3.4 起通过 PEP 456 引入 SipHash 作为字符串哈希算法。SipHash 是一种带密钥的哈希函数密钥在进程启动时随机生成。攻击者无法预知当前进程使用的密钥就很难构造出大量碰撞的字符串。3.4 字符串哈希随机化保护不了什么哈希随机化保护了str、bytes这类类型但下面这些场景它管不到int keyint 的哈希值固定不受随机种子影响自定义对象只要你自己的__hash__写得烂随机化救不了你其他不受随机种子保护的内置类型比如 tuple 的哈希依赖内部元素的哈希如果内部元素是 int那 tuple 的哈希也不随机。所以在评估风险时一定要先问key 是什么类型来自哪里如果 key 是从不可信输入直接来的 int或者是我们自己写的自定义对象就不能把“哈希随机化”当成万能保护伞。4. 复现实验用基准测试看清楚 O(n²) 退化4.1 准备实验环境这个实验不需要安装任何第三方包只需要 Python 3。建议用 Python 3.10 或更高版本不过核心结论在 3.7 都一样。操作系统不限Linux、macOS、Windows 都能跑。下面所有代码保存为bench_hash.py在命令行运行python3 bench_hash.py4.2 基准 1正常整数 set 与劣质哈希对象 set 的对比先定义一个“故意写坏”的类# 文件路径bench_hash.py import time class BadHash: __slots__ () def __hash__(self): return 42 def __eq__(self, other): return self is other注意__eq__使用了self is other也就是只有同一个对象才相等。这样我们创建出来的 n 个对象哈希值虽然相同但彼此不相等set 会保留全部对象完美复现“大量元素挤在同一条探测链”的场景。然后写两个建 set 的函数def build_int_set(n): return set(range(n)) def build_bad_set(n): return {BadHash() for _ in range(n)}最后是主测试循环for n in (1000, 2000, 4000, 8000, 16000, 32000): t0 time.perf_counter() build_int_set(n) t_int time.perf_counter() - t0 t0 time.perf_counter() build_bad_set(n) t_bad time.perf_counter() - t0 print(fn{n:6} | int: {t_int:.4f}s | BadHash: {t_bad:.4f}s)在我本机跑出来的趋势大致如下不同机器上有差异但趋势一致n 1000 | int: 0.0001s | BadHash: 0.0004s n 2000 | int: 0.0002s | BadHash: 0.0015s n 4000 | int: 0.0005s | BadHash: 0.0060s n 8000 | int: 0.0010s | BadHash: 0.0260s n 16000 | int: 0.0021s | BadHash: 0.1050s n 32000 | int: 0.0042s | BadHash: 0.4210s看两个关键点普通int的耗时随着 n 增长接近线性n 翻倍耗时大约也翻倍。BadHash的耗时随 n 增长接近二次方n 从 1000 到 32000扩大了 32 倍耗时就放大了 1000 倍左右。这就是 O(n²) 退化的直观证据。4.3 基准 2整数倍数序列的隐蔽劣化再看一个更“隐蔽”的数字 key 案例。这次 key 本身还是 int但是一组有规律的倍数序列def build_factor_set(n, factor): s set() for i in range(1, n 1): s.add(i * factor) return s for factor in (1, 8, 64): t0 time.perf_counter() build_factor_set(100_000, factor) elapse time.perf_counter() - t0 print(ffactor{factor:2} time{elapse:.3f}s)在这个例子里factor1时 key 是连续整数低 3 位分布均匀factor8时所有 key 的低 3 位都是 0在哈希表容量较小时会大量争抢起始槽位。实际运行中倍数序列的构建时间通常会明显高于连续整数序列。注意这个测试的结果和 Python 版本、插入顺序、扩容时机都有关系不一定每次都稳定复现出巨大的倍数差距。它的意义在于提醒你即使全是 int key也不能理所当然地认为性能一定最优。尤其是当 key 来自外部且有规律时需要留个心眼。4.4 如何判断实验结果判断基准脚本是否“跑成功”的标准很简单普通 int set 的耗时近似线性增长BadHash set 的耗时出现明显的二次增长趋势数据量越大两类 key 的时间差越悬殊。如果你观察到 BadHash 的耗时增长没那么规则可能是因为机器上的 CPU 频率波动、后台进程干扰或者 n 还不够大。建议把最大 n 提高到 64000或者用timeit.repeat多次运行取中位数会稳定很多。5. 生产环境排查这类性能问题的路径基准测试能验证原理但线上问题通常不会像BadHash这么明显。真正遇到 set/dict 性能退化时建议按下面顺序排查。5.1 确认热点在哈希容器先用性能分析工具确认瓶颈确实在 set/dict 相关操作python -m cProfile -s cumulative your_script.py如果输出里频繁出现set.add、dict.__getitem__、dict.__setitem__等内置方法并且调用次数高得离谱那么哈希质量问题就是一个重点怀疑对象。5.2 检查 key 的类型与hash实现接下来要回答一个问题你的 key 到底是什么如果是内置的int、str、tuple它们的哈希质量通常有保障如果是自定义对象重点检查__hash__如果是继承自内置类型的子类检查是否重写了__hash__。在代码里快速定位所有自定义__hash__grep -rn def __hash__ your_project/看到类似下面这几类实现都要提高警惕def __hash__(self): return 1 def __hash__(self): return len(self.name) def __hash__(self): return self.channel_id % 10它们的共同问题是输出空间太小无法让元素在哈希表里均匀分散。5.3 用哈希分布抽样量化 key 质量如果你怀疑某批 key 的哈希质量差可以写一个小函数做抽样统计。把 key 的哈希值映射到若干个桶里观察分布是否均匀# 文件路径check_hash.py from collections import Counter def hash_distribution(values, slot_count64): buckets Counter(hash(v) % slot_count for v in values) return buckets # 实际使用时传入你的真实 key 列表 # ints [1, 2, 3, ...] # print(hash_distribution(ints))如果某个桶的元素数量远高于平均值说明哈希值在低几位上高度集中。尤其注意初始位置只使用哈希值的低位所以“低位分布”比“整体分布”更重要。也可以拿它直接对比正常 key 和可疑 keyclass BadHash: __slots__ () def __hash__(self): return 42 print(hash_distribution(range(10000))) print(hash_distribution([BadHash() for _ in range(10000)]))正常情况下每个桶数量大致都在 150 上下一旦所有元素都集中到同一个桶问题马上就暴露了。5.4 利用 sys.hash_info 与 PYTHONHASHSEED 排查有时候我们需要确认当前 Python 环境是否启用了哈希随机化。可以执行import sys print(sys.hash_info)在较新的 CPython 版本里输出类似sys.hash_info(width64, modulus2305843009213693951, inf314159, nan0, imag1000003, algorithmsiphash13)algorithm字段说明字符串哈希算法是 SipHash。不同 Python 版本显示的字段可能略有差异但algorithm一般都在。要确认字符串哈希随机化是否生效最直接的办法是在命令行连续运行两次python3 -c print(hash(csdn)) python3 -c print(hash(csdn))如果两次输出不一样说明随机种子生效。如果你需要固定种子排查顺序相关的问题可以在启动时设置PYTHONHASHSEED0 python3 your_script.py但这个操作会降低对哈希碰撞 DoS 的防御只建议在本地复现和测试时使用生产环境千万不要用。6. 常见问题与排查思路问题现象可能原因排查方式解决方案构建大 set/dict 明显变慢大量 key 哈希值相同或分布集中用基准测试对比正常 key检查 hash 分布重写__hash__或改用 int 索引/key自定义对象无法放入 set类定义了__eq__导致__hash__被置为None检查类是否定义了__hash__属性同时实现__hash__并保证与__eq__一致两次运行中 set 的迭代顺序不同字符串哈希随机化导致顺序变化设置PYTHONHASHSEED0复现不要依赖 set 顺序需要保序时用 dict/list修改对象字段后从 dict 里查不到可变对象被用作 key哈希值随字段变化检查 key 类型是否可变使用不可变副本或固定 ID 作为 key删除再插入后性能不降反升dummy 槽位积累触发提前扩容用基准对比高频增减场景适当时候重建容器避免长期高频删改线上服务处理用户请求偶发高延迟大量碰撞 key 导致哈希表退化分析请求 key 分布监控 set/dict 耗时限制输入规模/长度保持哈希随机化升级 Python每一条在真实项目里都可能出现。尤其是“修改对象字段后查不到”这个问题很多人以为是缓存失效实际上是因为对象哈希值变了哈希表按照新哈希值找位置自然找不到旧位置上的旧对象。这是“可变对象作 key”最经典的坑。7. 最佳实践让 set/dict 保持真正的 O(1)7.1 默认用不可变内置类型做 key工程上最稳妥的做法是不要轻易把自定义对象直接作为 key。优先使用intstrtuple内部元素也必须是不可变、可哈希类型这些内置类型的哈希算法经过高度优化分布质量好比较成本也可控。如果业务上能用一个整数 ID 代表业务对象就不要把整个对象塞进去。7.2 自定义hash的正确姿势如果确实需要自定义对象作为 key最简单可靠的方式是组合字段的 tuple 哈希# 文件路径models.py class Point: __slots__ (x, y) def __init__(self, x, y): self.x x self.y y def __hash__(self): return hash((self.x, self.y)) def __eq__(self, other): if not isinstance(other, Point): return NotImplemented return self.x other.x and self.y other.y几个要点__hash__和__eq__必须成对实现参与哈希的字段必须是不可变字段两个对象相等时参与哈希的字段必须相同__slots__可以降低内存占用但这不是必须的。如果你有大量字段tuple 哈希的成本会随字段数线性增长。这时候可以评估是否只取少数几个“区分度足够高”的字段组合或者使用更专业的哈希混合方式。对于绝大多数业务场景hash((a, b, c))已经足够好不要过早优化。7.3 处理不可信输入的安全策略当 dict/set 的 key 来自外部输入时需要把“哈希随机化”和“输入规模控制”同时考虑。保持默认哈希随机化不要为了复现问题就在生产环境固定PYTHONHASHSEED对请求参数数量、单个参数长度、JSON 对象字段数量做限制如果是自研协议不要把“外部可控的 int”直接当作大批量 key 使用避免把不可信长字符串重复作为 key 做大集合哈希计算本身也有 O(len) 成本。哈希碰撞 DoS 的核心不是“碰撞一定发生”而是“攻击者能否低成本制造大量碰撞”。随机种子大幅提高了这个成本但输入规模限制仍然是最后一道防线。7.4 性能关键路径上的取舍在高性能路径上可以做的优化有很多批量构造尽量从已有 list 一次性构造set(lst)或dict(zip(keys, values))解释器会利用序列长度做容量提示减少多次扩容避免高频删改如果某个 set/dict 会被频繁增删考虑定期重建减少 dummy 槽位积累超大 set 的替代方案如果 key 是连续整数可以考虑bytearray、bitarray或 Bloom Filter容量和性能都可能优于哈希表避免在循环内部逐次向大容器 add/update先收集到局部变量再一次性合并。这些优化不一定能解决“哈希分布差”的问题但可以减少哈希表的扩容和重排开销。7.5 给团队代码评审的建议把“哈希质量”纳入代码评审的检查清单比事后排查线上问题便宜得多。建议重点检查以下几点__hash__是否返回常量或取值空间过小的值是否有可变对象被直接用作 key是否在高效路径上频繁执行 set/dict 操作是否有人为了调试设置PYTHONHASHSEED0并留在了配置文件里是否把用户可控输入直接送进了大容器这些问题看起来都很基础但往往会在最复杂的数据流里埋雷。8. 总结与进一步学习方向set和dict是 Python 里最常用的两个数据结构但它们的性能优势从来都不是无条件的。平均 O(1) 的前提是哈希值充分分散最坏 O(n²) 的代价是哈希值高度集中。在自定义对象、规律整数序列、恶意输入三类场景里这个前提都可能失效。建议你现在就做三件事把本文的基准脚本在你自己机器上跑一遍感受一下 O(n²) 退化有多明显检查手头项目里所有自定义__hash__用哈希分布函数抽样看质量把这篇文章分享给团队里写缓存、去重、批量导数据的同学避免大家一起踩坑。如果你想继续深入推荐直接读 CPython 源码里的Objects/dictobject.c和Objects/setobject.c重点看find_empty_slot、set_lookkey这几个热路径函数。再配合 PEP 456 理解 SipHash 的引入背景你对“哈希表为什么快、什么时候慢”的理解会超过绝大多数 Python 开发者。