二次探测无法根除次级聚集，仅缓解主聚集；当hash(key1)==hash(key2)时，二者探测序列完全相同，形成与初始哈希值相关的局部密集区。
二次探测本身不能消除次级聚集（Secondary Clustering），它只是缓解主聚集；所谓“二次聚集优化”，其实是通过调整表长、探测公式或插入策略来降低其发生概率，不是靠改探测逻辑就能根治的问题。
为什么二次探测会引发次级聚集
当两个不同键 key1 和 key2 的初始哈希值相同（即 hash(key1) == hash(key2)），它们的整个探测序列就完全一致：(h + 1²) % m、(h + 2²) % m、(h + 3²) % m……这意味着它们会“排队”争抢同一组空位，形成新的局部密集区——这就是次级聚集。
它不像主聚集那样由线性步长导致连续占位，但同样拖慢查找和插入，尤其在负载因子 >0.5 后明显恶化。
- 次级聚集只与初始哈希值有关，跟键本身无关
- 只要表长
m不是质数，i² % m的周期会缩短，探测位置重复更快 - 标准公式
(h + i²) % m没有引入键相关扰动，无法区分同义词
C++中避免次级聚集的三个实操要点
不靠“魔改探测公式”，而是在工程约束下做有效取舍：
立即学习“C++免费学习笔记（深入）”；
-
表长必须为质数：比如选
101、1009、10007。非质数表长（如100）会导致i² % 100在i=10后开始循环，实际探测位置远少于理论值 -
负载因子严格控制在 0.5 以下：一旦
size / capacity > 0.5，探测失败率陡增。建议在size * 2 >= capacity时触发扩容，并用新质数重哈希 -
插入前加一次轻量扰动：比如把
key异或上其地址哈希或低几位翻转，再算初始h。不改变探测序列结构，但让同义词大概率分到不同起始点：size_t h = (key ^ (key >> 13)) % capacity;
二次探测 vs 线性探测 vs 双重哈希：C++实测关键差异
别只看理论复杂度，真实瓶颈常在缓存与分支预测：
-
线性探测：步长恒为 1，CPU 预取友好，L1 cache 命中率高；但主聚集严重，
find()平均探查次数随负载上升极快（>0.8 时接近 O(n)） - 二次探测：步长跳变，预取失效多，cache 行浪费更明显；但探查路径分散，平均比较次数在负载 ≤0.5 时比线性探测低 30%~40%
-
双重哈希：第二哈希函数（如
hash2(key) = P - (key % P)，P是略小于表长的质数）提供强扰动，基本消灭次级聚集；但每次探测多一次模运算+减法，热点路径延迟略高
结论：若数据量小、内存紧、负载可控（如编译器符号表），二次探测够用；若追求稳定吞吐且允许额外计算（如网络包分类），双重哈希更可靠。
删除操作必须标记而非清空，否则查找链断裂
这是开放寻址法里最容易被忽略的陷阱：一旦你用 memset 或直接赋 0/-1 清掉一个槽位，所有依赖该位置“作为路径一部分”的后续查找就会提前终止，导致漏查。
- 必须引入三态标记：
EMPTY（从未使用）、OCCUPIED（当前有效）、DELETED（曾占用、可插入、但查找需跨过） - 插入时遇到
DELETED可以覆盖；查找时遇到DELETED必须继续探测，直到EMPTY - C++ 中推荐用枚举而非宏定义，避免类型混淆：
enum class SlotState { EMPTY, OCCUPIED, DELETED };
真正难的不是写对探测循环，而是让 delete() 和 find() 对 DELETED 的语义理解完全同步——差一行判断，整张表就静默失效。
