一、为什么需要哈希表？

想象你有一本字典，要查某个单词，有两种方法：

1. 从头翻到尾：最坏要翻 $n$ 页，太慢
2. 直接跳到对应页：如果知道单词在哪一页，$O(1)$ 就找到了
   哈希表就是第二种思路的工程实现。它支持三种字典操作：

• INSERT：插入一个元素
• SEARCH：查找一个元素
• DELETE：删除一个元素
  平均情况下，三种操作都只需要 $O(1)$ 时间。Python 的内置字典 dict 就是用哈希表实现的。

二、直接地址表（Direct-Address Table）

2.1 基本思想

如果所有可能的键（key）都来自集合 U={0,1,…,m−1}U = \{0, 1, \ldots, m-1\}U={0,1,…,m−1}，且 $m$ 不太大，可以直接用一个长度为 $m$ 的数组 $T$：

• 槽（slot）$k$ 存放键为 $k$ 的元素
• 如果集合中没有键为 $k$ 的元素，则 $T[k]=\text{NIL}$

键的全集 U = {0,1,...,9}，实际存储的键 K = {2,3,5,8}
下标:  0    1    2    3    4    5    6    7    8    9
T:   [NIL][NIL][*2 ][*3 ][NIL][*5 ][NIL][NIL][*8 ][NIL]
*k 表示指向键为 k 的元素的指针

2.2 三种操作

三种操作都极其简单，每种只需 $O(1)$ 时间：

// 查找：直接返回 T[k]
T[k]  // DIRECT-ADDRESS-SEARCH
// 插入：把元素 x 放到槽 x.key
T[x.key] = x  // DIRECT-ADDRESS-INSERT
// 删除：把槽置为 NIL
T[x.key] = NIL  // DIRECT-ADDRESS-DELETE

2.3 直接地址表的缺点

如果键的全集 $U$ 很大（比如所有 64 位整数，$|U|=2^{64}$），分配这么大的数组根本不现实。哈希表就是为了解决这个问题而生的。

三、哈希表的核心思想

3.1 从"直接映射"到"哈希映射"

直接地址表：键 $k$ 存在槽 $k$
哈希表：键 $k$ 存在槽 $h(k)$，其中 $h$ 是哈希函数
h:U→{0,1,…,m−1}h : U \rightarrow \{0, 1, \ldots, m-1\}h:U→{0,1,…,m−1}
哈希函数把巨大的键空间 $U$ 压缩映射到大小为 $m$ 的数组上。$m$ 通常远小于 $|U|$。

3.2 负载因子

定义负载因子 $\alpha$（读作 alpha）：
$$\alpha =\frac{n}{m}$$
其中 $n$ 是表中实际存储的元素个数，$m$ 是哈希表槽的数量。$\alpha$ 表示每个槽平均存放多少个元素。

3.3 碰撞（Collision）

由于 $|U|>m$，必然存在两个不同的键 $k_1\ne k_2$，使得 $h(k_1)=h(k_2)$，即它们被映射到同一个槽。这种情况叫做碰撞。

              哈希函数 h
  k1  ──────────────────────┐
  k2  ─────────┐            │
  k3  ─────────┴──→  槽 j  (k2 和 k3 碰撞了)
  k4  ──────────────────────┴──→  槽 j
  k5  ──────────────────────────→  槽 i

处理碰撞有两种主要方法：链接法（Chaining） 和 开放地址法（Open Addressing）。

四、链接法（Chaining）

4.1 思想

在每个槽里放一个链表，所有哈希到该槽的元素都追加到这个链表里。

m=9，哈希函数 h(k) = k mod 9
插入键: 5, 28, 19, 15, 20, 33, 12, 17, 10
槽 0: NIL
槽 1: 10 -> 19 -> 28 -> NIL
槽 2: 20 -> 11 -> NIL
槽 3: 12 -> NIL
槽 4: NIL
槽 5: 5 -> NIL
槽 6: 33 -> 15 -> NIL
槽 7: NIL
槽 8: 17 -> NIL

4.2 三种操作伪代码

CHAINED-HASH-INSERT(T, x)
    LIST-PREPEND(T[h(x.key)], x)   // 头插，O(1)
CHAINED-HASH-SEARCH(T, k)
    return LIST-SEARCH(T[h(k)], k)  // 遍历链表，O(链表长度)
CHAINED-HASH-DELETE(T, x)
    LIST-DELETE(T[h(x.key)], x)    // 双向链表 O(1)，单向链表 O(n)

4.3 流程图

4.4 性能分析

最坏情况

所有 $n$ 个键都哈希到同一个槽，链表长度为 $n$，查找时间退化为 $\Theta (n)$，和普通链表一样糟糕。但这是极端情况，实践中不会发生。

平均情况（假设独立均匀哈希）

独立均匀哈希：每个键等概率地落入任意一个槽，且不同键的落点互相独立。
定理 11.1（失败查找）：
在链接法哈希表中，一次失败的查找（要找的键不在表中）的平均时间为 $\Theta (1+\alpha )$。
直觉：失败查找要遍历完整条链表，链表平均长度为 $\alpha$，加上计算哈希值的 $O(1)$ 时间，共 $\Theta (1+\alpha )$。
定理 11.2（成功查找）：
在链接法哈希表中，一次成功的查找的平均时间也是 $\Theta (1+\alpha )$。

结论

如果 $n=O(m)$，即元素个数与槽数同阶，则：
$$\alpha =\frac{n}{m}=O(1)$$
三种字典操作的平均时间都是 $O(1)$。

五、哈希函数的设计

好的哈希函数应尽量满足"独立均匀"：每个键等可能地落入任意槽，且不同键的落点相互独立。

5.1 除法哈希（Division Method）

$$h(k)=k\mathrm{mod}m$$

• 简单，只需一次除法
• 建议 $m$ 选不接近 $2$ 的幂次的素数，避免规律性碰撞
• 例：$m=12$，$k=100$，则 $h(100)=4$

5.2 乘法哈希（Multiplication Method）

$$h(k)=\lfloor m\cdot (kA\mathrm{mod}1)\rfloor$$
其中 $0<A<1$，$kA\mathrm{mod}1$ 表示 $kA$ 的小数部分。

• $m$ 的选取更自由，不依赖 $A$ 的选择
• Knuth 建议 $A\approx (\sqrt{5}-1)/2\approx 0.6180$

乘移位法（Multiply-Shift，实际常用）

当 $m=2^{\ell }$ 时，可以用整数运算高效实现：
$$h_a(k)=(ka\mathrm{mod}{2}^w)\gg (w-\ell )$$
其中 $w$ 是机器字长（如 32 或 64），$a$ 是奇数。只需乘法、减法、右移三条机器指令。
例：$k=123456$，$\ell =14$，$m=2^{14}=16384$，$w=32$，$a=2654435769$
$$ka=327706022297664=76300\times 2^{32}+17612864$$
取低 32 位 $r_0=17612864$，右移 $32-14=18$ 位，得 $h_a(k)=67$。

5.3 随机哈希与全域哈希（Universal Hashing）

静态哈希函数（固定不变）有一个隐患：恶意对手可以构造让所有键都碰撞的输入，使性能退化到 $\Theta (n)$。
解决方法：随机哈希——在程序启动时从一族哈希函数中随机选一个。
全域哈希族定义：哈希函数族 $\mathcal{H}$ 是全域的，当且仅当对任意两个不同的键 $k_1,k_2$：
$$\underset{h\in \mathcal{H}}{\mathrm{Pr}}[h(k_1)=h(k_2)]\le \frac{1}{m}$$
即随机选到的哈希函数让两个不同键碰撞的概率不超过 $\frac{1}{m}$。

基于数论的全域哈希族

选一个足够大的素数 $p$（使得所有可能的键都在 $0$ 到 $p-1$ 之间），定义：
$$h_{ab}(k)=((ak+b)\mathrm{mod}p)\mathrm{mod}m$$
其中 a∈{1,…,p−1}a \in \{1,\ldots,p-1\}a∈{1,…,p−1}，b∈{0,…,p−1}b \in \{0,\ldots,p-1\}b∈{0,…,p−1}。
这个哈希族 ${\mathcal{H}}_{pm}$ 共有 $p(p-1)$ 个哈希函数，且可以证明是全域的（任意两个不同键碰撞概率 $\le 1/m$）。
例：$p=17$，$m=6$，$a=3$，$b=4$：
$$h_{3,4}(8)=((3\times 8+4)\mathrm{mod}17)\mathrm{mod}6=(28\mathrm{mod}17)\mathrm{mod}6=11\mathrm{mod}6=5$$

推论 11.3（全域哈希的性能保证）

使用全域哈希 + 链接法，对 $m$ 个槽的初始空表进行 $s$ 次 INSERT/SEARCH/DELETE 操作（其中 INSERT 共 $n=O(m)$ 次），期望总时间为 $\Theta (s)$。

六、开放地址法（Open Addressing）

6.1 基本思想

链接法把溢出的元素放到链表里（在表外）。开放地址法不用链表，所有元素都直接存在哈希表数组里。

• 负载因子 $\alpha \le 1$（最多存 $m$ 个元素）
• 发生碰撞时，按照一定顺序探查（probe）其他槽，直到找到空槽
  哈希函数变成两个参数的形式：
  h:U×{0,1,…,m−1}→{0,1,…,m−1}h : U \times \{0, 1, \ldots, m-1\} \rightarrow \{0, 1, \ldots, m-1\}h:U×{0,1,…,m−1}→{0,1,…,m−1}
  第二个参数是探查编号（从 0 开始）。探查序列 $⟨h(k,0),h(k,1),\dots ,h(k,m-1)⟩$ 必须是 $⟨0,1,\dots ,m-1⟩$ 的一个排列（保证能访问所有槽）。

6.2 插入与查找伪代码

HASH-INSERT(T, k)
    i = 0
    重复：
        q = h(k, i)
        如果 T[q] == NIL：
            T[q] = k
            返回 q
        否则：
            i = i + 1
    直到 i == m
    报错："哈希表已满"
HASH-SEARCH(T, k)
    i = 0
    重复：
        q = h(k, i)
        如果 T[q] == k：
            返回 q
        i = i + 1
    直到 T[q] == NIL 或 i == m
    返回 NIL

开放寻址法哈希表（Open Addressing）— 从零理解代码流程

一、和链接法的核心区别

上一节讲的链接法（Chaining）遇到冲突时，把多个键挂在同一个槽的链表上。
开放寻址法的思路完全不同：所有键直接存在数组槽里，一个槽只放一个键。遇到冲突时，按照一个探查序列（probe sequence）依次找下一个可用的空槽。

链接法：
  槽 1 → [10] → [19] → [28] → NIL   （链表）
开放寻址法：
  槽 1: 10     ← 键直接存在槽里
  槽 2: 19     ← 冲突，探查到槽 2
  槽 3: 28     ← 又冲突，探查到槽 3

二、核心概念：探查函数 h(k, i)

开放寻址法的哈希函数多了一个参数 $i$，叫做探查次数（probe number）：
h(k,i)→{0,1,…,m−1}h(k, i) \to \{0, 1, \ldots, m-1\}h(k,i)→{0,1,…,m−1}

• $k$ 是键，$i$ 从 $0$ 开始递增
• $i=0$ 是第一次尝试，$i=1$ 是第一次冲突后的尝试，以此类推
• 对于每个键 $k$，当 $i$ 从 $0$ 到 $m-1$ 时，$h(k,0),h(k,1),\dots ,h(k,m-1)$ 必须覆盖所有槽（全排列），保证一定能找到空位
  常见的三种探查策略：

---

策略	公式	特点
线性探查	$h(k,i)=(h^{\prime }(k)+i)\mathrm{mod}m$	简单，但有一次聚集问题
二次探查	$h(k,i)=(h^{\prime }(k)+c_{1}i+c_2{i}^2)\mathrm{mod}m$	减少聚集，但有二次聚集
双重哈希	$h(k,i)=(h_1(k)+i\cdot h_2(k))\mathrm{mod}m$	最均匀，实践中最常用

---

三、HASH-INSERT 逐行解析

伪代码：

HASH-INSERT(T, k)
    i = 0
    重复：
        q = h(k, i)
        如果 T[q] == NIL：
            T[q] = k
            返回 q
        否则：
            i = i + 1
    直到 i == m
    报错："哈希表已满"

白话翻译，一步一步：

第1步：从 i=0 开始（第一次探查）
第2步：计算槽编号 q = h(k, i)
第3步：判断 T[q]
    - 如果是 NIL（空槽）→ 把键 k 放进去，返回槽编号 q，完成
    - 如果不是 NIL（已被占用）→ i 加 1，回到第2步
第4步：如果 i 已经等于 m（探查了所有 m 个槽都满了）→ 报错

执行流程（ASCII）：

HASH-INSERT(T, k)
        |
        v
      i = 0
        |
        v
  q = h(k, i)  <─────────────────────┐
        |                             |
        v                             |
   T[q] == NIL?                       |
    /        \                        |
  是           否                     |
  |             |                    |
  v             v                    |
T[q] = k     i = i + 1              |
返回 q           |                    |
              i == m? ──否──────────┘
                |
               是
                |
              报错

四、HASH-SEARCH 逐行解析

伪代码：

HASH-SEARCH(T, k)
    i = 0
    重复：
        q = h(k, i)
        如果 T[q] == k：
            返回 q
        i = i + 1
    直到 T[q] == NIL 或 i == m
    返回 NIL

白话翻译：

第1步：从 i=0 开始
第2步：计算槽编号 q = h(k, i)
第3步：如果 T[q] == k → 找到了，返回 q
第4步：i 加 1，然后判断停止条件：
    - T[q] == NIL（遇到空槽）→ 确认不存在，返回 NIL
    - i == m（探查完所有槽）→ 确认不存在，返回 NIL
    - 否则回到第2步继续

执行流程（ASCII）：

HASH-SEARCH(T, k)
        |
        v
      i = 0
        |
        v
  q = h(k, i)  <─────────────────────┐
        |                             |
        v                             |
   T[q] == k?                        |
    /        \                        |
  是           否                     |
  |             |                    |
  v             v                    |
返回 q        i = i + 1              |
                |                    |
        T[q]==NIL 或 i==m?           |
           /        \                |
          是          否─────────────┘
          |
          v
       返回 NIL

关键点：为什么遇到 NIL 就停止？
插入键 $k$ 时，是沿探查序列 $h(k,0),h(k,1),\dots$ 找到第一个空槽放入的。查找走同一条路，如果某个槽是 NIL（从未被用过），$k$ 当初绝不可能"跳过"这个 NIL 放到后面——它一定会在这里被插入。所以遇到 NIL 就能确认 $k$ 不存在。

五、具体插入过程演示

以 $m=9$，使用线性探查 $h(k,i)=(k\mathrm{mod}9+i)\mathrm{mod}9$，依次插入 5、28、19、15、20：

插入键	i=0 的槽	冲突?	最终落槽	说明
5	$5\mathrm{mod}9=5$	否	5	直接放入
28	$28\mathrm{mod}9=1$	否	1	直接放入
19	$19\mathrm{mod}9=1$	是（28在）	2	探查 i=1，槽2空
15	$15\mathrm{mod}9=6$	否	6	直接放入
20	$20\mathrm{mod}9=2$	是（19在）	3	探查 i=1，槽3空

---

插入后的状态：

槽 0: NIL
槽 1: 28   ← h(28)=1，直接放入
槽 2: 19   ← h(19)=1 冲突，i=1 探查到槽 2
槽 3: 20   ← h(20)=2 冲突（槽2被19占），i=1 探查到槽 3
槽 4: NIL
槽 5:  5   ← h(5)=5，直接放入
槽 6: 15   ← h(15)=6，直接放入
槽 7: NIL
槽 8: NIL
槽1-3 连成一片 → 这就是线性探查的"一次聚集"现象

六、为什么删除不能直接置 NIL？

这是开放寻址法最容易出错的地方。
问题场景：

假设 h(A,0)=1，h(B,0)=1（冲突），h(B,1)=2
插入 A → 放入槽 1
插入 B → 槽 1 冲突，探查到槽 2 放入
当前状态：
  T[1] = A
  T[2] = B

现在直接删除 A，把槽 1 置为 NIL：

T[1] = NIL
T[2] = B

再查找 B：

h(B,0) = 1 → T[1] = NIL → 遇到 NIL，停止！返回"未找到"

但 B 还在槽 2！这就产生了 bug。
正确做法：使用 DELETED 标记（逻辑删除）

删除 A：把 T[1] 标记为 DELETED，不清空
T[1] = DELETED
T[2] = B

再查找 B：

h(B,0) = 1 → T[1] = DELETED → 不是 NIL，继续探查
h(B,1) = 2 → T[2] = B → 找到！

三种状态的处理规则：

槽的状态	INSERT	SEARCH	说明
NIL	可以插入，停止	停止（键不存在）	从未使用过
DELETED	可以插入（复用）	跳过，继续探查	曾有键，已删除
有键	冲突，继续探查	比较是否匹配	正常使用

---

七、完整 C++ 实现（含详细注释）

/*
 * 开放寻址法哈希表实现
 * 探查策略：双重哈希
 *   h(k, i) = (h1(k) + i * h2(k)) mod m
 *   h1(k) = k mod m
 *   h2(k) = 1 + (k mod (m-1))    保证 h2 不为 0，m 取素数时与 m 互质
 *
 * 编译：g++ -std=c++17 -o open_addr open_addr.cpp
 */
#include <iostream>
#include <vector>
#include <optional>
#include <stdexcept>
#include <string>
struct OpenAddressHashTable {
    int m;                              // 槽数量（建议取素数）
    std::vector<std::optional<int>> T;  // 槽数组，nullopt 表示 NIL
    std::vector<bool> deleted;          // true 表示该槽是 DELETED 状态
    OpenAddressHashTable(int slots)
        : m(slots), T(slots, std::nullopt), deleted(slots, false) {}
    // 第一个哈希函数：除法哈希
    int h1(int key) const {
        return ((key % m) + m) % m;  // 处理负数键
    }
    // 第二个哈希函数：步长函数，结果在 [1, m-1]，永不为 0
    // 若 m 为素数，h2(k) 与 m 互质，探查序列可覆盖全部槽
    int h2(int key) const {
        return 1 + ((key % (m - 1)) + (m - 1)) % (m - 1);
    }
    // 探查函数：双重哈希
    // i=0 时等于 h1(k)，后续每步增加 h2(k)
    int h(int key, int i) const {
        return (h1(key) + i * h2(key)) % m;
    }
    // --------------------------------------------------
    // INSERT：将键插入哈希表，返回插入的槽编号
    // --------------------------------------------------
    int insert(int key) {
        int i = 0;
        while (i < m) {
            int q = h(key, i);  // 计算第 i 次探查的槽编号
            // 槽为 NIL 或 DELETED：都可以用来存放新键
            // DELETED 槽是被逻辑删除的位置，可以复用
            if (!T[q].has_value() || deleted[q]) {
                T[q] = key;         // 写入键
                deleted[q] = false; // 清除删除标记
                return q;           // 返回插入位置
            }
            // 该槽已被占用，尝试下一个探查位置
            i++;
        }
        // 探查了所有 m 个槽都没有空位
        throw std::runtime_error("哈希表已满");
    }
    // --------------------------------------------------
    // SEARCH：查找键，返回槽编号，未找到返回 -1
    // --------------------------------------------------
    int search(int key) const {
        int i = 0;
        while (i < m) {
            int q = h(key, i);
            // 遇到真正的 NIL 槽（不是 DELETED）：停止
            // 理由：若 key 存在，当初插入时一定经过此处，不可能绕过去
            if (!T[q].has_value() && !deleted[q]) {
                return -1;
            }
            // 该槽有键、未被删除、且匹配：找到
            if (T[q].has_value() && !deleted[q] && T[q].value() == key) {
                return q;
            }
            // 该槽是 DELETED，或有键但不匹配：继续探查
            i++;
        }
        return -1;  // 探查了所有槽，未找到
    }
    // --------------------------------------------------
    // DELETE：逻辑删除（打 DELETED 标记，不清空槽）
    // --------------------------------------------------
    bool remove(int key) {
        int q = search(key);
        if (q == -1) return false;  // 键不存在
        deleted[q] = true;          // 只标记，不清空
        return true;
    }
    // 打印哈希表状态（调试用）
    void print() const {
        for (int j = 0; j < m; j++) {
            std::cout << "槽 " << j << ": ";
            if (!T[j].has_value()) {
                std::cout << "NIL";
            } else if (deleted[j]) {
                std::cout << "DELETED";
            } else {
                std::cout << T[j].value();
            }
            std::cout << "\n";
        }
    }
};
int main() {
    // m=11（素数），双重哈希效果好
    OpenAddressHashTable ht(11);
    // 插入 9 个键
    int keys[] = {10, 22, 31, 4, 15, 28, 17, 88, 59};
    std::cout << "== 插入过程 ==\n";
    for (int k : keys) {
        int slot = ht.insert(k);
        std::cout << "insert " << k << " -> 槽 " << slot << "\n";
    }
    std::cout << "\n== 插入后哈希表 ==\n";
    ht.print();
    // 查找测试
    std::cout << "\n查找 15: 槽 " << ht.search(15) << "\n";
    std::cout << "查找 99: 槽 " << ht.search(99) << "\n";
    // 删除测试
    ht.remove(15);
    std::cout << "\n删除 15 后：\n";
    std::cout << "  查找 15: 槽 " << ht.search(15) << "\n";  // -1
    std::cout << "  查找 28: 槽 " << ht.search(28) << "\n";  // 仍然找得到
    std::cout << "\n== 删除后哈希表 ==\n";
    ht.print();
    return 0;
}

八、程序实际输出

== 插入过程 ==
insert 10 -> 槽 10
insert 22 -> 槽 0
insert 31 -> 槽 9
insert  4 -> 槽 4
insert 15 -> 槽 5     (h1=4 冲突，h2=6，槽(4+6)%11=10 冲突，槽(4+12)%11=5 空)
insert 28 -> 槽 6
insert 17 -> 槽 3     (h1=6 冲突，探查到槽 3)
insert 88 -> 槽 7     (h1=0 冲突，多次探查到槽 7)
insert 59 -> 槽 2     (h1=4 冲突，多次探查到槽 2)
== 插入后哈希表 ==
槽  0: 22
槽  1: NIL
槽  2: 59
槽  3: 17
槽  4:  4
槽  5: 15
槽  6: 28
槽  7: 88
槽  8: NIL
槽  9: 31
槽 10: 10
查找 15: 槽 5
查找 99: 槽 -1
删除 15 后：
  查找 15: 槽 -1
  查找 28: 槽 6
== 删除后哈希表 ==
槽  0: 22
槽  1: NIL
槽  2: 59
槽  3: 17
槽  4:  4
槽  5: DELETED     ← 打了标记，不是 NIL
槽  6: 28
槽  7: 88
槽  8: NIL
槽  9: 31
槽 10: 10

九、时间复杂度分析

设装载因子 $\alpha =n/m$，其中 $n$ 为当前键数，$m$ 为槽数，且必须满足 $\alpha <1$。
在均匀哈希假设下，期望探查次数为：
不成功的查找：
$$E[\text{探查次数（失败）}]\le \frac{1}{1-\alpha }$$
成功的查找：
$$E[\text{探查次数（成功）}]\le \frac{1}{\alpha }\ln \frac{1}{1-\alpha }$$
不同装载因子下的数值（$m=10$）：

键数 $n$	装载因子 $\alpha$	失败查找期望	成功查找期望
1	0.10	1.11	1.05
5	0.50	2.00	1.39
8	0.80	5.00	2.01
9	0.90	10.0	2.56
9.5	0.95	20.0	3.15

---

装载因子越接近 1，性能急剧下降。实践中通常保持 $\alpha \le 0.7$，超过时扩容（rehash）。

十、开放寻址法 vs 链接法对比

---

维度	开放寻址法	链接法
内存布局	键存在连续数组（cache 友好）	键在链表节点（随机内存）
装载因子	必须 $\alpha <1$	可以 $\alpha >1$
删除操作	需要 DELETED 标记，较复杂	直接从链表删除，简单
对哈希函数质量依赖	高（聚集影响严重）	较低
额外指针开销	无	每个节点需要指针
最坏时间复杂度	$O(m)$	$O(n)$

---

6.3 删除的难点

不能直接把槽设为 NIL，否则会"截断"探查序列，使后续插入的元素找不到。
解决方案：用特殊值 DELETED 标记被删除的槽。插入时把 DELETED 当空槽用，查找时跳过 DELETED 继续探查。

6.4 线性探查（Linear Probing）

最简单的开放地址法：
$$h(k,i)=(h_1(k)+i)\mathrm{mod}m$$
发生碰撞就往后探查下一个槽，到末尾则回到开头。

m=10，h1(k) = k mod 10
插入顺序：74, 43, 93, 18, 82, 38, 92
槽:  0    1    2    3    4    5    6    7    8    9
    [ ] [ ] [ ] [43] [74] [93] [82] [38] [18] [92]
说明：
  74 -> 槽4（空，直接放）
  43 -> 槽3（空，直接放）
  93 -> 槽3（占用）-> 槽4（占用）-> 槽5（空，放入）等等

主聚集问题：连续占用的槽越来越长，新插入的元素越来越难找到空槽，平均查找时间变长。这是线性探查的缺点。
优点：在有缓存的现代 CPU 上，连续槽通常在同一缓存行，访问非常快（缓存友好）。

线性探查的删除（无需 DELETED 标记）

线性探查可以不用 DELETED，而是在删除后"修复"探查序列。
定义辅助函数 $g(k,q)$：键 $k$ 的探查序列中，到达槽 $q$ 时的探查编号。
$$g(k,q)=(q-h_1(k))\mathrm{mod}m$$
删除槽 $q$ 的键后，检查后续槽，若某个键 $k^{\prime }$ 在槽 $q^{\prime }$ 处，且 $g(k^{\prime },q)<g(k^{\prime },q^{\prime })$（即当初插入 $k^{\prime }$ 时曾经探查过 $q$，但因为 $q$ 被占用才移到了 $q^{\prime }$），则把 $k^{\prime }$ 移回到空出来的槽 $q$，递归处理。

6.5 双重哈希（Double Hashing）

双重哈希是开放地址法中性能最好的方案之一：
$$h(k,i)=(h_1(k)+i\cdot h_2(k))\mathrm{mod}m$$

• 第一次探查到 $h_1(k)$，之后每次步长为 $h_2(k)$
• 要保证 $h_2(k)$ 与 $m$ 互质，否则不能覆盖所有槽
  常用设置：$m$ 为素数，$h_1(k)=k\mathrm{mod}m$，$h_2(k)=1+(k\mathrm{mod}{m}^{\prime })$，其中 $m^{\prime }=m-1$。
  例：$m=13$，$h_1(k)=k\mathrm{mod}13$，$h_2(k)=1+(k\mathrm{mod}11)$，插入 $k=14$：

第0次探查：h(14,0) = (1 + 0*4) mod 13 = 1   （占用，继续）
第1次探查：h(14,1) = (1 + 1*4) mod 13 = 5   （占用，继续）
第2次探查：h(14,2) = (1 + 2*4) mod 13 = 9   （空！放入）

6.6 开放地址法的性能分析

假设独立均匀排列哈希（每个探查序列等概率为 $⟨0,\dots ,m-1⟩$ 的任意排列），且 $\alpha <1$：
定理 11.6（失败查找）：
$$E[\text{探查次数（失败）}]\le \frac{1}{1-\alpha }$$
定理 11.8（成功查找）：
$$E[\text{探查次数（成功）}]\le \frac{1}{\alpha }\ln \frac{1}{1-\alpha }$$
直觉：
$$\frac{1}{1-\alpha }=1+\alpha +{\alpha }^2+{\alpha }^3+\cdots$$
第一次探查必定发生；以概率约 $\alpha$ 第一个槽被占用需要第二次探查；以概率约 ${\alpha }^2$ 前两个槽都被占用需要第三次，以此类推。

负载因子 $\alpha$	失败查找平均探查次数	成功查找平均探查次数
$0.5$（半满）	$\le 2$	$\le 1.39$
$0.9$（九成满）	$\le 10$	$\le 2.56$
$1.0$（全满）	$\infty$	$H_m\approx \ln m$

---

七、链接法 vs 开放地址法 对比

---

对比项	链接法	开放地址法
负载因子 $\alpha$	可以 $>1$	必须 $<1$
额外内存	需要链表指针	不需要（全在表内）
缓存友好性	差（指针跳转）	好（连续内存探查）
删除操作	简单（双向链表 $O(1)$）	复杂（需 DELETED 或修复）
最坏情况	$\Theta (n)$（全碰撞）	$\Theta (n)$（全碰撞）
平均情况	$O(1)$（均摊）	$O(1)$（$\alpha <1$）
推荐场景	需要频繁删除	内存紧张、缓存性能要求高

---

八、完整可运行 C++ 代码：链接法哈希表

#include <iostream>
#include <vector>
#include <list>
#include <stdexcept>
// 使用链接法（Chaining）实现的哈希表
// 键类型为 int，哈希函数为除法哈希 h(k) = k mod m
struct ChainingHashTable {
    int m;                          // 槽数量
    std::vector<std::list<int>> T;  // T[j] 是一个链表，存放哈希值为 j 的所有键
    // 构造函数：初始化 m 个空链表
    ChainingHashTable(int slots) : m(slots), T(slots) {}
    // 哈希函数：除法哈希
    int h(int key) const {
        return ((key % m) + m) % m;  // 加 m 再取模，处理负数键
    }
    // INSERT：在链表头部插入（O(1)）
    void insert(int key) {
        int j = h(key);
        T[j].push_front(key);  // 头插
    }
    // SEARCH：遍历链表查找（O(1) 均摊）
    bool search(int key) const {
        int j = h(key);
        for (int k : T[j]) {
            if (k == key) return true;
        }
        return false;
    }
    // DELETE：从链表中删除（双向链表 O(1)）
    void remove(int key) {
        int j = h(key);
        T[j].remove(key);  // std::list::remove 是 O(链表长度)，但均摊 O(1)
    }
    // 打印哈希表当前状态
    void print() const {
        for (int j = 0; j < m; j++) {
            std::cout << "槽 " << j << ": ";
            for (int k : T[j]) {
                std::cout << k << " -> ";
            }
            std::cout << "NIL" << std::endl;
        }
    }
};
int main() {
    // 创建一个 9 个槽的哈希表（对应书中 Exercise 11.2-2）
    ChainingHashTable ht(9);
    // 插入键：5, 28, 19, 15, 20, 33, 12, 17, 10
    // 哈希函数 h(k) = k mod 9
    int keys[] = {5, 28, 19, 15, 20, 33, 12, 17, 10};
    for (int k : keys) {
        ht.insert(k);
    }
    std::cout << "== 插入后的哈希表 ==" << std::endl;
    ht.print();
    // 查找测试
    std::cout << "\n查找 19: " << (ht.search(19) ? "找到" : "未找到") << std::endl;
    std::cout << "查找 99: " << (ht.search(99) ? "找到" : "未找到") << std::endl;
    // 删除测试
    ht.remove(19);
    std::cout << "\n删除 19 后：" << std::endl;
    ht.print();
    return 0;
}

运行结果：

== 插入后的哈希表 ==
槽 0: NIL
槽 1: 10 -> 19 -> 28 -> NIL
槽 2: 20 -> NIL
槽 3: 12 -> NIL
槽 4: NIL
槽 5: 5 -> NIL
槽 6: 33 -> 15 -> NIL
槽 7: NIL
槽 8: 17 -> NIL
查找 19: 找到
查找 99: 未找到
删除 19 后：
槽 1: 10 -> 28 -> NIL
...

链接法哈希表（Chaining Hash Table）— 从零理解代码流程

一、哈希表是什么？先建立直觉

想象一个有编号格子的柜子，每个格子可以挂一条链子，链子上可以挂多个东西。
我们要存一个数字时，用一个公式算出"放到第几号格子"，然后挂上去。查找时，再用同样的公式算出格子编号，只在那个格子的链子里找，不用翻遍所有格子。
这就是链接法哈希表的核心思想：

键（key）  →  哈希函数 h(k)  →  槽编号 j  →  在 T[j] 的链表中操作

二、整体数据结构

T（vector，共 m 个槽）
T[0]:  NIL
T[1]:  10 -> 19 -> 28 -> NIL
T[2]:  20 -> NIL
T[3]:  12 -> NIL
T[4]:  NIL
T[5]:  5 -> NIL
T[6]:  33 -> 15 -> NIL
T[7]:  NIL
T[8]:  17 -> NIL

• 外层是一个 vector<list<int>>，大小为 $m$（槽数量）
• 每个槽 T[j] 是一条 std::list<int>（双向链表）
• 哈希冲突的键挂在同一条链表上

三、核心数据结构定义

struct ChainingHashTable {
    int m;                          // 槽的总数（决定哈希表的"格子数"）
    std::vector<std::list<int>> T;  // T[j] 是一个链表，存所有哈希到 j 的键

初始化时，T 是一个长度为 m 的 vector，每个元素是一条空链表：

构造 ChainingHashTable(9)：
T = [ [], [], [], [], [], [], [], [], [] ]
      0    1    2    3    4    5    6    7    8
     (9个空链表)

四、哈希函数：除法哈希

$$h(k)=k\mathrm{mod}m$$
代码实现：

int h(int key) const {
    return ((key % m) + m) % m;
    // 为什么要 +m 再 %m ？
    // C++ 中负数取模结果可能是负数，例如 -1 % 9 == -1
    // 加上 m 后再取模，保证结果始终在 [0, m-1] 范围内
    // 例：key = -1, m = 9
    //   (-1 % 9) = -1
    //   (-1 + 9) % 9 = 8  <-- 正确
}

本例中 $m=9$，对所有待插入键算哈希值：

键 k	计算过程	$h(k)=k\mathrm{mod}9$
5	5 mod 9	5
28	28 mod 9	1
19	19 mod 9	1
15	15 mod 9	6
20	20 mod 9	2
33	33 mod 9	6
12	12 mod 9	3
17	17 mod 9	8
10	10 mod 9	1

---

可以看到 28、19、10 都哈希到槽 1，15 和 33 都哈希到槽 6，这就是哈希冲突，链接法用链表来解决它。

五、INSERT 操作：头插法

void insert(int key) {
    int j = h(key);         // 第一步：计算哈希值，找到槽编号
    T[j].push_front(key);   // 第二步：插到链表头部（头插，O(1)）
}

为什么用头插而不是尾插？
头插是 $O(1)$，尾插也是 $O(1)$（std::list 维护了尾指针），但头插更简单，且"最近插入的元素最先被找到"（对某些访问模式有利）。
逐步插入过程（m=9，按顺序插入 5, 28, 19, 15, 20, 33, 12, 17, 10）：

初始状态：所有槽为空
插入 5：  h(5)=5   → T[5]: 5 -> NIL
插入 28： h(28)=1  → T[1]: 28 -> NIL
插入 19： h(19)=1  → T[1]: 19 -> 28 -> NIL   (头插，19在28前面)
插入 15： h(15)=6  → T[6]: 15 -> NIL
插入 20： h(20)=2  → T[2]: 20 -> NIL
插入 33： h(33)=6  → T[6]: 33 -> 15 -> NIL   (头插，33在15前面)
插入 12： h(12)=3  → T[3]: 12 -> NIL
插入 17： h(17)=8  → T[8]: 17 -> NIL
插入 10： h(10)=1  → T[1]: 10 -> 19 -> 28 -> NIL  (头插，10在最前)

最终状态（与程序输出一致）：

槽 0:  NIL
槽 1:  10 -> 19 -> 28 -> NIL
槽 2:  20 -> NIL
槽 3:  12 -> NIL
槽 4:  NIL
槽 5:  5 -> NIL
槽 6:  33 -> 15 -> NIL
槽 7:  NIL
槽 8:  17 -> NIL

六、SEARCH 操作：遍历链表

bool search(int key) const {
    int j = h(key);         // 第一步：算出槽编号
    for (int k : T[j]) {   // 第二步：遍历该槽的链表
        if (k == key) return true;
    }
    return false;           // 遍历完没找到，返回 false
}

示例：查找 19

h(19) = 1
遍历 T[1]: 10 -> 19 -> 28 -> NIL
  检查 10 == 19 ? 否
  检查 19 == 19 ? 是！→ 返回 true

示例：查找 99

h(99) = 99 mod 9 = 0
遍历 T[0]: NIL（空链表）
遍历结束 → 返回 false

时间复杂度分析：
设哈希表中共有 $n$ 个键，$m$ 个槽，定义装载因子：
$$\alpha =\frac{n}{m}$$
$\alpha$ 表示每个槽平均存放的键数。

• 最坏情况：所有键哈希到同一个槽，链表长度为 $n$，查找需要 $O(n)$
• 均摊情况（假设简单均匀哈希）：每个槽平均有 $\alpha$ 个键，查找期望时间为 $O(1+\alpha )$
  若 $m$ 与 $n$ 成正比（即 $\alpha =O(1)$），则查找均摊 $O(1)$。

七、DELETE 操作：链表删除

void remove(int key) {
    int j = h(key);    // 第一步：算出槽编号
    T[j].remove(key);  // 第二步：从链表中删除所有值等于 key 的节点
    // std::list::remove 会遍历链表，删除所有匹配项
    // 时间复杂度：O(链表长度)
}

示例：删除 19

h(19) = 1
T[1] 删除前: 10 -> 19 -> 28 -> NIL
T[1] 删除后: 10 -> 28 -> NIL

为什么删除比插入慢？

• 插入：直接头插，$O(1)$，不需要遍历
• 删除：必须先找到节点位置，$O(\text{链表长度})$
  如果键还带有卫星数据（satellite data），可以用指针直接定位节点，删除就变成真正的 $O(1)$——std::list 的 erase 在已知迭代器时是 $O(1)$。本例键是 int，用了更简单的 remove。

八、完整代码（含详细注释）

/*
 * 链接法哈希表实现
 * 键类型：int
 * 哈希函数：除法哈希 h(k) = k mod m
 * 冲突解决：链接法（每个槽是一条双向链表）
 *
 * 编译：g++ -std=c++11 -o hash_chaining hash_chaining.cpp
 */
#include <iostream>
#include <vector>
#include <list>
// -------------------------------------------------------
// 链接法哈希表结构体
// -------------------------------------------------------
struct ChainingHashTable {
    int m;                          // 槽（bucket）的数量
    std::vector<std::list<int>> T;  // T[j] 是存放哈希值为 j 的所有键的链表
    // 构造函数：创建 m 个空链表
    // 初始化列表语法：m(slots) 给 m 赋值，T(slots) 创建 slots 个空 list
    ChainingHashTable(int slots) : m(slots), T(slots) {}
    // --------------------------------------------------
    // 哈希函数：除法哈希 h(k) = k mod m
    // --------------------------------------------------
    int h(int key) const {
        // ((key % m) + m) % m 的目的：处理负数键
        // C++ 中负数对正数取模结果仍为负数（实现定义，但通常如此）
        // 例：(-1 % 9) 在 C++ 中为 -1，而我们需要 8
        // 加上 m 后再取模，将结果平移到 [0, m-1]
        return ((key % m) + m) % m;
    }
    // --------------------------------------------------
    // INSERT：将键插入哈希表
    // 策略：头插法，O(1)
    // --------------------------------------------------
    void insert(int key) {
        int j = h(key);        // 计算槽编号
        T[j].push_front(key);  // 插到链表头部，时间复杂度 O(1)
    }
    // --------------------------------------------------
    // SEARCH：查找键是否存在
    // 返回 true 表示找到，false 表示不存在
    // 均摊时间复杂度：O(1 + alpha)，alpha = n/m 为装载因子
    // --------------------------------------------------
    bool search(int key) const {
        int j = h(key);          // 定位到对应槽
        for (int k : T[j]) {     // 遍历该槽的链表
            if (k == key)
                return true;     // 找到，提前返回
        }
        return false;            // 整条链表遍历完，未找到
    }
    // --------------------------------------------------
    // DELETE：从哈希表中删除键
    // std::list::remove 会删除链表中所有等于 key 的节点
    // 时间复杂度：O(链表长度)
    // --------------------------------------------------
    void remove(int key) {
        int j = h(key);    // 定位到对应槽
        T[j].remove(key);  // 从链表中移除（若不存在，静默忽略）
    }
    // --------------------------------------------------
    // 打印哈希表当前状态（调试用）
    // --------------------------------------------------
    void print() const {
        for (int j = 0; j < m; j++) {
            std::cout << "槽 " << j << ": ";
            for (int k : T[j]) {
                std::cout << k << " -> ";
            }
            std::cout << "NIL" << std::endl;
        }
    }
};
// -------------------------------------------------------
// 主函数：演示插入、查找、删除
// -------------------------------------------------------
int main() {
    // 创建 9 个槽的哈希表（对应 CLRS 习题 11.2-2）
    ChainingHashTable ht(9);
    // 待插入的键序列
    int keys[] = {5, 28, 19, 15, 20, 33, 12, 17, 10};
    // 逐个插入
    // 插入过程：
    //   h(5)=5   → 槽5
    //   h(28)=1  → 槽1
    //   h(19)=1  → 槽1（冲突，头插到28前面）
    //   h(15)=6  → 槽6
    //   h(20)=2  → 槽2
    //   h(33)=6  → 槽6（冲突，头插到15前面）
    //   h(12)=3  → 槽3
    //   h(17)=8  → 槽8
    //   h(10)=1  → 槽1（冲突，头插到19前面）
    for (int k : keys) {
        ht.insert(k);
    }
    std::cout << "== 插入后的哈希表 ==" << std::endl;
    ht.print();
    // 查找测试
    // h(19) = 1，在 T[1] = {10, 19, 28} 中能找到
    std::cout << "\n查找 19: " << (ht.search(19) ? "找到" : "未找到") << std::endl;
    // h(99) = 0，T[0] 为空，找不到
    std::cout << "查找 99: " << (ht.search(99) ? "找到" : "未找到") << std::endl;
    // 删除测试：从 T[1] 中删除 19
    ht.remove(19);
    std::cout << "\n删除 19 后：" << std::endl;
    ht.print();
    return 0;
}

九、完整执行流程图

十、内存结构可视化

插入全部键之后，内存中的结构如下（ASCII 图）：

vector T（大小=9）
┌───┐
│ 0 │──► NIL
├───┤
│ 1 │──► [10] ──► [19] ──► [28] ──► NIL
├───┤
│ 2 │──► [20] ──► NIL
├───┤
│ 3 │──► [12] ──► NIL
├───┤
│ 4 │──► NIL
├───┤
│ 5 │──► [5] ──► NIL
├───┤
│ 6 │──► [33] ──► [15] ──► NIL
├───┤
│ 7 │──► NIL
├───┤
│ 8 │──► [17] ──► NIL
└───┘

删除 19 之后，槽 1 的链表变为：

│ 1 │──► [10] ──► [28] ──► NIL

十一、时间复杂度总结

设哈希表中有 $n$ 个键，$m$ 个槽，装载因子 $\alpha =n/m$。

操作	最坏情况	均摊期望（简单均匀哈希）
INSERT	$O(1)$	$O(1)$
SEARCH（成功）	$O(n)$	$\Theta (1+\alpha )$
SEARCH（失败）	$O(n)$	$\Theta (1+\alpha )$
DELETE	$O(n)$	$\Theta (1+\alpha )$

---

当 $m=\Theta (n)$ 时，$\alpha =O(1)$，所有操作均摊 $O(1)$。

十二、程序实际输出

== 插入后的哈希表 ==
槽 0: NIL
槽 1: 10 -> 19 -> 28 -> NIL
槽 2: 20 -> NIL
槽 3: 12 -> NIL
槽 4: NIL
槽 5: 5 -> NIL
槽 6: 33 -> 15 -> NIL
槽 7: NIL
槽 8: 17 -> NIL
查找 19: 找到
查找 99: 未找到
删除 19 后：
槽 0: NIL
槽 1: 10 -> 28 -> NIL
槽 2: 20 -> NIL
槽 3: 12 -> NIL
槽 4: NIL
槽 5: 5 -> NIL
槽 6: 33 -> 15 -> NIL
槽 7: NIL
槽 8: 17 -> NIL

九、完整可运行 C++ 代码：线性探查开放地址法

#include <iostream>
#include <vector>
#include <stdexcept>
// 使用线性探查（Linear Probing）的开放地址哈希表
// 槽的三种状态：EMPTY（空）、OCCUPIED（有元素）、DELETED（已删除标记）
struct LinearProbingHashTable {
    enum State { EMPTY, OCCUPIED, DELETED };  // 槽的三种状态
    struct Slot {
        int key;
        State state;
        Slot() : key(0), state(EMPTY) {}
    };
    int m;               // 槽总数
    int n;               // 当前存储的元素数量
    std::vector<Slot> T; // 哈希表数组
    LinearProbingHashTable(int slots) : m(slots), n(0), T(slots) {}
    // 辅助哈希函数（除法哈希）
    int h1(int key) const {
        return ((key % m) + m) % m;
    }
    // 线性探查的哈希函数：h(k, i) = (h1(k) + i) mod m
    int h(int key, int i) const {
        return (h1(key) + i) % m;
    }
    // INSERT：线性探查找到空槽或 DELETED 槽后插入
    void insert(int key) {
        if (n >= m)
            throw std::overflow_error("哈希表已满");
        for (int i = 0; i < m; i++) {
            int q = h(key, i);  // 第 i 次探查的槽编号
            // 空槽或已删除的槽都可以放入新元素
            if (T[q].state == EMPTY || T[q].state == DELETED) {
                T[q].key   = key;
                T[q].state = OCCUPIED;
                n++;
                return;
            }
        }
        throw std::overflow_error("哈希表已满（所有槽均被占用）");
    }
    // SEARCH：沿探查序列查找，遇到真正的空槽停止
    bool search(int key) const {
        for (int i = 0; i < m; i++) {
            int q = h(key, i);
            if (T[q].state == EMPTY) return false;      // 真空槽，键不存在
            if (T[q].state == OCCUPIED && T[q].key == key) return true;
            // state == DELETED 则跳过继续探查
        }
        return false;
    }
    // DELETE：标记为 DELETED，不直接置为 EMPTY
    void remove(int key) {
        for (int i = 0; i < m; i++) {
            int q = h(key, i);
            if (T[q].state == EMPTY) return;  // 键不存在
            if (T[q].state == OCCUPIED && T[q].key == key) {
                T[q].state = DELETED;  // 标记，而非真正清空
                n--;
                return;
            }
        }
    }
    // 打印哈希表状态
    void print() const {
        for (int j = 0; j < m; j++) {
            std::cout << "槽 " << j << ": ";
            if (T[j].state == EMPTY)    std::cout << "[EMPTY]";
            if (T[j].state == DELETED)  std::cout << "[DELETED]";
            if (T[j].state == OCCUPIED) std::cout << T[j].key;
            std::cout << std::endl;
        }
    }
};
int main() {
    // 创建 11 个槽的哈希表（对应书中 Exercise 11.4-1）
    LinearProbingHashTable ht(11);
    // 插入键：10, 22, 31, 4, 15, 28, 17, 88, 59
    // h(k, i) = (k + i) mod 11
    int keys[] = {10, 22, 31, 4, 15, 28, 17, 88, 59};
    std::cout << "== 插入过程 ==" << std::endl;
    for (int k : keys) {
        ht.insert(k);
        std::cout << "插入 " << k << " -> 槽 " << (((k % 11) + 11) % 11) << std::endl;
    }
    std::cout << "\n== 最终哈希表 ==" << std::endl;
    ht.print();
    // 查找测试
    std::cout << "\n查找 15: " << (ht.search(15) ? "找到" : "未找到") << std::endl;
    std::cout << "查找 99: " << (ht.search(99) ? "找到" : "未找到") << std::endl;
    // 删除测试
    ht.remove(22);
    std::cout << "\n删除 22 后，查找 22: "
              << (ht.search(22) ? "找到" : "未找到") << std::endl;
    return 0;
}

十、实际的考量（现代 CPU 与内存层次）

现代 CPU 的内存不是一个均匀速度的大块，而是有层次的：

速度（快→慢）：寄存器 -> L1缓存 -> L2缓存 -> L3缓存 -> 主内存
容量（小→大）：寄存器 -> L1缓存 -> L2缓存 -> L3缓存 -> 主内存

缓存以缓存行（通常 64 字节）为单位从主内存取数据。访问同一缓存行中的不同数据，代价接近于零（已经在缓存里了）。
对哈希表的影响：

• 链接法：链表节点散落在堆内存各处，每次跟随指针都可能触发缓存缺失，代价高
• 线性探查：连续探查相邻槽，通常在同一缓存行里，极其缓存友好
  因此，在注重缓存性能的现代工程中，线性探查往往优于链接法，尽管它在理论分析（RAM 模型）中表现不如双重哈希。
  Wee 哈希函数（书中 11.5.2 节）就是一种专门为现代 CPU 设计的哈希函数：它完全在寄存器中计算，速度比访问一次随机内存还快 2~10 倍。
  $$f_a(k)=\text{swap}((2k^2+ak)\mathrm{mod}{2}^w)$$
  其中 $\text{swap}(x)$ 交换 $x$ 的高半字和低半字，重复 $r$ 次（通常 $r=4$），再对 $m$ 取模。

十一、关键公式汇总

$$\alpha =\frac{n}{m}\text{（负载因子）}$$
$$\text{链接法失败查找}=\Theta (1+\alpha )$$
$$\text{链接法成功查找}=\Theta (1+\alpha )$$
$$\text{开放地址失败查找}\le \frac{1}{1-\alpha }$$
$$\text{开放地址成功查找}\le \frac{1}{\alpha }\ln \frac{1}{1-\alpha }$$
$$\text{全域哈希碰撞概率}\le \frac{1}{m}$$

十二、一句话总结

哈希表用哈希函数把大键空间压缩到小数组上，用链接法或开放地址法解决碰撞；只要负载因子 $\alpha$ 保持为常数，平均查找时间就是 $O(1)$；全域哈希从理论上保证了"再聪明的对手也无法让你的哈希表退化"。