Skip to main content

Chapter 19: Hash Table Foundations

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

哈希表在没有全局排序的前提下,通过 hash function 与 bucket 索引把全局查找压缩到局部候选集合,但在冲突退化或 rehash 边界下仍会退回线性扫描与迭代器失效。本章从底层对象模型、负载策略与输入风险出发,建立分析 unordered_* 容器性能与语义边界的工程框架。

C++11 起标准库提供 unordered_map、unordered_set、unordered_multimap 与 unordered_multiset(详见 cppreference 的 std::unordered_map 页面),其查找、插入与删除的平均 O(1) 复杂度依赖两个前提:hash value 分布充分分散,且单 bucket 内的候选数受负载策略控制。典型 STL 实现分为容器层(bucket array、元素计数、Hash、KeyEqual、max_load_factor)与节点层(存储 value 并按冲突策略挂接)。

全章共用代码样本(下文各节持续拆解)

贯穿材料核心代码

贯穿全章的代码样本是词频统计函数 count_words:先用 reserve 预留桶空间,再在循环中执行 ++freq[word]。

#include <string>
#include <unordered_map>
#include <vector>

void count_words(const std::vector<std::string>& words) {
std::unordered_map<std::string, int> freq;
freq.reserve(words.size());

for (const std::string& word : words) {
++freq[word];
}
}

++freq[word] 覆盖两条核心执行路径:word 已存在时定位已有节点并递增计数;word 缺席时构造新节点再递增默认值。两条路径都必须依次经过 Hash 计算、bucket 定位与 KeyEqual 比较。

19.1 hash function、hash value 与 bucket 定位​

模板参数 Hash(默认 std::hash<Key>)负责将 key 映射为 std::size_t 类型的全局 hash value,容器随后将其压缩到当前 bucket array 的有效下标范围内。C++ 标准并未规定压缩算术的具体形式:常见实现要么采用质数桶数 + 取模,要么采用 2 的幂桶数 + 位掩码;阅读源码时应关注“全局整数到桶下标的压缩动作”,而非绑定某种固定运算符。

边界与误区

注意

hash value 只负责缩小搜索范围,key_equal 才负责判定语义相等。hash 分布差仅导致性能退化,而等价 key 产出不同 hash 会直接破坏查找正确性。按 UnorderedAssociativeContainer 要求,KeyEqual 判定相等的两个 key 必须产生相同 hash value,因此自定义 key 时 Hash 与 KeyEqual 必须覆盖同一组字段。

下面的示例将 id 与 region 同时纳入判等与哈希组合,确保等价对象进入同一 bucket 路径:

#include <cstddef>
#include <functional>
#include <string>
#include <utility>
#include <unordered_map>

struct UserKey {
int id;
std::string region;
};

struct UserKeyEqual {
bool operator()(const UserKey& left, const UserKey& right) const {
return left.id == right.id && left.region == right.region;
}
};

struct UserKeyHash {
std::size_t operator()(const UserKey& key) const {
std::size_t h1 = std::hash<int>{}(key.id);
std::size_t h2 = std::hash<std::string>{}(key.region);
return h1 ^ (h2 + 0x9e3779b9u + (h1 << 6) + (h1 >> 2));
}
};

using UserScore = std::unordered_map<UserKey, int, UserKeyHash, UserKeyEqual>;

19.2 bucket array、collision、chaining 与 open addressing​

Bucket array 是哈希表的一级索引结构。当不同 key 产生相同 hash value,或不同 hash value 被桶数量压缩到同一下标时,即发生 collision。对于 freq[word],每次查找都要扫描目标 bucket 内的全部候选节点并用 key_equal 逐一比对,因此平均 O(1) 必须将全表元素数与 bucket_count() 结合观察。

标准无序容器公开了 bucket_count()、bucket(key)、bucket_size(n)、begin(n) 与 end(n) 等桶接口并承诺节点引用稳定性,这使得 STL 源码普遍采用 chaining;工程上常将它与 open addressing(如 linear probing、quadratic probing、double hashing)对比取舍:

维度Chaining(常见 STL 形状)Open Addressing
元素位置节点独立分配,bucket 存链入口与 next 指针元素直接存于连续表格槽位(常配控制字节)
冲突路径扫描目标 bucket 的局部链表(local iterator)沿 linear/quadratic/double hashing 探测序列寻槽
删除动作修改前驱指针,销毁节点并释放存储维护空槽、tombstone 或重新整理探测路径
迭代器与引用未 rehash 时节点地址稳定,引用不易失效扩容搬移通常使槽位内更多对象地址改变
Cache 局部性链表指针跳转增加 cache miss连续槽位通常缓存更友好

回到贯穿样本,执行 freq.reserve(words.size()) 后,后续 ++freq[word] 若未触发 rehash,已有节点的地址保持稳定;一旦发生扩容 rehash,bucket array 会重建并将节点重新分配到新桶(node-based 实现通常只重挂链指针而不必重建 value 对象,具体策略属实现细节,工程上只依赖标准的复杂度与失效承诺)。

核心判断

阅读哈希表源码时的快速定型线索:看到 bucket 数组、独立分配节点、next 指针与 begin(n)/end(n) 局部迭代器,即按 chaining 路径追踪;看到连续槽位、控制字节、probe sequence 与 tombstone,即按 open addressing 路径追踪。

19.3 load factor、max_load_factor、rehash 与 reserve​

load_factor() 度量平均每个 bucket 承载的元素数,与 max_load_factor() 共同控制“链长(时间)与桶数组内存(空间)”的权衡;UnorderedAssociativeContainer 的 hash policy 表 定义了以下四个核心控制接口:

接口直接作用对象核心语义与约束
load_factor()只读观测值返回当前平均每桶元素数(size() / bucket_count())
max_load_factor()扩容负载阈值容器试图维持的平均负载上限;越高越省桶空间但平均链更长
rehash(n)bucket 数量保证桶数同时满足 size() / max_load_factor() 约束且至少为 n,并重算索引重建表
reserve(n)预期元素数量等价通过 rehash(ceil(n / max_load_factor())) 为至少 n 个元素预留桶容量

在 count_words 中,words.size() 是唯一词数的上界,提前执行 freq.reserve(words.size()) 仍能把批量插入期间的多次 rehash 前置合并。下面的代码通过标准接口观察容量策略结果:

#include <iostream>
#include <string>
#include <unordered_map>

void show_hash_policy() {
std::unordered_map<std::string, int> freq;
freq.max_load_factor(1.0f);
freq.reserve(1000);

std::cout << freq.bucket_count() << '\n';
std::cout << freq.load_factor() << '\n';
}

观察上述输出时需注意两条策略边界:

  • 桶数非精确指定:reserve(1000) 请求的是至少容纳 1000 个元素的策略空间,实际 bucket_count() 由实现选择(如取质数或 2 的幂),不可假定恰好等于 1000。
  • 非逐桶均匀保证:max_load_factor(1.0f) 仅约束全表平均负载,不保证每个桶恰好含 1 个元素,局部拥挤度仍取决于 key 集合与 Hash。

边界与误区

注意

clear、rehash、reserve 与容器赋值会使全部 iterator 失效;insert、emplace、operator[] 仅在触发 rehash 时使 iterator 失效。与之相对,指向元素的 pointer 与 reference 在 rehash 期间通常保持有效,仅在对应元素被 erase 时失效。

排查顺序

判断句柄是否跨越危险边界的固定顺序:1) 确认调用是否可能改变 bucket array;2) 检查持有的 iterator 是否跨越该次潜在 rehash;3) 区分手里保存的是 iterator(随 rehash 失效)还是元素 pointer/reference(仅随自身被 erase 失效)。

19.4 哈希退化、哈希攻击与输入风险​

哈希退化指大量 key 集中落入少数 bucket,使 bucket_size(n) 异常膨胀、单次 find 退化为线性扫描;常见诱因包括低质量 Hash、错误等价关系、过高负载因子或刻意构造的输入。下面的 ConstantHash 构造了极端退化场景:

#include <cstddef>
#include <string>
#include <unordered_map>

struct ConstantHash {
std::size_t operator()(const std::string&) const {
return 0;
}
};

using SlowMap = std::unordered_map<std::string, int, ConstantHash>;

对 SlowMap 执行 ++freq[word] 时,所有元素都落入同一 bucket,容器依靠 KeyEqual 扫描链表仍能保持语义正确,但性能彻底退化为 O(n)。这划清了两条边界:hash 一致性保正确性,hash 分布保复杂度。

当退化被用于制造服务端 CPU 耗尽时即成为哈希攻击(collision flooding)。C++ 标准库并未规定默认 std::hash<std::string> 必须具备随机化、加盐或抗碰撞能力(这属于平台与实现策略),因此工程上须按输入信任域选型:

输入来源典型场景风险与标准承诺工程应对策略
可信内部输入内部枚举、固定配置、编译期已知键分布可预期,无恶意碰撞构造使用默认 std::hash,保持字段一致并提前 reserve
不可信外部输入网络请求、用户上传、日志回放、多租户标准不承诺抗碰撞安全,易触发最坏 O(n)采用带随机种子/加盐 hasher、限制键数与键长、设超时或改用有序容器

排查顺序

定位哈希退化切忌只看总 size()(10 万元素均匀分布与集中在单桶开销完全不同),应依次排查:1) KeyEqual 与 Hash 是否覆盖同一组字段;2) load_factor() 是否逼近或超出 max_load_factor();3) 抽样观察 bucket_count() 与最大 bucket_size(n) 识别分布偏斜。

19.5 哈希表复杂度分析​

单次操作的真实成本取决于访问了多少候选元素。按 UnorderedAssociativeContainer 要求表,find(k)、insert、erase 为平均 O(1)、最坏 O(size),rehash(n) 为平均线性、最坏平方级。在贯穿材料 count_words 中,整体开销拆分为三部分:

  • 哈希计算:读取 key 内容计算 hash value,与 key 长度相关(如 std::string 需遍历字符)。
  • 定位与候选扫描:bucket 下标映射为 O(1),分布良好时每桶仅需常数次 KeyEqual 比较。
  • 节点构造与扩容:新 key 需分配节点并构造 std::pair<const std::string, int>;提前 reserve(words.size()) 将反复扩容的 rehash 成本合并前置。

工程分析还需严格区分“均摊”与“平均”,避免误判瓶颈来源:

复杂度概念核心依赖机制典型操作示例
均摊(Amortized)O(1)偶发高成本重建被大量常规操作分摊std::vector::push_back 扩容;哈希表插入触发的偶发 rehash
平均(Average)O(1)hash 分布分散 + 负载因子受控哈希表 find 扫描局部桶;单次插入定位目标桶链

源码走读与容器选型可按以下五步清单依次排查:

  1. 等价一致性:确认 KeyEqual 与 Hash 是否基于同一组字段。
  2. 容量策略:核对预期元素数、load_factor() 与 max_load_factor() 是否匹配。
  3. 冲突形状:检查最大 bucket_size(n) 是否远高于均值,排除集中输入。
  4. 失效边界:判断操作是否可能触发 rehash,以及保存的 iterator 是否跨过失效点。
  5. 输入风险:确认 key 是否来自不可信外部输入,决定是否需要加盐 hasher、规模上限或有序容器。

最小自检任务​

动手自检先独立判断

阅读下面的代码,回答三个问题:

  1. BadHash 是否破坏查找正确性?
  2. table.reserve(10000) 改变了容器内部什么状态?
  3. 循环结束后 saved 是否还可以安全地作为 iterator 使用(或与 table.end() 比较)?
#include <cstddef>
#include <string>
#include <unordered_map>
#include <vector>

struct BadHash {
std::size_t operator()(const std::string&) const {
return 0;
}
};

void build(const std::vector<std::string>& keys) {
std::unordered_map<std::string, int, BadHash> table;
table.reserve(10000);

auto saved = table.end();
for (const std::string& key : keys) {
auto [it, inserted] = table.emplace(key, 1);
if (inserted && saved == table.end()) {
saved = it;
}
}
}

本章知识点总结​

  • 定位与等价约束

    Hash 将 key 转为整数并压缩成 bucket index,KeyEqual 判定等价性;等价 key 必须产生相同 hash,两者须覆盖同一组字段。

  • 冲突与对象布局

    bucket array 将查找缩小到局部候选集;STL 普遍采用独立节点链(chaining)满足桶接口与引用稳定性,区别于连续槽位探测的 open addressing。

  • 负载与容量策略

    load_factor() 反映平均桶长,max_load_factor() 约束扩容阈值;reserve(n) 按预期元素数经由 rehash 预算桶数,合并批量插入扩容开销。

  • rehash 失效边界

    clear、rehash、reserve 与赋值使全表 iterator 失效,insert/emplace/operator[] 仅在触发 rehash 时失效;pointer/reference 仅随目标元素被 erase 失效。

  • 退化与输入风险

    低质量 Hash、过高负载或恶意同桶输入会将平均 O(1) 拖垮为 O(n) 线性扫描;标准 std::hash 不承诺抗碰撞,外部输入需加盐或限流。

  • 复杂度与均摊辨析

    find 的平均 O(1) 依赖分布与负载控制,而插入的 rehash 成本属于均摊 O(1);总成本还必须计入 key 哈希计算(如字符串长度)与节点构造。

  • 工程排查顺序

    按“等价一致性 → 容量策略 → 冲突偏斜(bucket_size(n))→ rehash 失效边界 → 输入信任域”五步定界,避免单看 size() 误判瓶颈。