python中in操作在set上平均为o(1)哈希查找，而在list上为o(n)线性扫描；百万数据下实测查询速度相差300倍以上，根本差异在于数据结构：set基于哈希表可直接定位桶并少量比对，list只能逐个比较。
in 在 list 上是线性扫描，而在 set 上是哈希查表——这是根本差异，不是“慢一点”，而是量级差距。
为什么 list 的 in 是 O(n)？
Python 执行 x in my_list 时，内部就是从头到尾调用 == 逐个比对：
- 哪怕找到第一个匹配就停，最坏情况（比如查末尾元素或不存在）仍要扫完整个列表
- 100 万元素的
list，查一次可能做 100 万次比较 - 没有索引、不跳转，纯靠遍历
为什么 set 的 in 是平均 O(1)？
set 底层是哈希表，x in my_set 的过程是：
- 先算
hash(x)，得到一个整数桶号 - 直接跳到对应桶里，只比对该桶中少数几个（通常 1–2 个）候选元素
- 只要哈希分布正常、负载因子不过高，基本一次定位 + 一次比对就出结果
实测差距有多大？
百万级数据下典型耗时（10 万次查询）：
-
999999 in large_list：约 2.5 秒 -
999999 in large_set：约 0.008 秒
快了 **300 倍以上**。这不是优化循环体能解决的，是数据结构决定的天花板。
哪些情况会让 set 的 in 变慢？
绝大多数业务场景不会踩中，但得知道边界：
- 自定义类没重写
__hash__或写得极差 → 所有实例哈希值相同 → 桶里堆成链表 → 退化为线性扫描 - 集合极小（比如只有 3 个元素）→ 哈希计算开销可能略高于直接比对，但这种规模根本不该成为瓶颈
- 频繁插入导致多次 rehash → 单次
in不受影响，但构造过程抖动明显
真正容易被忽略的是：很多人在写 if x in config_list: 这类逻辑时，压根没意识到 config_list 是静态配置、会被查几百次——这时转成 set 几乎零成本，收益却极大。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
