★ FEATURED ARTICLE 1. 从一个真实的性能翻车现场说起去年帮一个做数据清洗的朋友排查脚本卡顿的问题场景很朴素读一个几十万行的日志文件逐行解析出用户 ID判断这个 ID 是否在“已处理名单”里不在就追加进去。逻辑简单到不能再简单但脚本跑到十几万行的时候速度肉眼可见地掉下来最后干脆卡住不动。我让他把“已处理名单”的数据结构从列表换成集合其他一行代码没动跑完同样的数据从原来的四分多钟降到不到两秒。他当时的第一反应是“是不是哪里写错了”第二反应是“凭什么”。这个“凭什么”就是我想在这篇里聊透的东西。字典、集合、列表这三个东西几乎是每个人学编程第一天就会用到的容器但恰恰因为太熟很多人从来没认真想过它们底层到底怎么存数据、查找一次要花多少代价。结果就是代码能跑但一上量就崩而且崩得莫名其妙。这篇内容适合所有写过循环、用过in判断、做过去重的人看。不管你是刚入门的新手还是写了几年业务代码但没系统补过数据结构这一课的老手我都会用最直白的方式把这三者的性能差异讲清楚并且给出可以直接抄的选型规则和实测数据。核心关键词就三个字典、集合、列表、性能比较、查找效率、哈希表。看完你应该能做到拿到一个需求三秒钟判断该用哪个容器而不是凭感觉随手写个列表了事。2. 为什么同样是“找东西”速度能差几万倍2.1 列表查找的真相一个一个问过去列表的底层是一块连续的内存元素按顺序挨着放。这带来一个巨大的好处如果你知道下标比如lst[5000]它能直接算出第 5000 个元素的内存地址一步到位这叫随机访问复杂度是 O(1)。但问题出在“按值查找”上。当你写if x in lst的时候列表并不知道x在哪它唯一能做的就是从头开始一个一个拿出来跟你比第 0 个是不是不是。第 1 个是不是不是。一直问到找到为止或者问完整个列表都没找到。这就意味着最坏情况下你要比较 N 次平均也要 N/2 次。一个十万元素的列表查一次平均要问五万次。如果你在一个十万次的循环里每次都做这个查找那就是五十亿次比较。这就是我朋友脚本卡死的根本原因——不是代码写错了是数据结构选错了导致计算量爆炸。用生活化的类比列表查找就像你拿着一把钥匙去一栋没有编号、没有前台的大楼里挨家挨户敲门问“这是你家钥匙吗”。楼里有一万户你平均要敲五千次门。2.2 字典和集合的秘密武器哈希函数直接定位字典和集合走的是完全不同的路子。它们底层都是哈希表核心思想是不给元素排队而是给每个元素算一个“门牌号”直接送到对应的位置。具体过程是这样的当你往集合里放一个元素x它先调用哈希函数算出x的哈希值比如算出来是 87342然后对这个值取模对哈希表的容量取余得到一个槽位下标比如 342就把x放到第 342 号槽里。下次你要查x在不在同样算一遍哈希、取模直接去 342 号槽看一眼就行——一步到位不需要遍历。这就是为什么集合和字典的查找、插入、删除平均复杂度都是 O(1)。注意我说的是“平均”后面会讲什么时候会退化。还是用大楼类比字典和集合相当于大楼有个智能前台你报出钥匙编号前台直接告诉你“在 342 房间”你坐电梯直达一次搞定。楼里有一万户还是一亿户对你来说都是坐一次电梯的事。2.3 一张表看清三者的复杂度差异操作列表 list字典 dict集合 set按下标访问O(1)不支持不支持按值查找inO(n)O(1) 平均O(1) 平均插入尾部O(1) 摊销O(1) 平均O(1) 平均插入中间O(n)不适用不适用删除O(n)O(1) 平均O(1) 平均去重O(n²) 朴素做法O(n)O(n)保持顺序天然有序3.7 保持插入序无序这张表建议直接记住。它基本上覆盖了日常 90% 的选型场景。看到“查找”“判断存在”“去重”这几个词脑子里就应该自动跳出字典或集合而不是列表。3. 哈希表凭什么这么快代价又是什么3.1 哈希函数与冲突处理快是有前提的哈希表能做到 O(1)前提是哈希函数把元素均匀地撒到各个槽位里。如果所有元素都算到同一个槽那这个槽就退化成一个列表查找又变成 O(n) 了。这种情况叫哈希冲突。不同的语言处理冲突的方式不一样。常见的有两种链地址法每个槽挂一个链表冲突的元素挂在同一个链表上和开放寻址法冲突了就按某种规则找下一个空槽。Python 的字典和集合用的是开放寻址法的变体这也是为什么它的内存布局比较紧凑、缓存友好。这里有个关键点很多人不知道哈希表的性能依赖于负载因子。负载因子 已用槽位 / 总槽位。当负载因子超过某个阈值Python 里大约是 2/3哈希表就会扩容——申请一块更大的内存把所有元素重新哈希一遍搬过去。扩容那一下是 O(n) 的但因为扩容后容量翻倍平摊到每次插入上仍然是 O(1) 摊销复杂度。注意如果你的代码对延迟极其敏感比如实时系统要留意扩容带来的偶发卡顿。可以在初始化时预估数据量提前给字典或集合一个足够大的初始容量避免运行中反复扩容。3.2 可哈希的门槛不是什么东西都能塞进去能用哈希的前提是元素可哈希。什么叫可哈希简单说就是它的哈希值在整个生命周期内不能变。所以列表、字典、集合这些可变对象不能作为字典的键也不能放进集合里。而数字、字符串、元组且元组内元素也都可哈希就可以。这个限制经常让新手踩坑。比如你想用“一组坐标”作为字典的键写成d[(1, 2)] a是可以的因为元组不可变但写成d[[1, 2]] a就会直接报错。解决办法是把列表转成元组d[tuple([1, 2])] a。3.3 内存换速度字典和集合更“吃内存”天下没有免费的午餐。哈希表为了维持 O(1) 的查找必须预留大量空槽位来降低冲突概率所以它的内存占用通常比列表大得多。一个存 1000 个整数的列表内存基本就是 1000 个整数加一点开销而一个存 1000 个整数的集合底层可能分配了 2000 甚至 4000 个槽位。我实测过一组数据Python 3.1164 位环境容器元素数量大致内存占用list100 万整数约 8 MBset100 万整数约 32 MBdict100 万键值对约 42 MB所以选型时要权衡如果你需要频繁查找用字典/集合换来的时间收益远远超过内存代价如果你只是顺序遍历、很少查找列表反而更省内存、遍历也更快因为内存连续CPU 缓存命中率高。4. 实测对比用数据说话4.1 查找性能实测我写了一段基准测试在一个包含 100 万个元素的容器里查找 1000 个随机元素分别用列表、集合、字典测三次取平均。核心代码逻辑如下import time import random N 1_000_000 QUERIES 1000 data_list list(range(N)) data_set set(range(N)) data_dict {i: i for i in range(N)} targets [random.randint(0, N - 1) for _ in range(QUERIES)] def bench(container, name): start time.perf_counter() hit 0 for t in targets: if t in container: hit 1 elapsed time.perf_counter() - start print(f{name}: {elapsed:.4f}s, hit{hit}) bench(data_list, list) bench(data_set, set) bench(data_dict, dict)实测结果不同机器会有差异但量级关系稳定容器1000 次查找耗时相对倍数list约 3.2 秒1x基准set约 0.00006 秒约 5 万倍快dict约 0.00007 秒约 4.5 万倍快这个差距是不是有点反直觉列表查 1000 次要三秒多集合几乎是瞬间完成。原因就是前面说的列表每次查找平均要比较 50 万次1000 次就是 5 亿次比较而集合每次查找就是算个哈希、跳一次内存1000 次也就 1000 次操作。4.2 去重性能实测去重是另一个高频场景。朴素做法是遍历列表用if x not in result判断后追加这本质上是在列表里反复查找复杂度 O(n²)。正确做法是直接用集合# 慢O(n²) def dedup_slow(items): result [] for x in items: if x not in result: result.append(x) return result # 快O(n)但会打乱顺序 def dedup_fast(items): return list(set(items)) # 快且保序O(n) def dedup_ordered(items): seen set() result [] for x in items: if x not in seen: seen.add(x) result.append(x) return result对 10 万个有重复元素的列表去重实测方法耗时是否保序dedup_slow约 18 秒保序dedup_fast约 0.01 秒不保序dedup_ordered约 0.02 秒保序dedup_ordered这个写法是我最推荐的用一个集合记录“见过的元素”用列表记录“结果顺序”既拿到 O(n) 的速度又保住了原始顺序。多花的那点内存完全值得。4.3 遍历性能实测列表反而赢了有意思的是如果只是单纯遍历不做任何查找列表往往比集合和字典更快。因为列表内存连续CPU 预取机制能高效工作而哈希表的元素散落在各个槽位缓存命中率低。实测遍历 100 万个元素容器遍历耗时list约 0.012 秒set约 0.018 秒dict遍历键约 0.020 秒差距不算大但方向很明确纯遍历用列表查找用字典/集合。不要因为“集合查找快”就把所有东西都换成集合那是另一种形式的想当然。5. 选型决策三秒钟判断该用谁5.1 一张决策流程图文字版拿到需求按这个顺序问自己我需要按位置访问元素吗比如“取第 3 个”“取最后一个”——需要就用列表。我需要频繁判断“某个值在不在里面”吗——需要就用集合只存值或字典值带附加信息。我需要去重吗——用集合或者“集合列表”保序去重。我需要键值映射吗比如“根据用户 ID 查订单”——用字典。以上都不需要只是存一串数据顺序处理——用列表。5.2 常见场景对照表场景推荐容器理由存一批日志按顺序处理list顺序遍历无需查找判断用户是否已访问过setO(1) 查找天然去重统计每个词出现次数dict键是词值是计数维护一个有序的结果集list需要顺序和下标求两个列表的交集/并集set集合运算一行搞定缓存计算结果dict键是输入值是输出存配置项dict键值映射语义清晰集合运算这块补充一句很多人不知道集合支持交集、|并集、-差集比手写循环快得多也清晰得多a set([1, 2, 3, 4]) b set([3, 4, 5, 6]) print(a b) # {3, 4} print(a | b) # {1, 2, 3, 4, 5, 6} print(a - b) # {1, 2}5.3 一个容易忽略的坑字典键的顺序Python 3.7 之后字典保证按插入顺序遍历。这是个很重要的特性意味着你可以用字典同时实现“快速查找”和“保序”不需要额外维护一个列表。但在 3.7 之前字典是无序的如果你的代码要兼容老版本就不能依赖这个顺序。集合则始终是无序的不要指望遍历集合能得到稳定顺序。如果业务需要顺序要么用列表要么用dict.fromkeys()来去重保序items [3, 1, 2, 3, 1] ordered_unique list(dict.fromkeys(items)) print(ordered_unique) # [3, 1, 2]这个写法比“集合列表”更简洁效果一样也是我日常最常用的去重保序写法。6. 踩过的坑与排查技巧6.1 常见问题速查表现象可能原因排查方向循环越跑越慢循环内用了列表做in判断把列表换成集合或字典去重后顺序乱了用了list(set(...))改用dict.fromkeys()报错 unhashable type把列表/字典当键或塞进集合转成元组或字符串内存暴涨大量小集合/字典评估是否能用列表替代字典查找也变慢哈希冲突严重或频繁扩容检查键的哈希分布预估容量集合遍历顺序每次不同集合本身无序需要顺序就换列表或字典6.2 三个我实际踩过的坑第一个坑在循环里反复构造集合。有次我写了个函数每次调用都把一个列表转成集合再查找。单次调用没问题但在一个百万次的循环里调用光是构造集合就花了大量时间。正确做法是把集合在循环外构造一次循环内复用。这个坑很隐蔽因为代码逻辑完全正确只是位置放错了。第二个坑用列表做“已处理”标记。就是开头我朋友那个案例。判断“是否已处理”用列表数据量一大就崩。这类“存在性判断”场景几乎百分之百应该用集合。我现在看到if x not in some_list在循环里出现就会条件反射地警觉。第三个坑以为字典一定比列表快。有次我为了“优化”把一个只用来顺序遍历的列表换成了字典结果反而慢了还多占了内存。字典的优势在查找不在遍历。选型要看主要操作是什么不能一刀切。6.3 性能优化的正确姿势不要凭感觉优化。我见过太多人一上来就把所有列表换成集合结果代码可读性下降性能还没提升多少。正确流程是先测量用time.perf_counter()或性能分析工具找到真正的瓶颈。再定位确认瓶颈是不是数据结构选型导致的。后替换只替换真正热点的部分不要全局大改。再验证替换后重新测量确认确实变快了。提示优化前先问自己“这个代码会被调用多少次”。调用一次的函数慢一点无所谓调用百万次的函数每一微秒都值得抠。把精力花在热点上才是有效优化。7. 一些进阶但实用的细节7.1 预分配容量减少扩容如果你明确知道要往字典或集合里放多少元素可以提前给个初始容量减少扩容次数。Python 里没有直接的reserve接口但可以用一些技巧比如先构造一个足够大的字典再清空或者直接用推导式一次性构造。不过说实话日常业务代码里这个优化的收益通常不明显除非你在写底层库或者对性能极度敏感的场景否则不必刻意为之。7.2 用collections里的专用容器标准库的collections模块里有几个针对特定场景优化的容器值得知道defaultdict访问不存在的键时自动给默认值省去if key not in d的判断统计计数特别方便。Counter专门用来计数底层是字典但提供了most_common()等好用方法。OrderedDict3.7 之前用来保序现在基本被普通字典取代但它的move_to_end方法在某些 LRU 场景还有用。from collections import defaultdict, Counter # 统计词频 words [a, b, a, c, a] counter Counter(words) print(counter.most_common(2)) # [(a, 3), (b, 1)] # 分组 groups defaultdict(list) for name, dept in [(A, 研发), (B, 测试), (C, 研发)]: groups[dept].append(name) print(dict(groups)) # {研发: [A, C], 测试: [B]}7.3 什么时候列表反而不可替代最后强调一下列表的不可替代性避免矫枉过正需要下标访问lst[i]是 O(1)字典和集合做不到。需要切片lst[2:5]这种操作只有列表有。需要保持顺序且频繁在尾部增删列表的append和pop()都是 O(1)。元素本身不可哈希比如列表里套列表这时候只能用列表。我个人的经验是默认用列表遇到“查找”“去重”“映射”这三个词再考虑换。这个默认策略能覆盖大部分场景也不会让你陷入过度优化的陷阱。写到这里回到开头那个朋友的案例。他后来问我“那我以后是不是所有地方都用集合”我说不是你得先想清楚这个容器主要拿来干嘛。如果只是顺序读一遍列表又快又省内存如果反复问“在不在”那集合和字典就是降维打击。工具没有好坏只有合不合适。把这句话刻进脑子里比记住任何一张复杂度表都管用。
阅读完成 · 觉得有帮助？
