双散列法通过独立的hash2(k)为同hash1(k)键生成不同探测序列，有效缓解一次与二次聚集；关键要求是hash2(k)非零且与表长m互质，推荐实现为1+(key%(m-1))，探测上限设为m次以防死循环。
双散列法在 C++ 开放寻址哈希表中确实能显著缓解一次聚集（primary clustering）和二次聚集（secondary clustering），但它不是“开箱即用”的银弹——hash2(k) 设计不当或表长选错，会直接导致插入失败或死循环。
为什么线性/平方探测挡不住聚集，而双散列可以
线性探测每次偏移固定为 1，冲突后位置连续，容易形成大段已占区域（一次聚集）；平方探测虽跳得更远，但对同一 hash1(k) 值的所有键，探测序列完全相同（二次聚集）。双散列引入第二个散列函数 hash2(k)，让不同键即使 hash1(k) 相同，也能走出**完全不同**的探测路径。
关键点在于：hash2(k) 必须保证对任意合法键 k，输出值与表长 m 互质（即 gcd(hash2(k), m) == 1），否则探测步长和表长存在公因数，必然陷入子集循环。
- 错误示例：若
m = 9，hash2("abc") = 3，则探测序列为(h1 + 0×3) % 9、(h1 + 1×3) % 9、(h1 + 2×3) % 9… 实际只遍历模 3 同余类，永远覆盖不到全部桶 - 安全做法：令
m为质数，并定义hash2(k) = P - (k % P)（P是略小于m的质数），或更常用：hash2(k) = 1 + (k % (m - 1))—— 此时结果范围是[1, m-1]，与质数m必然互质
如何写一个不崩的 hash2 函数（C++ 实现要点）
不能直接对原始键取模再套用 hash1 的逻辑。hash2 需要输出一个**非零、且与表长互质**的整数，同时避免和 hash1 共享相同输入处理路径（否则两函数强相关，失去“双重”意义）。
立即学习“C++免费学习笔记（深入）”；
以 size_t 键为例，推荐实现：
size_t hash2(size_t key, size_t m) {
// 确保结果 ∈ [1, m-1]，且 m 是质数 → 自动满足 gcd(result, m) == 1
return 1 + (key % (m - 1));
}若键是 std::string，不要复用 hash1 的字符串哈希算法（比如 std::hash<:string>{}(s) % m</:string>），应构造独立扰动：
- 用不同常数做乘加：
hash1用31，hash2就用107 - 或错位异或：
hash2(s) = (std::hash<:string>{}(s) ^ (std::hash<:string>{}(s) >> 13)) % (m - 1) + 1</:string></:string> - 绝对禁止返回 0 —— 探测步长为 0 意味着原地死锁
插入时的探测公式和终止条件怎么写才安全
标准双散列探测公式是：(hash1(k) + i * hash2(k)) % m，其中 i = 0, 1, 2, ...。但仅靠这个公式无法防止死循环，必须叠加两个硬性约束：
- 探测轮数
i上限设为m（不是m-1）：因为最多尝试m次就能遍历所有桶（当hash2(k)与m互质时） - 遇到
EMPTY状态立即插入；遇到EXIST且键相等则更新；若循环m次仍未找到空位，说明表已满（或hash2不合规），必须扩容
典型插入循环片段：
for (size_t i = 0; i < m; ++i) {
size_t idx = (hash1(key) + i * hash2(key, m)) % m;
if (state[idx] == EMPTY) {
// 插入
break;
} else if (state[idx] == EXIST && keys[idx] == key) {
// 更新
break;
}
}
// 若 i == m 仍未 break → 扩容后重试表长 m 必须是质数吗？能不能用 2 的幂
可以用 2 的幂，但代价是 hash2(k) 必须手工确保与 m 互质 —— 而 2 的幂只有因数 2，所以 hash2(k) 必须恒为奇数。这增加了实现负担，且一旦疏漏（比如 hash2 返回了偶数），立刻死循环。
更稳妥的做法是坚持用质数表长：m 取 2^N 附近最大质数（如容量 1024 → 用 1021；2048 → 用 2039）。C++ 标准库 std::unordered_map 内部就预置了一组质数序列用于扩容，可直接借鉴。
真正容易被忽略的是：**扩容后所有键必须重新计算 hash1 和 hash2 并插入新表** —— 因为 hash2(k, m) 依赖当前表长，旧表的探测路径在新表上完全无效。
