05. 哈希表

0. 本章先解决什么问题

哈希表解决的问题是:

如何根据 key 快速找到 value?

它是很多系统中最常用的结构之一:

• 字典和映射。
• 集合。
• 缓存。
• 去重。
• 计数。
• 索引。
• 路由表。
• 符号表。

哈希表常说平均 O(1),但这句话有很多前提。本章要讲清:

• 哈希函数是什么?
• key 如何映射到桶?
• 冲突为什么不可避免?
• 拉链法和开放寻址如何处理冲突?
• 负载因子和扩容为什么重要?
• 哈希表什么时候会退化?
• 如何把哈希表用于实际问题?

这张图怎么读

这张图说明了哈希表最重要的工程事实:平均 O(1) 来自散列均匀和负载受控;一旦冲突堆积或触发扩容,单次操作就可能变慢。读哈希表时不要只背复杂度,要看 key 分布、负载因子、冲突策略和 rehash 成本。

1. 哈希表的最小模型

哈希表底层通常有一个桶数组:

bucket[0]
bucket[1]
bucket[2]
…
bucket[m-1]

插入 key-value:

hash = hashFunction(key)
index = hash % bucket_count
放入 bucket[index]

查找 key:

hash = hashFunction(key)
index = hash % bucket_count
到 bucket[index] 找 key

核心思想:

把任意 key 转成数组下标附近的位置。

2. 哈希函数

哈希函数把 key 转成整数。

好的哈希函数应该:

哈希函数不是越复杂越好。它要在分布和计算成本之间平衡。

如果哈希分布差,很多 key 会落到同一个桶,哈希表就会退化。

3. 冲突为什么不可避免

key 的可能数量通常远大于桶数量。

例如无限多个字符串,要放进有限个桶:

不同 key 落到同一个 index 是不可避免的。

这叫哈希冲突。

所以哈希表必须设计冲突处理策略。

4. 拉链法

拉链法让每个桶保存一个链或小容器。

bucket[0] -> (k1,v1) -> (k2,v2)
bucket[1] -> empty
bucket[2] -> (k3,v3)

查找时:

定位桶
在桶内逐个比较 key

优点:

• 实现直观。
• 删除相对简单。
• 负载因子可以超过 1。

缺点:

• 节点可能分散,cache 不友好。
• 冲突严重时桶内链很长。

5. 开放寻址

开放寻址不在桶外挂链,而是在数组中寻找其他空位置。

如果目标桶被占用:

尝试下一个位置
或按某种探测序列继续找

常见探测:

优点:

• 数据更集中,cache 友好。
• 不需要额外节点指针。

缺点:

• 删除处理复杂。
• 负载高时性能明显下降。
• 容易出现聚集。

6. 负载因子

负载因子:

load_factor = 元素数量 / 桶数量

负载因子越高:

• 空桶越少。
• 冲突越多。
• 查找和插入成本越高。

所以哈希表通常会在负载因子超过阈值时扩容。

扩容过程:

申请更大的桶数组
遍历旧元素
重新计算位置
放入新桶

这叫 rehash。

7. rehash 的成本

rehash 是 O(n),因为要重新搬所有元素。

所以哈希表插入常说:

平均或摊还 O(1)

但触发扩容那一次可能很贵。

如果系统对延迟敏感,可以:

• 提前预估容量。
• 分批 rehash。
• 控制负载因子。
• 避免短时间大量插入造成抖动。

8. 查找为什么还要比较 key

哈希值相同或桶相同,不代表 key 一定相同。

查找流程通常是:

计算 hash
定位桶
在候选项中比较 key 是否真正相等

所以哈希表依赖两个规则:

如果相等判断和哈希规则不一致,结构会出错。

基本约束:

如果两个 key 相等,它们的 hash 必须一致。

反过来不要求成立:

hash 一致的 key 不一定相等。

机制深挖:hash/equality 契约错了,表会“逻辑损坏”

哈希表正确性依赖一个契约:

equal(a, b) == true
=> hash(a) == hash(b)

如果违反这个契约,会出现非常诡异的现象:

所以设计 key 时要问:

哪些字段决定身份?
这些字段是否插入后保持不变?
hash 和 equality 是否使用同一组身份字段?

哈希表不是只依赖“散列快”,它还依赖“身份定义稳定”。

9. 可变 key 的危险

如果 key 插入哈希表后被修改,导致 hash 或相等判断改变,后果很危险。

示意:

插入时 key 在 bucket[3]
修改 key 后它应该在 bucket[7]
但实际还留在 bucket[3]

之后查找可能找不到。

所以作为 key 的数据最好不可变,或至少参与 hash/equality 的字段不能在表内修改。

10. 哈希表的退化场景

哈希表平均很快,但不是无条件快。

攻击性冲突:平均 O(1) 也可能被打穿

如果外部用户能控制 key,且哈希函数容易被构造冲突,攻击者可以让大量 key 落入同一桶:

bucket[7] -> k1 -> k2 -> k3 -> … -> kn

这时一次查找可能从平均 O(1) 退化成 O(n)。在面向外部输入的系统里,这不只是性能问题,也可能是拒绝服务风险。

缓解思路包括:

这就是为什么“哈希表很快”在工程里要加条件:key 分布、负载因子、冲突策略和攻击面都要受控。

11. 哈希表和有序结构的区别

哈希表擅长:

按 key 精确查找

不擅长:

按顺序遍历
范围查询
找前驱后继
按最小/最大取元素

如果需要有序能力,通常要考虑:

• 排序数组。
• 平衡搜索树。
• 跳表。
• B+ 树。

选型时问:

我只需要知道 key 是否存在,还是还需要 key 的顺序?

12. 哈希表的常见用途

很多算法用哈希表把重复查找从 O(n) 降到平均 O(1)。

13. 联系实际:什么时候选哈希表

适合:

1. 按 key 精确查找非常频繁。
2. 不要求按 key 有序遍历。
3. 可以接受平均性能模型。
4. key 的哈希和比较成本可控。
5. 能估计容量或接受扩容。

不适合:

1. 需要范围查询。
2. 需要有序输出。
3. key 会频繁变化。
4. 最坏情况必须严格受控。
5. 内存非常紧张且桶空位不可接受。

实际系统里,哈希表常和其他结构组合:

哈希表负责按 id 定位
链表负责维护顺序
堆负责维护优先级

手推:负载因子为什么会改变冲突概率

假设桶数组有 8 个桶:

bucket_count = 8

插入 4 个 key:

load_factor = 4 / 8 = 0.5

如果 hash 分布均匀,很多桶仍然为空,查找时平均碰到的冲突较少。

插入 12 个 key:

load_factor = 12 / 8 = 1.5

即使 hash 很均匀,也一定有桶里不止一个 key。拉链法里链会变长;开放寻址里探测距离会变长。

哈希表的平均 O(1) 依赖一个条件:

平均每个桶里要处理的候选数量可控。

负载因子太高时,定位到桶只是第一步,后面还要在候选里找真正 key。这个候选集合越大,哈希表越不像 O(1)。

边界条件:开放寻址删除不能简单清空格子

开放寻址用探测序列寻找位置:

hash(key) -> slot i
如果 i 被占用 -> 看 i+1、i+2 …

假设插入:

A 应该在 3,实际放 3
B 应该在 3,冲突后放 4
C 应该在 3,冲突后放 5

查找 C 时会走:

slot 3 -> 不是 C
slot 4 -> 不是 C
slot 5 -> 找到 C

如果删除 B 时直接把 slot 4 清空,查找 C 可能在 slot 4 看到空位后提前停止:

slot 3 -> 不是 C
slot 4 -> 空
=> 误以为 C 不存在

所以开放寻址通常需要 tombstone 标记:

这个位置曾经有元素,现在删除了,但查找不能在这里停。

这就是开放寻址删除比拉链法更容易写错的地方。哈希表不是只有 hash 函数,探测序列、删除语义和 rehash 策略共同决定正确性。

排障卡:哈希表突然变慢时看四件事

哈希表平均很快,但平均值会隐藏尖峰。

练习:画一个只有 4 个桶的哈希表,把 8 个 key 放进去。先假设分布均匀,再假设全部冲突到同一个桶。两张图一对比,你会理解为什么“平均 O(1)”必须配合哈希质量、负载控制和扩容策略一起看。

14. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 哈希表为什么平均能快速查找?
2. 哈希函数、桶数组、取模定位各做什么?
3. 冲突为什么不可避免?
4. 拉链法和开放寻址有什么区别?
5. 负载因子为什么影响性能?
6. rehash 为什么会造成单次 O(n) 抖动?
7. 为什么 key 相等必须保证 hash 一致?
8. 可变 key 为什么危险?
9. 哈希表为什么不适合范围查询和有序遍历?

哈希表的本质是用空间和哈希规则换快速定位。它很强,但前提和退化场景必须清楚。

延伸阅读

• HashMap
• from - zero · data-structures