Skip to main content

Chapter 19: Hash Table Foundations

哈希表要解决的问题，是在没有全局有序关系的前提下，用一个 key 快速定位到可能存放元素的位置。本章围绕一个贯穿材料展开：用 std::unordered_map<std::string, int> 统计字符串出现次数。读完本章后，读者应能从一个 find、insert 或 reserve 调用出发，追踪 key 如何进入 hash function，hash value 如何落到 bucket，冲突链如何被扫描，rehash 如何改变桶数组，并判断平均常数复杂度在什么输入条件下成立。

C++ 标准库的 unordered_map、unordered_set、unordered_multimap 和 unordered_multiset 从 C++11 起提供无序关联容器。以 std::unordered_map 为例，标准接口暴露 hash function、key equality predicate、bucket interface 和 hash policy；cppreference 的 std::unordered_map 页面 将其描述为按 key 的 hash 组织到 buckets 中，并给出查找、插入、删除的平均常数复杂度。这里的平均常数来自两个前提：hash value 分布足够分散，单个 bucket 里的候选元素数量受负载策略控制。

本章讨论的是哈希表基础结构本身，后续 Chapter 20 再进入 unordered_map / unordered_set 的具体接口路径。本章先建立源码阅读时的对象图：容器对象保存 bucket array、元素节点数量、hash function、key_equal 和 max_load_factor；每个元素节点保存 value，并通过某种冲突处理策略被 bucket 定位。常见 STL 实现形状更接近 bucket array + node chain；open addressing 会作为对比策略出现，用来说明冲突处理会怎样改变节点布局、删除成本和 iterator 行为。

下面的代码提供贯穿材料。正文后续每节都会回到这段代码，追踪同一个 key 在哈希表中的运行路径。

#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 已存在，容器需要定位已有节点并修改 int；如果 word 缺席，operator[] 需要构造一个新节点，再把计数从默认值递增。两条路径都要先经过 hash function、bucket 定位和 key_equal 比较。

19.1 hash function、hash value 与 bucket 定位​

Hash function 是把 key 映射成整数 hash value 的函数对象。在标准库接口中，它通常由模板参数 Hash 表示，默认值是 std::hash<Key>。hash value 仍处在全局整数空间；容器必须把它压缩到当前 bucket array 的有效范围内，得到一个 bucket index。

对贯穿材料中的 word，一次查找可以抽象成三个动作：先调用 hash_function()(word) 得到 std::size_t 类型的 hash value，再用当前 bucket 数量计算 bucket index，随后只在对应 bucket 中比较候选元素。C++ 标准没有要求实现必须使用 % bucket_count，常见实现可能使用质数桶数量加取模，也可能使用 2 的幂桶数量加 bit mask。源码阅读时应识别“hash value 到 bucket index 的压缩动作”，少依赖某一种算术形式。

这个过程可以用下图定位。图里的 bucket_index 是容器内部定位结果，key_equal 只在候选节点之间确认语义相等。

图中最容易误判的是 hash value 与 key equality 的关系。hash value 负责缩小搜索范围，key_equal 负责确认两个 key 是否等价。对于标准无序关联容器，等价 key 必须产生相同 hash value；UnorderedAssociativeContainer 要求也把 hash function 与 key equality predicate 放在同一组约束中说明。工程上这意味着自定义 key 时，Hash 与 KeyEqual 必须按同一组字段判断对象。

下面的示例展示一个一致的自定义 key。operator== 使用 id 和 region，hash function 也组合这两个字段；这样等价对象会进入同一 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>;

这段代码证明的规则是：hash table 的正确性先依赖等价关系的一致性，再依赖 hash 分布质量。分布差会带来性能问题；等价 key 的 hash 不一致会直接破坏查找语义。读 STL 源码时，hasher 和 key_equal 不应分开理解，它们共同决定“一个 key 应该去哪一个 bucket，以及 bucket 内哪些节点算同一个 key”。

19.2 bucket array、collision、chaining 与 open addressing​

Bucket array 是哈希表的一级索引结构。它保存多个 bucket 入口，每个 bucket 对应一组 hash value 压缩后落到同一位置的元素。collision 指不同 key 被定位到同一个 bucket 的情况，原因可能是 hash function 产生相同 hash value，也可能是不同 hash value 被 bucket 数量压缩到同一个下标。

贯穿材料中的 freq[word] 如果定位到一个已有元素较多的 bucket，容器还需要扫描 bucket 内候选节点，并用 key_equal 与 word 比较。候选节点越多，一次查找越接近线性扫描。哈希表平均常数时间的关键就在这里：全表元素数量需要和 bucket 数量一起观察，单个 bucket 的候选数量持续增长才会提高单次操作成本。

Chaining 是常见 STL 无序容器实现形状：bucket array 的每个位置指向一段节点链，节点通常独立分配，节点之间通过 next 指针连接。插入新元素时，容器先定位 bucket，再分配并构造节点，然后把节点挂入对应链。查找时，容器只扫描该 bucket 的链。删除时，容器修改链上的前驱指针，销毁目标节点，并释放节点存储。

Open addressing 是另一类哈希表策略：元素直接存放在表格槽位中，冲突发生后按探测序列寻找下一个可用槽位，例如 linear probing、quadratic probing 或 double hashing。它可以提升内存局部性，因为元素更集中；同时它把删除、扩容和探测序列维护变得更敏感。STL unordered_* 的 bucket interface、local iterator 和节点式稳定性要求，使源码阅读时更常见的对象图是 bucket array + node，而开放寻址主要作为工程对比。

从内存布局看，chaining 与 open addressing 的差异可以按同一组维度判断。

维度chainingopen addressing
元素位置节点独立分配，bucket 保存入口元素存放在表格槽位中
冲突路径扫描 bucket 链沿探测序列扫描槽位
删除动作断开节点并销毁元素需要维护空槽、墓碑或重新整理探测路径
迭代器和引用节点地址更容易保持稳定扩容搬移通常影响更多位置对象
cache locality链表指针跳转增加 cache miss连续槽位通常更友好

这张表服务于源码阅读时的第一轮识别。看到 bucket 数组、单独节点、next 指针、local iterator，就按 chaining 的路径阅读；看到连续槽位、控制字节、probe sequence、tombstone，就按 open addressing 的路径阅读。标准库无序容器的公开 bucket 操作包括 bucket_count()、bucket(key)、bucket_size(n)、begin(n) 和 end(n)，这些接口会把读者引向“先定位 bucket，再处理局部候选集合”的结构。

在 freq.reserve(words.size()) 之后，freq 通常已经拥有足够 bucket。后续 ++freq[word] 插入节点时，如果没有触发 rehash，已有元素的节点地址更容易保持稳定；如果扩容触发 rehash，bucket array 会重建，节点会重新分配到 bucket。这里的“重新分配到 bucket”通常是节点链重新挂接，value 对象未必被重新构造；具体动作属于实现策略，正文只依赖标准层面的 iterator 失效和复杂度承诺。

19.3 load factor、max_load_factor、rehash 与 reserve​

Load factor 是元素数量与 bucket 数量之间的比例，标准接口 load_factor() 返回平均每个 bucket 承载的元素数量。max_load_factor() 表示容器试图维持的最大平均负载。负载因子越高，平均 bucket 链越长；负载因子越低，bucket array 占用的空间越多。

贯穿材料里先调用 freq.reserve(words.size())，目的就是在批量插入前让容器准备足够 bucket。对标准无序关联容器，reserve(n) 的语义可理解为“为至少 n 个元素准备容量”，它等价地通过 rehash(ceil(n / max_load_factor())) 一类策略调整 bucket 数量；UnorderedAssociativeContainer 的 hash policy 表列出了 load_factor()、max_load_factor()、rehash(n) 和 reserve(n) 的关系。

rehash(n) 的直接对象是 bucket 数量。调用后，容器要保证 bucket 数量同时满足当前元素数量与 max_load_factor() 的约束，并且至少达到调用者请求的 bucket 数。它会重新建立 hash table：遍历已有元素，根据当前 bucket 数量重新计算 bucket index，再挂入新的 bucket array。

reserve(n) 的直接对象是预期元素数量。调用者在批量插入前知道元素规模时，用 reserve 表达更自然；源码中它最终仍要落到 bucket 数量决策。对贯穿材料来说，words.size() 只是插入次数上界，实际 unique word 数量可能更小。即使如此，提前 reserve 仍能降低插入过程中多次 rehash 的概率。

下面的代码把容量策略放到可观察接口上。它不依赖具体实现，只观察标准接口公开的 bucket 与 load factor 状态。

#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 数量由实现选择，调用者不应假定精确等于 1000。第二，max_load_factor(1.0f) 是策略提示，容器会用它约束后续增长；它不会让所有 bucket 都恰好含有一个元素，因为 hash 分布仍由 key 集合和 hash function 决定。

Rehash 对 iterator 的影响必须单独记住。以 std::unordered_map 为例，cppreference 的 iterator invalidation 表说明 clear、rehash、reserve 和赋值会使 iterator 失效，insert / emplace / operator[] 在触发 rehash 时才会使 iterator 失效；同一表也说明指向元素的 references 和 pointers 通常只在对应元素被 erase 时失效。工程判断顺序是：先判断操作是否可能改变 bucket array，再判断 iterator 是否跨越 rehash 边界，再判断手里保存的是 iterator、pointer 还是 reference。

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

哈希退化指大量元素集中到少量 bucket，使查找、插入和删除从平均常数时间滑向线性扫描。退化的直接表现是某些 bucket 的 bucket_size(n) 异常大，单次 find 需要比较许多候选 key。它可能来自低质量 hash function、错误的等价关系、过高的 load factor，也可能来自被刻意构造的输入集合。

下面的示例构造了一个性能退化的 hash function。它始终返回同一个 hash value，因此所有 key 都落入同一个 bucket 路径。代码用于解释退化现象；工程代码应为 key 选择能覆盖判等字段且分布合理的 hash function。

#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] 一类操作时，hash 定位只能把所有元素送入同一个 bucket。容器仍能保持语义正确，因为 key_equal 会在链上找到等价 key；性能承诺会退到线性扫描。这个例子把正确性和性能边界分开：hash 一致性保障可查到元素，hash 分布保障候选集合规模受控。

哈希攻击是退化输入的安全版本：攻击者了解或推测服务端使用的 hash 策略后，提交大量会落入相同 bucket 的 key，让服务器在插入、查找或解析请求参数时消耗大量 CPU。C++ 标准库默认 std::hash<std::string> 是否带随机化、盐值或抗碰撞设计，属于实现与平台策略；标准层面不承诺密码学安全，也不承诺面对敌意输入时维持常数时间。

工程上应按输入来源判断风险。内部枚举、固定配置项、编译期已知键集合通常可使用普通 std::hash。来自网络、用户上传、日志回放或跨租户环境的 key 集合，需要把 hash 策略纳入安全边界：可以使用带随机种子的 hasher、限制单次请求元素数量、控制最大输入长度、设置超时或改用能提供更稳定最坏情况的有序结构。

哈希退化排查时，先看 key_equal 与 hash 是否使用同一组字段，再看 load_factor() 与 max_load_factor()，再抽样查看 bucket_count()、最大 bucket_size(n) 和 key 分布。这个顺序能把语义错误、容量策略和输入分布分开。只看总元素数量会掩盖问题，因为 10 万个元素均匀分布与 10 万个元素集中在一个 bucket 的成本完全不同。

19.5 哈希表复杂度分析​

哈希表复杂度应从单次操作访问了多少候选元素来分析。一次 find(key) 的主路径是：计算 hash value，定位 bucket，扫描该 bucket 的候选节点，并用 key_equal 比较。hash 计算通常与 key 长度相关，例如字符串 hash 需要读取字符；bucket 定位通常是常数；候选节点数量决定平均复杂度与最坏复杂度的差距。

标准无序关联容器的 find、insert、erase 等操作一般给出平均 O(1)、最坏 O(n) 的复杂度边界。UnorderedAssociativeContainer 要求表对 find(k) 给出平均 O(1)、最坏 O(size) 的说明，对 rehash(n) 给出平均线性、最坏平方级的说明。这些边界说明哈希表的快来自“候选集合小”，退化时仍要面对线性扫描。

对贯穿材料中的 count_words，整体成本可以分成三部分。第一部分是对每个字符串计算 hash，成本与字符串长度有关。第二部分是每次定位 bucket 和扫描候选节点，平均分布良好时接近每个 key 常数次比较。第三部分是插入新 key 时分配节点、构造 std::pair<const std::string, int>，并在触发 rehash 时重建 bucket array。reserve(words.size()) 的作用是把第三部分中的多次增长成本尽量前置。

复杂度分析还要区分“均摊”和“平均”。std::vector::push_back 常说均摊 O(1)，主要来自扩容成本被摊到多次插入上；哈希表查找的平均 O(1)更多依赖 hash 分布和负载因子。哈希表插入同时包含这两层因素：单次 bucket 扫描受分布影响，偶发 rehash 成本可以被批量插入摊薄。把这两层混在一起，会误判性能瓶颈。

源码阅读和工程选型时，可以使用下面的判断顺序。

  • 先确认 key 的等价关系：KeyEqual 使用哪些字段，Hash 是否覆盖同一组字段。
  • 再确认容量策略：当前 load_factor()、max_load_factor() 和预计元素数量是否匹配。
  • 再确认冲突形状：最大 bucket size 是否远高于平均值，是否存在集中输入。
  • 再确认操作边界：当前操作是否会触发 rehash，保存的 iterator 是否跨越失效点。
  • 再确认输入风险：key 是否来自敌意输入，是否需要随机化 hasher、输入规模限制或有序容器。

这个顺序把正确性、容量、冲突、失效和安全分开处理。对于 Chapter 20 的具体容器接口，读者可以继续用它判断 operator[]、insert、find、erase 和 reserve 的真实成本。

最小自检任务​

阅读下面的代码，判断三件事：BadHash 是否破坏查找正确性；table.reserve(10000) 改变了什么对象；循环结束后 saved 是否可以继续作为 iterator 使用。

#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;
        }
    }
}

答案要点​

BadHash 使所有 key 进入同一个 bucket 路径，但没有直接破坏查找正确性；默认 std::equal_to<std::string> 仍会在候选节点中确认等价 key。它破坏的是分布质量，查找和插入会退化成对同一 bucket 链的线性扫描。

table.reserve(10000) 改变的是 hash policy 下的 bucket array 规模决策。调用者表达“准备至少容纳 10000 个元素”的需求，容器会根据 max_load_factor() 选择 bucket 数量，并重建 hash table。最终 bucket 数量由实现决定。

saved 是 iterator。循环中的 emplace 如果触发 rehash，已有 iterator 会失效；失效后继续拿它和 table.end() 比较也失去有效语义。前置 reserve(10000) 只能在实际插入规模不超过策略容量时降低 rehash 概率。稳妥判断要比较 keys 的 unique 数量、当前 max_load_factor() 和 bucket 策略；保存 pointer 或 reference 的失效边界与 iterator 不同，erase 对应元素时才会失效。

本章知识点总结​

  • 哈希定位：hash function 把 key 转成 hash value，容器再把 hash value 压缩成 bucket index。
  • 等价约束：等价 key 必须产生相同 hash value，Hash 与 KeyEqual 要围绕同一组字段设计。
  • bucket 角色：bucket array 是哈希表的一级索引，它把全表查找缩小到局部候选集合。
  • 冲突成本：collision 会增加 bucket 内候选数量，单次操作成本取决于需要比较多少候选 key。
  • 链式结构：常见 STL 无序容器实现形状使用 bucket array 加节点链，节点独立分配并通过链表处理冲突。
  • 开放寻址：open addressing 把元素放进表格槽位，通过探测序列处理冲突，局部性和删除边界与 chaining 不同。
  • 负载因子：load_factor() 表示平均每个 bucket 的元素数量，max_load_factor() 影响容器扩容策略。
  • reserve 语义：reserve(n) 表达预期元素数量，容器据此选择 bucket 数量并可能触发 rehash。
  • rehash 后果：rehash 重建 bucket array，并使无序容器 iterator 失效。
  • 退化条件：低质量 hash、过高负载和集中输入会让平均常数操作退化成线性扫描。
  • 攻击边界：面对敌意输入时，普通 std::hash 的标准语义不提供抗碰撞安全承诺。
  • 分析顺序：先查等价关系，再查容量策略，再查冲突分布，再查 iterator 失效，再查输入风险。