双散列法负载因子超0.7时asl断崖式上升，因聚集效应致探测路径卡死；安全扩容阈值应设为0.65（含墓碑计数），表长须为质数且h2∈[1,capacity−1]。
双散列法在负载因子超过 0.7 后，平均查找长度（ASL）会断崖式上升，不是“变慢一点”，而是从常数级退化为接近线性——这不是实现有 bug，而是数学规律决定的。
为什么 load_factor > 0.7 就必须 rehash
开放寻址下，查找失败时的平均探测次数 ASL_unsuccessful ≈ 1 / (1 − λ)，这只是一个下界近似；实际因聚集效应，λ = 0.7 时实测 ASL 常达 3.5–4.2，λ = 0.8 时跳到 7–9，λ = 0.9 时可能突破 20。这不是缓慢增长，而是探测路径被“卡住”的指数现象。
根本原因在于：哪怕 h2(key) 设计正确，当空槽太少时，不同键的探测序列会高频重叠在少数几个位置上，形成局部热点。此时 h2 的“多样性”被稀疏性淹没。
- std::unordered_map 能设
max_load_factor(1.0)，是因为它用拉链法，冲突不阻塞探测路径 - 你自己写的双散列是闭散列，所有元素挤在一块数组里，没有“绕路”余地
- 实测表明：λ = 0.75 是性能拐点，部分插入操作延迟突增 5–10 倍，不是均值问题，而是长尾毛刺
如何安全设置扩容阈值与新表长
不能等 size() >= capacity * 0.7 再扩容——因为删除后留下的墓碑（DELETED）不计入 size()，但会拖慢查找。真实有效负载应按 (size() + tombstone_count) / capacity 估算，触发点建议设为 0.65。
新表长必须是质数，且不能是旧表长的整数倍（比如旧 size=101，新 size 不能选 202），否则 h2(key) 在新表中仍可能与表长不互质，导致探测循环。
- 推荐做法：预存质数序列，如
{11, 23, 47, 97, 193, 389, 769, 1531, 3079}，每次扩容取下一个 - 扩容时必须对每个有效元素（
OCCUPIED状态）重新计算h1(key)和h2(key)，因为capacity变了，两者输出都变 - 墓碑状态也要迁移，但新表中遇到墓碑仍要继续探测——语义不能丢
h2(key) 返回 0 或与表长不互质的典型错误
最常见错误是写成 h2(key) = key % (capacity - 1)，没加 1，导致结果可能为 0；或者 capacity 是合数（如 100），而 h2(key) = key % 99，此时 gcd(99, 100) = 1 表面看没问题，但若某 key 算出 h2 = 33，而 capacity=100，则探测步长 33 与 100 不互质（gcd=1？等等，33 和 100 确实互质），但若 capacity=99，h2=33 就完蛋了——所以关键还是表长本身得是质数。
- 安全底线：
h2(key)必须 ∈ [1, capacity−1]，且capacity是质数 → 自动保证互质 - 推荐实现：
return 1 + (key % (capacity - 1))，简单、可控、无分支 - 绝对避免复用
h1的中间结果，比如h1用了std::hash<t>{}(key)</t>，h2就别再用它取低 16 位——两函数必须正交
删除后查找失败的“幽灵中断”问题
这是双散列最容易忽略的致命细节：删掉一个元素后如果直接把桶设为 EMPTY，后续查找依赖该桶做“中转”的键就会提前终止，误判为不存在。例如键 A、B、C 的 h1 都是 5，h2 分别是 2、3、4，插入后落在位置 5、7、0；删掉 B（位置 7）后若清为 EMPTY，查 C 时探到 7 就停，永远找不到 0。
必须引入第三种状态 DELETED（墓碑），且这个状态必须可区分于 EMPTY 和 OCCUPIED ——不能靠 bool is_deleted 字段模拟，而要用枚举或联合体明确编码三种状态。
- 查找时遇到
DELETED继续探测 - 插入时可复用
DELETED位置，但遍历时跳过 - 过多墓碑会拖慢查找，需在 rehash 时一并清理，不能长期积累
真正难的不是写出 h1 和 h2 公式，而是让整个状态机（EMPTY/DELETED/OCCUPIED）在插入、查找、删除、rehash 四个操作下始终自洽。任何一环漏掉墓碑语义或互质校验，都会在高负载下突然崩出不可复现的查找失败。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
