【经验分享】数据结构——哈希查找冲突处理方法（开放地址法-线性探测、平方探测、双散列探测、再散列，分离链接法）

命运之光

发布于 2024-08-17 08:32:46

690

发布于 2024-08-17 08:32:46

文章被收录于专栏：我在本科期间写的文章

1. 线性探测（Linear Probing）

题目：给定一个哈希表大小

m = 7

的哈希表，插入一组关键字 [10, 22, 31, 4, 15, 28]，并使用线性探测解决冲突。

步骤：

计算每个关键字的哈希值

h(k) = k \% m

如果该位置为空，则插入；如果发生冲突，线性探测下一个位置直到找到空位。

表格：

关键字 k k k	初始哈希值 h ( k ) = k % 7 h(k) = k \% 7 h(k)=k%7	插入位置
10	3	3
22	1	1
31	3	4（冲突，线性探测到4）
4	4	5（冲突，线性探测到5）
15	1	2（冲突，线性探测到2）
28	0	0

k

初始哈希值

h(k) = k \% 7

插入位置103322113134（冲突，线性探测到4）445（冲突，线性探测到5）1512（冲突，线性探测到2）2800

表格内容：

列1: 关键字
列2: 初始哈希值
列3: 实际插入位置

2. 平方探测（Quadratic Probing）

题目：假设哈希表大小 (m = 7)，插入关键字 [18, 41, 22, 44, 59]，使用平方探测解决冲突。

步骤：

计算初始哈希值。
如果发生冲突，使用平方探测

h_i = (h(k) + i^2) \% m

寻找插入位置。

表格：

关键字 k k k	初始哈希值 h ( k ) = k % 7 h(k) = k \% 7 h(k)=k%7	探测序列 h i = ( h ( k ) + i 2 ) % 7 h_i = (h(k) + i^2) \% 7 hi=(h(k)+i2)%7	插入位置
18	4	4, 5	4
41	6	6	6
22	1	1	1
44	2	2, 3	2
59	3	3, 4, 6, 0	0

k

初始哈希值

h(k) = k \% 7

探测序列

h_i = (h(k) + i^2) \% 7

插入位置1844, 5441666221114422, 325933, 4, 6, 00

表格内容：

列1: 关键字
列2: 初始哈希值
列3: 探测序列（尝试的插入位置）
列4: 实际插入位置

3. 双散列探测（Double Hashing）

题目：在一个哈希表中，使用哈希函数

(h_1(k) = k \% 7

和

h_2(k) = 1 + (k \% 5)

对关键字 [19, 27, 36, 10] 进行插入，解决冲突时使用双散列。

步骤：

计算初始哈希值

h_1(k)

。

如果发生冲突，计算第二个哈希值

h_2(k)

并进行双散列探测

h_i = (h_1(k) + i \times h_2(k)) \% m

表格：

关键字 k k k	初始哈希值 h 1 ( k ) = k % 7 h_1(k) = k \% 7 h1(k)=k%7	第二哈希值 h 2 ( k ) = 1 + ( k % 5 ) h_2(k) = 1 + (k \% 5) h2(k)=1+(k%5)	插入位置
19	5	5	5
27	6	3	6
36	1	2	1
10	3	1	3

k

初始哈希值

h_1(k) = k \% 7

第二哈希值

h_2(k) = 1 + (k \% 5)

插入位置19555276363612110313

表格内容：

列1: 关键字
列2: 初始哈希值
列3: 第二哈希值（用于探测）
列4: 实际插入位置

4. 分离链接法（Separate Chaining）

题目：哈希表大小为

m = 5

，插入关键字 [10, 21, 32, 43, 54]，使用分离链接法解决冲突。

步骤：

计算哈希值

h(k) = k \% 5

将冲突的元素插入对应链表中。

表格：

桶位置	关键字链表
0	[10]
1	[21]
2	[32]
3	[43]
4	[54]

表格内容：

列1: 桶位置
列2: 链表中存储的关键字

5. 再散列（Rehashing）

题目：给定哈希表大小

m = 5

，插入关键字 [12, 26, 31, 17, 21, 8]，当表的装填因子大于0.7时，进行再散列。

步骤：

插入关键字并计算当前装填因子。
如果超过阈值，增加哈希表大小并重新计算所有元素的哈希值，重新插入。

表格：

关键字 k k k	初始哈希值 h ( k ) = k % 5 h(k) = k \% 5 h(k)=k%5	插入位置	装填因子
12	2	2	0.2
26	1	1	0.4
31	1	3	0.6
17	2	4	0.8（再散列）
21	1	1（新的哈希表，重新计算位置）	0.4
8	3	3	0.5

k

初始哈希值

h(k) = k \% 5

插入位置装填因子12220.226110.431130.617240.8（再散列）2111（新的哈希表，重新计算位置）0.48330.5

表格内容：

列1: 关键字
列2: 初始哈希值
列3: 实际插入位置
列4: 当前装填因子

如何解答这些常见问题

在处理涉及哈希查找冲突处理方法的题目时，以下是如何解答这些常见问题的步骤和方法：

1. 写出处理冲突的方法名称

常见的方法名称：

开放地址法：线性探测（Linear Probing）、平方探测（Quadratic Probing）、双散列探测（Double Hashing）、再散列（Rehashing）
链地址法：分离链接法（Separate Chaining）

2. 构造基于该处理冲突方法的哈希表

示例：假设哈希表大小为 7，插入关键字 [10, 22, 31, 4, 15, 28]。

线性探测：如前面所述，计算初始哈希值，然后逐步探测下一个空闲位置。
平方探测：计算初始哈希值后，按平方探测公式寻找空闲位置。
双散列探测：使用两个不同的哈希函数，根据冲突次数使用第二个哈希值探测位置。
分离链接法：构造链表，存储发生冲突的元素。

表格：

线性探测和平方探测可以通过表格展示每个关键字的初始哈希值和最终插入位置。
分离链接法通过展示每个桶位置的链表内容来表示。

3. 求出该哈希表在等概率情况下查找成功的ASL（平均查找长度）

计算方法：

成功查找的ASL 是所有查找成功的情况下的查找长度的平均值。
每个元素在哈希表中的查找长度等于插入时探测到的位置数目。
公式：

\text{ASL}_{\text{success}} = \frac{\sum (\text{每个元素的查找长度})}{\text{元素个数}}

示例：假设构造出的哈希表为：

位置	关键字	查找长度
0	28	1
1	15	2
2	22	1
3	10	1
4	31	2
5	4	1
6	-	-

那么成功查找的ASL为：

\ \text{ASL}_{\text{success}} = \frac{1 + 2 + 1 + 1 + 2 + 1}{6} = 1.33 \

4. 查找失败的ASL（平均查找长度）

计算方法：

失败查找的ASL 是查找一个元素不存在时所需探测长度的平均值。
在开放地址法中，失败的查找长度是探测完所有空位后确认不存在该元素。
公式：

\text{ASL}_{\text{failure}} = \frac{\sum (\text{失败时的查找长度})}{\text{失败查找次数}} \

示例：假设查找一个不存在的元素，它的查找长度为探测了 3 次才发现空位，另一种情况查找了 4 次才发现空位，那么失败查找的ASL为：

\text{ASL}_{\text{failure}} = \frac{3 + 4}{2} = 3.5 \\

5. 采用线性探测开放定址法处理冲突，构造哈希表

示例：假设哈希表大小为 7，插入关键字 [10, 22, 31, 4, 15, 28]。计算每个关键字的初始哈希值，并使用线性探测处理冲突。

表格：

关键字 k k k	初始哈希值 h ( k ) = k % 7 h(k) = k \% 7 h(k)=k%7	插入位置
10	3	3
22	1	1
31	3	4（冲突，线性探测到4）
4	4	5（冲突，线性探测到5）
15	1	2（冲突，线性探测到2）
28	0	0

k

初始哈希值

h(k) = k \% 7

插入位置103322113134（冲突，线性探测到4）445（冲突，线性探测到5）1512（冲突，线性探测到2）2800

6. 采用链地址法处理冲突，构造哈希表

示例：哈希表大小为 7，插入关键字 [10, 22, 31, 4, 15, 28]，并使用链地址法解决冲突。

表格：

位置	链表内容
0	[28]
1	[22, 15]
2	-
3	[10]
4	[31, 4]
5	-
6	-

总结

解题时，需要清晰理解每种冲突处理方法的原理，并熟练运用它们进行哈希表的构造和ASL的计算。合理构建表格可以帮助准确表达解题过程。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除

text

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度