二次探测仍会出现次级聚集，是因为当不同键哈希后基础索引相同（hash(k1) == hash(k2)），其探测序列完全一致，即均按(base + i²) % table_size遍历，导致冲突键在相同路径上堆积；虽缓解主聚集，但形成局部次级聚集，拖慢尾部查找平均时间（ASL）。
二次探测 本身不能消除次级聚集，但能显著缓解主聚集；真正影响性能上限的，是表长选择、负载因子控制和删除标记机制——不解决这三点，光调探测公式没用。
为什么二次探测还会出现“次级聚集”？
当两个不同键 k1 和 k2 经哈希后得到相同基础索引（即 hash(k1) == hash(k2)），它们的探测序列完全一致：(base + i*i) % table_size。这意味着所有冲突于同一位置的键，会走完全相同的探查路径，形成新的局部聚集，这就是次级聚集。
它不像线性探测那样蔓延成大片，但会拖慢查找尾部元素的平均时间（ASL）。
- 必须用质数作为
table_size：否则i*i % table_size的取值周期变短，探测序列提前重复，有效探查位置锐减 - 负载因子建议 ≤ 0.5：超过后空槽稀疏，探测轮次激增，
insert和search的最坏情况从 O(1) 滑向 O(√n) - 删除不能清空槽位，必须设
is_deleted标记：否则后续查找会在中途“误判为空”而终止，漏掉本该在更远位置的元素
C++中二次探测的正确实现要点
常见错误是直接套用 (hash(key) + i*i) % size，却忽略负偏移、越界循环和终止条件。
立即学习“C++免费学习笔记（深入）”；
正确写法需包含三重防护：
- 基础哈希结果先做非负归一化：
size_t base = hash(key) % table.size();（避免负数取模行为未定义） - 每次探测前加
table.size()再取模：(base + i*i) % table.size()不够健壮，应写为(base + i*i) % table.size()已足够，但若用带符号整型算i*i可能溢出，推荐用size_t i - 探测轮次上限必须设为
min(table.size(), 2 * (table.size() / 2 + 1))级别，简单起见可直接用table.size() / 2 + 1—— 超过即认为表已逻辑满，需扩容
示例关键片段：
size_t probe(size_t base, size_t i) const {
return (base + i * i) % table.size();
}
<p>bool insert(int key) {
size_t base = key % table.size();
for (size_t i = 0; i <= table.size() / 2 + 1; ++i) {
size_t idx = probe(base, i);
if (table[idx] == EMPTY || table[idx] == DELETED) {
table[idx] = key;
used[idx] = true;
if (table[idx] == DELETED) deleted_count--;
return true;
}
if (table[idx] == key) return false; // 已存在
}
return false; // 探测失败，需扩容
}二次探测 vs 线性探测 vs 双重哈希：真实性能分水岭在哪？
三者理论 ASL（平均查找长度）差异不大，实际表现却常因细节失控而天差地别。
-
线性探测：缓存友好，但主聚集让插入后期频繁跳 cache line；适合只读或低频更新场景 -
二次探测：步长跳跃打散局部访问，但次级聚集+删除标记使内存访问模式不可预测；适合中等更新频率、负载可控的嵌入式或游戏逻辑表 -
双重哈希：第二哈希函数（如hash2(key) = P - (key % P)，P 为略小于表长的质数）让不同键的探测路径彻底错开，几乎无聚集；但两次哈希计算开销高，且hash2(key)不能为 0
真正卡住性能的，往往不是探测方式本身，而是：没有在负载达 0.7 前触发扩容，或 用非质数表长导致探测序列坍缩——这两点比选哪种探测法重要十倍。
容易被忽略的删除与扩容陷阱
二次探测哈希表的 erase 不是把槽清零，而是置为 DELETED 状态；否则 search 会提前终止。但这也带来新问题：大量 DELETED 槽堆积后，insert 查找空位变慢，且无法通过当前负载因子准确判断是否该扩容。
- 必须单独维护
deleted_count，并在扩容时跳过DELETED槽，只迁移有效数据 - 扩容阈值不能只看
used_count / table.size()，而应结合deleted_count：当(used_count + deleted_count) > table.size() * 0.6时就该扩了 - 新表长必须是比原长大的下一个质数（如用筛法预生成小质数表），否则二次探测退化为“伪随机跳”
这个环节出错，会导致表看似没满，但插入成功率断崖下跌——现象是 insert 频繁返回 false，而 used_count 还不到一半。
