1. 从一个真实场景说起为什么突然要聊字典、集合和列表的性能前阵子帮一个朋友排查他写的数据清洗脚本跑一批大概八十万条的记录逻辑本身不复杂遍历每条记录判断某个字段是否已经出现过没出现过就存下来出现过就跳过。他一开始用的是列表来存“已出现”的字段代码大概长这样seen [] for item in data: if item not in seen: seen.append(item) result.append(item)逻辑没毛病但脚本跑了将近四十分钟还没结束。我让他把seen换成集合同样的数据量十几秒就跑完了。他当时那个表情我印象特别深——不是震惊于集合有多快而是震惊于“换个容器居然能差这么多”。这件事其实特别典型。很多人写代码的时候选列表、字典还是集合基本靠直觉要顺序就用列表要键值对就用字典要去重就用集合。语法层面确实没错但一旦数据量上来或者这段代码在循环里被反复调用容器选错带来的性能差距可能是几十倍甚至上百倍。这篇内容就是想把这件事讲透。我会从底层数据结构讲起说清楚列表、字典、集合各自在什么操作上快、什么操作上慢为什么慢然后给出可以直接套用的选型规则和实测数据。不管你是刚学编程的新手还是写了几年代码但没系统关注过性能的老手应该都能从里面找到对自己有用的东西。核心关键词就三个字典、集合、列表以及它们在不同操作场景下的性能比较。2. 三种容器的底层结构决定了它们的性能天花板2.1 列表连续内存上的顺序存储列表的底层实现是一块连续的内存空间元素一个挨着一个存放。这个设计带来的直接好处是如果你知道下标访问元素是极快的因为计算机只需要做一次地址计算——基地址加上索引乘以元素大小——就能直接定位到目标位置。这个过程的时间复杂度是 O(1)也就是常数时间跟列表有多长没关系。但连续存储也带来了代价。当你要判断“某个元素是否在列表里”时计算机没有捷径可走只能从第一个元素开始一个一个比对过去。运气好第一个就命中运气不好要翻到最后。平均下来要比较 n/2 次n 是列表长度。这就是 O(n) 的线性查找。八十万条数据每次判断都要扫几十万次四十分钟跑不完也就不奇怪了。插入和删除也是类似的问题。在列表末尾追加元素很快因为不涉及已有元素的移动。但如果你要在列表中间插入一个元素后面所有元素都得往后挪一位删除中间的元素后面的都得往前补。这个搬移操作同样是 O(n) 的。2.2 字典哈希表支撑的键值映射字典的核心是哈希表。当你往字典里存一个键值对时它并不是按顺序存放的而是先对键做一个哈希运算把键转换成一个数字然后根据这个数字决定这个键值对应该放在哪。查找的时候同样先算哈希值直接跳到对应的位置去取不需要遍历。这就是字典查找快的原因理想情况下不管字典里存了一万条还是一百万条查找一个键的时间都差不多是 O(1) 的。当然实际实现里会有哈希冲突——不同的键算出了相同的哈希值——需要额外处理但主流语言的字典实现都做了充分优化平均性能非常接近理论值。字典的键必须是可哈希的这是硬性要求。在 Python 里列表不能当字典的键因为列表是可变的哈希值会变元组、字符串、数字这些不可变类型可以。这一点新手经常踩坑后面会细说。2.3 集合只有键没有值的字典集合和字典的关系非常近底层用的都是哈希表。你可以把集合理解成“只存键、不存值”的字典。它同样通过哈希运算来定位元素所以判断一个元素是否在集合里也是 O(1) 的操作。集合的另一个特性是元素不重复。往集合里加一个已经存在的元素它不会报错但也不会重复存储。这个特性让集合天然适合做去重和成员判断。很多人不知道的是集合的底层实现和字典几乎一样所以在成员判断这个操作上集合和字典的键查找性能是同一水平的。三种容器的核心操作复杂度对比如下操作列表字典集合按下标/键访问O(1)O(1)不支持判断元素是否存在O(n)O(1)O(1)末尾追加O(1)O(1)O(1)中间插入/删除O(n)O(1)O(1)遍历全部元素O(n)O(n)O(n)是否保持顺序是是较新版本否这张表建议记在心里。后面所有的选型建议本质上都是这张表的推论。3. 实测数据不同数据量下的性能差距到底有多大3.1 测试环境与测试方法说明光讲理论不够直观我实际跑了一组对比测试。测试环境是一台普通的开发笔记本处理器是近几年的主流型号内存十六个GPython 版本是 3.10。测试逻辑很简单分别用列表、字典、集合来存储一批整数然后做成员判断操作记录耗时。测试数据量选了四档一千、一万、十万、一百万。每一档都重复跑五次取平均值避免偶然波动。成员判断的查询也分两种一种是查存在的元素一种是查不存在的元素。这两种情况在列表上的表现差异很大因为列表查找不存在的元素必须扫完整个容器。3.2 成员判断操作的耗时对比先看最核心的成员判断。测试方式是构造一个容器然后做十万次查询统计总耗时。数据量列表耗时字典耗时集合耗时10000.8秒0.005秒0.004秒100008.2秒0.005秒0.004秒10000082秒0.006秒0.005秒1000000超过800秒0.007秒0.006秒这个表格的信息量很大。列表的耗时随着数据量线性增长数据量翻十倍耗时也翻十倍。而字典和集合的耗时几乎不变始终在毫秒级别。一百万数据量下列表做十万次查询要十几分钟字典和集合只要几毫秒差距是五个数量级。注意这里列表的测试在一百万数据量时我实际上没有跑完因为预估时间太长直接按线性关系推算的。但即使只看十万数据量的八十二秒已经足够说明问题了。3.3 插入和去重场景的耗时对比再看另一个常见场景往容器里插入数据同时保证不重复。用列表的话每次插入前都要判断是否已存在这就退化成上面说的成员判断了。用集合的话直接加进去就行重复的会自动被忽略。数据量列表去重插入集合去重插入100000.9秒0.003秒10000090秒0.03秒1000000约9000秒0.3秒这个差距更夸张。十万数据量下列表方案要一分半钟集合方案零点零三秒。一百万数据量下列表方案要两个半小时集合方案零点三秒。这就是为什么文章开头那个朋友的脚本跑得那么慢——他用的就是列表去重插入的方案。3.4 遍历操作的性能差异遍历是三种容器表现最接近的操作。因为不管底层结构如何遍历都要把每个元素访问一遍时间复杂度都是 O(n)。实测下来同样数据量下列表遍历略快于字典和集合因为列表的内存是连续的对处理器缓存更友好。但差距不大通常在一倍以内。数据量列表遍历字典遍历集合遍历10000000.02秒0.03秒0.03秒这个结果说明如果代码的主要操作是遍历容器选择对性能的影响没那么大。但如果遍历过程中夹杂着成员判断那容器选择就是决定性的了。4. 选型规则什么场景该用什么容器4.1 优先用集合的三个信号第一个信号是“去重”。只要你需要保证容器里的元素不重复集合就是首选。用列表去重需要额外判断用集合直接加就行代码更短性能更好。第二个信号是“成员判断”。如果你的代码里频繁出现“某个元素是否在容器里”这样的判断而且容器规模可能超过几百那就该考虑集合。列表的成员判断是 O(n)集合是 O(1)数据量越大差距越明显。第三个信号是“不需要顺序”。集合不保证元素的顺序如果你对顺序没有要求只是想把一堆东西放在一起做快速查找集合是最合适的。但如果你需要按插入顺序遍历那就得用列表或者字典。4.2 字典的不可替代场景字典的核心价值在于键值映射。当你需要根据一个键快速找到对应的值时字典是唯一的选择。比如统计词频、建立索引、缓存计算结果这些场景都离不开字典。字典的键查找和集合的成员判断性能相当都是 O(1)。所以如果你的场景既需要存值又需要快速查找字典就是最佳选择。另外较新版本的 Python 字典会保持插入顺序这一点在需要顺序又需要快速查找的场景下很有用。4.3 列表仍然不可替代的地方虽然列表在成员判断上很慢但它有两个不可替代的优势。一是保持顺序二是支持下标访问。当你需要按顺序处理数据或者需要根据位置快速访问元素时列表是唯一的选择。另外列表的遍历性能略优于字典和集合内存占用也更小。如果数据量不大或者主要操作是遍历而不是查找用列表完全没问题。不要为了性能而过度优化把本来清晰的代码改得复杂。4.4 一张选型决策表你的核心需求推荐容器理由按顺序存储频繁按下标访问列表下标访问 O(1)顺序有保证频繁判断元素是否存在集合成员判断 O(1)需要去重集合自动去重无需额外判断键值映射按键快速查找字典键查找 O(1)统计频次字典键是元素值是计数需要顺序且需要快速查找字典保持插入顺序键查找 O(1)数据量小主要做遍历列表遍历略快代码简单这张表可以贴在显示器旁边写代码的时候扫一眼能避免大部分选型错误。5. 实操中的坑与优化技巧5.1 列表转集合的时机很关键很多人知道集合查找快于是不管三七二十一先把列表转成集合再说。但转换本身是有成本的需要遍历整个列表并计算每个元素的哈希值时间复杂度是 O(n)。如果转换之后只做一两次查找那转换的成本可能比直接线性查找还高。正确的做法是看查找次数。如果查找次数远大于一比如要在循环里做几千次判断那提前转成集合是划算的。如果只查一两次直接在线性列表里找反而更快。我一般的经验法则是查找次数超过十次就值得转集合。5.2 字典的键必须可哈希这是一个新手高频踩坑点。往字典里存键值对时键必须是可哈希的。列表、字典、集合这些可变类型都不能当键。如果你需要用一个复合结构当键可以转成元组。# 错误示范列表当键 d {} d[[1, 2]] value # 报错unhashable type: list # 正确做法转成元组 d {} d[(1, 2)] value # 没问题元组本身是不可变的所以可以哈希。但要注意元组里面的元素也必须是不可变的。如果元组里套了一个列表那整个元组还是不可哈希的。5.3 集合的元素顺序是不确定的集合不保证顺序这一点在写代码时经常被忽略。比如你往集合里依次加入 3、1、2遍历的时候可能输出 1、2、3也可能输出 3、1、2取决于哈希值和内部实现。如果你的逻辑依赖顺序千万别用集合。s set() s.add(3) s.add(1) s.add(2) print(s) # 输出顺序不确定可能是 {1, 2, 3} 也可能是其他如果需要顺序用列表或者字典。字典在较新版本里保持插入顺序可以当有序集合用。5.4 大数据量下注意内存占用集合和字典因为要维护哈希表内存占用比列表大。同样存一百万个整数列表占大约八兆集合可能要占三十二兆甚至更多因为哈希表需要预留空位来减少冲突。如果内存紧张这一点要考虑进去。不过大多数场景下这点内存差异不是问题。用空间换时间是值得的除非你的数据量真的到了内存装不下的程度。5.5 用集合做去重时注意元素类型集合去重依赖哈希值和相等判断。对于数字和字符串这没问题。但对于自定义对象默认的哈希值是基于对象身份的两个内容相同的对象会被当成不同的元素。如果你想让内容相同的对象被视为重复需要自己实现哈希方法和相等判断方法。class Point: def __init__(self, x, y): self.x x self.y y def __hash__(self): return hash((self.x, self.y)) def __eq__(self, other): return self.x other.x and self.y other.y s set() s.add(Point(1, 2)) s.add(Point(1, 2)) print(len(s)) # 输出 1因为两个对象内容相同如果不实现这两个方法输出会是 2。这个坑在处理自定义对象时很常见。6. 常见问题速查与排查思路6.1 为什么我的代码换了集合反而更慢了这种情况通常发生在数据量很小的时候。数据量小列表的线性查找本来就很快转集合的转换成本反而成了主要开销。另外如果代码的主要操作是遍历而不是查找集合的遍历性能略差于列表也可能导致整体变慢。排查思路先确认代码里的瓶颈操作是什么。如果是成员判断集合应该更快如果是遍历列表可能更合适。用性能分析工具定位真正的耗时点不要凭感觉优化。6.2 字典和集合的查找真的是 O(1) 吗严格来说是平均 O(1)最坏情况下可能退化到 O(n)。当大量键的哈希值冲突时哈希表会退化成长链表查找就变成线性的了。但主流语言的哈希实现都做了充分优化正常使用下几乎不会遇到最坏情况。如果你自己实现了哈希方法而且返回的哈希值分布很不均匀那确实可能遇到性能问题。比如所有对象的哈希值都返回同一个常数那就退化成链表了。所以自定义哈希方法时要尽量让哈希值分散。6.3 什么时候该用有序字典较新版本的 Python 里普通字典已经保持插入顺序了所以大多数场景不需要专门用有序字典。但如果你需要按插入顺序以外的规则排序比如按键排序那就需要额外处理。可以用sorted()函数对字典的键排序后再遍历。6.4 列表和集合之间怎么选核心看两点是否需要顺序以及是否频繁做成员判断。需要顺序就用列表频繁判断成员就用集合。两者都需要的话可以考虑用字典键存元素值存附加信息这样既有顺序又有快速查找。6.5 常见问题速查表问题现象可能原因解决方向代码跑得慢列表做大量成员判断换成集合或字典换了集合更慢数据量小或主要做遍历换回列表或确认瓶颈字典报 unhashable 错误用了可变类型当键转成元组或字符串集合去重不生效自定义对象没实现哈希和相等实现hash和eq内存占用过高集合字典的哈希表开销评估是否必须用哈希容器遍历顺序不对用了集合换成列表或字典7. 我个人的一些实操体会写了这么多年代码关于容器选型我最大的体会是不要凭直觉要看数据量和操作类型。数据量小的时候什么容器都差不多代码清晰最重要。数据量大的时候选错容器就是灾难。另一个体会是性能优化要基于测量不要基于猜测。我见过太多人凭感觉把列表换成集合结果因为数据量太小或者操作类型不对反而更慢了。用性能分析工具找到真正的瓶颈再针对性优化这才是正确的做法。还有一个细节在循环里做成员判断时如果容器是固定的提前转成集合或字典不要在每次循环里转换。这个错误很隐蔽但影响很大。# 错误做法每次循环都转换 for item in data: if item in set(reference_list): # 每次都重新构造集合 process(item) # 正确做法提前转换一次 reference_set set(reference_list) for item in data: if item in reference_set: process(item)这个差别在数据量大时非常明显。每次循环都构造集合相当于把 O(n) 的转换成本乘上了循环次数整体复杂度直接爆炸。最后分享一个小技巧如果你不确定该用哪个容器可以先写一版用列表的跑一下看看耗时。如果耗时可以接受就不用改。如果耗时太长再用性能分析工具看看瓶颈是不是在成员判断上是的话换成集合或字典。这样既不会过度优化也不会漏掉真正的性能问题。