因为开放寻址法需显式标记EMPTY、EXIST、DELETE三种状态，而std::vector<std::pair<K,V>>无法区分“空槽”与“合法键值对”，易导致查找失败或覆盖；且删除必须逻辑删除（置DELETE）以保探测链连续，不能直接擦除。
为什么开放寻址法的哈希表不能直接用 std::vector<std::pair<K, V>> 存值
因为开放寻址法要求所有键值对都存在一个连续数组里，删除时不能真删（否则会断开探测链），得用“逻辑删除”标记。如果用 std::vector 存 std::pair，遇到空位或已删除位就得额外维护状态，不如一开始就用结构体封装状态。
常见错误是把 nullptr 或默认构造的 K 当作“空槽”，结果键本身合法（比如 K=int 时 0 是有效键），导致查找失败或覆盖。
- 必须为每个槽位显式记录三种状态：
EMPTY、OCCUPIED、DELETED - 推荐用枚举 + 联合体（
union）或独立状态数组，避免默认构造值干扰 - 负载因子超过
0.7就必须扩容，否则查找性能急剧下降（平均探测次数翻倍）
hash() 和 probe() 怎么配合才能不漏掉槽位
线性探测（i, i+1, i+2, ...）最简单但容易聚集；二次探测（i, i+1, i+4, i+9, ...）能缓解，但要求表长是素数且负载因子 < 0.5，否则可能永远探不到空位。
真正实用的是双重哈希：用两个哈希函数，步长由第二个函数决定，能保证遍历全部槽位——前提是第二个函数结果与表长互质。
立即学习“C++免费学习笔记（深入）”；
- 第一哈希：
h1(key) % capacity，定位起点 - 第二哈希：
h2(key) = 1 + (hash2(key) % (capacity - 1))，强制步长 ≥1 且与capacity互质 - 探测序列：
(h1 + j * h2) % capacity，j = 0,1,2,... - 别用
std::hash直接模表长——它输出是size_t，高位信息在模小素数时易丢失，建议先异或折叠再模
插入时遇到 DELETED 槽位要不要停
要停。开放寻址法的查找逻辑是：“找到 OCCUPIED 且 key 匹配 → 成功；找到第一个 EMPTY → 失败”。DELETED 槽位只是占位符，不影响查找链连续性，但插入时它是**唯一可复用的位置**。
如果不在这儿停，继续往后找，就浪费了已释放的空间，还可能把新元素插到更远位置，拉长后续所有查找路径。
- 插入流程：探测到
EMPTY→ 插入；探测到DELETED且尚未记录首个可插位置 → 记下该位置；探测到OCCUPIED且 key 相等 → 更新值；探测到OCCUPIED且 key 不等 → 继续 - 必须在第一次遇到
DELETED时记下索引，后续再遇到不更新——否则可能选到离起点更远的删除位 - 扩容后所有
DELETED状态自动清零，所以不用在扩容时特殊处理
扩容时怎么避免重复哈希计算和内存抖动
扩容不是简单把旧数组拷过去。旧表中每个 OCCUPIED 项都得重新哈希、重新探测插入到新表，DELETED 项直接丢弃。如果新容量选得不合理（比如非素数），会导致大量冲突，让重建过程变慢甚至死循环。
实测发现：从 8 开始，每次乘 2 加 1（即 8→17→37→73→149…）生成的素数序列，在负载因子 0.7 下探测长度稳定在 2–3 次，比单纯翻倍快 30% 以上。
- 新容量必须是素数，且 > 旧容量 × 2（确保负载率回落到 0.35 以下）
- 不要用
std::vector::resize()后逐个emplace_back——这会触发多次内存分配；应先reserve，再用原始指针批量构造 - 移动构造值类型时，注意
K和V是否有 noexcept 移动构造函数，否则异常安全难保证
最难调的其实是哈希函数和扩容阈值的组合：改一个参数，整个探测分布就偏移，有些 key 查找时间突增 10 倍。上线前一定要用真实数据跑一遍长尾延迟 P99。
