C++如何实现哈希表的链地址法-C++-PHP中文网

链地址法哈希表推荐用std::vector实现，桶数取质数，插入前需遍历桶内链表检查键重复，扩容时必须重哈希迁移所有节点。

c++如何实现哈希表的链地址法

哈希表用链地址法时，`std::vector` + `std::list` 是最直接的选择

标准库没提供现成的“链地址哈希表”容器，但组合 std::vector 存桶、每个桶用 std::list（或 std::forward_list）存冲突元素，是最贴近教科书实现的方式。别硬造 std::unordered_map 的简化版——它底层就是链地址（GCC 用 std::list，Clang 用单向链表），但封装太深，没法直观看到桶和节点关系。

关键不是“能不能用”，而是“要不要自己写”。如果只是为了快速存取键值对，直接用 std::unordered_map；如果是为了理解哈希冲突处理、调试桶分布、或嵌入式环境不能用 STL 容器，则手写链地址表有意义。

std::vector<:list k v>>></:list> 是推荐结构：支持 O(1) 桶索引，std::list 支持高效头插/遍历/删除
哈希函数必须返回 size_t，再对 bucket_count 取模得到下标，别漏模运算：hash(key) % buckets.size()
桶数量建议设为质数（如 13、31、97），能减少同余冲突；用合数（如 16、100）在某些哈希分布下容易让多个键挤进同一桶

插入操作必须检查重复键，否则会存多份相同 key

链地址法本身不禁止重复 key，但语义上哈希表通常要求 key 唯一。如果你跳过查找直接 push_back，就可能在一个桶里塞进 {"a", 1} 和 {"a", 2} 两个节点——这不是 bug，是逻辑错误。

正确流程是：先定位桶 → 遍历该桶的 std::list → 用 operator== 或自定义比较器比对 first（即 key）→ 找到则更新 value，没找到才插入新节点。

C++ Code Review Master

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

下载

别用 std::find_if 遍历时只传 key，要传整个 std::pair 的 lambda：[&key](const auto& p) { return p.first == key; }
更新 value 时别重建节点，直接赋值：it->second = value;，避免无谓构造/析构
如果 key 类型重载了 == 但没定义哈希函数，编译会报错 error: call to implicitly-deleted default constructor of 'std::hash<k>'</k>，这时得显式特化 std::hash 或传入自定义哈希对象

`rehash` 触发条件和迁移逻辑最容易出错

负载因子（size() / bucket_count()）超过阈值（比如 0.75）就得扩容。但只调大 std::vector 容量不够——旧桶里的所有节点必须重新计算哈希、分配到新桶中，否则查找必然失败。

常见错误是：只 buckets.resize(new_size)，然后以为万事大吉；或者迁移时仍用旧 bucket_count 取模，导致下标越界或错放。

迁移前保存旧桶引用：auto old_buckets = std::move(buckets);，再 buckets.resize(new_size)，避免迭代器失效
遍历每个旧桶：for (auto& bucket : old_buckets)，再遍历其中每个 std::pair，用新桶总数重新哈希：hash(p.first) % buckets.size()
别在迁移循环里调用 insert()——它又会触发 rehash，造成无限递归；必须直插 buckets[index].push_back(p)

自定义哈希和比较器要同步，否则 `find` 找不到刚 `insert` 的 key

哈希函数决定 key 落在哪一个桶，等于比较器决定“哪两个 key 算相同”。两者不一致，就会出现：插入时算出桶 A，查找时算出桶 B，自然找不到。

典型场景是自定义字符串类或结构体，用了 std::hash<:string></:string> 但比较时按指针比（== 没重载），或哈希用了 std::hash 但比较用了 strcmp。

如果传入自定义哈希类型 H，必须同时传入匹配的等价谓词 Eq，且满足：若 h(a) == h(b)，则 eq(a, b) 应为 true（反之不强制，但强烈建议保持一致）
用 std::unordered_map 时，哈希和等价默认绑定；但手写链地址表时，这两者完全解耦，容易疏忽
调试技巧：打印某个 key 的 hash(key) 和 hash(key) % bucket_count，再用同样输入跑 find，看两次结果是否一致