字典查找最坏情况为O(n)，因哈希冲突导致开放寻址探测链过长，当大量键映射到同一区域或装填因子过高时，需顺序比对多个候选键。
字典查找为什么不是永远 O(1)
Python 字典平均查找是 O(1)，但最坏情况会退化到 O(n)——不是理论漏洞，而是哈希冲突 + 冲突解决机制共同导致的。
哈希表本质是数组，键通过哈希函数映射成索引。理想情况下每个键映射到唯一位置；但现实中不同键可能算出相同哈希值（哈希冲突），Python 用开放寻址法（open addressing） 解决：当位置被占，就线性探测下一个空槽。
一旦大量键哈希到同一区域（比如恶意构造的 key、或哈希函数在特定输入下失效），探测链就会变长。极端时，整个字典变成“伪链表”，每次 in 或 d[key] 都得顺序比对多个候选键（还要逐字符比对字符串 key 是否真匹配），退化为 O(n)。
常见触发场景包括：
立即学习“Python免费学习笔记（深入）”；
- 使用自定义类作 key 但没重写
__hash__和__eq__，导致哈希值全为 0 - 读取用户输入或外部数据后直接用作 dict key，而这些字符串恰好有强哈希碰撞倾向（如某些版本 Python 对短字符串的哈希算法较弱）
- 字典长期不扩容、装填因子（load factor）接近 1.0，空槽稀少，探测距离被迫拉长
怎么判断你遇到了最坏情况
不能只看运行时间变慢——得确认是哈希冲突导致的退化，而不是其他瓶颈。
最直接的方法是检查字典的装填因子和冲突统计：
用 sys.getsizeof(d) 粗略看内存占用趋势（持续增长但 key 数不变？可能是内部哈希表未及时扩容）
更准的是用 dict.__sizeof__() + 查看 CPython 源码级调试信息（不推荐日常用），但实用办法是：在怀疑场景下，手动测 timeit 同一 key 的多次查找，再对比随机 key 的耗时。如果某几个 key 明显慢一个数量级，且它们的 hash(key) % dict_size 结果高度集中，基本就是冲突热点。
如何避免退化到 O(n)
Python 自身会动态扩容字典（当装填因子 > 2/3 时），所以多数情况无需干预。但你可以主动规避风险点：
不要把不可控的字符串（比如原始日志行、URL 参数）直接当 key 用，先做简单清洗或加盐哈希（如 hashlib.md5(s.encode()).hexdigest()[:8]）
若 key 是自定义对象，必须同时实现 __hash__（返回 int）和 __eq__，且保证相等对象哈希值一致
对高频查询的 dict，初始化时预估大小，用 dict.fromkeys(keys, default) 或直接 {k: v for ...} 构造，比逐个 d[k] = v 插入更利于初始哈希表布局
避免反复 del d[k] 后又插入新 key——这会留下“伪删除标记”，影响后续插入位置选择，间接抬高冲突概率
set 和 dict 在退化行为上一样吗
完全一样。因为 set 底层复用字典的哈希表实现（只是 value 固定为 dummy 占位符）。所以 x in s 和 k in d 面临相同的哈希冲突路径与最坏复杂度。
真正区别在于：set 不支持键值对操作，少了 key 比对环节（不需要调用 <strong>eq</strong> 做完整匹配），所以在冲突已发生时，实际耗时略低一点——但复杂度阶数仍是 O(n)。
最易被忽略的一点：退化不是“偶尔慢”，而是局部慢——某个 key 查得慢，不代表所有 key 都慢；你可能只在处理某类数据时才踩中这个坑，测试时却用均匀随机数据没暴露出来。
