二次探测法通过平方步长（1²、2²、3²…）打破线性堆积，使冲突键探测路径跳跃分散，缓解主聚集；需注意负数取模修正、i上限为size−1、删除用DELETED标记；推荐表长取质数并控制负载因子＜0.7。
二次探测法不是“换种方式找空位”，而是用平方步长打破线性堆积惯性，让冲突键的探测路径快速散开，从而缓解变量聚集、提升检索稳定性。
为什么二次探测能减少聚集
线性探测每次只+1，一旦某段位置被占满，新插入的键会不断往同一方向“排队”，形成主聚集；而二次探测按 1²、2²、3²… 跳跃，偏移量增长快（1→4→9→16），天然避开连续拥堵区。比如原始哈希值都是5，在大小为11的表中：
- 线性探测：依次试5→6→7→8→9→10→0→1…容易卡在局部
- 二次探测：依次试5→(5+1)%11=6→(5+4)%11=9→(5+9)%11=3→(5+16)%11=10…位置分布更跳跃、更分散
关键实现细节与避坑点
实际编码中，仅写 (hash + i*i) % size 不够稳健，必须注意三处细节：
- 负数取模：C/Java中 -1 % 11 = -1，需转为正索引，推荐写法：(hash + i*i + size) % size
- 探测上限：i 最大取到 size−1，否则可能死循环或越界；若 i 达上限仍未找到空位，说明表已满
- 删除标记：不能直接清空槽位（否则后续查找会中断），需设 DELETED 状态，允许插入但不阻断查找链
让探测更可靠：两个实用优化方向
标准二次探测仍可能产生次级聚集（不同键走相同探测序列）。可结合以下策略增强鲁棒性：
- 表长选质数：如 11、17、31，能显著提升 (hash + i²) % size 的覆盖均匀性，避免周期性重复
- 负载因子触发扩容：当元素数 / 表长 > 0.7 时强制 rehash，新表大小建议取下一个质数（如原为11，扩至17），而非简单翻倍
和线性探测比，什么时候该选它
不是所有场景都适合二次探测。适用条件很明确：
- 数据量中等（几万到百万级）、内存敏感（如嵌入式或高频缓存）
- 读多写少，且对最坏查找延迟有一定容忍（二次探测平均查找长度略高于线性，但方差更小）
- 无法接受链地址法的指针开销或缓存不友好问题
如果插入频繁且负载常超0.75，建议直接上双重哈希；若追求极致简单且数据量小，线性探测反而更稳。
