Skip to main content

Chapter 54: Mini Hash Table

核心问题与阅读主线

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

哈希表将 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_ 仅在节点进入链表后递增:

  1. 查重:计算 hash_(key) 并调用 find_node,命中则直接返回 {existing, false}。
  2. 预判扩容:在 new node 前调用 maybe_rehash_for(size_ + 1),保证扩容失败时原表不变,也避免新节点刚构造就被二次搬迁。
  3. 重算索引与托管:基于最新 buckets_.size() 重新计算 index,并用 std::unique_ptr<node> 托管新建节点,防止提交前抛异常泄漏。
  4. 原子提交:执行 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 本身常是热路径主要耗时来源。

排查顺序

  1. 哈希输入稳定:hash_ 仅依赖受 const Key 保护的不可变键,未混入可变状态。
  2. 下标越界检查:index_for 结果严格落在 0 <= index < bucket_count() 区间。
  3. 冲突链全扫描:从 buckets_[index] 沿 next 完整遍历至 nullptr,无漏检节点。
  4. 最终等价裁决:经 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 失效范围
findO(1)(退化 O(N))只读不分配无失效无失效
insert(未触发 rehash)O(1)新建 1 个 node 头插无失效无失效
insert(触发 rehash)O(size())重建桶数组并重挂节点全部失效无失效
eraseO(1)(退化 O(N))断链并 delete 目标节点仅被删元素失效仅被删元素失效
rehashO(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);

请依次回答:

  1. A、B、C、D 分别落入哪个 bucket?
  2. erase(B) 需要改写哪个指针?
  3. 若 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 权衡空间与均摊耗时。