x in set 是 O(1) 因哈希表直接定位，x in list 是 O(n) 因需逐个比较；百万数据下查询快5500倍；构造开销不影响查找优势，误用不可哈希对象或频繁类型转换会抵消性能收益。
为什么 x in set 是 O(1)，而 x in list 是 O(n)
因为底层数据结构完全不同：set 用哈希表，list 用动态数组。执行 x in set 时，Python 先算 hash(x)，直接跳到对应桶里比对；x in list 则必须从头开始调用 == 逐个比较，最坏情况扫完整个列表。
这不是“写法优化”能解决的——哪怕只查一次，list 就得遍历，set 就是一次定位+一次比对。常见类型如 int、str、tuple 天然可哈希，几乎总能稳住 O(1)。
百万数据下实测差距有多夸张
在含 100 万个整数的容器中查 1000 次随机值：
-
list耗时约 11.8 秒 -
set耗时约 0.002 秒
快 5500 倍，不是“快一点”，是数量级断层。换成一千万数据，list 耗时涨到约 0.12 秒，set 仍稳定在 1.1e-6 秒量级。如果目标值总在列表末尾，list 实际耗时线性增长；set 几乎不受影响。
立即学习“Python免费学习笔记（深入）”；
哪些写法会直接抵消 set 的性能优势
很多人测出 set(range(10000)) 构造比 list(range(10000)) 慢，就怀疑 set 不快——这是误解。构造是一次性成本，in 才是高频操作。只要查 3 次以上，set 总耗时就反超。
- 反复在循环里写
if x in some_list→ 应提前some_set = set(some_list)复用 - 在循环中反复
set(big_list)→ 类型转换开销吃掉所有收益 - 误以为
set支持索引 →s[0]直接报TypeError: 'set' object is not subscriptable - 往
set里塞不可哈希对象（如[1, 2]、{'a': 1}）→ 直接抛TypeError，不是慢，是语法失败
什么情况下 set 的 in 会变慢
哈希表不是银弹，但日常几乎不会踩中：
- 大量哈希冲突：比如自定义类没重写
__hash__，所有实例哈希值相同 → 退化成链表遍历 - 集合极小（3–5 个元素）：哈希计算开销可能反超线性扫描，但这种规模本就不该成为瓶颈
- 频繁扩缩容：往空
set里塞几百万元素时，中间多次rehash会带来抖动（单次in仍不受影响）
真正容易被忽略的是：很多人把 list 当通用容器硬扛查找逻辑，直到线上超时才意识到——in 操作的底层机制，决定了它根本不适合高频存在性判断。选对结构，比优化循环体重要得多。
