python字典哈希冲突严重时退化为o(n)，主因是自定义类哈希函数不当、人为构造碰撞字符串、禁用扩容致负载因子过高、或使用哈希质量差的键类型；有序性不缓解冲突。
Python 字典在哈希冲突严重时会退化，最坏情况下查找、插入、删除操作的时间复杂度从平均 O(1) 降为 O(n)。
哈希冲突集中发生时
当大量键经过 hash() 计算后映射到同一个哈希桶（bucket），字典会在线性探测过程中逐个检查后续位置。若连续多个桶都被占用，每次操作都需遍历一长串位置。
- 典型诱因：自定义类未正确定义
__hash__和__eq__，导致不同对象返回相同哈希值 - 人为构造场景：用大量字符串如
"a","aa","aaa"等，某些 Python 版本下可能产生碰撞 - 不推荐用可变对象（如 list）作键——虽会报错，但若绕过检查强行插入，极易引发不可预测冲突
负载因子过高且未及时扩容
字典内部维护一个“负载因子”（元素数 ÷ 桶总数），CPython 默认阈值约 0.66。一旦超过，就会触发扩容（通常翻倍）并重哈希所有键值对。如果被禁用扩容或手动控制内存（如嵌入式环境），桶空间长期不足，冲突概率陡增。
- 扩容本身是 O(n) 操作，频繁触发会影响吞吐稳定性
- 小字典（如仅几个键）一般不受影响；退化多见于含数千以上键、且哈希分布极不均匀的场景
键类型本身哈希质量差
内置类型（str、int、tuple）哈希函数经过充分优化，冲突率低。但若使用自定义类型，且 __hash__ 返回常量（如 return 42），所有实例都会挤进同一个桶。
- 例如：
class BadKey: __hash__ = lambda self: 1，插入 1000 个实例后，查找任一键平均要比较 500 次 - 即使哈希值分散，若
__eq__判等开销大（如比对大字符串或调用网络请求），也会拖慢“冲突链”上的实际判断速度
Python 3.6+ 的有序性不影响退化逻辑
插入顺序保留是通过紧凑数组实现的优化，并未改变哈希表本质。有序性带来缓存友好性提升，但不能缓解哈希冲突本身。退化与否，只取决于哈希分布与桶空间是否匹配。
- 有序 ≠ 更少冲突，也不代表更省内存；它只是让迭代行为可预测
- 内存布局改进（如去掉空洞）降低了整体开销，但没改变最坏时间复杂度边界
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
