python字典和集合用开放寻址法处理哈希冲突，采用伪随机探测：先计算初始索引，冲突时按j=(5*j)+1+perturn迭代探测，perturn右移更新以避免聚集；删除键后设为伪空位（deleted）以保证查找连续性；负载因子≥2/3时触发重哈希扩容。
Python 的字典（dict）和集合（set）底层使用开放寻址法（Open Addressing）处理哈希冲突，具体是其中的“伪随机探测”（pseudo-random probing），而不是链地址法（chaining）。
哈希冲突发生时，Python 怎么找下一个空位？
当两个键计算出相同的哈希值（模数组长度后下标相同），Python 不会把它们链在一起，而是按固定规则尝试其他索引位置：
- 初始位置由
hash(key) & (mask)算出（mask = table_size - 1，要求表长是 2 的幂） - 若该位置已被占用（且不是被删除的“伪空位”），就用探测序列跳转：
j = (5*j) + 1 + perturb，再对 mask 取模
其中perturb初始为哈希值右移 5 位，每次迭代右移再更新，用于打散探测路径，避免聚集 - 不断尝试直到找到空槽，或遇到一个从未被使用过的槽位（说明键不存在）
“伪空位”（dummy slot）是什么？为什么需要它？
Python 字典允许动态增删，删除一个键后，对应位置不能简单置为空（否则后续查找可能因中断探测链而失败）。所以它会标记为 DELETED（内部常量），即“伪空位”：
Python之模块学习 中文WORD版
下载
本文档主要讲述的是Python之模块学习；python是由一系列的模块组成的，每个模块就是一个py为后缀的文件，同时模块也是一个命名空间，从而避免了变量名称冲突的问题。模块我们就可以理解为lib库，如果需要使用某个模块中的函数或对象，则要导入这个模块才可以使用，除了系统默认的模块（内置函数）不需要导入外。希望本文档会给有需要的朋友带来帮助；感兴趣的朋友可以过来看看
- 插入时，伪空位可被复用
- 查找时，遇到伪空位需继续探测，不能停
- 这保证了开放寻址下删除操作的正确性
负载因子过高时，Python 如何应对？
Python 会监控已使用槽位（含伪空位）占总槽数的比例。当负载因子 ≥ 2/3 时，触发重哈希（rehash）：
立即学习“Python免费学习笔记（深入）”；
- 分配一个更大的哈希表（通常是原大小的 2 倍或更多，且保持 2 的幂）
- 将所有有效键值对重新 hash 并插入新表
- 伪空位被丢弃，表结构被“压缩”，提升空间利用率和查询效率
和链地址法相比，开放寻址有什么特点？
Python 的选择兼顾了局部性与实现简洁性：
- ✅ 缓存友好：数据连续存储，CPU 预取效率高
- ✅ 无指针开销：不需要额外的链表节点内存
- ⚠️ 删除复杂：必须引入伪空位机制
- ⚠️ 扩容代价高：重哈希需复制全部活跃项
