C++实现哈希冲突的开放寻址法 _ 线性探测与二次探测逻辑【实战】-C++-PHP中文网

线性探测遇到hash[i]==occupied时继续探测下一位置，必须区分occupied、deleted、empty三种状态：插入可覆盖deleted，查找遇empty即停，删除仅置deleted。

c++实现哈希冲突的开放寻址法 _ 线性探测与二次探测逻辑【实战】

线性探测的核心是：当目标位置已被占用，就顺序检查下一个位置（模数组长度），直到找到空位或已删除标记。关键不是“跳过被占位置”，而是**必须区分 occupied 和 deleted 状态**——否则删除后会导致后续查找断裂。

实操建议：

2*i 是线性步长的变体，仍属线性探测范畴；真正的二次探测要求步长随探测次数非线性增长，典型公式是 (hash(key) + i*i) % table_size。目的是减少“聚集”——多个 key 在同一初始位置冲突后，不会沿着完全相同的路径探测。

但要注意：

不能只看 size == capacity——因为存在 DELETED 占位，逻辑上可插入，物理上却无连续空位。真正的“满”是指：从 hash 值开始，按探测规则走完所有位置，没遇到一个 EMPTY。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

实操建议：

线性探测下，“满”的充要条件是：探测过程中遇到的第一个 EMPTY 出现在起始位置之后，且中间全是 OCCUPIED 或 DELETED；但判断成本高，通常预设装载因子阈值（如 0.7）触发扩容
二次探测下，最多探测 table_size / 2 次（数学证明），超过即认为无法插入，必须扩容
每次插入失败时，不要盲目重试，应先检查当前 size 是否已达 capacity * 0.7，是则先 rehash()

开放寻址表的 std::vector 或裸数组在扩容时会重新分配内存，此时所有元素要迁移。如果 value 类型的移动构造函数抛异常，可能导致部分元素丢失、状态不一致。

关键点：

使用 std::vector<:optional>></:optional> 存储槽位，而非原始指针或裸 T[]，避免未初始化对象析构问题
迁移元素时，用 std::move_if_noexcept 或显式 try-catch 包裹赋值逻辑，确保强异常安全
哈希函数和相等比较函数必须是 noexcept，否则 find/insert 的异常行为不可控
不要在 operator[] 中隐式插入（像 std::unordered_map 那样），开放寻址表的插入成本高，应显式提供 insert() 和 try_emplace()