散列表

概念

散列表（Hash Table，又称哈希表）是通过散列函数（hash function） $H$ 把关键字直接映射成存储地址的表： $H (k e y)$ 就是该记录该放的位置。

它与此前所有查找方法的根本区别是：不做比较。顺序查找、折半查找、B 树都靠"比大小"缩小范围，散列表靠"算地址"一步到位，因此平均查找时间是 O(1)。

代价是冲突（collision）：不同的关键字可能算出同一个地址。冲突不可避免——关键字空间远大于地址空间，抽屉原理（pigeonhole principle）决定了它必然发生。所以散列表的全部技术难点，都集中在"怎么处理冲突"。

一句话区分：折半查找是"每次排除一半"，散列是"一次算到门口"。前者 O(log n)，后者平均 O(1)，但后者要额外解决"好几个人算到同一个门口"的问题。

原理

一、散列函数的构造

好散列函数的标准只有两条：计算简单、地址分布均匀（让冲突尽量少）。

方法	形式	适用场景
除留余数法（最常用）	$H (k) = k mod p$	通用； $p$ 取不大于表长的最大质数
直接定址法	$H (k) = a \cdot k + b$	关键字连续、分布已知，不会冲突
数字分析法	取关键字中分布均匀的若干位	关键字位数多、且各位分布不均
平方取中法	$k^{2}$ 后取中间几位	关键字位数不多，取中位能充分混合
折叠法	分段相加后取低位	关键字位数很多

为什么 $p$ 要取质数：若 $p$ 含小因子（如 12 = 4×3），则所有以 4 或 3 为因子的关键字会集中到少数几个地址上，分布立刻变差。取质数能最大限度打散这种规律。

二、处理冲突的两大类方法

1. 开放定址法（open addressing）

冲突时不另开空间，而是在表内按探测序列另找一个空位：

H_{i} = (H (k) + d_{i}) mod m, i = 1, 2, 3, \dots

$m$ 是表长， $d_{i}$ 是第 $i$ 次的增量。按 $d_{i}$ 的取法分三种：

名称	$d_{i}$	探测序列（以 $H (k) = h$ 为例）	缺点
线性探测法	$1, 2, 3, \dots$	$h + 1, h + 2, h + 3, \dots$	产生一次聚集（primary clustering）：连续占用区越滚越大
平方探测法	$1^{2}, - 1^{2}, 2^{2}, - 2^{2}, \dots$	$h \pm 1^{2}, h \pm 2^{2}, \dots$	只探测部分单元； $m$ 为 $4 k + 3$ 型质数时可覆盖全表
双散列法	$i \cdot H_{2} (k)$	$h + H_{2} (k), h + 2 H_{2} (k), \dots$	需再设计一个散列函数

开放定址法不能直接删除元素。若把某元素抹成空，它后面那串被探测"挤"过去的元素就断了线索，查找会误判为不存在。正确做法是懒惰删除（lazy deletion）：给该单元打一个 删除标记（墓碑，tombstone），查找时"跳过但它不算空"，插入时可以复用。

2. 链地址法（separate chaining，又叫拉链法）

表本身只存 $m$ 个指针，所有同义词串成一条单链表。冲突不再是问题——插到链尾即可。

优点：从不出现"找不到空位"；删除直接摘链；装填因子 α 可以大于 1；代价是每个结点多一个指针域。

三、装填因子与 ASL

装填因子（load factor）：

α = \frac{n}{m} = \frac{表中已有记录数}{表长}

结论要记牢：散列表的平均查找长度只与 $α$ 有关，与 $n$ 、 $m$ 各自的绝对值无关。

冲突处理方法	成功 ASL（近似）	失败 ASL（近似）
线性探测	$\frac{1}{2} (1 + \frac{1}{1 - α})$	$\frac{1}{2} (1 + \frac{1}{(1 - α)^{2}})$
平方探测 / 双散列	$- \frac{1}{α} \ln (1 - α)$	$\frac{1}{1 - α}$
链地址法	$1 + \frac{α}{2}$	$α$

α 越大 → 冲突越多 → ASL 越长。这就是"散列表快"的前提：α 要压在合理范围内（工程上通常 ≤ 0.75，超了就扩容重散列）。

示例

例 1：同一组关键字，两种冲突处理的 ASL 对比

关键字序列 19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79，表长 $m = 13$ ，散列函数 $H (k) = k mod 13$ 。分别用线性探测法与链地址法建表，求等概率下查找成功与查找失败的平均查找长度。

第一步，逐个算初始散列地址 $k mod 13$ ：

关键字	19	14	23	1	68	20	84	27	55	11	10	79
$k mod 13$	6	1	10	1	3	7	6	1	3	11	10	1

第二步，线性探测逐个落位（探测次数即比较次数）：

关键字	初始地址	探测过程	落位	探测次数
19	6	6 空	6	1
14	1	1 空	1	1
23	10	10 空	10	1
1	1	1 占 → 2 空	2	2
68	3	3 空	3	1
20	7	7 空	7	1
84	6	6 占 → 7 占 → 8 空	8	3
27	1	1、2、3 占 → 4 空	4	4
55	3	3、4 占 → 5 空	5	3
11	11	11 空	11	1
10	10	10、11 占 → 12 空	12	3
79	1	1~8 占 → 9 空	9	9

第三步，写出散列表：

下标  0    1    2    3    4    5    6    7    8    9   10   11   12
    ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
    │ 空 │ 14 │  1 │ 68 │ 27 │ 55 │ 19 │ 20 │ 84 │ 79 │ 23 │ 11 │ 10 │
    └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘

第四步，算成功 ASL（12 个关键字，探测次数求和再平均）：

A S L_{成功} = \frac{1 + 1 + 1 + 2 + 1 + 1 + 3 + 4 + 3 + 1 + 3 + 9}{12} = \frac{30}{12} = 2.5

第五步，算失败 ASL（按"从地址 $i$ 出发探测到第一个空单元，含与该空单元的那次比较"口径）：

只有一个空单元（下标 0），所以从下标 0 出发 1 次就失败，从下标 12 出发要探 12、0 共 2 次，依此类推：

A S L_{失败} = \frac{1 + 13 + 12 + 11 + \dots + 2}{13} = \frac{91}{13} = 7

口径提醒：有的教材不把"与空单元比较"那一次计入，则分子为 $91 - 13 = 78$ ， $A S L_{失败} = 6$ 。考试按题目给的约定，两种都要会。

第六步，换成链地址法，同义词按插入顺序挂链：

下标 0 │→ NULL
下标 1 │→ [14] → [1] → [27] → [79] → NULL        链长 4
下标 2 │→ NULL
下标 3 │→ [68] → [55] → NULL                      链长 2
下标 4 │→ NULL
下标 5 │→ NULL
下标 6 │→ [19] → [84] → NULL                      链长 2
下标 7 │→ [20] → NULL                             链长 1
下标 8 │→ NULL
下标 9 │→ NULL
下标 10│→ [23] → [10] → NULL                      链长 2
下标 11│→ [11] → NULL                             链长 1
下标 12│→ NULL

链上的探测次数依次是 1,2,3,4 / 1,2 / 1,2 / 1 / 1,2 / 1，求和：

A S L_{成功} = \frac{(1 + 2 + 3 + 4) + (1 + 2) + (1 + 2) + 1 + (1 + 2) + 1}{12} = \frac{21}{12} = 1.75

失败时从 13 个地址出发，非空链要走到表尾的 NULL 才算失败，空链比较一次 NULL：

A S L_{失败} = \frac{12 + 13}{13} = \frac{25}{13} \approx 1.92

结论： $α = 12 / 13 \approx 0.92$ 已经很拥挤。即便如此，链地址法的成功 ASL（1.75）仍明显优于线性探测（2.5），失败 ASL 更是差了 3 倍多——因为线性探测有聚集效应，会被整片连续区拖累。

例 2：平方探测的探测序列

$m = 11$ （质数且 $11 = 4 \times 2 + 3$ ）， $H (k) = k mod 11$ ，依次插入 47, 7, 29, 11, 9, 84, 54, 20, 3。

关键字	初始地址	探测过程（ $h \pm 1^{2}, h \pm 2^{2} \dots$ ）	落位
47	3	3 空	3
7	7	7 空	7
29	7	7 占 → $7 + 1 = 8$ 空	8
11	0	0 空	0
9	9	9 空	9
84	7	7、8 占 → $7 - 1 = 6$ 空	6
54	10	10 空	10
20	9	9、10 占 → $9 + 1 = 10$ 占 → $9 - 1 = 8$ 占 → $9 + 4 = 2$ 空	2
3	3	3 占 → $3 + 1 = 4$ 空	4

下标  0    1    2    3    4    5    6    7    8    9   10
    ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
    │ 11 │ 空 │ 20 │ 47 │  3 │ 空 │ 84 │  7 │ 29 │  9 │ 54 │
    └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘

注意第 9 个关键字 3：它的初始地址 3 已被 47 占据、4 是空的，于是直接落到 4。平方探测的探测序列是"跳着走"的，因此不会像线性探测那样连成一片——这正是它抑制聚集的原因。

C 语言：开放定址（线性探测）与链地址法

#include <stdio.h>
#include <stdlib.h>

#define M 13                 /* 表长，取质数 */
#define EMPTY  -1
#define DELETED -2           /* 墓碑：懒惰删除标记 */

int h(int key) { return key % M; }

/* ---------- 开放定址：线性探测 ---------- */
int tbl[M];
void initTbl(void) { for (int i = 0; i < M; i++) tbl[i] = EMPTY; }

int openInsert(int key) {
    int i = h(key);
    for (int c = 0; c < M; c++) {
        if (tbl[i] == EMPTY || tbl[i] == DELETED) {  /* 空位或墓碑都能复用 */
            tbl[i] = key;
            return i;
        }
        i = (i + 1) % M;                             /* 线性探测 */
    }
    return -1;                                       /* 表满 */
}

/* 返回查找成功的探测次数；失败返回 0 */
int openSearch(int key) {
    int i = h(key), cnt = 0;
    while (tbl[i] != EMPTY && cnt < M) {
        cnt++;
        if (tbl[i] == key) return cnt;
        i = (i + 1) % M;
    }
    return 0;
}

/* ---------- 链地址法 ---------- */
typedef struct Node { int key; struct Node *next; } Node;
Node *chain[M];

void chainInsert(int key) {                          /* 头插法 */
    int i = h(key);
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key; p->next = chain[i]; chain[i] = p;
}

int chainSearch(int key) {
    int cnt = 0;
    for (Node *p = chain[h(key)]; p; p = p->next) {
        cnt++;
        if (p->key == key) return cnt;
    }
    return 0;
}

int main(void) {
    int keys[] = {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79};
    int n = 12;

    /* 线性探测 */
    initTbl();
    int sum = 0;
    for (int i = 0; i < n; i++) openInsert(keys[i]);
    printf("线性探测表: ");
    for (int i = 0; i < M; i++) {
        if (tbl[i] == EMPTY) printf("  _ ");
        else                 printf("%3d ", tbl[i]);
    }
    printf("\n");
    for (int i = 0; i < n; i++) sum += openSearch(keys[i]);
    printf("线性探测 ASL成功(实测) = %d/%d\n", sum, n);

    /* 链地址法 */
    for (int i = 0; i < n; i++) chainInsert(keys[i]);
    sum = 0;
    for (int i = 0; i < n; i++) sum += chainSearch(keys[i]);
    printf("链地址法 ASL成功(实测) = %d/%d\n", sum, n);
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

上面 openInsert 与 chainInsert 是本篇的核心：前者靠"探测序列 + 墓碑"，后者靠"链表串同义词"。运行后实测两个 ASL 分别是 30/12 与 21/12，与手算一致。

Python 对照

M = 13
EMPTY, DELETED = None, "DEL"

def h(key): return key % M

# —— 开放定址：线性探测 ——
tbl = [EMPTY] * M          # Python 用列表当数组，None 表示空
def open_insert(key):
    i = h(key)
    for _ in range(M):
        if tbl[i] is EMPTY or tbl[i] == DELETED:
            tbl[i] = key
            return i
        i = (i + 1) % M
    return -1

def open_search(key):      # 返回探测次数，0 表示失败
    i, cnt = h(key), 0
    while tbl[i] is not EMPTY and cnt < M:
        cnt += 1
        if tbl[i] == key: return cnt
        i = (i + 1) % M
    return 0

keys = [19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79]
for k in keys: open_insert(k)
print("线性探测表:", ["_" if v is EMPTY else v for v in tbl])
print("ASL成功:", sum(open_search(k) for k in keys) / len(keys))

# —— 链地址法：dict + list 一目了然 ——
chain = {i: [] for i in range(M)}
for k in keys:
    chain[k % M].append(k)
print("链:", {i: v for i, v in chain.items() if v})
succ = sum(chain[k % M].index(k) + 1 for k in keys)
print("ASL成功:", succ / len(keys))

# Python 自带的 dict / set 就是工业级散列表（开放定址 + 扰动函数）
d = {k: k for k in keys}
print("dict 查找 27:", 27 in d, " 查找 100:", 100 in d)

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

1. 必背结论

散列表不做比较，靠函数算地址，平均 ASL 为 O(1)；但最坏情况仍是 O(n)（全部关键字冲突成一条链）。
平均查找长度只取决于装填因子 α，与 $n$ 、 $m$ 单独的数值无关。
除留余数法中 $p$ 取"不大于表长的最大质数"，目的是让分布更均匀。
冲突无法避免，只能处理。处理方式：开放定址（线性探测 / 平方探测 / 双散列）、链地址法、再散列法。
开放定址法删除元素必须用墓碑标记，不能直接把单元置空。
链地址法 α 可以 > 1（每链平均更长），开放定址法必须 α < 1（表内必须有空位）。

2. 手算 ASL 的标准流程

成功 ASL：逐键算 $H (k)$ → 写探测过程 → 每个键的探测次数 / 键的个数。失败 ASL：对表上每一个地址，从它出发探测到"空单元"为止的比较次数，再除以表长 $m$ 。

失败 ASL 的分母永远是表长 $m$ （或 $H$ 的取值个数），不是关键字的个数。 这是最常错的一处。

3. 易错点

失败 ASL 的口径：把"与空单元的那次比较"算不算进去，各教材不一致。线性探测例中数值可能是 7 或 6，链地址法可能是 25/13 或 12/13。必须按题目约定，并写清楚。
平方探测不一定能扫遍全表：表长 $m$ 必须为 $4 k + 3$ 型的质数，才能保证探测序列覆盖所有单元；否则可能出现"表里明明有空位却找不到"的假满。
线性探测的聚集：一次聚集让连续占用区雪球越滚越大，是它 ASL 明显劣于链地址法的根本原因；平方探测和双散列就是为消除聚集而设计的。
除留余数法的 $p$ 不要取成表长本身，若表长是合数（如 12），取模后就只剩少数几个地址被用到。
"散列表查找时间与表长无关"这句要加限定：是在 α 固定、且散列函数均匀的前提下成立。若把 $n$ 固定、无限增大 $m$ ，则 α → 0，ASL → 1。
散列表不适合范围查询：age between 20 and 30 这种要全表扫，这是它相比 B+ 树的致命短板，也是数据库索引仍以 B+ 树为主的原因。

4. 与前面章节的对照（高频选择）

查找方法	依赖	平均时间复杂度	能否范围查找
顺序查找	比较	O(n)	可以（低效）
折半查找	比较 + 有序 + 顺序存储	O(log n)	可以
B 树 / B+ 树	比较 + 有序 + 多路	O(log n)	可以
散列表	函数映射	O(1)	不可以

小结

散列表用散列函数把关键字直接算成地址，换来了平均 O(1) 的查找，代价是必须处理冲突。
散列函数首选除留余数法， $p$ 取不大于表长的最大质数；要分布均匀，不要有规律。
冲突处理两条主流路线：开放定址（表内找下一个空位，删除要用墓碑）与链地址法（同义词挂链，删除方便、α 可 > 1）。
一切性能都压在装填因子 α 上，α 越小越快；α 太大时要扩容重散列。
至此查找一篇收尾：顺序、折半、分块、B 树、散列表——考点几乎全部落在 ASL 手算与方法选型上。
下一步进入 408 的另一个必考大题区：排序。先从最朴素的插入类开始。

下一篇：插入类排序：直接插入、折半插入、希尔

散列表

概念

原理

一、散列函数的构造

二、处理冲突的两大类方法

1. 开放定址法（open addressing）

2. 链地址法（separate chaining，又叫拉链法）

三、装填因子与 ASL

示例

例 1：同一组关键字，两种冲突处理的 ASL 对比

例 2：平方探测的探测序列

C 语言：开放定址（线性探测）与链地址法

Python 对照

考点

小结

我的笔记

评论（0）

散列表 ​

概念 ​

原理 ​

一、散列函数的构造 ​

二、处理冲突的两大类方法 ​

1. 开放定址法（open addressing） ​

2. 链地址法（separate chaining，又叫拉链法） ​

三、装填因子与 ASL ​

示例 ​

例 1：同一组关键字，两种冲突处理的 ASL 对比 ​

例 2：平方探测的探测序列 ​

C 语言：开放定址（线性探测）与链地址法 ​

Python 对照 ​

考点 ​

小结 ​

我的笔记

评论（0）

散列表

概念

原理

一、散列函数的构造

二、处理冲突的两大类方法

1. 开放定址法（open addressing）

2. 链地址法（separate chaining，又叫拉链法）

三、装填因子与 ASL

示例

例 1：同一组关键字，两种冲突处理的 ASL 对比

例 2：平方探测的探测序列

C 语言：开放定址（线性探测）与链地址法

Python 对照

考点

小结