Python dict 的哈希实现与碰撞处理
Python dict底层用带种子的多项式哈希与伪随机探测（5*i+1+pertrub）实现开放寻址，表长必为2的幂，删除置DELETED标记不缩容，自定义键须保证__hash__与__eq__一致且基于不可变字段。
Python dict 的底层哈希函数怎么算？
Python 的 dict 使用开放寻址法（open addressing），不是链地址法。每个键的哈希值由 hash() 生成，但真正存入哈希表时会做掩码处理：index = hash(key) & (table_size - 1)，所以表大小必须是 2 的幂——这是为了位运算加速，也决定了扩容时机（负载因子超 2/3 就翻倍）。
-
hash() 对不可变类型有定义：str、int、tuple（元素全不可变）等；可变类型如 list、dict 直接报 TypeError: unhashable type
- 字符串哈希不是简单累加，而是带种子的多项式滚动哈希（受
HASH_RANDOMIZATION 影响，启动时随机化，防 DOS 攻击）
- 同一进程内相同字符串哈希值稳定；但不同 Python 进程或重启后可能不同（除非设
PYTHONHASHSEED=0）
碰撞发生时 dict 怎么找下一个空槽？
碰撞不靠拉链，而是用探测序列线性试探。Python 3.7+ 使用的是“伪随机探测”（perturb-based probing）：
初始位置：i = hash(key) & mask
若冲突，计算扰动值 perturb = hash(key)，然后迭代：i = (5*i + 1 + perturb) & mask，再更新 perturb >>= 5
探测直到遇到空槽（NULL）、已删除标记（DELETED）或匹配的键
DELETED 槽位必须保留，否则后续查找可能提前终止（比如删了中间一个，后面同探测序列的键就找不到了）
探测不是纯线性（i+1, i+2...），避免聚集效应；但也不是完全随机，保证可重现
hash() 对不可变类型有定义：str、int、tuple（元素全不可变）等；可变类型如 list、dict 直接报 TypeError: unhashable type
HASH_RANDOMIZATION 影响，启动时随机化，防 DOS 攻击）PYTHONHASHSEED=0）初始位置：
i = hash(key) & mask若冲突，计算扰动值
perturb = hash(key)，然后迭代：i = (5*i + 1 + perturb) & mask，再更新perturb >>= 5探测直到遇到空槽（
NULL）、已删除标记（DELETED）或匹配的键DELETED槽位必须保留，否则后续查找可能提前终止（比如删了中间一个，后面同探测序列的键就找不到了）探测不是纯线性（
i+1, i+2...），避免聚集效应；但也不是完全随机，保证可重现
DELETED，不立即收缩表。只有当空槽（含 DELETED）占比过高、且实际键数远小于当前容量时，才会在下次插入触发 resize。
- 插入操作可能触发扩容（表满或负载过高），但删除从不触发缩容
- 手动缩容只能重建：
d = {k: v for k, v in d.items()}，或用copy.copy(d)（效果相同） - 大量增删后，
dict可能存在大量DELETED槽，导致查找变慢（探测路径变长）、内存虚高
自定义类作为 dict 键时最容易踩的坑
必须同时正确定义 __hash__ 和 __eq__，且满足：相等的对象必须有相同哈希值。
- 错误写法：
hash 返回固定值（如 return 42）→ 所有实例哈希相同，退化为 O(n) 查找
- 更隐蔽的错：
hash 基于可变属性（如 self.name），但之后改了该属性 → 哈希值变化，键再也找不到了（Python 不会重新定位）
- 正确做法：只对真正不可变的字段哈希，且一旦实例化就不能改；或者干脆不实现
hash，让实例默认不可哈希（更安全）
hash 返回固定值（如 return 42）→ 所有实例哈希相同，退化为 O(n) 查找hash 基于可变属性（如 self.name），但之后改了该属性 → 哈希值变化，键再也找不到了（Python 不会重新定位）hash，让实例默认不可哈希（更安全）哈希表的高效依赖于均匀分布和低碰撞率，而 Python 的实现把探测逻辑、删除标记、扩容策略都封装得很深——你几乎不用碰它，但一旦要 debug 性能抖动或诡异的键丢失，就得意识到这些细节还在底下跑。
