Python字典哈希冲突通过开放寻址法解决：冲突时按伪随机探测序列查找空槽或匹配项，负载因子超2/3触发翻倍扩容，删除打DELETED标记避免探测链断裂。
哈希冲突会让字典从“一步到位”变成“逐个比对”
字典查一个键，理想情况是：算出哈希值 → 对表长取模 → 直接跳到对应槽位 → 拿到值。这确实是 O(1)。但一旦发生哈希冲突（比如 hash("a") % 8 == hash("b") % 8），目标槽位已被占，Python 就得按探测序列（如二次探测）挨个往后试——每试一个位置，都要先比哈希值，再比键本身。探测次数越多，单次查找就越接近线性扫描。
冲突多时，平均探测长度显著上升
CPython 字典的性能拐点很明确：当负载因子（used_slots / total_slots）超过 2/3，冲突概率陡增，平均探测长度快速攀升。实测中，负载因子从 0.6 升到 0.9，查找耗时可能翻倍甚至更高。这不是理论推导，而是真实 profiling 可见的现象——尤其在用大量字符串作键、且字符串前缀高度相似时（如 "user_0001", "user_0002"…），哈希分布容易局部聚集。
动态扩容虽能缓解，但代价是插入卡顿
字典不会坐视冲突恶化：当负载因子触达阈值，它会触发扩容（通常是翻倍），然后把所有已有键值对重新哈希、搬进新表。这个过程是 O(n) 的，且会阻塞当前线程。你可能在批量插入时突然遇到一次几百毫秒的延迟，日志里却只看到一条 dict[key] = value ——问题就出在这里。
- 扩容不是均匀发生的：它总在第 N+1 次插入时“啪”一下触发
- 扩容后旧内存不会立刻释放，GC 压力可能短暂升高
- 若频繁增删，字典可能在扩缩容之间震荡，反而更伤性能
自定义类作键时，__hash__ 实现不当会雪上加霜
如果你把自定义对象当字典键，而它的 __hash__ 方法返回常量（如 return 42），那所有实例都会映射到同一个槽位——字典退化成链表，查找变成 O(n)。更隐蔽的问题是：若 __eq__ 和 __hash__ 不一致（比如两个逻辑相等的对象哈希值不同），字典行为将不可预测，甚至漏查键。
真正关键的不是“有没有冲突”，而是“冲突是否可控”。哈希表的设计目标从来不是消灭冲突，而是让探测路径足够短、扩容足够稀疏、哈希分布足够散——这些细节，全藏在你每次调用 hash() 和构造 dict 的瞬间里。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
