导航图15
## 导航图15
### 散列表中删除部分元素后的查找效率分析（2023）
## 注意
采用开放定址法时，不能直接物理删除表中已有元素。否则，可能截断其他同义词的查找路径，导致查找失败。正确的做法是：对被删元素所在位置设置一个删除标记，实现逻辑删除。但该方法的副作用是：经过多次删除后，散列表看似已满，但实际上有许多位置未被利用。
#### 2. 拉链法（链接法，chaining）
为了处理冲突，可将散列到同一地址的所有同义词组织成一个链表。每个链表由其对应的散列地址唯一确定。具体而言，若散列地址为 $i$，则该同义词链表的头指针存放在散列表的第 $i$ 个单元中。因此，查找、插入和删除操作主要在相应的同义词链表中进行。拉链法特别适用于需要频繁执行插入和删除操作的场景。例如，关键字序列 $\{19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79\}$，散列函数 $H(\text{key}) = \text{key}\%13$，采用拉链法处理冲突，建立的表如图 7.33 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 7.33 拉链法处理冲突的散列表
<!-- page: 332 -->
2027年数据结构考研复习指导
## 7.5.4 散列查找及性能分析的应用
**考点击左** 数列表的构造及查找效率的分析（2010、2018、2019、2024）
散列表的查找过程与构造过程基本一致。对于给定的关键字 key，先通过散列函数计算其初始地址，然后按如下步骤执行：
初始化：Addr=H(key)；
① 检查散列表中地址 Addr 处是否有记录：若无记录，则查找失败；若有记录，则比较该记录与 key 的值，若相等，则查找成功，否则转到步骤②。
② 按指定的冲突处理方法计算下一个探测地址，将 Addr 更新为此地址，返回步骤①。
例如，关键字序列{19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数 $H(\text{key}) = \text{key} \% 13$，采用线性探测法处理冲突，所得的散列表 L 如图 7.34 所示（表长为 16）。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | 14 | 01 | 68 | 27 | 55 | 19 | 20 | 84 | 79 | 23 | 11 | 10 | | | |
图 7.34 用线性探测法得到的散列表 L
查找关键字 84 的过程：初始散列地址 $H(84) = 6$。因 L[6] 非空且 $\mathrm{L}[6] \neq 84$，冲突：第一次探测的地址 $H_{1} = (6 + 1)\% 16 = 7$，因 L[7] 非空且 $\mathrm{L}[7] \neq 84$，冲突：第二次探测的地址 $H_{2} = (6 + 2)\% 16 = 8$，L[8] 非空且 $\mathrm{L}[8] = 84$，查找成功，返回其存储地址。
查找关键字 38 的过程：初始散列地址 $H(38) = 12$。因 L[12] 非空且 $\mathrm{L}[12] \neq 38$，冲突：第一次探测的地址 $H_{1} = (12 + 1)\% 16 = 13$，因 L[13] 为空，查找失败。
各关键字的查找比较次数如图 7.35 所示。
| 关键字 | 14 | 01 | 68 | 27 | 55 | 19 | 20 | 84 | 79 | 23 | 11 | 10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 比较次数 | 1 | 2 | 1 | 4 | 3 | 1 | 1 | 3 | 9 | 1 | 1 | 3 |
图 7.35 查找各关键字的比较次数
平均查找长度（ASL）为
$$
\mathrm {A S L} = (1 \times 6 + 2 + 3 \times 3 + 4 + 9) / 12 = 2. 5
$$
对于同一关键字集合和相同的散列函数，不同的冲突处理方法会生成不同的散列表结构，从而导致不同的平均查找长度。本例的 ASL 与上节拉链法的结果不同，正好体现了这一特性。
从散列表的查找过程可见：
1）尽管散列表在关键字与其存储位置之间建立了直接映射，但由于冲突的存在，查找过程仍需将给定值与表中关键字进行比较。因此，ASL 仍是衡量散列表查找效率的核心指标。
**考点击左** 影响散列表查找效率的因素（2011、2022）
2）散列表的查找效率主要取决于三个因素：散列函数、冲突处理方法和装填因子。
装填因子通常记为 $\alpha$，定义为散列表的填充程度，即
$$
\alpha = \frac {\text {表中记录数} n}{\text {散列表长度} m}
$$
散列表的平均查找长度主要依赖于装填因子 $\alpha$，而不直接依赖于 $n$ 或 $m$。直观地看，$\alpha$ 越大，表示表越“满”，发生冲突的可能性越高；反之，$\alpha$ 越小，冲突越少。
读者应能根据给定的散列表长度、元素个数、散列函数及冲突处理方法，构造出相应的散列表，并进一步计算查找成功时的平均查找长度与查找失败时的平均查找长度。
<!-- page: 333 -->
第7章 查找
321
## 7.5.5 本节试题精选
### 一、单项选择题
01. 只能在顺序存储结构上进行的查找方法是（ ）。
A. 顺序查找法
B. 折半查找法
C. 树形查找法
D. 散列查找法
02. 散列查找一般适用于（ ）的情况下的查找。
A. 查找表为链表
B. 查找表为有序表
C. 关键字集合比地址集合大得多
D. 关键字集合与地址集合之间存在对应关系
03. 下列关于散列表的说法中，正确的是（ ）。
I. 若散列表的填装因子 $\alpha < 1$，则可避免碰撞的产生
II. 散列查找中不需要任何关键字的比较
III. 散列表在查找成功时平均查找长度仅与表长有关
IV. 若在散列表中删除一个元素，不能简单地将该元素删除
A. I 和 IV
B. II 和 III
C. III
D. IV
04. 在开放定址法中散列到同一个地址而引起的“堆积”问题是由（ ）引起的。
A. 同义词之间发生冲突
B. 非同义词之间发生冲突
C. 同义词之间或非同义词之间发生冲突
D. 散列表“溢出”
05. 下列关于散列冲突处理方法的说法中，正确的有（ ）。
I. 采用平方探测法处理冲突时不易产生聚集
II. 采用线性探测法处理冲突时，所有同义词在散列表中一定相邻
III. 采用链地址法处理冲突时，若限定在链首插入，则插入任意一个元素的时间相同
IV. 采用链地址法处理冲突易引起聚集现象
A. I 和 III
B. I、II 和 III
C. III 和 IV
D. I 和 IV
06. 设有一个含有200个元素的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过1.5，则散列表应至少能够容纳（ ）个元素（设查找成功的平均查找长度为 $\mathrm{ASL} = [1 + 1 / (1 - \alpha)] / 2$，其中 $\alpha$ 为装填因子）。
A. 400
B. 526
C. 624
D. 676
07. 假定有 $K$ 个关键字互为同义词，若用线性探测法把这 $K$ 个关键字填入散列表，至少要进行（ ）次探测。
A. $K - 1$
B. $K$
C. $K + 1$
D. $K(K + 1) / 2$
08. 对包含 $n$ 个元素的散列表进行查找，平均查找长度（ ）。
A. 为 $O(\log_2 n)$
B. 为 $O(1)$
C. 不直接依赖于 $n$
D. 直接依赖于表长 $m$
09. 采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（ ）。
A. 数据元素过多
B. 负载因子过大
C. 散列函数选择不当
D. 解决冲突的方法选择不当
10. 当用线性探测再散列法解决冲突时，计算出的一系列“下一个空位”的要求是（ ）。
A. 必须大于或等于原散列地址
B. 必须小于或等于原散列地址
C. 可以大于或小于但不等于原散列地址
D. 对地址在何处没有限制
<!-- page: 334 -->
2027年数据结构考研复习指导
11. 一组记录的关键字为{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，用链地址法构造散列表，散列函数为 $H(\text{key}) = \text{key mod } 13$，散列地址为 1 的链中有（ ）个记录。
A. 1
B. 2
C. 3
D. 4
12. 在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下，所探测的这些位置上的关键字值（ ）；若采用线性探测法，则（ ）。
A. 一定都是同义词
B. 不一定都是同义词
C. 都相同
D. 一定都不是同义词
13. 若采用链地址法构造散列表，散列函数为 $H(\text{key}) = \text{key mod } 17$，则需（①）个链表。这些链的链首指针构成一个指针数组，数组的下标范围为（②）。
① A. 17
B. 13
C. 16
D. 任意
② A. $0 \sim 17$
B. $1 \sim 17$
C. $0 \sim 16$
D. $1 \sim 16$
14. 设散列表长 $m = 14$，散列函数为 $H(\text{key}) = \text{key}\%11$，表中仅有 4 个结点 $H(15) = 4$，$H(38) = 5$，$H(61) = 6$，$H(84) = 7$，若采用线性探测法处理冲突，则关键字为 49 的结点地址是（ ）。
A. 8
B. 3
C. 5
D. 9
15. 现有长度为 17、初始为空的散列表 HT，散列函数 $H(\text{key}) = \text{key}\%17$，用线性探查法解决冲突。将关键字序列 26, 25, 72, 38, 8, 18, 59 依次插入 HT 后，查找 59 需探查（ ）次。
A. 2
B. 3
C. 4
D. 5
16. 现有长度为 17、初始为空的散列表 HT，散列函数 $H(\text{key}) = \text{key}\%17$，用平方探测法解决冲突：$H_{1}(\text{key}) = (H(\text{key}) \pm i^{2})\%17$。将关键字序列 6, 22, 7, 26, 9, 23 依次插入 HT 后，则关键字 23 存放在散列表中的位置是（ ）。
A. 0
B. 2
C. 6
D. 15
17. 将 10 个元素散列到 100000 个单元的散列表中，则（ ）产生冲突。
A. 一定会
B. 一定不会
C. 仍可能会
D. 不确定
18. 【2011 统考真题】为提高散列表的查找效率，可以采取的正确措施是（ ）。
I. 增大装填（载）因子
II. 设计冲突（碰撞）少的散列函数
III. 处理冲突（碰撞）时避免产生聚集（堆积）现象
A. 仅 I
B. 仅 II
C. 仅 I、II
D. 仅 II、III
19. 【2014 统考真题】用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（ ）。
A. 存储效率
B. 散列函数
C. 装填（装载）因子
D. 平均查找长度
20. 【2018 统考真题】现有长度为 7、初始为空的散列表 HT，散列函数 $H(k) = k\%7$，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插入 HT 后，查找成功的平均查找长度是（ ）。
A. 1.5
B. 1.6
C. 2
D. 3
21. 【2019 统考真题】现有长度为 11 且初始为空的散列表 HT，散列函数是 $H(\text{key}) = \text{key}\%7$，采用线性探查（线性探测再散列）法解决冲突。将关键字序列 87, 40, 30, 6, 11, 22, 98, 20 依次插入 HT 后，HT 查找失败的平均查找长度是（ ）。
A. 4
B. 5.25
C. 6
D. 6.29
22. 【2022 统考真题】下列因素中，影响散列（哈希）方法平均查找长度的是（ ）。
<!-- page: 335 -->
第7章 查找
323
I. 紧填因子
II. 散列函数
III. 冲突解决策略
A. 仅 I、II
B. 仅 I、III
C. 仅 II、III
D. I、II、III
23. 【2023 统考真题】现有长度为 5、初始为空的散列表 HT，散列函数 $H(k) = (k + 4)\%5$，用线性探查再散列法解决冲突。若将关键字序列 2022,12,25 依次插入 HT，然后删除关键字 25，则 HT 中查找失败的平均查找长度为（ ）。
A. 1
B. 1.6
C. 1.8
D. 2.2
24. 【2025 统考真题】下列关于散列方法处理冲突的叙述中，正确的是（ ）。
A. 只要散列表不满，线性探查再散列一定能找到一个空闲位置
B. 只要散列表不满，二次探查再散列一定能找到一个空闲位置
C. 线性探查再散列处理的冲突，一定是发生在同义词之间的冲突
D. 二次探查再散列处理的冲突，一定是发生在非同义词之间的冲突
## 二、综合应用题
01. 若要在散列表中删除一个记录，应如何操作？为什么？按照处理冲突的方法为开放地址法和拉链法分别说明。
02. 假定把关键字 key 散列到有 $n$ 个表项（从 0 到 $n - 1$ 编址）的散列表中。对于下面的每个函数 $H(\text{key})$（key 为整数），这些函数能够当作散列函数吗？若能，它是一个好的散列函数吗？说明理由。设函数 $\text{random}(n)$ 返回一个 0 到 $n - 1$ 之间的随机整数（包括 0 与 $n - 1$ 在内）。
1）$H(\text{key}) = \text{key}/n$。
2）$H(\text{key}) = 1$。
3）$H(\text{key}) = (\text{key} + \text{random}(n))\%n$。
4）$H(\text{key}) = \text{key}\%p(n)$；其中 $p(n)$ 是不大于 $n$ 的最大素数。
03. 使用散列函数 $H(\text{key}) = \text{key}\%11$，把一个整数值转换成散列表下标，散列表的长度为 11，现在要把数据 $\{1, 13, 12, 34, 38, 33, 27, 22\}$ 依次插入散列表。
1）使用线性探测法来构造散列表。
2）使用链地址法构造散列表。
试针对这两种情况，分别确定查找成功所需的平均查找长度，及查找不成功所需的平均查找长度。
04. 已知一组关键字为 $\{26, 36, 41, 38, 44, 15, 68, 12, 6, 51, 25\}$，用链地址法解决冲突，假设紧填因子 $\alpha = 0.73$，散列函数的形式为 $H(\text{key}) = \text{key}\%P$，$P$ 为不大于表长的最大素数，请回答以下问题：
1）构造出散列函数。
2）分别计算出等概率情况下查找成功和查找失败的平均查找长度（查找失败的计算中只将与关键字的比较次数计算在内即可）。
05. 设散列表为 $\mathrm{HT}[0\dots 12]$，即表的大小为 $m = 13$。现采用双散列法解决冲突，散列函数和再散列函数分别为：
$H_0(\text{key}) = \text{key}\%13$ 注：$\%$ 是取模运算（$= \bmod$）
$H_i = (H_{i-1} + \mathrm{REV}(\text{key} + 1)\%11 + 1)\%13; \quad i = 1, 2, 3, \dots, m-1$
其中，函数 $\mathrm{REV}(x)$ 表示颠倒十进制数 $x$ 的各位，如 $\mathrm{REV}(37) = 73$、$\mathrm{REV}(7) = 7$ 等。若插入的关键码序列为 $(2, 8, 31, 20, 19, 18, 53, 27)$，请回答：
1）画出插入这 8 个关键码后的散列表。
<!-- page: 336 -->
2027年数据结构考研复习指导
2）计算查找成功的平均查找长度 ASL。
06. 【2010 统考真题】将关键字序列(7, 8, 30, 11, 18, 9, 14)敷列存储到敷列表中。敷列表的存储空间是一个下标从 0 开始的一维数组，敷列函数为 $H(\text{key}) = (\text{key} \times 3) \mod 7$，处理冲突采用线性探测再敷列法，要求装填（载）因子为 0.7。
1）请画出所构造的敷列表。
2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。
07. 【2024 统考真题】将关键字序列 20, 3, 11, 18, 9, 14, 7 依次存储到初始为空，长度为 11 的敷列表 HT 中，敷列函数 $H(\text{key}) = (\text{key} \times 3)\%11$。$H(\text{key})$ 计算出的初始敷列地址为 $H_0$，发生冲突时探查地址序列是 $H_1, H_2, H_3, \dots$，其中 $H_k = (H_0 + k^2)\%11$，$k = 1, 2, 3, \dots$。
请回答下列问题：
1）画出所构造的 HT，并计算 HT 的装填因子。
2）给出在 HT 中查找关键字 14 的关键字比较序列。
3）在 HT 中查找关键字 8，确认查找失败时的敷列地址是多少？
## 7.5.6 答案与解析
### 一、单项选择题
#### 01. B
顺序查找可以是顺序存储或链式存储；折半查找只能是顺序存储且要求关键字有序；树形查找法要求采用树的存储结构，既可以采用顺序存储也可以采用链式存储；散列查找中的链地址法解决冲突时，采用的是顺序存储与链式存储相结合的方式。
#### 02. D
关键字集合与地址集合之间存在对应关系时，通过散列函数表示这种关系。这样，查找以计算散列函数而非比较的方式进行查找。
#### 03. D
冲突（碰撞）是不可避免的，与装填因子无关，因此需要设计处理冲突的方法，说法 I 错误。散列查找的思想是计算出散列地址来进行查找，然后比较关键字以确定是否查找成功，说法 II 错误。散列查找成功的平均查找长度与装填因子有关，与表长无直接关系，说法 III 错误。在开放定址的情形下，不能随便删除散列表中的某个元素，否则可能会导致搜索路径被中断（因此通常的做法是在要删除的地方做删除标记，而不是直接删除），说法 IV 正确。
#### 04. C
在开放定址法中散列到同一个地址而产生的“堆积”问题，是同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起，导致关键字查询需要经过较长的探测距离，降低了散列的效率。因此要选择好的处理冲突的方法来避免“堆积”。
#### 05. A
平方探测法采用的增量序列是非线性的，它可以跳过一些已被占用的单元，而不是顺序地探测下一单元，这样能减小冲突的概率，说法 I 正确。散列地址 $i$ 的关键字，和为解决冲突形成的某次探测地址为 $i$ 的关键字，都争夺地址 $i, i + 1, \dots$，因此不一定相邻，说法 II 错误。说法 III 正确。同义词冲突不等于聚集，链地址法处理冲突时将同义词放在同一个链表中，不会引起聚集现象，说法 IV 错误。
#### 06. A
若有 200 个元素要放入散列表，采用线性探测法解决冲突，限定查找成功的平均查找长度不
<!-- page: 337 -->
第7章 查找
325
超过 1.5，则
$$
\mathrm{ASL}_{\text{成功}} = \frac{1}{2} \left(1 + \frac{1}{1 - \alpha}\right) \leqslant 1.5 \Rightarrow \alpha = \frac{200}{m} \leqslant \frac{1}{2} \Rightarrow m \geqslant 400
$$
07. D
$K$ 个关键字在依次填入的过程中，只有第一个不会发生冲突，所以探测次数为 $1 + 2 + 3 + \dots + K = K(K + 1)/2$。
08. C
散列表的平均查找长度与装填因子 $\alpha$ 直接相关，表的查找效率不直接依赖于表中已有表项个数 $n$ 或表长 $m$。若表中存放的记录全是某个地址的同义词，则平均查找长度为 $O(n)$ 而非 $O(1)$。
09. D
聚集是因选取不当的处理冲突的方法，而导致不同关键字的元素对同一散列地址进行争夺的现象。用线性探查法时，容易引发聚集现象。
10. C
“下一个空位”可以大于或小于但不等于原散列地址，等于原散列地址是没有意义的。
11. D
由散列函数计算可知，14, 1, 27, 79 散列后的地址都是 1，所以有 4 个记录。
12. A, B
因为在链地址法中，映射到同一地址的关键字都会链到与此地址相对应的链表上，所以探测过程一定是在此链表上进行的，从而这些位置上的关键字均为同义词；但在线性探测法中出现两个同义关键字时，会把该关键字对应地址的下一个地址也占用掉，两个地址分别记为 Addr、Addr + 1，查找一个满足 $H(\text{key}) = \text{Addr} + 1$ 的关键字 key 时，显然首次探测到的不是 key 的同义词。
13. A, C
H 的取值有 17 种可能，对应到不同的链表中，所以链表的个数应为 17。因为 $H(\text{key})$ 的取值范围为 $0 \sim 16$，所以数组下标为 $0 \sim 16$。
14. A
线性探测法的公式为 $H_{1} = (H(\text{key}) + d_{1})\% m$，其中 $d_{1} = 1,2,\dots,m - 1$。$H(49) = 49\%11 = 5$，有冲突；$H_{1} = (H(49) + 1)\%14 = 6$，有冲突；$H_{2} = (H(49) + 2)\%14 = 7$，有冲突；$H_{3} = (H(49) + 3)\%14 = 8$，无冲突。
15. C
插入过程如下：$H(26) = 9$，不冲突；$H(25) = 8$，不冲突；$H(72) = 4$，不冲突；$H(38) = 4$，冲突，冲突处理后的地址为 5；$H(8) = 8$，冲突，冲突处理后的地址为 10；$H(18) = 1$，不冲突；$H(59) = 8$，冲突，冲突处理后的地址为 11。因此，在表中查找 59 需要探查 4 次。
16. B
插入过程如下：$6\%17 = 6$；$22\%17 = 5$；$7\%17 = 7$；$26\%17 = 9$；$9\%17 = 9$，冲突，平方探测法探测 10（无冲突）；$23\%17 = 6$，冲突，平方探测法探测 7（冲突），探测 5（冲突），探测 10（冲突），探测 2（无冲突）。因此，关键字 23 应放在位置 2。构造的散列表如下表所示。
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 元素 | | | 23 | | | 22 | 6 | 7 | | 26 | 9 | | | | | | |
17. C
由于散列函数的选取，仍然有可能产生地址冲突，冲突不能绝对地避免。
18. D
散列表的查找效率取决于散列函数、处理冲突的方法和装填因子。显然，冲突的产生概率与
<!-- page: 338 -->
2027年数据结构考研复习指导
装填因子（表中记录数与表长之比）的大小成正比，说法I与题意相反。说法II显然正确。采用合适的冲突处理方法可避免聚集现象，也将提高查找效率，说法III正确。例如，用链地址法处理冲突时不存在聚集现象，用线性探测法处理冲突时易引起聚集现象。