课程 · #8 / 11

哈希表

djb2 哈希 → 桶下标 → 平均 O(1)

Hash table · djb2 hash mod cap

size0

cap8

load0.00

init

key value

动手试试：插入若干键；橙色的闪烁就是探测序列。切换 chaining ↔ linear probing（链地址 ↔ 线性探测），看两种迥然不同的冲突策略。然后 resize（扩容），看每个键都被重新散列。

为什么它重要

哈希表实现了那个梦寐以求的圣杯：平均情况下 O(1) 的查找、插入和删除。每一个字典、集合、缓存和数据库索引背后都有它。理解散列是写出高效算法的根本。

核心思想

想象一座巨大的图书馆，书按作者姓氏的首字母上架。要找"Knuth"，直接走到 'K' 区即可——不必把所有书都翻一遍。

哈希表的工作方式一样，只是更聪明。一个哈希函数把任意键转换成一个数组下标：

hash("Knuth") → 42 → 存到下标 42

神奇之处：这个转换是 O(1)。你直接算出下标，而不是去搜索。

棘手之处：冲突。两个不同的键可能散列到同一个下标。解决办法有：

链地址法：每个桶是一条由冲突元素组成的链表
开放定址法：去找下一个空槽

只要有一个好的哈希函数和较低的装载因子，操作平均下来就保持 O(1)。

要点回顾

平均 O(1) 的插入、查找、删除
需要一个分布均匀的好哈希函数
冲突不可避免——必须加以处理
装载因子影响性能——太满时要扩容

不变式

哈希表不变式: 函数纯粹性：哈希函数是确定的——同一个键总是映射到同一个槽。（如果不是这样，你什么都找不到。）; 桶的完整性：每个存入的键 k 都位于一个可从 hash(k) mod capacity 出发、按所选冲突策略到达的槽（链地址法：同一个桶；探测法：起始桶，再沿确定的探测序列）。; 装载因子上界：α = n / capacity 保持在扩容阈值以下（探测法通常是 0.7，链地址法是 1.0）。一旦越过，表就会重新散列——和数组翻倍是同一套摊还说法。

再深入一些

哈希函数家族 —— 按使用场景挑选

密码学哈希（SHA-256、BLAKE3）是杀鸡用牛刀：它们被设计成不可伪造，而不是快。哈希表在意的是速度 + 均匀分布，而不是抵御攻击者的抗碰撞性。

| 家族 | 速度 | 备注 | |---|---|---| | FNV-1a | 非常快 | 代码极小，对短键很棒；演示里的 djb2 属同一家族 | | MurmurHash3 | 快，分布良好 | 许多语言运行时的默认选择（Java 8+、较老的 Go） | | xxHash3 | 极快 | 原始吞吐最佳；被 zstd、LZ4、数据帧库采用 | | CityHash / FarmHash | 快，源自 Google | 与 MurmurHash 同一档次 | | SipHash | 中等偏快，带密钥 | Rust HashMap、Python 3.4+、Perl 的抗 DoS 默认选择 | | SHA-256 | 慢（密码学级别） | 密码学用途；用于 HashMap，绝不；用于内容寻址存储，可以 |

为什么装载因子重要 —— 生日悖论

当 m 个桶里均匀分布 n 个键时，发生任意一次冲突的概率会在 n ≈ √(π·m/2) 附近超过 50%——这与生日悖论是同一套数学（用远比桶数少的元素就出乎意料地容易碰撞）。

当 α = n/m = 0.7 时，即便是一个完美的哈希函数也会有许多长度为 2 或 3 的链。探测法退化得比链地址法更快——在 α = 0.9 时，线性探测的期望探测次数约为 5.5，而在 α = 1.0 时它会发散。选 0.7 这条线是一种惯例，目的是让探测次数平均保持在 2 左右。

哈希碰撞 DoS 攻击

如果攻击者能选定你的输入并预测你的哈希函数，他们就能精心构造一批全部落到同一个桶里的键——把你的 O(1) 拖垮成 O(n)。Java 7 有过一次著名事件：当 CGI 参数是恶意构造的时，HashMap<String, ...> 直接爆炸。现代运行时的修复办法是带密钥散列：在进程启动时生成一个随机秘密，哈希函数（SipHash）把它混入每一次计算。没有这个秘密，攻击者就无法预测键会落到哪儿。

如果你正在写一个把不可信输入当作哈希键的库（HTTP 解析器、JSON 反序列化器、数据库查询层），务必确保你的哈希表用的是带密钥散列。Rust 默认的 HashMap 做到了这一点；C++ std::unordered_map 没有。

进阶冲突策略

除了链地址法和线性探测，还有两种套路以复杂度换取更好的最坏情况保证：

罗宾汉散列（Robin Hood hashing）——探测时，如果你发现某个槽的现住户探测的距离比你已探测的更短，你就与它交换。这会让探测距离均匀化，并约束最坏情况。
布谷鸟散列（Cuckoo hashing）——用两个哈希函数；若两个槽都满了，就把现住户赶走，再把它插到它的另一个哈希位置。查找保证最坏情况 O(1)（检查两个槽，搞定）。
跳房子散列（Hopscotch hashing）——把每个键保持在其家桶的一个有界邻域内，于是即便发生冲突，查找也对缓存友好。

这些都出现在生产环境里：跳房子散列见于某些 Java 库，罗宾汉散列是 Rust 2018 之前的默认实现，布谷鸟散列见于网络路由器的查找表。

数学细节

时间复杂度（平均情况）: Insert: O(1); Lookup: O(1); Delete: O(1)
最坏情况（大量冲突）: O(n)
装载因子: α = n / capacity; 通常当 $\alpha > 0.7$ 时扩容

实现

Rust 中的 HashMap

use std::collections::HashMap;

let mut map = HashMap::new();
map.insert("key", 42);       // O(1) avg
let val = map.get("key");    // O(1) avg
map.remove("key");           // O(1) avg

// Iteration is O(n)
for (k, v) in &map {
    println!("{}: {}", k, v);
}

何时使用

字典/映射（键值存储）
集合成员测试
缓存与记忆化
统计频次

练习

三道题目，展示了为什么哈希表是算法界的瑞士军刀：

字母异位词分组 —— 中等 · "先规范化再分桶"——按等价关系聚类的模板
LRU 缓存 —— 中等 · 哈希 + 双向链表——最经典的"两种结构合用"设计
无重复字符的最长子串 —— 中等 · 滑动窗口 + "上次出现下标"哈希——O(n) 的字符串窗口套路

→ 浏览全部练习题

🪣 哈希表