17370845950

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 如何应对？

Python 会监控已使用槽位（含伪空位）占总槽数的比例。当负载因子 ≥ 2/3 时，触发重哈希（rehash）：

• 分配一个更大的哈希表（通常是原大小的 2 倍或更多，且保持 2 的幂）
• 将所有有效键值对重新 hash 并插入新表
• 伪空位被丢弃，表结构被“压缩”，提升空间利用率和查询效率

和链地址法相比，开放寻址有什么特点？

Python 的选择兼顾了局部性与实现简洁性：

• ✅ 缓存友好：数据连续存储，CPU 预取效率高
• ✅ 无指针开销：不需要额外的链表节点内存
• ⚠️ 删除复杂：必须引入伪空位机制
• ⚠️ 扩容代价高：重哈希需复制全部活跃项