调试爬虫程序的时候我遇到过一件怪事代码逻辑没有问题网络请求也正常但一个set去重操作却越来越慢。从几千条 URL 增加到几万条 URL耗时的增长完全不是线性而是直接往二次方向狂奔。后来定位到根源问题不是出在爬虫本身而是 Python 的 set 在特定条件下会暴露出quadratic-time performance也就是二次时间性能。很多人对 Python 的set和dict的第一印象是“查得快、插入快、去重方便”认为它们是常数时间复杂度的代名词。这个印象不能算错但只适用于“通常情况”。一旦键的哈希行为异常、容器不断扩容、或者操作被嵌套进一个外层循环整体时间复杂度就可能从 O(n) 变成 O(n²)甚至更糟。这篇文章我想聊清楚三件事set/dict 的 O(1) 承诺到底是怎么来的真实项目里哪些写法会让它退化成二次复杂度以及当性能已经劣化时你可以按什么顺序去定位和排查。最后会给你一套可复用的判断框架方便你在自己的代码里做预防。1. 先搞清楚 set 和 dict 的常数时间承诺到底是怎么来的要理解退化必须先理解正常情况。Python 的set和dict底层都建立在哈希表之上。哈希表最核心的承诺是通过哈希函数把任意对象映射成一个整数再用这个整数定位到内部数组的某个位置于是插入、查找、删除的平均时间复杂度都是 O(1)。1.1 哈希表基础hash、桶、负载因子我们可以把哈希表想象成一个有编号的货架。每个对象要存放时先算一次hash()得到一个整数然后根据这个整数决定放在哪个格子里。def simple_hash_example(value): return hash(value)CPython 内部并不是拿hash值直接当数组下标用的而是会再经过一次掩码运算把它映射到数组大小范围内的一个索引。这个映射关系由当前的表容量决定。哈希表不能无限制地往里塞数据否则格子会被占满。因此当插入的数据量达到某个阈值时就会触发扩容。这个阈值通常用“负载因子”来衡量概念含义桶 / slot哈希表内部数组中可存放元素的位置负载因子已用桶数量 / 总桶数量扩容当负载因子超过阈值时申请更大数组并重新插入所有键重哈希扩容后所有键的索引要基于新容量重新计算在 CPython 的实现里扩容之后表的容量通常会变大而所有元素的相对位置也会改变。这个扩容过程本身需要遍历已有元素复杂度是 O(n)。如果只在增长到很大时偶尔扩容一次整体平均仍然接近 O(1)。但如果你的程序反复触发扩容或者在一个循环里反复构建大表成本就会被反复放大。1.2 CPython 中经典实现开放寻址与稀疏表CPython 的 dict 和 set 不是用“数组 链表”实现的而是用“开放寻址法”。也就是说当两个键算出来的索引冲突时Python 会按照一套规则继续探测下一个空位而不是在同一个索引下挂一个链表。这种设计的优点是对缓存友好内存也更紧凑。但它有一个值得注意的副作用当表变得越来越满时探测序列会变长插入和查找的成本也会明显上升。所以 CPython 通常会保持表比较稀疏宁可浪费一点内存也不让表装得太满。这也是为什么你在实际工程里会观察到一个 set 或者 dict 在元素较少时速度很快但当元素数量连续翻倍、表不断扩容时单次操作偶尔会出现一次明显的卡顿。如果这种卡顿发生在一个大循环里整体耗时就会相当难看。1.3 为什么说“通常 O(1)”而不是“绝对 O(1)”官方文档和大多数教科书都会说 set/dict 的平均时间复杂度是 O(1)。但这里的“平均”有前提键的哈希值分布足够均匀。键对象是不可变的且__hash__方法稳定。哈希表没有被恶意或偶然地写入大量哈希值相同的键。操作本身不会触发频繁的扩容和重哈希。只要这些条件被破坏“平均 O(1)”就会退化成“最坏 O(n)”。当你在代码里用一个大循环反复做这类操作时总复杂度就可能是 O(n²)。这其实是集合和字典这类数据结构里最容易被忽略的一部分你没有写错语法也没有犯很低级的性能错误只是底层的数据结构在特定输入下产生了退化。2. 真正触发 O(n²) 的几种常见路径很多人以为二次复杂度只会出现在“循环套循环”的写法里。其实 set/dict 本身就可能成为二次复杂度的来源。下面这几条路径是我在实际项目和调试中经常遇到的。2.1 失控的哈希碰撞当“唯一”键不再唯一最典型的场景是大量键拥有相同或相近的哈希值。如果把哈希表的每个索引想象成车位碰撞就是多辆车抢同一个车位。开放寻址法会去找附近的其他空位但如果很多键的哈希值撞在一起找车位的时间就会越来越长。Python 内置的字符串、整数、元组在正常情况下哈希分布做得不错但并不意味着你不需要担心。比如当你把自定义对象作为 set 或 dict 的键时如果__hash__返回一个常量那么所有实例都会落在同一个桶区域。插入 N 个这样的键可能就变成 O(n²)。class BadKey: def __hash__(self): return 1 def __eq__(self, other): return self is other bad_set set() for i in range(10000): bad_set.add(BadKey())上面这段代码不会报错但运行时间会随range规模增长变得异常慢。原因不是 set 本身差而是我们给哈希表提供了灾难级的输入。2.2 循环里反复 resize动态扩容带来的重哈希哈希表为了保持性能会按负载因子动态扩容。扩容本身不是问题问题在于你在循环里不断插入大量数据而且中途没有任何删除操作。如果数据量一直在增长扩容就会周期性发生。周期性扩容带来的不是一次额外的 O(n)而是多次。N 次插入过程中扩容的总代价大约为 O(n)分摊到每次插入是 O(1)。这通常是可以接受的。但如果你在一个外层循环里每一轮都构建一个新的 set 或 dict并且构建的规模也在成倍增长那总耗时就会变成二次。一个典型的反面模式是result [] for i in range(n): s set() for j in range(i): s.add(j) result.append(len(s))这里外层循环每次都会重建一个规模递增的 set每次重建都包含扩容和重哈希整体复杂度是 O(n²)。虽然单看内部循环插入是 O(1)但外层多了一层累加成本。2.3 不可变类型与错误 hash 实现自定义对象做 key 的陷阱把自定义对象放进 set 或作为 dict 的 key是很常见的需求。但很多人没有注意到dict/set 对 key 有两个硬性要求__hash__必须在对象的生命周期内保持不变。__eq__相等的两个对象__hash__也必须相等。如果违背了第一条你可能遇到“对象在字典里却根据它找不到值”的神奇问题。如果违背了第二条哈希表就会把相等对象放到不同位置导致查找失败或性能下降。更隐蔽的问题是自定义对象如果没有重写__hash__默认是基于对象 id 实现的。两个内容完全相同的对象__eq__如果重写成按内容比较但__hash__仍基于 id那么它们即使相等也拥有不同哈希值。这在逻辑上是错误的也会让哈希表无法正常工作。推荐的做法是让自定义对象使用不可变字段来计算哈希或者直接使用dataclass(frozenTrue)、NamedTuple、frozenset等内置结构。2.4 深层 set/dict 嵌套和数据倍增组合爆炸还有一种二次退化不是来自哈希表本身而是来自数据结构的组合方式。比如你在一个 dict 的 value 里又放了一个 set外层循环每处理一条数据都要在外层 dict 里做一次查询同时在内层 set 里做一次更新。如果外层有 n 条记录内层平均也有 n 条记录那么整体就是 O(n²)。这种情况下即使每次哈希操作都很快总规模仍然会失控。users {} for user_id, tags in raw_data: current users.setdefault(user_id, set()) for tag in tags: current.add(tag)这段代码本身很常见但如果你在raw_data上再套一层循环去处理多批数据复杂度就会线性叠加成二次。2.5 误用 in、交集、并集在嵌套循环里set 的in操作是 O(1)但如果把in放进一个遍历所有元素的循环里整体就是 O(n)。如果外层也是循环两个 set 的规模都是 n那么a set(...) b set(...) for x in a: if x in b: ...这段代码看起来没什么问题但它的复杂度是 O(len(a))。只有当你要遍历的是 a 的每个元素而 b 的查询是常数时间时才是 O(n)。可如果你写成for x in a: for y in b: if x y: ...那就完全退化成 O(n²) 了。有人会狡辩说“但我在用 set 啊”可 set 的子集判断不是用去两两比较的它应该用a b、a.intersection(b)或者x in b。3. 用实际案例复现“看起来线性、实际二次”的过程理论说完了下面用几个最小例子来复现。这样你可以直接复制到自己的环境里验证。3.1 一个最简单的复现脚本set.add 循环 vs range先用内置整数键做一个对照组import time def make_set(n): s set() for i in range(n): s.add(i) return s for n in [10000, 20000, 40000, 80000]: start time.perf_counter() make_set(n) cost time.perf_counter() - start print(fn{n}, cost{cost:.4f}s)在我的环境里这组数据基本会呈现线性增长。因为整数对象的哈希值就是它自身分布非常均匀哈希表可以保持低碰撞。这里是安全区间。接着把__hash__返回常量的BadKey换成同样的循环class BadKey: def __hash__(self): return 1 def __eq__(self, other): return self is other def make_bad_set(n): s set() for i in range(n): s.add(BadKey()) return s for n in [1000, 2000, 4000, 8000]: start time.perf_counter() make_bad_set(n) cost time.perf_counter() - start print(fn{n}, cost{cost:.4f}s)n 翻一倍耗时大约涨四倍这就是典型的二次复杂度。同一个数据结构只是因为哈希分布质量不同性能就从“几乎不耗时的线性增长”变成了“肉眼可见的失控”。这个实验也说明set/dict 的 O(1) 并不是无条件成立的。它的前提是哈希值分布足够好。3.2 自定义对象未实现__hash__造成碰撞再来看一个更日常的例子。定义一个普通类只重写__eq__不重写__hash__class User: def __init__(self, name): self.name name def __eq__(self, other): return self.name other.namePython 会认为User(a) User(a)但两者的哈希值默认基于对象 id因此把一个User放入 set 后再用另一个相等的User去查询会得到 False。a User(alice) b User(alice) s {a} print(b in s) # False这就是一个典型的“相等对象哈希不一致”问题。它不仅会导致逻辑错误还会让 set/dict 在做去重时产生“重复数据无法合并”的现象数据量一大哈希表内部还会产生大量实际冲突进一步拖慢性能。修复方式很简单要么让对象不可变并实现__hash__要么用NamedTuple或frozen dataclass。3.3 在批量、爬虫、量化场景中的影响你可能觉得自定义对象做 key 不常用但实际工程里很容易踩到类似问题。比如爬虫中用 set 去重 URL如果 URL 不是字符串而是某种封装对象封装类的哈希实现写得不好去重性能就会退化。再比如把股票交易数据按时间戳聚合到多个 dict 中如果时间戳存在多种表示方式你用 tuple 做 key 时没处理好类型统一也会导致重复构建和哈希冲突。举个爬虫场景的例子# 爬虫伪代码仅演示结构 seen_urls set() for page in range(1, 10000): url fhttps://example.com/list/{page} seen_urls.add(url)如果 page 是字符串性能正常但如果这里你 hash 的对象是一个自定义 Response 对象并且__hash__实现不理想那整体去重的耗时就会非常可观。量化交易场景同理当你用一个复杂结构作为 dict 的 key比如(timestamp, symbol)如果 tuple 元素本身包含自定义对象那么这个自定义对象的__hash__质量会直接影响整体聚合性能。这些场景的共同特点是数据规模不大但操作频率高单个操作看起来都是 O(1)但累积起来就成了性能瓶颈。3.4 如何测量并定位timeit、perf_counter、cProfile如果怀疑 set/dict 退化了先不要盲目优化。先用量化工具确认复杂度是否符合预期。最基础的方法是记录不同输入规模下的耗时观察增长倍数输入规模耗时1耗时2增长倍数nt1t2-2n2倍左右4倍左右线性二次4n4倍左右16倍左右线性二次如果输入规模翻倍后耗时翻倍说明基本是线性耗时翻四倍就要怀疑是二次。这个方法虽然粗糙但定位很快。进一步定位可以用cProfile看函数调用耗时占比也可以用tracemalloc看内存增长是否异常。如果发现某个add、__hash__、__eq__调用特别多说明碰撞和比较成本已经上来了。import cProfile cProfile.run(make_bad_set(4000))输出里会显示__hash__被调用了多少次以及set_add的累计耗时。如果__hash__和__eq__的调用次数远超元素个数基本可以判定发生了碰撞。4. 工程上可以怎么避免退化知道问题在哪接下来就是怎么在工程上避免。我的建议不是“不要用 set/dict”而是“在合适的时候用并且把输入和自定义行为管好”。4.1 优先控制输入规模和 hash 质量如果一块逻辑的输入规模本来就在可控范围内而且用的是 Python 内置 str、int、tuple 做键那么大多数情况下 set/dict 的性能都不用操心。你需要担心的场景是输入规模会持续增长且你不知道上限。键是自定义对象且不能保证哈希质量。同一个数据结构会被频繁重建。你正在一个外层循环里不断向同一个容器追加数据。如果命中其中一两条建议在数据入口处先做一次校验或归一化。比如把 URL 先转成字符串再放入 set把时间字段统一成同一种格式再放入 tuple。4.2 对自定义对象实现稳定且分布良好的__hash__和__eq__如果你确实需要自定义对象作为键最稳妥的方式是让对象不可变并基于所有参与相等比较的字段来计算哈希。from dataclasses import dataclass dataclass(frozenTrue) class Point: x: int y: int points set() points.add(Point(1, 2)) print(Point(1, 2) in points) # TruefrozenTrue的 dataclass 会自动实现正确的__eq__和__hash__同时保证字段不可变。这个方案基本能避开大多数自定义对象哈希陷阱。如果不想用 dataclass用NamedTuple也是可接受的from typing import NamedTuple class Point(NamedTuple): x: int y: int这两种方式都是工程上更稳的选择。4.3 使用namedtuple、frozenset、dataclass(frozenTrue)等内置不可变结构有些人的代码里喜欢用 list 或 dict 作为 key然后发现TypeError: unhashable type: list。他们可能改用一个 tuple 代替但 tuple 里的元素如果是 list也仍然不可哈希。正确的做法是把可变结构转成不可变结构list - tupledict - frozenset(dict.items()) 或重新设计映射set - frozenset这样做不仅可以避免报错还可以让哈希值分布更稳定减少碰撞风险。4.4 避免在小循环里反复创建大 set/dict这是一个常见的工程坏味道。例如每一批数据处理时你都新建一个包含大量映射关系的 dict然后在这个循环里反复查询。正确的做法是把这个映射表提升到循环外部只构建一次。# 坏味道每次循环都重新构建 for chunk in chunks: mapping build_mapping(chunk) for item in chunk: if item in mapping: ... # 更合理先构建一次映射 mapping build_mapping(all_items) for chunk in chunks: for item in chunk: if item in mapping: ...后者把构建成本从“每批一次”降成“全局一次”如果批次很多性能提升会非常明显。4.5 尽量用生成器和流式处理避免全量聚合如果数据的最终目的是逐条输出或聚合不要一开始就全量塞进一个大 dict/set。能用生成器处理就优先用生成器。生成器可以减少中间容器的大小也降低内存和哈希表扩容压力。比如统计日志中的 key 频次你确实需要 dict 来计数但你可以先做“小窗口聚合”再定期合并结果。这比把所有记录一次性装入内存更稳妥尤其是当数据规模达到百万级时。5. 一套可复用的排查框架当代码突然变慢时先查什么如果代码已经变慢了不建议一上来就怀疑哈希函数。先按下面的顺序排查能从外到内快速定位问题。5.1 第一层看增长曲线判断是线性还是二次找出最耗时的循环把输入规模缩小到 1/10再扩大到相同数量级记录三到五个数据点。规模耗时10k0.25s20k0.98s40k3.90s如果增长倍数接近 4 倍说明大概率是二次复杂度。这时再看耗时压在哪个数据结构上。5.2 第二层检查键的 hash 值分布如果怀疑 set/dict 本身有问题直接打印一部分键的 hash 值观察有没有大量重复或聚集for sample in keys[:100]: print(hash(sample))如果大量 hash 值落在相同的低位说明冲突概率很高。如果所有结果都是同一个数字那已经属于灾难性碰撞了。这里要留意Python 的str、bytes等内置类型在较新版本里引入了随机化种子不同进程之间的 hash 值会变化这是正常现象。我们要看的不是数值本身而是分布是否均匀。5.3 第三层检查 resize 和内存分配如果 set/dict 的元素数量巨大可以在运行时用sys.getsizeof观察容器占用s set() for i in range(100000): s.add(i) print(sys.getsizeof(s))如果内存突然跳变说明触发了扩容。单独一次扩容不是大问题但如果代码里反复创建新容器内存分配和释放本身也会拖慢速度。可以使用tracemalloc查看内存增长是否集中在某处。5.4 第四层检查自定义对象和库的写法如果你的键不是基本类型优先看这几个文件里的__hash__、__eq__是否实现正确。很多第三方库会自定义内部对象不一定针对哈希性能做过优化。当你把它们作为 key 使用时问题就转移到了你的代码层。可以用inspect查看对象是否重写了__hash__import inspect from your_module import YourClass print(inspect.getsource(YourClass.__hash__))如果一个类没有显式定义__hash__它通常继承自 object这种哈希在作为数据键时往往是次优的。5.5 最后考虑换用替代结构如果以上步骤都查过仍然无法把复杂度压下来可以考虑换数据结构场景替代方案去重数量极大bloomfilter/ Redis Set计数统计collections.Counter/defaultdict(int)有序去重sortedcontainers.SortedSet大数据量聚合数据库索引 / 外部排序 / 流式聚合但注意替代方案也有自己的适用边界不要为了避开一个坑而掉进另一个坑。先用基准测试验证再替换。6. 一个边界不是所有 O(n²) 都要优化最后想补充一个容易被忽略的点。发现二次复杂度不代表你立刻要改成某种高级结构。技术文章很容易让人产生“我以后要严格审查每一个 set/dict”的焦虑但工程实践更讲究成本效益。6.1 哪些情况其实可以放心如果数据规模很小比如一次最多几百条那么即使退化到 O(n²)耗时也还是毫秒级。这种情况下维护代码的清晰度比强行优化更重要。脚本只在本地运行输入规模受控。数据是配置参数数量固定。临时调试代码不需要长期维护。加入边界保护比如if len(items) 10000:再切换策略。只要数据规模的上限能被控制住二次复杂度不一定构成问题。6.2 优化前先量化过早优化是万恶之源在你决定重写数据结构之前先用五分钟做一项测量。真实项目里全量聚合往往不是唯一的瓶颈。如果数据从数据库读取、网络传输、磁盘 IO 已经占用了 90% 的时间那么 CPU 内部的哈希碰撞可能根本不值得优化。我的建议是先把最耗时的函数摘出来做一个最小基准测试然后决定要不要动手。优化完再跑一次同样的基准用数据对比替代感觉判断。6.3 长期建议把性能边界当成 API 契约的一部分如果你写的模块会被别人调用最好在注释或文档里写明这个函数期望的输入规模大概是多少。如果数据量超过某个阈值建议用什么方式处理。自定义 key 是否要求实现__hash__。这看起来只是小细节但能帮未来维护者少走很多弯路。最后说几句Python 的 set 和 dict 是日常开发里最常用的数据结构也是我见过的最容易被“无意识误用”的工具。它们大多数时候表现很好但性能承诺并不是免费的背后依赖的是均匀的哈希分布、合理的负载因子和不可变的键对象。当一段代码越来越慢时与其怀疑 Python 本身不如先问三个问题我的键是稳定的吗哈希值分布正常吗操作是不是嵌套在循环里把这三个问题排查完你会发现自己对 set/dict 的理解已经从“会用”上升到了“理解机制”的层面。这种理解才是避免二次时间性能问题的根本解法。