开放寻址法哈希表易错主因是vector重分配导致指针失效、探测越界、忽略DELETED状态；必须用三态桶、解耦哈希与探测、保证步长互质、负载因子超0.7及时扩容。
为什么开放寻址法的哈希表在 C++ 里容易写错
直接手写开放寻址哈希表，最常踩的坑不是逻辑，而是 std::vector 的移动语义和内存重分配——一旦触发 resize()，所有已存储的键值对指针或引用会失效，而你可能还在用旧桶数组索引做探测。更隐蔽的是：未定义行为常出现在探测循环里越界访问（比如没检查 i >= capacity）或忘记跳过被删除标记（DELETED 状态）导致查找失败。
核心结构体必须包含三种状态桶
每个桶不能只存 std::pair，否则无法区分“空”和“曾存在但已删除”。必须用枚举或整数标记状态：EMPTY、OCCUPIED、DELETED。否则删除后插入新元素会卡死在旧位置，后续查找永远绕不开它。
enum class BucketState { EMPTY, OCCUPIED, DELETED };
template
struct HashBucket {
K key;
V value;
BucketState state = BucketState::EMPTY;
};
哈希函数与探测策略要解耦
别把 hash(key) % capacity 写死在查找逻辑里。容量变化时模数变，哈希值就得重算——但你没法遍历所有已有元素去重哈希。正确做法是：哈希函数只返回 size_t，探测逻辑（线性/二次/双重哈希）单独封装。线性探测最简单，但聚集严重；二次探测推荐用 (hash + i * i) % capacity，注意 i * i 可能溢出，应转为 size_t 并取模。
- 哈希函数建议用
std::hash，对自定义类型需特化{}(key) - 探测步长必须保证遍历完整个数组（即步长与容量互质），线性探测天然满足
- 负载因子超过 0.7 就必须
resize()，否则性能断崖下跌
insert() 和 find() 必须处理 DELETED 桶
find() 遇到 DELETED 不能停，必须继续探；insert() 遇到第一个 EMPTY 或 DELETED 才可插入（优先填 DELETED 以减少聚集）。这是开放寻址法正确性的关键，漏掉就等于把哈希表当成了链地址法来用。
立即学习“C++免费学习笔记（深入）”；
size_t probe = hash % capacity;
for (size_t i = 0; i < capacity; ++i) {
size_t idx = (probe + i) % capacity; // 线性探测
auto& b = buckets[idx];
if (b.state == BucketState::EMPTY) {
// 可插入
b.key = std::move(key);
b.value = std::move(value);
b.state = BucketState::OCCUPIED;
++size;
return true;
}
if (b.state == BucketState::OCCUPIED && b.key == key) {
b.value = std::move(value); // 更新
return true;
}
// DELETED：跳过，继续探
}
实际使用中，最难调的是 resize 时机和迁移逻辑——老桶里的 DELETED 状态在新表里不该保留，必须只迁移 OCCUPIED 项。这点稍不注意，扩容后查不到数据，又找不到原因。
