二次探测不能消除次级聚集，因其同义词键的探测序列完全相同；需表长为质数、负载因子＜0.5、哈希值充分打散，才能缓解该问题。
二次探测本身不能消除次级聚集（secondary clustering），它只是把主聚集从“连续块”变成“固定偏移序列”。真正能缓解次级聚集的，是让不同键的探测路径尽可能不重合——这要求表长为质数、哈希函数输出足够分散，且负载因子严格控制在 0.5 以下。
为什么二次探测会引发次级聚集？
次级聚集不是代码写错了，而是数学结构决定的：所有哈希值相同的键（即同义词），其二次探测序列完全一致。例如，key1 和 key2 都满足 hash(key) % table_size == 3，那么它们的探测位置都是 (3 + 1) % size、(3 + 4) % size、(3 + 9) % size……哪怕表里只有这两个键，它们也会在相同位置反复“踩脚”。
这种现象和线性探测的主聚集不同——它不依赖插入顺序，只取决于哈希值是否相等，因此更隐蔽、更难调试。
- 典型表现：插入/查找耗时突然变长，但
load_factor看起来还不高（比如 0.45） - 验证方法：统计各槽位被探测的频次，会发现若干条“热点路径”明显高于均值
- 根本原因：探测序列由
i*i决定，而i*i mod table_size的周期性和分布质量，直接受table_size影响
表长必须是质数，且不能随便选
非质数表长会导致探测序列提前循环或覆盖不全。比如 table_size = 16，则 i² mod 16 的取值只有 {0,1,4,9} 四种，探测永远卡在这 4 个偏移上——相当于有效探测空间被砍掉 75%。
质数能保证 i² mod p 在 i = 1..p-1 范围内产生至少 (p-1)/2 个不同余数（二次剩余理论），大幅提高路径分散度。
- 推荐做法：用预计算质数表，如
{11, 23, 47, 97, 193, 383, 769, 1531, 3079, 6151, 12289, 24593} - 避免动态计算：运行时调用
is_prime()检查表长，开销远超收益 - 扩容时机：当
size() > capacity * 0.5时立即扩容，不要等到0.7——二次探测对负载极度敏感
hash(key) 输出必须打散，不能直接 key % size
如果键本身是等差序列（如 100, 200, 300...），而表长又是偶数，key % size 会生成高度重复的哈希值，放大次级聚集效应。
必须引入扰动：乘法散列、FNV-1a 或简单但有效的 std::hash 封装，再取模。
- 错误示例：
index = key % capacity（整数键直接取模） - 安全写法：
index = std::hash{}(key) % capacity - 自定义类型：必须重载
std::hash特化，且 hash 值不能只依赖单个字段（比如只用id忽略name） - 性能提示：
std::hash调用开销可忽略，别为了省一次函数调用牺牲分布质量
删除操作必须标记 DELETED，不能置空
二次探测的查找逻辑依赖“探测链连续性”：遇到空槽（EMPTY）就终止搜索；但遇到已删除槽（DELETED）必须继续——否则后续插入的同义词可能插进 DELETED 位置，而原本该位置之后的键再也无法被查到。
这个细节一旦漏掉，bug 表现为“键明明存在却查不到”，且只在多次删插混合后出现，极难复现。
- 状态枚举至少要三个值：
EMPTY、OCCUPIED、DELETED - 插入时只接受
EMPTY或DELETED槽位 - 查找时跳过
DELETED但不停止，只在EMPTY停止 - 清理策略：可定期触发 rehash，但不要在每次删除后立即 compact——代价太高
最常被忽略的一点：二次探测的“优化”不是靠改探测公式（比如加个随机项），而是靠严守三个硬约束——质数表长、低负载因子、高质量哈希值。任何试图绕过这三者的“小技巧”，最终都会在数据量上升后暴露为不可预测的性能拐点。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
