17370845950

Python字典用哈希表而非红黑树，因核心诉求是O(1)平均查找；采用开放寻址法处理冲突，扩容触发于负载因子超2/3，插入有序且查找分三步：算hash、位运算得索引、探测匹配。

Python字典为什么用哈希表而不是红黑树

因为字典核心诉求是 O(1) 平均查找，而红黑树是 O(log n)。哈希表在键类型支持 __hash__ 且分布合理时，能稳定维持常数级操作；Python 的 dict 还做了大量优化（如开放寻址、紧凑存储），实际性能远超理论值。

注意：不可哈希类型（如 list、dict）不能当键，会直接报 TypeError: unhashable type，不是运行时才检查，而是插入前就校验。

哈希冲突怎么处理：开放寻址 + 伪随机探测

Python 不用链地址法，而是用开放寻址（open addressing）。每个桶只存一个键值对，冲突时按固定规则找下一个空位。探测序列不是线性（+1, +2…），而是基于原哈希值生成伪随机步长：index = (5 * index + 1) + perturb，其中 perturb 右移 5 位再参与下一轮计算——这能显著缓解“聚集效应”。

• 插入时若桶非空，先比对键的哈希值，不等则跳；相等再调用 == 比较键本身
• 删除元素不真正清空桶，而是打上 DELETED 标记，避免后续查找断裂
• 标记太多会触发 rehash，此时所有 DELETED 桶被回收，空间重排

字典扩容时机与负载因子的实际表现

Python 3.6+ 的字典是“插入有序”，但扩容逻辑没变：当已用槽数（含 DELETED）超过总槽数的 2/3 时触发扩容。注意，这个 2/3 是硬编码在 CPython 源码里的，不是可配置参数。

扩容不是简单翻倍，而是按预设大小序列增长：8 → 16 → 32 → 64 → 128 → ...，每次分配新数组后，把所有有效项重新 hash 插入。

• 频繁增删小字典（比如反复 pop 再 insert）可能因 DELETED 积累导致隐式扩容，实测内存占用可能突增 2–3 倍
• dict.clear() 会重置为初始大小（8 个槽），不是保留原容量
• 如果提前知道元素数量，用 {k:v for k,v in iterable} 比循环 dict[k]=v 更省内存（CPython 会预估大小）

从源码角度看 key 查找的三步关键判断

调用 dict[key] 时，CPython 实际执行的是 dict_getitem 函数，核心路径只有三步比对：

1. 计算 key 的 hash 值（调用 key.__hash__()）
2. 用 hash & (mask) 得到初始索引（mask = table_size - 1，所以 table_size 必须是 2 的幂）
3. 在该索引及后续探测位置中：
   - 跳过空槽和 DELETED 槽
   - 遇到 hash 匹配的槽 → 再用 == 比较 key 对象本身
   - hash 不匹配或 key 不等 → 继续探测

这意味着：两个不同对象只要 __hash__ 返回相同值且 __eq__ 返回 True，就被视为同一键——这是用户可控的行为，也是自定义类作字典键时最容易出错的地方。

真正难调试的问题往往藏在这里：比如你重写了 __eq__ 却忘了同步更新 __hash__，或者 hash 值依赖了可变字段。