Python字典哈希值通过hash(key)扰动后与(table_size-1)按位与得到索引，要求表大小为2的幂；冲突时采用伪随机探测，删除打标记不释放内存，扩容阈值0.65触发翻倍重建。
Python 字典的哈希值是怎么算出来的
Python 的 dict 底层靠哈希表实现，每个键（key）必须是可哈希的（即有 hash 方法且不可变）。哈希值不是直接用 hash(key) 原样存进去的，而是做了位运算扰动：hash(key) & (table_size - 1) —— 这要求表大小始终是 2 的幂，所以实际索引是哈希值的低位截取。
- 如果自定义类作为 key，必须同时实现
hash和eq，否则可能查不到或重复插入 -
str、int、tuple（只含可哈希元素）天然支持，但list、dict、set不行，会报TypeError: unhashable type - 同一进程内，相同字符串的
hash()值稳定；但 Python 3.3+ 默认启用哈希随机化（-R或PYTHONHASHSEED），跨进程不保证一致
哈希冲突时 Python 怎么找下一个空槽
冲突发生时，CPython 用开放寻址法（open addressing），具体是 伪随机探测（perturb-based probing），不是线性探测或二次探测。
- 探测序列由初始哈希和一个不断右移的扰动值
perturb共同决定：i = (5*i) + 1 + perturb; perturb >>= 5 - 这个设计让冲突分布更均匀，避免“聚集”（clustering）
- 空槽（
NULL）、已删除槽（DELETED）、有效槽（USED）三态并存，删除操作不真正清内存，只打标记，避免查找中断
常见错误现象：
- 插入大量键后字典变慢，不一定是哈希差，更可能是负载因子超过 0.65 触发扩容（复制整个哈希表）
- 频繁增删导致大量
DELETED槽，虽不占逻辑空间，但影响探测效率，最终也会触发重建
为什么有时两个不同对象 hash() 相同却能共存于 dict
哈希值相同 ≠ 键相等。Python 查找时分两步：
立即学习“Python免费学习笔记（深入）”；
- 计算哈希值，定位大致桶位置
- 在该桶及后续探测路径中，逐个比对
key is other or key == other（先用is快判，再用==）
所以：
-
hash(1)和hash(1.0)相同，但1 == 1.0为True，它们不能同时存在：后者会覆盖前者 -
hash("a")和hash("b")可能碰巧相同（尤其小字符串），只要"a" != "b"，就能共存，只是查找要多探几次 - 自定义类若
hash返回常数（如return 42），所有实例哈希都一样，性能退化为 O(n)，但语法上完全合法
扩容机制如何影响性能和内存占用
字典在插入时检查负载因子（used / table_size），超过 0.65 就扩容（翻倍），但扩容不是简单复制：
- 新表大小是 ≥ 2×旧容量的最小 2 的幂（例如从 8 → 16，但 128 → 256）
- 所有键值对按新哈希重新散列，旧探测路径作废
- 删除操作不触发缩容，只有显式调用
dict.clear()或引用被回收才释放内存 - 使用
dict.fromkeys(keys, default)初始化大批量数据时，如果 keys 是 list，内部仍会逐个插入，无法预分配最优大小；想省时间得先估算数量，再用{k: default for k in keys}（解释器有优化）
容易被忽略的一点：哈希表的「空闲槽」其实一直存在，哪怕你删光所有项，只要没触发 gc 或重新赋值，底层数组不会缩小。观察 sys.getsizeof(d) 就能发现这点。
