Chapter 54: Mini Hash Table
哈希表把“通过 key 定位元素”的问题拆成两层：第一层用哈希值选择一个 bucket，第二层在该 bucket 的冲突集合中确认等价 key。本章实现一个最小 mini_hash_table<Key, T>，目标是让读者能追踪 insert、find、erase、rehash 背后的对象关系、内存责任、复杂度来源和 iterator 失效边界。
标准 std::unordered_map 的接口语义围绕 bucket、hash policy、lookup 和 modifier 展开。公开资料对 std::unordered_map 的描述集中在两个事实：元素按 key 的 hash 分配到 bucket，查找、插入和删除在平均情况下具有常数复杂度；等价 key 必须由 key_equal 判断，并要求等价 key 得到相同 hash。这个语义可以在 cppreference 的 std::unordered_map 页面 中回溯。Mini 实现采用常见的 separate chaining 形状：桶数组保存链表入口，节点保存元素和值，冲突元素挂在同一个 bucket 的单向链中。
本章的贯穿材料是下面这个教学简化实现。它省略 allocator traits、copy / move 构造、异常传播策略细节、node handle、heterogeneous lookup 和完整 iterator，只保留哈希表核心路径。每一节都会回到这段结构，解释一个操作如何维护 bucket、node、hash、元素数量和负载因子之间的不变量。
#include <cstddef>
#include <functional>
#include <memory>
#include <utility>
#include <vector>
template<class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>>
class mini_hash_table {
struct node {
std::pair<const Key, T> value;
std::size_t cached_hash;
node* next;
node(Key key, T mapped, std::size_t hash_value, node* next_node)
: value(std::move(key), std::move(mapped)),
cached_hash(hash_value),
next(next_node) {}
};
std::vector<node*> buckets_;
std::size_t size_ = 0;
float max_load_ = 1.0f;
Hash hash_;
KeyEqual equal_;
public:
using iterator = node*;
mini_hash_table() : buckets_(8, nullptr) {}
~mini_hash_table() {
clear_nodes();
}
std::pair<iterator, bool> insert(Key key, T mapped);
iterator find(const Key& key) const;
bool erase(const Key& key);
void rehash(std::size_t requested_bucket_count);
std::size_t size() const noexcept {
return size_;
}
std::size_t bucket_count() const noexcept {
return buckets_.size();
}
float load_factor() const noexcept {
return buckets_.empty()
? 0.0f
: static_cast<float>(size_) / static_cast<float>(buckets_.size());
}
private:
node* find_node(const Key& key, std::size_t hash_value) const;
void maybe_rehash_for(std::size_t next_size);
std::size_t min_bucket_count_for(std::size_t element_count) const noexcept {
return static_cast<std::size_t>(
static_cast<float>(element_count) / max_load_
) + 1;
}
std::size_t next_bucket_count(std::size_t requested) const noexcept {
std::size_t count = 8;
while (count < requested) {
count *= 2;
}
return count;
}
static std::size_t index_for(std::size_t hash_value, std::size_t bucket_count) noexcept {
return hash_value % bucket_count;
}
void clear_nodes() noexcept {
for (node*& head : buckets_) {
node* current = head;
while (current != nullptr) {
node* next = current->next;
delete current;
current = next;
}
head = nullptr;
}
size_ = 0;
}
};
这段代码已经暴露哈希表的核心判断顺序：先确定 bucket 数组是否存在，再用 hash 计算 bucket index，然后只在对应链表中比较 key，插入和删除只改变一条链以及元素数量，扩容时重建 bucket 到 node 的入口关系。读源码时也应按这个顺序检查，先看定位函数，再看节点所有权，再看修改操作的提交点，最后看 rehash 对外部位置对象的影响。
54.1 bucket array
Bucket array 是哈希表的第一层索引结构。它的元素类型在这个 mini 实现中是 node*，每一个槽位保存一条冲突链的头指针。给定一个 key，哈希表先计算 hash_(key)，再把哈希值映射成 0 <= index < bucket_count() 的数组下标，最终只访问 buckets_[index] 这一条链。
这个结构把全表扫描拆成“数组定位 + 局部链表扫描”。如果有 8 个 bucket，哈希值分别映射到 0 到 7 的槽位，相同槽位中的元素形成冲突集合。平均查找成本来自冲突链长度；桶数组越稀疏，平均链长越短，空间开销越高。哈希表的工程判断因此始终围绕三件事：bucket 数量、元素数量、哈希分布。
buckets_ 只保存链表入口，元素对象存放在独立分配的 node 中。这个设计带来一个直接后果：rehash 时通常移动 node 指针和 next 指针，元素对象的地址可以保持稳定；iterator 仍然会失效，因为 iterator 的遍历路径依赖 bucket 入口和链表连接。标准 std::unordered_map 的失效规则也体现了这一区分：rehash 和 reserve 会使 iterator 失效，指向元素的 pointer / reference 通常只在对应元素被 erase 时失效。
下面的 Mermaid 图只表达本章 mini 实现的对象关系。图中的 bucket 数组负责入口，node 负责元素和下一跳，size_ 负责记录元素数量；它们共同形成哈希表不变量。
图中最关键的路径是 key → hash value → bucket index → bucket slot → node chain。find 走这条路径只读取结构，insert 走完路径后可能把新 node 挂到链头，erase 走完路径后断开某一个 node，rehash 会重算所有 node 的 bucket index 并改写链表入口。
Mini 实现使用 % bucket_count 作为定位方式。常见实现也可能使用 2 的幂 bucket 数，并用 hash_value & (bucket_count - 1) 取得下标。取模和掩码都只是把哈希值压缩到数组范围；差异在于掩码依赖 bucket 数为 2 的幂，并且更依赖 hash 低位的分布质量。读源码时看到 % 或 &，应把注意力放在 bucket count 策略和 hash 分布假设上。
54.2 node 结构
Node 是哈希表的元素载体。本章 mini 实现的 node 保存三类状态：value 保存 std::pair<const Key, T>，cached_hash 保存已经计算过的哈希值，next 连接同一个 bucket 中的下一个节点。value 代表用户可见元素，next 代表冲突链结构，cached_hash 代表实现层面的优化和异常边界。
value 中的 key 使用 const Key，对应关联容器的核心约束：元素进入容器后，key 决定它所属的 bucket 和等价关系。允许用户原地改 key 会破坏哈希表定位路径，因为旧 bucket 中的 node 可能已经无法用新 key 找到。mini 实现通过 std::pair<const Key, T> 把这个约束写进类型系统。
next 指针把同一个 bucket 中的 node 串成单向链表。插入链头时，新 node 的 next 指向旧头节点，再把 buckets_[index] 改成新 node。删除中间节点时，前驱节点的 next 改成被删节点的后继。这个设计让单个 bucket 内的插入和删除只修改常数个指针；整体成本仍然取决于定位到目标 node 前需要扫描多少个冲突节点。
cached_hash 是一个常见实现选择。它可以减少重复调用 hash 函数，并让 rehash 在重新分桶时直接使用旧哈希值。如果 hash 函数开销高，缓存能降低查找和扩容成本；如果 node 数量很大，缓存字段会增加每个节点的空间占用。工程上需要把 hash 计算成本、节点内存占用和 rehash 异常边界放在一起判断。
节点所有权由容器持有。mini 实现中 new node(...) 创建节点，erase 和析构路径调用 delete 销毁节点。完整 STL 实现通常通过 allocator 分配 node 存储，再用 allocator traits 构造和销毁 value_type。本章用 new / delete 简化材料，但责任关系相同：容器负责分配节点、构造元素、断链、销毁元素和释放节点内存。
54.3 hash
Hash 路径由三部分组成：Hash 把 key 转成 std::size_t，定位函数把哈希值转成 bucket index，KeyEqual 在冲突链中确认 key 等价。前两步负责缩小搜索范围，第三步负责最终语义判断。哈希值相同的 key 会落到同一条链；哈希值不同的 key 也可能因为取模或掩码后得到同一个 bucket index。
哈希表的等价规则由 KeyEqual 决定。对于 unique-key 表，equal_(a, b) 为 true 表示这两个 key 对应同一个元素位置。这个规则要求 Hash 和 KeyEqual 保持一致：当 equal_(a, b) 为 true 时，hash_(a) 和 hash_(b) 应得到相同值。这个约束使查找能先用 hash 定位 bucket，再在该 bucket 中比较等价 key。
下面这个 helper 展示了 mini 实现中查找节点的核心路径。它先计算 bucket index，再扫描链表；比较时先看 cached hash，再调用 equal_。cached hash 的比较只是快速过滤，最终语义仍由 equal_ 决定。
template<class Key, class T, class Hash, class KeyEqual>
auto mini_hash_table<Key, T, Hash, KeyEqual>::find_node(const Key& key,
std::size_t hash_value) const
-> node* {
const std::size_t index = index_for(hash_value, buckets_.size());
node* current = buckets_[index];
while (current != nullptr) {
if (current->cached_hash == hash_value && equal_(current->value.first, key)) {
return current;
}
current = current->next;
}
return nullptr;
}
这段代码说明了 hash 和 equality 的分工。cached_hash == hash_value 可以快速跳过大量候选节点，但 hash 碰撞仍然存在；equal_ 才能确认 key 是否代表同一个元素。工程上自定义 key 类型时，应把 Hash 和 KeyEqual 成对设计。只修改其中一个，哈希表可能出现插入成功后查找失败、重复等价 key、erase 找不到元素等问题。
定位函数也影响性能模型。hash_value % bucket_count 通常会进行除法或取模计算，成本高于位掩码；位掩码要求 bucket 数保持 2 的幂，并要求 hash 函数在低位也有足够分布。标准接口关注语义和复杂度，不绑定具体分桶策略；源码阅读时应把分桶策略看成实现选择。
54.4 insert
insert 的主路径必须按固定顺序提交：先计算 hash，检查等价 key，再根据负载因子决定是否 rehash，重新定位 bucket，构造 node，最后挂链并增加 size_。这个顺序保护两个不变量：unique-key 表中没有重复等价 key，外部可见的元素数量只在节点已经进入表后增加。
下面代码是本章 mini 实现的插入路径。参数按值传入，便于把 key 和 mapped value 移入 node。代码在 rehash 后重新计算 bucket index，因为 bucket 数可能已经变化。
template<class Key, class T, class Hash, class KeyEqual>
auto mini_hash_table<Key, T, Hash, KeyEqual>::insert(Key key, T mapped)
-> std::pair<iterator, bool> {
const std::size_t hash_value = hash_(key);
if (node* existing = find_node(key, hash_value)) {
return {existing, false};
}
maybe_rehash_for(size_ + 1);
const std::size_t index = index_for(hash_value, buckets_.size());
std::unique_ptr<node> created(
new node(std::move(key), std::move(mapped), hash_value, buckets_[index])
);
node* inserted = created.get();
buckets_[index] = created.release();
++size_;
return {inserted, true};
}
std::unique_ptr<node> 在这里承担临时所有权。new node(...) 成功后，节点还没有进入 bucket 链；如果后续在提交前发生异常，unique_ptr 会释放节点。提交点是 buckets_[index] = created.release()，这行之后 node 由容器链表拥有，size_ 随后更新。这个顺序让“节点可达”和“元素数量增加”保持一致。
maybe_rehash_for(size_ + 1) 放在构造 node 之前，能让扩容失败时表保持原状态。它也减少了“新节点构造成功后又触发 rehash”的清理分支。完整实现还要处理 allocator、构造异常、hash 函数异常和强异常安全策略；本章的简化版本保留了最重要的提交顺序。
插入链头会改变同一个 bucket 内的遍历顺序。无序关联容器的全局遍历顺序本来就由实现维护，用户应把遍历顺序视为实现维护的结果，业务逻辑只依赖 key 查询语义。更重要的工程结论是：插入若触发 rehash，已有 iterator 会失效；插入若没有触发 rehash，已有 node 通常保持在原链中，指向已有元素的引用和指针保持可用。
54.5 find
find 是哈希表最能体现平均常数复杂度的操作。它只做三件事：计算 hash，定位 bucket，扫描该 bucket 的冲突链。平均成本接近常数的前提是 hash 分布足够均匀，并且负载因子受控；当大量 key 聚集到同一个 bucket，find 会退化成链表线性扫描。
下面代码展示一个最小 find 接口。它复用 find_node，返回节点指针作为教学版 iterator 替身。完整容器会返回 iterator，并用 end iterator 表示未找到。
template<class Key, class T, class Hash, class KeyEqual>
auto mini_hash_table<Key, T, Hash, KeyEqual>::find(const Key& key) const -> iterator {
const std::size_t hash_value = hash_(key);
return find_node(key, hash_value);
}
find 的读取路径只观察 bucket array、node 链、元素数量和负载因子，因此它保持 iterator 有效。它仍会调用用户提供的 Hash 和 KeyEqual，所以它的实际成本包含用户函数成本。对于字符串 key、复合 key 或自定义 hash，hash 计算和 equality 比较可能成为热路径中的主要开销。
查找结果的正确性取决于 key 在容器内保持稳定。std::pair<const Key, T> 限制用户通过元素引用改 key；如果实现保存可变 key，或者通过不安全手段修改 key，bucket 位置和等价关系会失配。此时相同对象可能留在旧 bucket 中，之后用新 key 查找会落到另一个 bucket，结果无法反映真实存储状态。
读源码时可以按四个检查点判断一个哈希查找是否正确：hash 是否只由 key 参与，index 是否落在 bucket 数组范围内，链表扫描是否覆盖目标 bucket 的所有节点，最终等价判断是否调用容器保存的 key_equal。这四点任何一处出错，都会把哈希表从“局部扫描”变成“错误定位”。
54.6 erase
erase 在结构上比 find 多了一个前驱节点。单向冲突链中删除当前节点时，需要知道谁指向它：可能是 bucket 头指针，也可能是前驱节点的 next。因此 erase 的扫描状态通常包含 previous 和 current 两个指针。
下面代码展示按 key 删除一个元素的路径。命中目标节点后，代码先让链表绕过当前节点，再销毁节点并减少 size_。断链先于销毁，保证 bucket 链不会保留悬垂指针。
template<class Key, class T, class Hash, class KeyEqual>
bool mini_hash_table<Key, T, Hash, KeyEqual>::erase(const Key& key) {
const std::size_t hash_value = hash_(key);
const std::size_t index = index_for(hash_value, buckets_.size());
node* previous = nullptr;
node* current = buckets_[index];
while (current != nullptr) {
if (current->cached_hash == hash_value && equal_(current->value.first, key)) {
node* next = current->next;
if (previous == nullptr) {
buckets_[index] = next;
} else {
previous->next = next;
}
delete current;
--size_;
return true;
}
previous = current;
current = current->next;
}
return false;
}
删除 bucket 头节点和删除中间节点是同一个不变量的两个分支：被删除节点从链表入口集合中消失，其余节点保持原有相对连接。previous == nullptr 表示 bucket slot 本身持有当前入口；否则前驱节点持有当前入口。这个判断是单向链 erase 的关键点。
delete current 会依次调用 node 析构和 value 析构，再释放节点内存。对于包含资源的 mapped value，析构责任在这里完成。完整 STL 容器会把这一步拆成 allocator traits 的 destroy 和 deallocate；从工程含义看，erase 仍然承担“断开结构引用、结束元素生命周期、释放节点存储、更新元素数量”的责任链。
Erase 的失效边界比 rehash 小。它使被删除元素对应的 iterator、pointer 和 reference 失效；其他元素位于独立 node 中，通常保持地址稳定。这个性质是节点式 unordered 容器的重要工程特征：结构局部修改集中在一条 bucket 链上，元素存储位置不随普通 erase 大范围变化。
54.7 rehash
rehash 改变 bucket 数组的大小，并把所有节点重新分配到新的 bucket 中。它的核心动作是“重建入口关系”，通常无需重新构造用户元素。节点对象仍然是原来的 node，只是 next 指针和 bucket 头指针发生变化。
下面代码展示本章 mini 实现的 rehash。它先分配新的 bucket array，然后遍历旧 bucket，把每个 node 插入到新 bucket 的链头。cached_hash 让这个过程可以直接计算新 index，无需再次调用用户 hash 函数。
template<class Key, class T, class Hash, class KeyEqual>
void mini_hash_table<Key, T, Hash, KeyEqual>::rehash(std::size_t requested_bucket_count) {
const std::size_t min_needed = min_bucket_count_for(size_);
const std::size_t new_count = next_bucket_count(
requested_bucket_count > min_needed ? requested_bucket_count : min_needed
);
if (new_count == buckets_.size()) {
return;
}
std::vector<node*> next_buckets(new_count, nullptr);
for (node*& old_head : buckets_) {
node* current = old_head;
while (current != nullptr) {
node* following = current->next;
const std::size_t index = index_for(current->cached_hash, next_buckets.size());
current->next = next_buckets[index];
next_buckets[index] = current;
current = following;
}
old_head = nullptr;
}
buckets_.swap(next_buckets);
}
next_buckets 的分配发生在任何 node 改链之前。分配失败时，旧表保持原状。分配成功后，后续步骤只改写指针和计算 index；在本章简化实现中这些步骤为 noexcept。如果实现省略 cached hash，rehash 期间重新调用用户 hash 函数，异常安全处理会更困难，因为一部分节点可能已经迁移到新 bucket 中。
min_bucket_count_for(size_) 来自负载因子约束。公开文档对 std::unordered_map::rehash 的语义说明是：新的 bucket 数至少满足请求值，并满足 n >= size() / max_load_factor()，然后把元素放入新的 bucket。这个规则可以在 cppreference 的 rehash 页面 回溯。Mini 实现也应保持同样的方向：扩容结果必须容纳当前 size 和最大负载因子。
Rehash 的复杂度通常与元素数量线性相关，因为每个 node 都要被访问并重新挂入新 bucket；在极端碰撞和实现策略影响下，标准容器可能给出更保守的最坏情况复杂度。工程上应把 rehash 看成一次集中结构维护成本。频繁插入大量元素前，提前 reserve 或 rehash 可以把多次扩容压缩成更少的结构重建。
Iterator 失效是 rehash 的核心外部后果。即使 node 地址保持稳定，iterator 的“下一个元素”关系也可能依赖 bucket 顺序和链表连接；rehash 后这些关系已经改变。指向元素的引用和指针在节点未销毁时仍可用，这是节点所有权和遍历位置之间的边界。
54.8 load_factor
load_factor 是元素数量与 bucket 数量的比值，计算方式是 size() / bucket_count()。它表达全表平均压力，和单个 bucket 的实际链长属于两个观察层级。公开文档中 std::unordered_map::load_factor 返回每个 bucket 的平均元素数量，这一点可以在 cppreference 的 load_factor 页面 回溯。
Mini 实现用 max_load_ 控制扩容触发点。当插入后的期望元素数超过 max_load_ * bucket_count 时，表需要增加 bucket 数，以压低平均链长。下面是一个可读的触发函数。next_bucket_count 可以选择素数序列，也可以选择 2 的幂序列；选择哪一种取决于定位函数和 hash 分布策略。
template<class Key, class T, class Hash, class KeyEqual>
void mini_hash_table<Key, T, Hash, KeyEqual>::maybe_rehash_for(std::size_t next_size) {
if (buckets_.empty()) {
buckets_.assign(8, nullptr);
}
const float projected = static_cast<float>(next_size)
/ static_cast<float>(buckets_.size());
if (projected > max_load_) {
rehash(buckets_.size() * 2);
}
}
负载因子解释的是平均成本。假设 1024 个元素分布在 1024 个 bucket 中，平均负载因子是 1；如果 hash 分布均匀，多数 bucket 的链很短。若 hash 函数把这些 key 大量映射到同一个 index，平均值仍然可能看起来正常，但热点 bucket 的查找会退化。性能排查时应同时看 load_factor、bucket_count、bucket_size(index) 和 key 分布。
max_load_factor 的取值体现空间与时间的取舍。较低的阈值会增加 bucket array 空间占用，减少平均链长；较高的阈值会降低 bucket array 空间占用，增加冲突链扫描成本。节点式哈希表还包含每个 node 的指针字段、可能的 cached hash、分配元数据和内存碎片，因此实际内存成本高于 bucket_count * sizeof(node*) + size * sizeof(value_type) 这个粗略估算。
本章 mini 哈希表的最终判断顺序可以固定为：先确认 key 等价规则和 hash 一致性，再看 bucket 定位策略，然后看 node 所有权和链表不变量，接着检查 insert / erase 的提交顺序，最后用负载因子与 rehash 规则解释平均复杂度和失效边界。这个顺序能迁移到 std::unordered_map、std::unordered_set 和多数节点式哈希表源码阅读中。
最小自检任务
阅读下面这段操作序列，判断每一步后哈希表结构如何变化，并说明哪些外部位置对象会失效。假设 index_for(hash, bucket_count) 使用取模，初始 bucket 数为 4，max_load_ = 1.0f，并且 hash(A)=1、hash(B)=5、hash(C)=2、hash(D)=9。四个 key 两两不等价。
mini_hash_table<Key, int> table;
table.insert(A, 10);
table.insert(B, 20);
auto saved = table.find(A);
table.insert(C, 30);
table.erase(B);
table.insert(D, 40);
要求回答三点：第一，A、B、C、D 分别会落入哪个 bucket；第二，erase(B) 需要修改哪个指针；第三，如果 insert(D) 触发 rehash，判断 saved 代表的位置对象作为 iterator 使用的边界。
答案要点
初始 bucket 数为 4 时，A 的 index 是 1 % 4 = 1，B 的 index 是 5 % 4 = 1，二者进入同一个 bucket 的冲突链。C 的 index 是 2 % 4 = 2，进入另一个 bucket。插入链头策略下，B 插入后通常位于 bucket 1 链头，A 位于 B->next。
erase(B) 命中 bucket 1 的链头节点，所以需要把 buckets_[1] 改成 B->next，也就是指向 A。随后销毁 B 节点并减少 size_。被删除元素 B 的 iterator、pointer 和 reference 失效；A 和 C 的 node 未销毁，指向它们的引用和指针仍对应原元素。
D 的旧 bucket index 在 4 个 bucket 下是 9 % 4 = 1。如果插入 D 前或插入过程中触发 rehash，新的 bucket 数改变后必须重新计算 index，例如 8 个 bucket 下 D 的 index 是 9 % 8 = 1，A 的 index 也是 1 % 8 = 1，C 的 index 是 2 % 8 = 2。Rehash 会重建 bucket 入口和链表连接，saved 作为 iterator 应视为失效；如果它只是教学实现中的裸 node 指针，且 A 没有被 erase，指向的元素对象仍存在，这个事实只说明元素对象仍存在，标准 iterator 的遍历语义已经失效。
本章知识点总结
- 桶数组：bucket array 保存冲突链入口，哈希值经过定位函数后选择一个 bucket。
- 节点所有权：node 保存用户元素、下一跳指针和可选 cached hash，容器负责节点分配、销毁和释放。
- 等价规则：
KeyEqual决定 key 是否代表同一个元素，等价 key 应得到相同 hash。 - 定位路径：查找先计算 hash，再定位 bucket，最后只在该 bucket 的冲突链中比较 key。
- 插入提交：insert 应先查重和处理扩容，再构造节点，最后挂链并更新元素数量。
- 删除断链：erase 通过前驱指针或 bucket 头指针绕过目标 node，再销毁节点并减少 size。
- 扩容重挂：rehash 分配新 bucket array，并把所有现有 node 按 cached hash 重新挂入新桶。
- 失效边界：rehash 会使 iterator 失效，普通 erase 只使被删除元素对应的位置对象失效。
- 负载因子：load factor 是元素数量除以 bucket 数量，用来估计平均链长和扩容压力。
- 性能判断：哈希表平均常数成本依赖 hash 分布、负载因子和用户 hash / equality 的实际开销。
- 空间成本：节点式哈希表的内存开销包含 bucket 指针数组、node 指针、cached hash、元素对象和分配元数据。
- 阅读顺序：读哈希表源码应依次检查 hash 一致性、bucket 定位、node 所有权、修改提交点和 rehash 规则。