Python 的 dict 使用开放寻址法（open addressing）解决哈希冲突，不是链地址法（chaining）。这意味着所有键值对都存放在一个连续的数组中，冲突时通过探测序列寻找下一个空槽，而不是拉链式挂新节点。
核心机制：开放寻址 + 伪随机探测
当两个键的哈希值对底层数组长度取模后落在同一位置（即发生冲突），Python 不会新建链表，而是按固定规则“试探”其他位置，直到找到空槽或匹配的键：
- 初始索引：
index = hash(key) & (mask)，其中mask = table_size - 1（数组长度必为 2 的幂） - 冲突时，使用二次探测变种：
index = (index + perturb + 1) & mask，其中perturb = perturb >> 5（不断右移扰动哈希高位） - 该扰动机制避免线性探测的聚集问题，提升分布均匀性
删除操作的特殊处理：使用 dummy 占位符
直接删掉一个槽会导致后续探测链断裂（因为查找依赖连续探测）。Python 用 dummy（内部标记为 DKIX_DUMMY）占位：
- 插入时，dummy 槽和空槽一样可被复用
- 查找时，遇到 dummy 会继续探测，不终止搜索
- 这保证了“已删键”的存在不影响其余键的查找正确性
扩容触发条件与影响
当装载因子（已用槽 / 总槽数）超过 2/3 时，字典自动扩容（通常翻倍），并重新哈希所有键值对：
立即学习“Python免费学习笔记（深入）”；
- 扩容重哈希彻底消除旧冲突，但带来 O(n) 时间开销
- 这也是为什么在循环中往 dict 添加大量键可能有性能抖动
- 可通过预设较大初始大小（如
dict.fromkeys(keys)或先初始化再填）缓解
实际开发中你不需要手动干预
这套机制完全由 CPython 内部实现（Objects/dictobject.c），对用户透明：
- 你无法控制探测顺序或占位策略
- 也不需要自己处理冲突——只要键实现了合理的
__hash__和__eq__ - 若自定义类作键，务必确保相等对象哈希值相同，否则查找失败
