> For the complete documentation index, see [llms.txt](https://datastructure-1.gitbook.io/datastructure-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://datastructure-1.gitbook.io/datastructure-docs/di-liu-bu-fen-cha-zhao/12-hash-tables.md).

# 第 12 章：哈希表

[<- 第 11 章　图论算法](/datastructure-docs/di-wu-bu-fen-tu/11-graph-algorithms.md) | [课程目录](/datastructure-docs/readme.md) | [第 13 章　并查集 ->](/datastructure-docs/di-liu-bu-fen-cha-zhao/13-disjoint-set-union.md)

> 所属模块：第六部分：查找\
> 对应实现：hashing.cpp

### 本章导航

* [12.1 散列映射的本质：从直接寻址到概率性 O(1) 检索](#c12-12-1)
* [12.2 鸽巢原理与生日悖论：为什么冲突不可避免？](#c12-12-2)
* [12.3 优秀哈希函数的设计准则与经典算法](#c12-12-3)
  * [12.3.1 除留余数法：为什么表大小必须取素数？](#c12-12-3-1)
  * [12.3.2 乘法哈希法与黄金分割常数](#c12-12-3-2)
  * [12.3.3 字符串哈希：BKDR 与雪崩效应（Avalanche Effect）](#c12-12-3-3)
* [12.4 冲突消解两大流派的深度较量](#c12-12-4)
  * [12.4.1 分离链接法（拉链法）与 Java 8 红黑树化阈值](#c12-12-4-1)
  * [12.4.2 开放寻址法：线性探测、二次探测与双重散列](#c12-12-4-2)
  * [12.4.3 开放寻址的墓碑机制（Tombstone）与查找链不变量](#c12-12-4-3)
* [12.5 负载因子（Load Factor）与渐进式扩容（Incremental Rehashing）](#c12-12-5)
* [12.6 完美哈希（FKS 方案）：最坏 O(1) 查询的数学构造](#c12-12-6)
* [12.7 分布式系统基石：一致性哈希（Consistent Hashing）与虚拟节点](#c12-12-7)
* [本章小结](#c12-summary)
* [思考题与经典大厂面试题](#c12-exercises)

***

## 第 12 章　哈希表

> 难度：★★☆☆☆ | 代码：[hashing.cpp](https://github.com/Huo0077/DataStructure/blob/main/hashing.cpp)

**前置知识**：[第 1 章](/datastructure-docs/di-yi-bu-fen-xu-lun/01-complexity-adt.md) 均摊分析（动态扩容重哈希），[第 2 章](/datastructure-docs/di-er-bu-fen-xian-xing-jie-gou/02-linear-list.md) 链表与数组。

**学习目标**：

1. 理解哈希表“用计算时间换取寻址空间”的设计哲学；
2. 掌握除留余数法、乘法哈希及字符串哈希的数论原理；
3. 掌握拉链法与开放寻址法（一次聚集、二次探测、双重散列）的利弊；
4. 熟练运用墓碑机制保证开放寻址删除时的查找链不中断；
5. 理解 FKS 完美哈希与一致性哈希在现代工程中的应用。

***

### 12.1 散列映射的本质：从直接寻址到概率性 O(1) 检索

如果所有可能的键集合 (U) 规模很小（如 ASCII 字符，(|U| = 256)），我们可以直接建立一个大小为 256 的数组，以字符的 ASCII 码为下标直接存取，称为**直接寻址表（Direct Addressing Table）**，查询时间为纯粹的 (O(1))。

但在真实业务中：

* 身份证号、IPv6 地址、URL 字符串等键的理论空间 (|U|) 极为庞大（如 18 位身份证号有 (10^{18}) 种可能）；
* 而我们实际存储的数据量 (n) 往往只有几十万或几百万（(n \ll |U|)）。
* 直接开辟 (10^{18}) 大小的数组需要数万 PB 内存，物理上完全不可行！

**哈希表（Hash Table / 散列表）** 应运而生：

* 建立一个容量仅为 (m \approx O(n)) 的紧凑桶数组；
* 通过**哈希函数 (h(\text{key}))**，将庞大宇宙中的键映射为 (\[0, m-1]) 内的整数下标；
* **核心代价**：由于空间被大幅压缩，不同的键可能被映射到相同的槽位，这就是**哈希冲突（Hash Collision）**！

***

### 12.2 鸽巢原理与生日悖论：为什么冲突不可避免？

* **鸽巢原理（Pigeonhole Principle）**：若有 (n) 只鸽子飞入 (m) 个巢，且 (n > m)，则至少有一个巢里有 2 只及以上的鸽子。由于 (|U| > m)，冲突在数学上不可避免。
* **生日悖论（Birthday Paradox）**：在一个只有 23 人的房间里，至少有两个人同一天生日的概率竟然超过了 50%！\
  *数学推导*：23 个人生日全不相同的概率为： \[ P(\text{全不同}) = \frac{365}{365} \times \frac{364}{365} \times \dots \times \frac{343}{365} \approx 0.4927 \implies P(\text{至少两人相同}) = 1 - 0.4927 = 50.73% ] 这表明：**即使哈希表还非常空旷，发生冲突的概率也远比直觉预想的要高得多**！因此，设计优良的哈希函数与冲突消解机制是哈希表的立足之本。

***

### 12.3 优秀哈希函数的设计准则与经典算法

一个理想的哈希函数必须满足**简单均匀散列假设（Simple Uniform Hashing）**：任何给定的键，均等可能地映射到 (m) 个槽位中的任意一个，且与其他键的映射相互独立。

#### 12.3.1 除留余数法：为什么表大小必须取素数？

公式：(h(k) = k \bmod m)\
**表大小 (m) 必须选素数，且不能接近 2 的幂次**！

```
【致命反例：若 m 选合数 (如 m = 12)】
假设输入的键有某种规律（如大量键是 4 或 6 的倍数）:
keys = [6, 12, 18, 24, 30, 36]
h(k) = k % 12 后的结果: [6, 0, 6, 0, 6, 0] ───> 所有的键被严重压缩在 0 和 6 两个槽中!
其余 10 个槽位全部空置，冲突率高达 100%!

【若 m 选素数 (如 m = 13)】
h(k) = k % 13 后的结果: [6, 12, 5, 11, 4, 10] ───> 6 个键均匀散布在 6 个完全不同的槽位中!
```

素数能够最大限度打破输入数据中潜在的公约数周期性，消除周期聚集。

#### 12.3.2 乘法哈希法与黄金分割常数

由 Donald Knuth 提出：

1. 选取一个常数 (A \in (0, 1))；
2. 计算 (k \cdot A) 并提取其小数部分 ((k \cdot A) \bmod 1)；
3. 乘以 (m) 并向下取整： \[ h(k) = \lfloor m \cdot (k \cdot A \bmod 1) \rfloor ] Knuth 证明，当选取黄金分割比的共轭数 (A = \frac{\sqrt{5} - 1}{2} \approx 0.6180339887\dots) 时，散列分布最为均匀。该方法对 (m) 的选取不敏感，通常令 (m = 2^p) 以便通过位运算加速。

#### 12.3.3 字符串哈希：BKDR 与雪崩效应（Avalanche Effect）

字符串作为键在现代开发中最为普遍。著名的 **BKDR Hash** 使用多项式滚动累加：

```cpp
uint64_t BKDRHash(const std::string& str) {
    uint64_t seed = 131; // 也可以是 31, 1313, 13131 等奇素数
    uint64_t hash = 0;
    for (char ch : str) {
        hash = hash * seed + static_cast<unsigned char>(ch);
    }
    return hash;
}
```

> **雪崩效应**：输入的字符串即使只变动一个比特（例如 `"test1"` 变为 `"test2"`），输出的哈希值也应当有大约 50% 的比特位发生剧烈翻转，避免相邻字符串产生相近的哈希值。

***

### 12.4 冲突消解两大流派的深度较量

#### 12.4.1 分离链接法（拉链法）与 Java 8 红黑树化阈值

每个槽位（Bucket）维护一个链表。当产生冲突时，直接将新键值对挂接在链表头部或尾部。

* **优点**：结构简单，对负载因子 (\alpha) 容忍度高（(\alpha) 可以超过 1.0）；
* **缺点**：链表节点离散分配，缺乏 CPU 缓存局部性；每个节点额外付出指针开销。
* **Java 8 `HashMap` 的工程演进**：\
  当某一个桶内的链表长度达到 **8** 且表总容量 (\ge 64) 时，该链表将**自动蜕变为一棵红黑树**！将最坏情况下的查找时间从 (O(n)) 强制截断为 (O(\log n))，有效抵御了针对哈希表的拒绝服务攻击（Hash DoS）。

#### 12.4.2 开放寻址法：线性探测、二次探测与双重散列

所有元素直接存储在桶数组内（无指针）。发生冲突时，通过某种规则在表中探测下一个可用槽位： \[ h\_i(k) = (h(k) + d\_i) \bmod m, \quad i = 0, 1, 2, \dots ]

| 探测方式                        | 探测增量序列 (d\_i)                    | 核心特性与缺陷                                                          |
| --------------------------- | -------------------------------- | ---------------------------------------------------------------- |
| **线性探测（Linear Probing）**    | (0, 1, 2, 3, \dots)              | **一次聚集（Primary Clustering）**：连续占用的槽位会迅速滚雪球般扩大，导致后续插入探测链越来越长。     |
| **二次探测（Quadratic Probing）** | (0, 1^2, -1^2, 2^2, -2^2, \dots) | 跳跃探测，化解了一次聚集；但具有相同初始哈希值的键仍会走相同路径（二次聚集）。                          |
| **双重散列（Double Hashing）**    | (i \cdot h\_2(k))                | 增量由第二个独立哈希函数 (h\_2(k)) 决定，不同键探测路径完全不同。**要求 (h\_2(k)) 与 (m) 互质**。 |

#### 12.4.3 开放寻址的墓碑机制（Tombstone）与查找链不变量

在开放寻址表中，**绝对不能直接把被删除的槽位清空为 `EMPTY`**！

```
查找链不变量破裂反例:
假设 key1 与 key2 发生冲突，key1 落在槽 3，key2 被线性探测推到了槽 4。
此时若直接把槽 3 的 key1 清空 (设为 EMPTY):
接下来查找 key2: 计算 h(key2) = 3，检查槽 3 发现是 EMPTY!
算法立刻误判: "该键不存在"，提前退出! 槽 4 里的 key2 永远失联!
```

**解决方案：墓碑机制（Lazy Deletion / Tombstone）**：

* 节点状态三值化：`EMPTY`（从未占用）、`OCCUPIED`（有效占用）、`DELETED`（已删除/墓碑）；
* **查找时**：遇到 `DELETED` 视同有占位，**继续向后探测**；只有遇到 `EMPTY` 才能断定键不存在；
* **插入时**：遇到 `DELETED` 或 `EMPTY` 均可作为空闲位置填入新元素。

***

### 12.5 负载因子（Load Factor）与渐进式扩容（Incremental Rehashing）

**负载因子（Load Factor）**： \[ \alpha = \frac{n}{m} = \frac{\text{表中元素总数}}{\text{散列表总容量}} ] 在开放寻址法中，当 (\alpha > 0.75) 后，查找失败的平均探测次数呈指数级暴增（**膝盖效应**）。因此，工业级哈希表通常在 (\alpha \ge 0.7 \sim 0.75) 时触发扩容（容量翻倍）。

#### Redis `dict` 的渐进式 Rehash 艺术：

若哈希表存有 1000 万个键，单次重分配内存并拷贝所有键需要耗费数百毫秒，导致单线程的 Redis 服务严重卡顿（Stop-the-world）。\
**Redis 解决方案**：

1. 维护两张哈希表：`ht[0]`（旧表）和 `ht[1]`（新表），以及游标 `rehashidx = 0`；
2. 在每次接收到客户端的增删改查请求时，顺手将 `ht[0]` 在 `rehashidx` 索引上的**单个槽位数据搬移到 `ht[1]`**，然后 `++rehashidx`；
3. 将一次性的大开销均摊到成千上万次日常请求中，做到纳秒级平滑过渡！

***

### 12.6 完美哈希（FKS 方案）：最坏 O(1) 查询的数学构造

由 Fredman, Komlós, Szemerédi 于 1984 年提出（FKS 完美哈希）。在键集合静态已知（如编程语言保留字、编译器关键字字典）的场景下，可以实现**最坏情况下严格 (O(1)) 查询，且总体空间严格为 (O(n))**！

```
               第一层哈希 (槽数 m = n):
               ┌───┬───┬───┬───┬───┐
               │ 0 │ 1 │ 2 │ 3 │ 4 │
               └───┴─┬─┴───┴─┬─┴───┘
                     │       │
       ┌─────────────┘       └─────────────┐
       ▼                                   ▼
第二层哈希表 (容量 S_1 = n_1² = 4)   第二层哈希表 (容量 S_3 = n_3² = 9)
[ 保证 0 冲突! ]                     [ 保证 0 冲突! ]
```

* **核心数学定理**：若将 (k) 个元素散列到大小为 (k^2) 的表中，根据生日悖论，**不发生任何冲突的概率 (> 1/2)**！
* 若发生冲突，只需重新随机挑选第二层哈希函数再次尝试，期望常数次即可找到零冲突哈希表。

***

### 12.7 分布式系统基石：一致性哈希（Consistent Hashing）与虚拟节点

在分布式缓存集群（如 Memcached、Redis Cluster）中，若使用简单取模 `h(key) % N`：

* 一旦某台服务器宕机（机器数从 (N) 变为 (N-1)），**几乎 99% 的键的映射位置全部失效**，引发毁灭性的缓存雪崩！

```
一致性哈希环 (0 ~ 2³² - 1):
                 Node_A
             .     │     .
          .        │        .
      Node_C       │       Node_B
         .         │         .
           .       │       .
                   v
每个 Key 沿环顺时针寻找距离最近的物理节点。
节点宕机或扩容时，仅影响该节点逆时针方向的相邻子集，其余节点完全不受波及！
```

* **虚拟节点（Virtual Nodes）**：为每个物理节点分配数十个虚拟副本节点（如 `NodeA#1`, `NodeA#2`）均匀撒在环上，彻底消除数据分布倾斜。

***

### 本章小结

1. **散列是用计算换空间**：哈希函数将无限键空间投射到有限槽位，冲突消解是哈希表的灵魂。
2. **数论保驾护航**：除留余数选素数，双重散列求互质，黄金分割乘法法消除周期分布。
3. **墓碑维持链式连续**：开放寻址不能直接赋空，惰性删除确保探测链不被腰斩。
4. **工业工程演进**：Java 8 树化防 DoS，Redis 渐进 Rehash 防卡顿，一致性哈希统领分布式集群。

***

### 思考题与经典大厂面试题

1. **二次探测的覆盖率证明**：在二次探测中，若表大小 (m) 为 (4k+3) 型素数，证明增量序列 (\pm 1^2, \pm 2^2, \dots) 能够恰好探测到全表中至少一半的槽位。
2. **布隆过滤器（Bloom Filter）**：哈希表不仅能存储键值，还能只判断“是否存在”。请简述布隆过滤器如何利用多个哈希函数与位图（BitMap）实现空间极小、允许假阳性但不允许假阴性的集合判重。
3. **哈希碰撞 DoS 攻击防范**：攻击者若通过逆向工程构造出上万个具有完全相同哈希值的字符串向 Web 服务器发送 POST 请求，服务器将遭受什么后果？工业界编程语言（如 Python、Go、Rust）如何通过 SipHash 随机种子抵御此类攻击？