哈希表：开放定址法

2026 大纲 六（七）散列（hash）表 · 开放定址法（基本概念与散列函数构造见拉链法）。

冲突了不挂链表，就在表里找个空位

拉链法处理冲突的办法是给每个地址挂一条链表。开放定址法换了个思路：不借助任何表外空间，就在数组里往后找一个空位放进去。

"开放"两个字的意思是：找空位时，整个数组对所有元素都是开放的——本来属于别人的地址，只要它空着，你也可以占。

通用公式是

$$H_i=(H(key)+d_i)modm$$

$d_i$ 叫增量序列，怎么取决定了这是哪一种探测法。

这个思路带来一条硬性规定：

🔴 必须 $\alpha <1$。 记录全都挤在表内，$n\le m$ 是物理限制。这是它与拉链法最硬的一条差别——拉链法的链表想挂多长挂多长，$\alpha$ 可以大于 1。

先动手看一眼

加载可视化中...

线性探测与它的堆积

$d_i=1,2,3,\cdots$，也就是一格一格往后挪。

#define EMPTY   -1   // 空位
#define DELETED -2   // 已删除（墓碑）

// 线性探测——查找。返回下标；-1 表示失败
int linearSearch(HashTable *ht, int key) {
    int pos = key % ht->size, i = 0;
    while (i < ht->size) {                 // 上限保证最坏探完整张表就退出，不死循环
        int cur = (pos + i) % ht->size;    // 取模实现"到表尾回到表头"
        if (ht->data[cur] == EMPTY)
            return -1;      // 🔴 真正的空位：插入时不可能越过它，后面不可能有 key
        if (ht->data[cur] == key)
            return cur;
        i++;                // DELETED 或别的关键字都要继续：探测链从那里穿过去了
    }
    return -1;
}

它有一个别人没有的好处：

🔴 只要散列表没满，线性探测一定能找到一个空位。 增量 $1,2,\cdots ,m-1$ 必然走遍全表，不可能漏掉哪个空槽。

但它也有一个别人没有的毛病——堆积（聚集）：

🔴 初始地址不同的记录，会争夺同一个后继地址。 当 $i,i+1,i+2$ 三个位置已被占用时，下一个散列地址是 $i$、$i+1$、$i+2$、$i+3$ 的记录都会被填进 $i+3$。已占用的连续区段像滚雪球一样越滚越长——区段越长，落进它的概率越大，落进来又让它更长。

这句话反过来就是一条被真题考过的判断："线性探查再散列处理的冲突一定发生在同义词之间"是错的。恰恰相反，线性探测的特点就是非同义词之间也会冲突——两个 $H(key)$ 完全不同的关键字，照样可能抢同一个位置。

堆积的量化演示（表长 $m=16$，$H(key)=keymod13$，依次插入 $19,14,23,1,68,20,84,27,55,11,10,79$）：

下标	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
元素	—	14	1	68	27	55	19	20	84	79	23	11	10	—	—	—
插入时的比较次数		1	2	1	4	3	1	1	3	9	1	1	3

最后插入的 79（$H(79)=1$）比较了 9 次——下标 1 到 8 已连成一整片，79 只能一路探测到 9 号空位。同一张表里，最早插入的元素 1 次命中，最晚插入的要 9 次。

⚠️ "一次聚集/二次聚集"这两个名字在不同教材里指的不是一回事：严蔚敏教材把线性探测的这个现象叫"二次聚集"（也称堆积），而另一种常见说法把它叫"一次聚集"、把平方探测里同义词共用探测序列的现象叫"二次聚集"。按现象判、别只背名字——问"哪种探测方法会引起非同义词之间的冲突"，答案确定无疑是线性探测。

平方探测：不堆积了，但可能找不到空位

$d_i=\pm 1^2,\pm 2^2,\cdots$，跳着走，非同义词的探测路线迅速分开，不再互相争抢。

代价是它不保证能找到空位——这与线性探测正好构成一组取舍：

🔴 线性探测保证找得到空位但堆积严重；平方探测不堆积却不保证找得到。

而且它对表长有硬要求：

🔴 表长必须是形如 $4j+3$ 的质数，探测序列 $\{0,\pm 1^2,\cdots ,\pm (\frac{m-1}{2}{)}^2\}$ 才覆盖全部 $m$ 个地址。

⚠️ 13 是质数但不是 $4j+3$ 型（$13mod4=1$），表长 13 时平方探测只能到达 7 个位置，表里还有空位也可能找不到。"取质数"这个条件不够。

⚠️ 还有一处更实际的提醒：真题会自己规定探测序列，以题面写的为准。 有的题写的是 $H_k=(H_0+k^2)modm$——只有正方向，没有 $-k^2$。这时就老老实实按 $+1,+4,+9,+16,\cdots$ 走，不要套教材的双向序列。

双散列：$m$ 取质数这个前提不能省

$d_i=i\times H_2(key)$，步长随关键字而变，连同义词的聚集也一并打散。

常用取法是把表长 $m$ 取成质数，再令 $H_2(key)=p-(keymodp)$（$p$ 是小于 $m$ 的最大质数）——此时 $H_2$ 落在 $1\sim p\subset [1,m-1]$，$m$ 是质数则比它小的正整数与它必然互素 ✓。

⚠️ $m$ 是合数时 $H_2$ 可能与 $m$ 不互素，探测序列会陷入循环。反例：$m=100$、$p=97$，关键字 47 算出 $H_2=97-47=50$，$gcd(50,100)=50\ne 1$，增量 $i\times 50mod100$ 只有 $50$ 与 $0$ 两个取值，探测序列在两个位置间来回打转，全表 100 个槽位只够到 2 个。

删除：只能打墓碑

查找判定失败的依据是"探测到一个空位"。若把某个位置直接置为 EMPTY，而它原本处在某条探测链的中间，这条链就被截断了——链上排在它后面的元素永远也找不到。

以表 55 1 23 14 - - - - 19 - -（$m=11$、$H(key)=keymod11$）为例，23 是因为和 1 冲突才被放到下标 2 的（探测链 1 → 2）。物理删除 1 后再查 23：$H(23)=1$ → 下标 1 是空位 → 判定失败。可是 23 明明就在下标 2。

🔴 解决方案是墓碑标记（懒删除）：把被删位置标记为 DELETED。查找时继续往下探测，插入时可以复用该位置。

int lazyDelete(HashTable *ht, int key) {
    int pos = linearSearch(ht, key);
    if (pos == -1) return 0;
    ht->data[pos] = DELETED;   // 打墓碑，绝不能写成 EMPTY
    ht->count--;
    return 1;
}

这条规则在算 ASL 时会直接影响答案：墓碑位不是真空，遇到它要继续探测，而且这一次探测照样算一次比较。下面的算例四就是这种题。

副作用：墓碑只增不减，删除多了查找要穿过大量墓碑，性能退化，工程上定期重散列。拉链法没有这个问题——它的删除是直接摘除链表结点，这是"频繁删除时优先选拉链法"的根本理由。

算 ASL：分母是散列函数的值域

成功 ASL 的分母是元素个数 $n$，没有争议。失败 ASL 的分母才是失分重灾区：

🔴 失败 ASL 的分母 = 散列函数的值域大小（除留余数法就是模数 $p$），不是表长 $m$，也不是 $n$。

道理在《查找基本概念》里讲过：失败查找从 $H(key)$ 这个地址出发，能当起点的地址只有 $H$ 的值域那么多。$H(key)=keymod7$ 而表长 11 时，下标 7~10 永远不会是任何一次查找的起点。

⚠️ 但"不能作为起点"和"不能被探测到"是两回事——探测过程完全可以走到下标 7~10 去，它们只是不能作为起点参与平均。

还有一条规定要先说清：

🔴 遇到空位的那一次也要算 1 次比较。 开放定址法访问空位是一次真实的表访问（就是靠它判定失败的），必须计入。这一点没有分歧。

算例一（$m=p=11$）：表为 55 1 23 14 - - - - 19 - -。

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1+1+2+1+1}{5}=\frac{6}{5}=1.2$$

逐地址推导失败：$H=0$ 探测 55(0)→1(1)→23(2)→14(3)→空(4)，共 5 次；$H=1$ 为 4 次；$H=2$ 为 3 次；$H=3$ 为 2 次；$H=4$ 为 1 次；$H=5,6,7$ 当场是空位各 1 次；$H=8$ 探 19(8)→空(9) 为 2 次；$H=9,10$ 各 1 次。

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{5+4+3+2+1+1+1+1+2+1+1}{11}=\frac{22}{11}=2.0$$

算例二（$m\ne p$，最容易算错的一类）：表长 $m=13$，$H(key)=keymod\mathbf{11}$，线性探测，依次插入 22, 12, 25, 14, 36：

下标:  0   1   2   3   4   5   6   7   8   9   10  11  12
元素:  22  12  -   25  14  36  -   -   -   -   -   -   -

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1+1+1+2+3}{5}=\frac{8}{5}=1.6$$

合法的初始散列地址只有 $0\sim 10$ 共 11 个：

出发地址	0	1	2	3	4	5	6	7	8	9	10
比较次数	3	2	1	4	3	2	1	1	1	1	1

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{3+2+1+4+3+2+1+1+1+1+1}{\mathbf{11}}=\frac{20}{11}\approx 1.82$$

若误用表长 13 做分母得 $\frac{20}{13}\approx 1.54$，就错了。

更多 ASL 算例：删除后的失败 ASL、以及堆积表的失败 ASL（做这两类题时展开）

算例三（删除后算失败 ASL）：$m=5$、$H(k)=(k+4)mod5$，线性探测，依次插入 2022、12、25，然后删除 25。

插入：$H(2022)=(2022+4)mod5=1$ → 下标 1；$H(12)=(12+4)mod5=1$ → 冲突，探到下标 2；$H(25)=(25+4)mod5=4$ → 下标 4。

删除 25 后，下标 4 打墓碑，不是真空：

地址	0	1	2	3	4
内容	空	2022	12	空	25 (deleted)

枚举 5 个起点（$H$ 的值域是 $0\sim 4$，与表长恰好相同）：

起点	探测路径（遇真空才终止）	比较次数
0	0(空)	1
1	1(2022) → 2(12) → 3(空)	3
2	2(12) → 3(空)	2
3	3(空)	1
4	4(墓碑) → 0(空)	2

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{1+3+2+1+2}{5}=\frac{9}{5}=1.8$$

⚠️ 起点 4 那一行是全题的考点：墓碑位要算 1 次比较，而且不能在这里终止。若把它当成空位，答案会变成 1，与正确答案差得很远。

算例四（堆积表的失败 ASL）：还是 $m=16$、$H(key)=keymod13$ 那张表，合法起点是 $0\sim 12$ 共 13 个。

出发地址	0	1	2	3	4	5	6	7	8	9	10	11	12
比较次数	1	13	12	11	10	9	8	7	6	5	4	3	2

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{1+13+12+11+10+9+8+7+6+5+4+3+2}{13}=\frac{91}{13}=7$$

而这张表的成功 ASL 只有 2.5：

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1\times 6+2+3\times 3+4+9}{12}=\frac{30}{12}=2.5$$

失败 7 而成功 2.5，这个悬殊差距正是堆积的写照：下标 1~12 连成一整片，从中间任何位置出发都要一路走到 13 号空位。（$H=0$ 只要 1 次，是因为下标 0 恰好是空的。）

线性探测的小规模建表与插入代码的一处坑（想手动模拟建表时展开）

$m=11$、$H(key)=keymod11$，依次插入 19, 1, 23, 14, 55：

关键字	$H(key)$	探测序列	最终位置	比较次数
19	8	8	8	1
1	1	1	1	1
23	1	1 → 2	2	2
14	3	3	3	1
55	0	0	0	1

下标:  0   1   2   3   4   5   6   7   8   9   10
元素:  55  1   23  14  -   -   -   -   19  -   -

插入代码：

int linearInsert(HashTable *ht, int key) {
    int pos = key % ht->size, i = 0;
    while (i < ht->size) {
        int cur = (pos + i) % ht->size;
        if (ht->data[cur] == EMPTY || ht->data[cur] == DELETED) {
            ht->data[cur] = key;           // 空位或墓碑位都可以复用
            ht->count++;
            return cur;
        }
        i++;
    }
    return -1;                             // 表满，插入失败
}

⚠️ 它在遇到第一个 DELETED 位时就写入，没有先确认 $key$ 是否已在探测链更靠后的位置上。若要求"不允许重复关键字"，正确做法是：先记住第一个 DELETED 的位置，继续探测到 EMPTY 或找到 $key$；找到 $key$ 就放弃插入，否则回填到记下的那个墓碑位。教材版本按"建表时不会插入重复关键字"的前提写，408 手工建表时也不涉及这一情形。

平方探测的道理、代码与可达槽位的枚举验证（想核实那张表长清单就展开）

为什么偏偏是 $4j+3$（理解性说明，不要求证明）：模 $m$ 的非零平方剩余恰有 $\frac{m-1}{2}$ 个。$m\equiv 3(\mathrm{mod}4)$ 时 $-1$ 不是平方剩余，$\{i^2\}$ 与 $\{-i^2\}$ 除 0 外完全不重合，合起来正好 $m$ 个余数，覆盖全表；$m\equiv 1(\mathrm{mod}4)$ 时 $-1$ 是平方剩余，两个方向探到的是同一批地址，只能到达 $\frac{m+1}{2}$ 个位置。

// 平方（二次）探测——查找
int quadraticSearch(HashTable *ht, int key) {
    int pos = key % ht->size;
    int i = 0;
    while (i <= ht->size / 2) {            // i 最多到 ⌊m/2⌋，正好覆盖全部探测项
        int cur = (pos + i * i) % ht->size;                    // 正方向 +i²
        if (ht->data[cur] == EMPTY) return -1;
        if (ht->data[cur] == key)  return cur;

        cur = ((pos - i * i) % ht->size + ht->size) % ht->size; // 负方向 -i²
        if (ht->data[cur] == EMPTY) return -1;                  // 先 +ht->size 再取模，防负下标
        if (ht->data[cur] == key)  return cur;
        i++;
    }
    return -1;
}

((pos - i*i) % m + m) % m 这个写法是必须的：C 语言里负数取模的结果可能是负的（如 -3 % 11 得 -3），直接拿去做下标会越界。查找时的探测顺序必须与插入时完全一致，否则"遇到 EMPTY 就判失败"这条推断不成立。

数值验证（已逐个枚举 $\{\pm i^{2}modm\}$ 的取值个数）：

表长 $m$	是质数？	$mmod4$	可达槽位数	是否覆盖全表
7	是	3	7 / 7	✅
11	是	3	11 / 11	✅
19	是	3	19 / 19	✅
23	是	3	23 / 23	✅
5	是	1	3 / 5	❌
13	是	1	7 / 13	❌
17	是	1	9 / 17	❌

伪随机探测法：$d_i$ 取一个伪随机数序列。例如伪随机数为 9 时，$H_0=5$ 冲突后的下一个地址是 $(5+9)mod11=3$。它与平方探测一样能避免非同义词聚集，也一样不保证探遍全表。

装填因子、四种方法的理论 ASL 公式与复杂度（选型、或题目只给装填因子时展开）

$\alpha =\frac{n}{m}$ 越大，冲突越多、探测链越长、ASL 越大，建议 $\alpha \le 0.75$。

等概率、散列函数均匀的假设下：

处理冲突的方法	查找成功 ASL	查找失败 ASL
线性探测法	${\displaystyle \frac{1}{2}}(1+{\displaystyle \frac{1}{1-\alpha }})$	${\displaystyle \frac{1}{2}}(1+{\displaystyle \frac{1}{(1-\alpha {)}^2}})$
平方探测法 / 伪随机探测法	$-{\displaystyle \frac{1}{\alpha }}\ln (1-\alpha )$	${\displaystyle \frac{1}{1-\alpha }}$
链地址法（拉链法）	$1+{\displaystyle \frac{\alpha }{2}}$	$\alpha +e^{-\alpha }$

两条能从公式直接读出的结论：

• 线性探测的失败 ASL 分母是 $(1-\alpha {)}^2$，恶化最快——$\alpha =0.9$ 时它是 $\frac{1}{2}(1+100)=50.5$，而平方探测只有 $\frac{1}{0.1}=10$。这就是堆积的量化代价。
• 链地址法的两个公式都不含 $\frac{1}{1-\alpha }$，所以 $\alpha \ge 1$ 时依然有意义，而开放定址法的公式在 $\alpha \to 1$ 时发散。"$O(1)$"是有前提的。

⚠️ 理论公式与直接计算通常对不上是正常的（公式假设关键字均匀随机分布）。题目给了具体的表就必须直接计算，不许套公式。

对比项	线性探测	平方探测	双散列	拉链法
非同义词聚集	严重	无	无	无
保证找到空位	是（表未满时）	否	否	不适用
删除操作	需墓碑标记	需墓碑标记	需墓碑标记	直接摘除结点
表长要求	无特殊要求	$4j+3$ 型质数	$H_2$ 需与 $m$ 互素	无特殊要求
装填因子	$<1$	$<1$	$<1$	可 $>1$

复杂度：查找、插入、删除的平均都是 $O\left(\frac{1}{1-\alpha }\right)$、最坏 $O(n)$；空间 $O(m)$，没有指针开销——这是开放定址法相对拉链法的唯一空间优势，但它要求 $\alpha <1$（必须预留空位），两相抵消后优势不大。

考点速记

三条结论：

1. 失败 ASL 的分母 = 散列函数的值域大小（除留余数法即模数 $p$），遇空位的那次也算 1 次比较。
2. 删除必须打墓碑；墓碑位在查找时要继续探测，且算一次比较。
3. 线性探测保证找得到空位但会堆积；平方探测不堆积却不保证找得到，且要求表长是 $4j+3$ 型质数。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 算查找成功的 ASL：给短表长、散列函数和几个关键字，依次插入后求成功 ASL。分母是元素个数。
• 算查找失败的 ASL：同样的设定但问失败。分母是散列函数的模数——表长 11 而 $H(key)=keymod7$ 时，分母是 7 不是 11。这一条考过不止一次。
• 删除之后再算失败 ASL：插入几个关键字后删掉一个，问失败 ASL。被删位置是墓碑不是空位，探测到它要继续走，且计一次比较。
• 散列法处理冲突的叙述判断：正确的是"只要散列表不满，线性探查再散列一定能找到一个空闲位置"；错的是"二次探查再散列一定能找到"（不保证）、"线性探查处理的冲突一定发生在同义词之间"（非同义词也会冲突）。
• 构造散列表并计算两个 ASL（大题）：给关键字序列、散列函数和装填因子，要求画出散列表并算成功/失败 ASL。⚠️ 装填因子是用来倒推表长的——$n=7$、$\alpha =0.7$ 就是 $m=10$。而散列函数若是 $mod7$，值域只有 $0\sim 6$，地址 7、8、9 只能靠探测填进去、且不能作为失败查找的起点。
• 二次探测建表 + 查找失败的地址（大题）：题面自定义 $H_k=(H_0+k^2)modm$（只有正方向），要求画表、算装填因子、写出查找某个关键字的比较序列，以及"确认查找失败时的散列地址是多少"——答的是探测到的那个空槽的地址，不是初始地址。

易错：失败 ASL 的分母是散列函数的值域，不是表长。 表长 $m$ 与模数 $p$ 不等时，这是最大的失分点。

易错：墓碑位不是空位。 删除后算 ASL 时，探测到墓碑要继续往下走，并且这一次计入比较次数。

易错："线性探查处理的冲突一定发生在同义词之间"是错的。 堆积的定义就是非同义词也来抢同一个后继地址。

易错：题面自定义的探测序列优先于教材。 看到 $H_k=(H_0+k^2)modm$ 就只往正方向探，别自作主张加上 $-k^2$。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）7.4.3 节「处理冲突的方法」，p223： 开放地址法的基本思想——"把记录都存储在散列表数组中， 当某一记录关键字 $key$ 的初始散列地址 $H_0=H(key)$ 发生冲突时，以 $H_0$ 为基础， 采取合适方法计算得到另一个地址 $H_1$……这种方法在寻找'下一个'空的散列地址时， 原来的数组空间对所有的元素都是开放的，所以称为开放地址法"； 通用公式 $H_i=(H(key)+d_i)modm$ 与线性探测、二次探测、伪随机探测三种 $d_i$。
• 同书 p224：堆积现象的描述——"当表中 $i$、$i+1$、$i+2$ 位置上已填有记录时， 下一个散列地址为 $i$、$i+1$、$i+2$ 和 $i+3$ 的记录都将填入 $i+3$ 的位置， 这种在处理冲突过程中发生的两个第一个散列地址不同的记录争夺同一个后继散列地址的现象 称作'二次聚集'（或称作'堆积'），即在处理同义词的冲突过程中又添加了非同义词的冲突"； 以及三种方法的优缺点——线性探测"只要散列表未填满，总能找到一个不发生冲突的地址"， 但会产生聚集；二次探测与伪随机探测可以避免聚集，但"不能保证一定找到不发生冲突的地址"。
• 同书 p226–p227：装填因子的定义；表 7.3 给出四种冲突处理方法在等概率下的理论平均查找长度； 以及"散列表的平均查找长度是 $\alpha$ 的函数，而不是记录个数 $n$ 的函数"。
• 同书 p227–p228：例 7.3 —— $m=16$、$H(key)=keymod13$、线性探测、关键字序列 $(19,14,23,1,68,20,84,27,55,11,10,79)$，正是本篇堆积演示与算例四的出处； 该例算得 $AS{L}_{succ}=2.5$、$AS{L}_{unsucc}=7$，并明确写出失败 ASL 的分母怎么算—— "假设散列函数的取值个数为 $r$，则 0 到 $r-1$ 相当于 $r$ 个查找失败的入口"， 本例中 $r=13$ 而表长为 16。

相关知识

拉链法（基本概念与散列函数构造在那一篇）｜ 查找基本概念（散列失败 ASL 分母为什么与众不同）｜ B 树、B+ 树（需要范围查询时的替代）｜ 折半查找（建立在全序之上）｜查找算法分析与对比

相关文章

• 查找基本概念
• 顺序查找
• 折半查找（二分查找）
• 分块查找
• 二叉排序树查找 → 见树章节
• 平衡二叉树查找 → 见树章节
• 红黑树查找 → 见树章节
• B 树
• B+ 树
• 哈希表：拉链法
• 查找算法对比

交互体验

前往完整可视化页面 →

真题练习

相关真题（7题）

2025Q92分2024Q4210分2023Q92分2019Q82分2018Q92分2011Q92分2010Q4110分