深入理解开放寻址法中的三种探测序列
一、引言
开放寻址法是解决散列表中冲突的一种重要方法，当发生冲突（即两个不同的键通过散列函数计算得到相同的散列值）时，它会在散列表中寻找下一个可用的存储位置。而探测序列就是用于确定在发生冲突后，依次尝试哪些存储位置的规则。下面详细介绍线性探测、二次探测和双重散列这三种常见的探测序列。
二、线性探测（Linear Probing）
1. 原理
线性探测是最简单的开放寻址法探测序列。当插入一个键值对，计算出的散列值对应的存储位置已被占用时，它会按照顺序依次检查下一个存储位置（通常是逐个向后检查），直到找到一个空的存储位置为止。如果检查到散列表的末尾还没有找到空位置，就会从散列表的开头继续检查。其探测函数的公式为：
h
(
k
,
i
)
=
(
h
′
(
k
)
+
i
)
m
o
d
m
h(k, i) = (h'(k)+i) \bmod m
h(k,i)=(h′(k)+i)modm
其中，
h
(
k
,
i
)
h(k, i)
h(k,i) 是经过
i
i
i 次探测后得到的存储位置，
h
′
(
k
)
h'(k)
h′(k) 是初始的散列值（即通过散列函数直接计算得到的位置），
i
i
i 是探测次数（
i
=
0
,
1
,
2
,
⋯
i = 0, 1, 2, \cdots
i=0,1,2,⋯），
m
m
m 是散列表的大小。
2. 示例
假设散列表的大小 m = 10 m = 10 m=10，散列函数 h ′ ( k ) = k m o d 10 h'(k)=k \bmod 10 h′(k)=kmod10。现在要依次插入键 23 23 23、 33 33 33、 43 43 43。
- 插入键 23 23 23： h ′ ( 23 ) = 23 m o d 10 = 3 h'(23)=23 \bmod 10 = 3 h′(23)=23mod10=3，位置 3 3 3 为空，直接插入。
- 插入键 33 33 33： h ′ ( 33 ) = 33 m o d 10 = 3 h'(33)=33 \bmod 10 = 3 h′(33)=33mod10=3，位置 3 3 3 已被占用，进行第一次探测 i = 1 i = 1 i=1， h ( 33 , 1 ) = ( 3 + 1 ) m o d 10 = 4 h(33, 1)=(3 + 1)\bmod 10 = 4 h(33,1)=(3+1)mod10=4，位置 4 4 4 为空，插入到位置 4 4 4。
- 插入键 43 43 43： h ′ ( 43 ) = 43 m o d 10 = 3 h'(43)=43 \bmod 10 = 3 h′(43)=43mod10=3，位置 3 3 3 已被占用，进行第一次探测 i = 1 i = 1 i=1， h ( 43 , 1 ) = ( 3 + 1 ) m o d 10 = 4 h(43, 1)=(3 + 1)\bmod 10 = 4 h(43,1)=(3+1)mod10=4，位置 4 4 4 也被占用，进行第二次探测 i = 2 i = 2 i=2， h ( 43 , 2 ) = ( 3 + 2 ) m o d 10 = 5 h(43, 2)=(3 + 2)\bmod 10 = 5 h(43,2)=(3+2)mod10=5，位置 5 5 5 为空，插入到位置 5 5 5。
3. 优缺点
- 优点：实现简单，只需要进行简单的加法和取模运算。
- 缺点：容易产生“聚集”现象，即连续被占用的存储位置会越来越长，导致后续插入和查找操作的效率降低。
三、二次探测（Quadratic Probing）
1. 原理
二次探测通过二次函数来确定探测序列，它在发生冲突时，不是像线性探测那样逐个向后检查，而是按照二次方的步长来检查存储位置。其探测函数的公式为：
h
(
k
,
i
)
=
(
h
′
(
k
)
+
c
1
i
+
c
2
i
2
)
m
o
d
m
h(k, i)=(h'(k)+c_1i + c_2i^2) \bmod m
h(k,i)=(h′(k)+c1i+c2i2)modm
其中，
c
1
c_1
c1 和
c
2
c_2
c2 是正的常数，
h
′
(
k
)
h'(k)
h′(k) 是初始散列值，
i
i
i 是探测次数（
i
=
0
,
1
,
2
,
⋯
i = 0, 1, 2, \cdots
i=0,1,2,⋯），
m
m
m 是散列表的大小。常见的情况是
c
1
=
c
2
=
1
c_1 = c_2 = 1
c1=c2=1。
2. 示例
同样假设散列表的大小 m = 10 m = 10 m=10，散列函数 h ′ ( k ) = k m o d 10 h'(k)=k \bmod 10 h′(k)=kmod10， c 1 = c 2 = 1 c_1 = c_2 = 1 c1=c2=1。要插入键 23 23 23、 33 33 33、 43 43 43。
- 插入键 23 23 23： h ′ ( 23 ) = 23 m o d 10 = 3 h'(23)=23 \bmod 10 = 3 h′(23)=23mod10=3，位置 3 3 3 为空，直接插入。
- 插入键 33 33 33： h ′ ( 33 ) = 33 m o d 10 = 3 h'(33)=33 \bmod 10 = 3 h′(33)=33mod10=3，位置 3 3 3 已被占用，进行第一次探测 i = 1 i = 1 i=1， h ( 33 , 1 ) = ( 3 + 1 × 1 + 1 × 1 2 ) m o d 10 = 5 h(33, 1)=(3+1\times1 + 1\times1^2)\bmod 10 = 5 h(33,1)=(3+1×1+1×12)mod10=5，位置 5 5 5 为空，插入到位置 5 5 5。
- 插入键 43 43 43： h ′ ( 43 ) = 43 m o d 10 = 3 h'(43)=43 \bmod 10 = 3 h′(43)=43mod10=3，位置 3 3 3 已被占用，进行第一次探测 i = 1 i = 1 i=1， h ( 43 , 1 ) = ( 3 + 1 × 1 + 1 × 1 2 ) m o d 10 = 5 h(43, 1)=(3+1\times1 + 1\times1^2)\bmod 10 = 5 h(43,1)=(3+1×1+1×12)mod10=5，位置 5 5 5 也被占用，进行第二次探测 i = 2 i = 2 i=2， h ( 43 , 2 ) = ( 3 + 1 × 2 + 1 × 2 2 ) m o d 10 = 9 h(43, 2)=(3+1\times2 + 1\times2^2)\bmod 10 = 9 h(43,2)=(3+1×2+1×22)mod10=9，位置 9 9 9 为空，插入到位置 9 9 9。
3. 优缺点
- 优点：一定程度上缓解了线性探测的“聚集”问题，因为它的探测步长是变化的。
- 缺点：仍然可能出现二次聚集的情况，即不同的初始散列值可能会产生相同的探测序列。
四、双重散列（Double Hashing）
1. 原理
双重散列使用两个散列函数来确定探测序列。当发生冲突时，它会根据第二个散列函数计算出的步长来依次检查存储位置。其探测函数的公式为：
h
(
k
,
i
)
=
(
h
1
(
k
)
+
i
×
h
2
(
k
)
)
m
o
d
m
h(k, i)=(h_1(k)+i\times h_2(k)) \bmod m
h(k,i)=(h1(k)+i×h2(k))modm
其中，
h
1
(
k
)
h_1(k)
h1(k) 是第一个散列函数计算得到的初始散列值，
h
2
(
k
)
h_2(k)
h2(k) 是第二个散列函数，
i
i
i 是探测次数（
i
=
0
,
1
,
2
,
⋯
i = 0, 1, 2, \cdots
i=0,1,2,⋯），
m
m
m 是散列表的大小。为了保证能够遍历散列表中的所有位置，
h
2
(
k
)
h_2(k)
h2(k) 的值必须与
m
m
m 互质。
2. 示例
假设散列表的大小 m = 10 m = 10 m=10，第一个散列函数 h 1 ( k ) = k m o d 10 h_1(k)=k \bmod 10 h1(k)=kmod10，第二个散列函数 h 2 ( k ) = 7 − ( k m o d 7 ) h_2(k)=7-(k \bmod 7) h2(k)=7−(kmod7)。要插入键 23 23 23、 33 33 33、 43 43 43。
- 插入键 23 23 23： h 1 ( 23 ) = 23 m o d 10 = 3 h_1(23)=23 \bmod 10 = 3 h1(23)=23mod10=3，位置 3 3 3 为空，直接插入。
- 插入键 33 33 33： h 1 ( 33 ) = 33 m o d 10 = 3 h_1(33)=33 \bmod 10 = 3 h1(33)=33mod10=3，位置 3 3 3 已被占用， h 2 ( 33 ) = 7 − ( 33 m o d 7 ) = 7 − 5 = 2 h_2(33)=7-(33 \bmod 7)=7 - 5 = 2 h2(33)=7−(33mod7)=7−5=2，进行第一次探测 i = 1 i = 1 i=1， h ( 33 , 1 ) = ( 3 + 1 × 2 ) m o d 10 = 5 h(33, 1)=(3+1\times2)\bmod 10 = 5 h(33,1)=(3+1×2)mod10=5，位置 5 5 5 为空，插入到位置 5 5 5。
- 插入键 43 43 43： h 1 ( 43 ) = 43 m o d 10 = 3 h_1(43)=43 \bmod 10 = 3 h1(43)=43mod10=3，位置 3 3 3 已被占用， h 2 ( 43 ) = 7 − ( 43 m o d 7 ) = 7 − 1 = 6 h_2(43)=7-(43 \bmod 7)=7 - 1 = 6 h2(43)=7−(43mod7)=7−1=6，进行第一次探测 i = 1 i = 1 i=1， h ( 43 , 1 ) = ( 3 + 1 × 6 ) m o d 10 = 9 h(43, 1)=(3+1\times6)\bmod 10 = 9 h(43,1)=(3+1×6)mod10=9，位置 9 9 9 为空，插入到位置 9 9 9。
3.优缺点
- 优点：是开放寻址法中最好的方法之一，能更均匀地分布键，减少聚集现象，使插入、查找和删除操作的平均性能更接近理想情况。
- 缺点：需要设计两个散列函数，实现相对复杂，计算开销也会稍微大一些。