双散列法探测公式为(h₁(key)+i×h₂(key))%table_size，关键需确保h₂(key)与表长互质、非零，且与h₁正交；h₂常取P−(key%P)（P为小于表长的最大质数），并须校验fallback，避免探测循环或漏位。
双散列法的探测公式怎么写才不踩坑
双散列法的核心是用两个哈希函数构造探测序列：(h1(key) + i * h2(key)) % table_size。很多人直接套公式，却忽略 h2(key) 的返回值必须与 table_size 互质，否则探测序列会提前循环、漏掉空位。比如 table_size = 8，若 h2(key) = 4，那探测位置永远只在偶数下标（0→4→0→…），奇数位置永远无法访问。
实操建议：
-
h2(key)最稳妥的取法是h2(key) = P - (key % P)，其中P是小于table_size的最大质数（如table_size = 16，选P = 13） - 绝对避免
h2(key) == 0，插入前必须做校验并 fallback（例如设为 1） - 不要复用
h1的实现逻辑，两个函数的扰动机制要正交——h1侧重均匀分布，h2侧重生成“步长多样性”
为什么线性探测一用就聚集，而双散列能缓解
线性探测的探测步长固定为 1，只要两个键在 h1 上冲突，它们后续所有探测位置完全重合，形成“一次冲突 → 全程共享路径”的一次聚集。二次探测虽改用平方步长，但不同键若 h1 相同，其探测序列仍高度相似，导致二次聚集。
双散列把步长和键本身绑定：h2(key) 不同，步长就不同。哪怕 h1(key1) == h1(key2)，只要 h2(key1) != h2(key2)，它们的探测路径就会快速分叉。这是它抗聚集的根本原因。
立即学习“C++免费学习笔记（深入）”；
注意点：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 聚集不会消失，只会被“打散”。当负载因子 > 0.7 时，即使双散列，平均查找长度也会明显上升
- 如果大量键的
h2值趋近（比如都集中在 3~5），仍可能局部聚集，此时需检查h2是否真具备足够熵
删除操作必须用“墓碑标记”，不能直接清空
开放寻址法里，删除一个元素后如果直接设为 EMPTY，会切断后续元素的查找链。比如键 A、B、C 依次插入，因冲突落在位置 3、4、5；删掉 B 后位置 4 变空，查 C 时在 4 就停了，误判为“不存在”。
正确做法是引入第三种状态：DELETED（墓碑）。查找时遇到它继续探查，插入时可复用该位置，但遍历时跳过。
关键细节：
- 墓碑不参与负载因子计算，但过多墓碑会拖慢查找——需要定期 rehash 清理
- 不能用布尔标记模拟墓碑（如
is_deleted字段），必须让存储单元本身可区分三种状态（EMPTY/DELETED/OCCUPIED） - 初始化时所有位置必须是
EMPTY，而非默认构造值（比如0或nullptr），否则无法和真实数据区分
负载因子超过 0.7 就该扩容，别硬扛
双散列对高负载极其敏感。实验表明：当 α = 0.8 时，平均查找长度比 α = 0.5 时高出 3 倍以上；到 α = 0.9，性能断崖式下跌。这不是理论推导，是实际压测中反复验证过的拐点。
扩容不是简单 realloc 数组：
- 新表大小必须是质数，且至少比原大小大 1.5 倍（推荐 2 倍），避免频繁扩容
- 所有现存元素必须重新
h1和h2计算，不能直接 memcpy —— 因为模数变了，探测序列全失效 - 墓碑标记在新表中不保留，只迁移有效数据；这反而是清理碎片的好时机
真正容易被忽略的是：rehash 过程中内存临时翻倍，且不可中断。如果表很大，又在实时系统里，得预留好空间并控制触发时机。
