平方探测法通过在哈希冲突时按±1²、±2²、…增量试探新位置来解决冲突，需表长为4k+3型质数以保证探查全覆盖；采用逻辑删除（DELETED状态）避免断链，并在装载因子≥0.45时及时扩容重散列。
平方探测法怎么处理哈希冲突？
平方探测法是开放寻址法中一种常用策略，核心逻辑是：当 hash(key) 位置已被占用，就尝试 hash(key) + 1²、hash(key) + 2²、hash(key) - 1²、hash(key) - 2² …… 直到找到空槽或已删除标记（deleted slot）。它比线性探测更分散，能缓解“一次聚集”（primary clustering）。
但注意：表长必须是形如 4k + 3 的质数（比如 7、11、19、23），否则无法保证探测序列覆盖全部桶位——这是最容易被忽略的前提条件。若随便用 16 或 10 做容量，探测会提前循环，导致插入失败或无限循环。
实际实现中建议采用“双向探测”：先正向加平方，再负向减平方（交替或分段），避免只朝一个方向跑偏。例如对索引 i，第 j 次探测位置为：(i + j*j) % capacity 和 (i - j*j + capacity) % capacity 交替尝试（后者加 capacity 是为防负数取模出错）。
如何设计删除操作才不破坏查找链？
开放寻址法不能真删（即置为 nullptr 或清空内存），否则后续查找会因“断链”而提前终止。必须引入“逻辑删除”状态，比如用枚举 SlotState::DELETED 标记该槽曾被使用过、当前为空闲、但查找时仍需跳过继续探查。
立即学习“C++免费学习笔记（深入）”；
插入时，遇到 EMPTY 或 DELETED 都可填入；查找时，遇到 EMPTY 就停（说明真不存在），遇到 DELETED 则继续；删除时，只改状态不释放数据（或延迟析构）。
常见错误包括：
- 把
DELETED当成EMPTY处理，导致查找漏掉本应存在的键 - 插入时只在
EMPTY处写入，跳过DELETED，造成空间浪费和负载率虚高 - 没重载移动/拷贝构造，导致
DELETED槽里残留的旧对象析构两次
为什么 load factor 超过 0.5 就容易崩？
平方探测的有效填充上限远低于线性探测。理论证明：当装载因子 α > 0.5 且表长为质数 ≡ 3 (mod 4)，仍能保证找到空位；但一旦 α 接近 0.5，平均探测次数会急剧上升，实际性能快速退化。实验表明，α = 0.45 已可能触发多次重散列。
所以不要等 size == capacity * 0.75 再扩容——开放寻址哈希表必须更早行动。推荐在 size >= capacity * 0.45 时触发 resize，并用新质数（下一个 ≡ 3 mod 4 的质数）重建整个表。
resize 不只是复制数据：必须重新计算每个键的哈希值并走完整探测流程插入新表，不能简单 memcpy。否则旧探测路径在新尺寸下完全失效。
C++ 实现时哪些细节最易出错？
模板参数、内存管理和探测边界是高频翻车点：
-
std::hash<Key>可能不支持自定义类型，记得特化或传入可调用对象（如HashFunc模板参数） - 探测循环必须带计数上限（比如
for (int j = 0; j ），否则遇上坏哈希或满表会死循环 - 所有取模运算必须用
(x % capacity + capacity) % capacity防负，尤其减法探测时i - j*j极易溢出负数 - 使用
std::vector<std::optional<value_type>>管理槽位比裸指针安全，但要注意std::optional的移动语义是否满足你的 value_type - 迭代器设计要跳过
DELETED和EMPTY，且不能暴露内部状态——用户看到的“范围”应只含有效元素
平方探测看着简单，真正稳定落地的关键不在算法本身，而在对边界、状态机和内存生命周期的严格控制。哪怕一个取模写错，整张表就可能静默失效。
