现代 C++ 实战（19）：哈希表实现

第 18 篇用 std::sort 做 O(log n) 查找前的准备；哈希表把查找压到平均 O(1)——键经哈希函数映射到桶，碰撞用链地址或开放寻址解决。理解这两条路，就摸清了 std::unordered_map 的底层地图。

demo：ref/cpp_demo/algorithms/hash_table/（链地址、线性探测、双重哈希 + 与标准库性能对比）。

这是「现代 C++ 实战」系列的第 19 篇。建议先读第 18 篇：排序算法。

一、哈希表在干什么？

操作	平均时间	思路
插入	O(1)	`index = hash(key) % bucket_count`
查找	O(1)	同 index，再比对 key
删除	O(1)	定位后删节点或标记槽位

碰撞（collision）：不同 key 算出同一 index。解决策略分两大类：

1 2	链地址法： bucket[i] → (k1,v1) → (k2,v2) → … 开放寻址： table[i], table[i+1], … 在同一数组里探测下一个空位

二、哈希函数

好哈希函数：确定性、均匀分布、O(1) 计算、输入小变输出大变（雪崩）。

// 整数：直接用 std::hash
size_t h = std::hash<int>{}(key) % bucket_count;

// 字符串：FNV-1a 示例（demo）
struct StringHash {
    size_t operator()(const std::string& str) const {
        size_t hash = 2166136261u;
        for (char c : str) {
            hash ^= static_cast<size_t>(c);
            hash *= 16777619u;
        }
        return hash;
    }
};

std::unordered_map 允许自定义 Hash 和 KeyEqual 模板参数。

三、链地址法（Chaining）

每个桶是一条链表（demo 用头插）：

1 2	size_t index = hash(key); // 遍历 buckets[index] 链表：存在则更新，否则 new Node 头插

优点	缺点
实现简单，删除容易	指针额外开销
元素数量可超过桶数	缓存局部性差
负载因子可 > 1（链表变长）	最坏 O(n) 全撞一桶

平均 O(1) 依赖哈希均匀 + 负载因子不太高。demo 阈值 0.75，超则 rehash（桶数 ×2，全体重新插入）。

四、开放寻址法（Open Addressing）

所有元素在同一数组；碰撞时按探测序列找下一空位。

线性探测

$$
h(k, i) = (hash(k) + i) \bmod m
$$

$i = 0, 1, 2, \ldots$ 直到空槽或 DELETED 槽。

优点	缺点
无指针，缓存友好	-primary clustering 聚集
实现较简单	删除需惰性删除（标记 DELETED）
	负载因子通常 < 0.7

删除不能只置 EMPTY——会截断探测链；demo 用 SlotStatus::DELETED，查找时跳过、插入时可复用。

二次探测 / 双重哈希

双重哈希（demo 第三种实现）：

$$
h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m
$$

$h_2(k) \neq 0$，与 $m$ 互质更好。比线性探测分散更均匀，减轻聚集。

五、负载因子与 rehash

$$
\text{负载因子 } \alpha = \frac{n}{m}
$$

（$n$ 元素数，$m$ 桶/槽位数。）

策略	典型阈值	rehash 时
链地址	~0.75	$m \leftarrow 2m$，重挂链表
开放寻址	~0.5–0.7	$m \leftarrow 2m$，重探测插入

rehash 均摊后插入仍 O(1) 均摊。

六、三种实现对比

	链地址	线性探测	双重哈希
结构	桶 + 链表	单数组	单数组
碰撞	链上追加	步进 +1	步进 $h_2$
删除	unlink 节点	DELETED 标记	同左
聚集	无（链长）	严重	较轻
适用	通用	内存紧、可估容量	开放寻址高性能

demo 对 10000 随机键测插入/查找/删除微秒数，并与 std::unordered_map 对比——标准库通常实现为链地址 + 桶数组，并高度优化。

七、与 `std::unordered_map`

std::unordered_map<int, std::string> m;
m[42] = "answer";
m.insert({1, "one"});
if (auto it = m.find(42); it != m.end()) { /* it->second */ }
m.erase(42);

// 自定义哈希
std::unordered_map<std::string, int, StringHash> sm;

	`unordered_map`	`map`
底层	哈希表	红黑树
平均查找	O(1)	O(log n)
有序遍历	❌	✅
需要 `operator<`	否	是

迭代器稳定性：rehash 会使所有迭代器失效；插入可能失效。C++17 起 merge、extract 支持节点提取。

八、demo 运行

1 2	cd ref/cpp_demo/algorithms/hash_table ./build.sh --run

输出：小规模插入/冲突/删除演示 + 三种手写实现与 std::unordered_map 的性能表 + 策略总结。

九、小结

概念	要点
哈希	key → index，取模桶数
链地址	桶内链表，实现简单
开放寻址	数组探测，省指针
双重哈希	第二哈希步长，减聚集
负载因子	过高则 rehash
工程	直接用 `unordered_map`