双散列通过独立哈希函数hash2生成非连续探测步长，有效缓解一次与二次聚集，使负载因子0.5–0.7区间性能更稳定；但load_factor＞0.7后探测链仍急剧增长，必须及时扩容。
双散列法本身不能绕过负载因子的物理限制，当 load_factor > 0.7 时，即使换用 hash2，探测链也会急剧变长，查找退化为 O(n)。
为什么双散列比线性/二次探测更适合高负载场景
线性探测（hash1(key) + i）和二次探测（hash1(key) + i*i）在冲突后都依赖单一偏移序列，容易形成“聚集”——即多个键争抢相邻位置，导致后续插入/查找雪崩。双散列引入第二个哈希函数 hash2(key) 生成步长，使探测路径分散、非连续，显著削弱一次聚集和二次聚集。
但注意：hash2(key) 不能返回 0（否则探测停住），也不能与表长 capacity 不互质（否则无法遍历全表）。常见安全写法是：
size_t hash2(const Key& key) {
size_t h = std::hash<key>{}(key);
return (h % (capacity - 1)) + 1; // 确保结果 ∈ [1, capacity-1]
}</key>
-
hash2输出必须严格大于 0 - 若
capacity是质数，hash2模capacity后加 1 更稳妥 - 不要复用
hash1的中间结果（比如直接取低 16 位），否则两函数强相关，失去“双散列”意义
负载因子超过 0.7 后，双散列也救不了性能
开放寻址类哈希表的冲突率与负载因子呈非线性增长。理论推导和实测均表明：当 load_factor ≥ 0.75 时，平均探测长度（ASL）开始指数上升。此时即使 hash2 再“随机”，空槽已稀疏，每次查找都要试十几个位置。
- STL 的
std::unordered_map默认在load_factor() > 1.0时强制rehash()，但那是拉链法；闭散列必须更早干预 - 实测中，
load_factor = 0.8下双散列的平均插入耗时可能比0.6时高 3–5 倍 - 扩容不是简单
new更大数组——所有已有元素必须重新hash1/hash2计算并插入，开销巨大
如何安全地实现双散列哈希表的扩容逻辑
扩容不是“把旧表拷过去”，而是重建探测路径。关键点在于：新表的 capacity 必须是质数，且与旧 capacity 无公因数；否则 hash2 在新表中可能产生固定循环，永远找不到空位。
- 预定义质数序列（如 {11, 23, 47, 97, 193, 389, 769, ...}），每次扩容选下一个
- 扩容触发条件建议设为
load_factor > 0.7，而非等到> 0.75 -
rehash()过程中，对每个有效元素调用新的hash1和hash2（因为capacity变了，两者输出都变） - 状态标记（
EMPTY/EXIST/DELETED）必须一并迁移，DELETED在新表中仍需保留语义（影响查找连续性）
双散列真正的价值不在“扛更高负载”，而在于让 0.5–0.7 区间内的性能更稳定、更可预测；一旦越过这个阈值，再精巧的 hash2 设计也掩盖不了空间不足的事实——该扩容就得扩容，别硬撑。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
