哈希表的冲突解决策略：二次探测法（Quadratic Probing）

描述
二次探测法是开放定址法（Open Addressing）中解决哈希冲突的一种策略。当插入或查找元素时，若哈希函数计算出的初始位置已被占用，则通过二次函数（如 \(i^2\)）逐步探测下一个空闲位置，避免线性探测可能导致的“聚集”现象。其核心公式为：

\[h(k, i) = (h'(k) + c_1 \cdot i + c_2 \cdot i^2) \mod m \]

其中 \(h'(k)\) 是初始哈希值，\(i\) 是探测次数（从 0 开始），\(m\) 是哈希表大小，\(c_1\) 和 \(c_2\) 是常数（通常 \(c_1=0, c_2=1\) 简化形式为 \(h(k, i) = (h'(k) + i^2) \mod m\)）。

解题过程

1. 初始哈希计算

   • 对关键字 \(k\) 计算初始位置 \(pos_0 = h'(k) \mod m\)。
   • 若 \(pos_0\) 为空，直接插入或返回查找结果；否则进入探测流程。

2. 二次探测序列生成

   • 第 \(i\) 次探测的位置为 \(pos_i = (h'(k) + i^2) \mod m\)（以简化形式为例）。
   • 例如：若 \(h'(k)=5, m=10\)，则探测序列为 \(5, 6, 9, 4, 1, 0, 1, 4, 9, 6\)（注意序列可能重复）。

3. 插入操作

   • 按探测顺序检查每个位置：若遇到空闲位置，插入元素并结束。
   • 若所有位置均被占用（或表满），抛出溢出异常。
   • 示例：在大小为 7 的哈希表中插入序列 {10, 20, 30}，设 \(h'(k)=k \mod 7\)：
     • 插入 10：\(pos_0=3\)（空）→ 直接插入。
     • 插入 20：\(pos_0=6\)（空）→ 直接插入。
     • 插入 30：\(pos_0=2\)（空）→ 直接插入。
     • 插入 17：\(pos_0=3\)（已被 10 占用）→ 探测 \(pos_1=(3+1^2)\mod 7=4\)（空）→ 插入。

4. 查找操作

   • 类似插入过程，按探测顺序检查每个位置：
     • 若找到目标关键字，返回位置。
     • 若遇到空闲位置，说明关键字不存在。
     • 若遍历完所有可能位置仍未找到，确认关键字不存在。

5. 删除操作的注意事项

   • 直接删除元素会导致探测链断裂，后续查找可能失败。
   • 解决方案：使用“墓碑标记”（Tombstone）标记已删除位置，插入时可复用该位置，但查找时需跳过墓碑继续探测。

6. 性能与局限性

   • 优点：缓解线性探测的聚集问题，平均性能优于线性探测。
   • 缺点：
     • 二次聚集：不同关键字的探测序列可能重叠。
     • 表大小限制：需保证表大小 \(m\) 为质数，且负载因子低于 0.5，否则可能无法探测所有位置（即序列可能无法覆盖全部索引）。
     • 删除操作需特殊处理。

关键点总结
二次探测通过平方步长分散冲突元素，但需注意表大小设计以避免探测序列缺失。实际应用中，常与双哈希（Double Hashing）等其他策略结合，进一步优化性能。