C++如何实现简单的哈希表(开放地址法)-C++-PHP中文网

应使用 std::hash{}(key) % capacity 而非手写取模；线性探测需以 probes

哈希函数选 std::hash 还是手写取模？

直接用 std::hash<t>{}(key)</t> 得到哈希值，再对表长取模——这是最常用也最稳妥的做法。别自己写“key % table_size”当哈希函数，整数键看似可行，但字符串、自定义类型会崩。C++ 标准库的 std::hash 已针对常见类型做了良好分布，你只需补一句取模：hash_val % capacity。注意：模运算前务必检查 capacity > 0，否则除零崩溃；扩容时要重新散列全部元素，不能只改模数。

线性探测怎么避免无限循环？

插入时若位置被占，就顺序往后找空位或匹配键；但必须设终止条件，否则遇到全满表会死循环。关键点有三个：
• 用 probes 控制最大探测次数（不是 <code>）<br>• 空槽（<code>nullptr 或 empty 标记）代表“此处无此键，且后面不可能有”
• 已删除标记（deleted）不能终止查找，但可作为插入目标
示例逻辑片段：
for (int i = 0, pos = hash(key); i     if (table[pos] == nullptr) return false; // 未找到<br>    if (table[pos]->first == key) return true; // 找到<br>}
这里没写插入，是因为插入还要处理 deleted 位置优先复用。

删除操作为什么不能真删？

开放地址法里“真删”（即置 nullptr）会断开后续键的查找链。比如键 A、B、C 挨着存，B 被删成空，查 C 时在线性探测中遇到空位就停了，永远找不到 C。必须用独立状态标记“已删除”，如 enum：enum SlotState { EMPTY, OCCUPIED, DELETED };。插入时优先选 DELETED 位，查找时不终止但跳过；遍历时可忽略 DELETED 项。这个细节漏掉，调试时会发现“刚插进去的键立刻查不到”。

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

下载

负载因子多少该扩容？

别等 size == capacity 再扩——那时探测长度已很长，性能骤降。经验阈值是 load_factor > 0.7 就触发扩容。扩容不是简单 new 更大数组，而是：
• 分配新 vector<pair>*></pair>（或带状态的结构体）
• 遍历旧表，跳过 EMPTY 和 DELETED，对每个 OCCUPIED 项重新计算哈希并插入新表
• 交换指针，delete 旧表
注意：新容量建议用质数（如 11, 23, 47…），能缓解聚集；若用 2 的幂，hash % capacity 等价于 hash & (capacity-1)，但分布质量更依赖哈希函数本身，风险略高。

开放地址法的麻烦不在代码量，而在状态组合的边界判断：空、占、删三种状态在插入/查找/删除中各自扮演不同角色，少一个分支就可能漏掉“本该找到却返回不存在”或“删一次后整段键失效”。动手前先画个三格状态转移草图，比直接敲代码省两小时调试时间。