Chapter 54: Mini Hash Table
核心问题与阅读主线
哈希表将 key 查找拆为“哈希选桶 + 桶内判等”两层索引,其工程难点在于同时守住均摊 O(1) 性能、节点所有权以及扩容时的迭代器失效边界。本章通过最小链地址法实现 mini_hash_table<Key, T>,直接剖析 insert、find、erase、rehash 与负载因子控制的核心路径。
依据 cppreference 的 std::unordered_map 页面,标准无序映射的核心契约有两条:元素按哈希分桶以实现平均 O(1) 的查找、插入与删除,且由 key_equal 判定等价的 key 必须产生相同 hash。下文采用经典的链地址法(separate chaining):桶数组存链表入口,冲突元素挂在同一 bucket 的单向链中。
全章共用代码样本(下文各节持续拆解)
本章的贯穿材料是一个最小链地址法实现 mini_hash_table<Key, T>(仅保留核心分桶与节点路径,省略 allocator 与拷贝移动等外围接口):
#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;
}
};
该骨架锁死了全表的核心不变量:buckets_ 仅存各冲突链入口指针,node 独占元素内存与 cached_hash,而 size_ 与 load_factor() 仅在节点实际挂链或断链后同步变更。
54.1 bucket array
buckets_ 是第一层索引数组,槽位类型为 node*,每个槽位保存一条冲突链的头指针。定位时先计算 hash_(key) 并映射为 0 <= index < bucket_count(),从而只访问 buckets_[index] 一条链;均摊链长取决于桶数、元素数与哈希分布三者的平衡。
关键事实
buckets_ 仅保存链表头指针而元素独立存于堆 node 中,因此 rehash 与 reserve 重建桶索引和 next 连接会使 iterator 失效;但节点自身地址未移动,指向元素的 pointer 与 reference 仍保持有效(仅在对应元素被 erase 时失效)。
将哈希值压缩到桶下标通常有两种取舍,阅读源码时需同步核对其桶数策略与分布假设:
| 定位策略 | 下标表达式 | 桶数量要求 | 工程取舍与分布敏感度 |
|---|---|---|---|
| 取模映射(本章实现) | hash_value % bucket_count | 任意正整数(常用素数或 2 的幂) | 存在整数取模开销,但能综合利用哈希值全部比特 |
| 位掩码映射 | hash_value & (bucket_count - 1) | 必须严格为 2 的幂 | 单条位运算指令极快,但只截取低位,强依赖低位分布均匀 |
54.2 node 结构
node 是哈希表的元素载体,由容器全权负责分配、构造与销毁。本章使用 new node(...) 与 delete 演示内存归属,完整 STL 容器则通过 allocator_traits 拆分为 allocate、construct、destroy 与 deallocate:
value(std::pair<const Key, T>):存储用户可见键值对。cached_hash(std::size_t):缓存键哈希值,供查找快筛与扩容复用。next(node*):串联同一 bucket 冲突链的下一节点;头插与断链均为O(1)指针修改,实际总耗时仍取决于链长。
边界与误区
value 将键声明为 const Key,从类型系统禁止就地修改 key。若强行改写节点内的 key,该 node 仍滞留在旧 bucket 链中,后续以新 key 查找会落到另一槽位导致元素“失联”。
是否在节点内保留 cached_hash,是空间占用、查找开销与 rehash 异常边界的典型权衡:
| 策略选择 | 查找对比开销 | rehash 成本与异常边界 | 单节点空间占用 |
|---|---|---|---|
节点缓存 cached_hash(本章实现) | 先做整型快筛,快速跳过碰撞节点 | 直接复用旧哈希重算新桶,迁移全程 noexcept | 每个 node 多占一个 std::size_t |
每次按需重算 hash_(key) | 每次判等前重算用户 Hash(长字符串较慢) | 迁移期需重调 Hash,若哈希函数可抛异常则强异常安全更复杂 | 节点更紧凑,大数据量下省内存 |
54.3 hash
哈希定位分三步协作:Hash 将 Key 转为 std::size_t,index_for 将哈希值压缩为桶下标,KeyEqual 在冲突链内裁决 key 是否等价。哈希值相同的 key 必入同一桶,哈希值不同的 key 也可能因取模或掩码而碰撞到同一桶。
下面 find_node 展示定位与判等的分工:
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;
}
边界与误区
- 等价必同散列:对于 unique-key 表,只要
equal_(a, b)为true,就必须保证hash_(a) == hash_(b);自定义 key 若只改Hash或KeyEqual其一,会出现“插入后find/erase找不到”或写入重复等价 key。 - 快筛不代判等:
current->cached_hash == hash_value仅做整数快速过滤,出现哈希碰撞时仍依赖equal_(current->value.first, key)做最终语义裁决。
54.4 insert
insert 必须按“查重 → 预判扩容 → 构节点 → 挂链提交”的固定顺序执行,确保 unique-key 表不产生重复键且 size_ 仅在节点进入链表后递增:
- 查重:计算
hash_(key)并调用find_node,命中则直接返回{existing, false}。 - 预判扩容:在
new node前调用maybe_rehash_for(size_ + 1),保证扩容失败时原表不变,也避免新节点刚构造就被二次搬迁。 - 重算索引与托管:基于最新
buckets_.size()重新计算index,并用std::unique_ptr<node>托管新建节点,防止提交前抛异常泄漏。 - 原子提交:执行
buckets_[index] = created.release()将头插节点所有权移交链表,随后++size_。
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};
}
核心判断
头插法会改变同一 bucket 内的遍历顺序(无序容器本就不保证遍历序)。更重要的是失效边界:若 insert 触发 rehash,已有 iterator 全部失效;未触发 rehash 时已有节点位置不动,指向已有元素的 pointer 与 reference 保持有效。
54.5 find
find 是最能体现均摊 O(1) 复杂度的只读路径:计算哈希、定位桶槽位、扫描该桶冲突链。一旦大量 key 聚集到同一 bucket,平均常数查找会直接退化为链表线性扫描。
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 不改写桶数组与链表连接,因此不会使任何 iterator 或引用失效;但在字符串或复合 key 场景下,用户自定义的 Hash 与 KeyEqual 本身常是热路径主要耗时来源。
排查顺序
- 哈希输入稳定:
hash_仅依赖受const Key保护的不可变键,未混入可变状态。 - 下标越界检查:
index_for结果严格落在0 <= index < bucket_count()区间。 - 冲突链全扫描:从
buckets_[index]沿next完整遍历至nullptr,无漏检节点。 - 最终等价裁决:经
cached_hash快筛后,必须调用容器保存的equal_确认 key 等价。
54.6 erase
在单向冲突链中删除节点必须知道谁指向它(可能是 buckets_[index] 或前驱节点的 next),因此 erase 扫描时需要同时维护 previous 与 current 两个指针。
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;
}
命中目标节点后,erase 按“断链 → 销毁 → 减计数”顺序完成状态收敛:
- 统一断链分支:
previous == nullptr时改写buckets_[index] = next,否则改写previous->next = next,保证链头与中间节点从入口集合中平滑移除。 - 先断链再析构:断链完成再执行
delete current(触发node与value析构并释放内存,标准 STL 对应allocator_traits::destroy与deallocate),最后--size_,防止桶链保留悬垂指针。 - 局部失效边界:
erase仅使被删元素自身的 iterator、pointer 与 reference 失效,其余节点地址与链路均不受影响。
54.7 rehash
rehash 调整 buckets_ 容量并将所有现存节点按新下标重挂到新桶链头。它只重建桶入口与 next 指针关系,不重新构造用户元素。
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);
}
依据 cppreference 的 rehash 页面,扩容后的桶数至少需同时满足请求值与负载约束 n >= size() / max_load_factor()。因需访问并重挂全部节点,rehash 典型耗时为 O(size());批量插入前预先 reserve 或 rehash,可将多次扩容压缩为一次重建。
核心判断
next_buckets 的内存分配在改写任何节点指针之前完成,分配失败时旧表完好无损。随后借助 cached_hash 直接重算索引并移链,不重调可能抛异常的用户 Hash,使迁移过程保持 noexcept。
综合前文四个核心操作,节点生命周期与位置对象的失效边界对比如下:
| 操作 / 场景 | 典型时间复杂度 | 节点内存动作 | Iterator 失效范围 | Pointer / Reference 失效范围 |
|---|---|---|---|---|
find | O(1)(退化 O(N)) | 只读不分配 | 无失效 | 无失效 |
insert(未触发 rehash) | O(1) | 新建 1 个 node 头插 | 无失效 | 无失效 |
insert(触发 rehash) | O(size()) | 重建桶数组并重挂节点 | 全部失效 | 无失效 |
erase | O(1)(退化 O(N)) | 断链并 delete 目标节点 | 仅被删元素失效 | 仅被删元素失效 |
rehash | O(size()) | 仅迁移 buckets_ 与 next | 全部失效 | 无失效 |
54.8 load_factor
依据 cppreference 的 load_factor 页面,load_factor() 定义为 size() / bucket_count(),反映全表每个 bucket 的平均元素压力。当插入后预期负载超过 max_load_ 时,maybe_rehash_for 触发扩容;next_bucket_count 可按 2 的幂或素数序列增长,具体取决于取模或位掩码策略。
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个桶时load_factor() == 1.0,但若哈希碰撞将大量 key 挤入同一桶,热点查找仍会退化;性能排查须联查load_factor()、bucket_count()、bucket_size(index)与键分布。 - 空间与时间取舍:调低
max_load_factor可缩短平均链长但增大桶数组开销;此外节点式哈希表实际内存远超bucket_count * sizeof(node*) + size * sizeof(value_type),还包含每节点的next、cached_hash与堆分配元数据。
最小自检任务
阅读下方操作序列,推导每一步后的结构状态与失效边界。假设 index_for(hash, bucket_count) 采用取模,初始 bucket 数为 4,max_load_ = 1.0f,且四个两两不等价的 key 满足 hash(A)=1、hash(B)=5、hash(C)=2、hash(D)=9:
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 使用的边界是什么?
本章知识点总结
- 两层索引
buckets_保存各冲突链入口,查找先由hash与index_for选桶,再仅在该桶的链表中对比 key。 - 节点与不可变键
node持有std::pair<const Key, T>、cached_hash与next,const Key从类型层面禁止原地改键破坏桶定位。 - 契约一致性
Hash与KeyEqual必须满足“等价必同散列”,cached_hash仅做快筛,最终语义以equal_为准。 - 提交顺序
insert按“查重 → 预判maybe_rehash_for→unique_ptr托管建节点 → 挂链release()→++size_”提交,守住唯一性与计数不变量。 - 断链与释放
erase用previous/current处理头节点或中间节点断链,先绕过节点再delete并减size_,避免悬垂指针。 - 失效边界
rehash先分配新桶数组再按cached_hash迁移节点,使全部 iterator 失效但保留未删元素的 pointer 与 reference;普通erase仅使被删元素自身失效。 - 负载与诊断
load_factor()仅反映平均链长,性能排查须联查bucket_size(index)与键分布,并用reserve/rehash权衡空间与均摊耗时。