本文概述
通常使用三种技术来计算开放寻址所需的探针序列：
- 线性探测。
- 二次探测。
- 双重哈希。
1.线性探测
它是计算机程序设计中的一种方案, 用于解决哈希表中的冲突。
假设将具有密钥k的新记录R添加到存储表T, 但是具有哈希地址H（k）的存储位置。 H已被填充。
解决冲突的自然钥匙是将R穿越到T（h）之后的第一个可用位置。我们假设位置为m的表T是圆形的, 因此T [i]在T [m]之后。
上面的冲突解决方案称为“线性探测”。
线性探测很容易实现, 但存在称为主聚类的问题。长期占用的插槽会积累起来, 从而增加了平均搜索时间。出现簇是因为接下来有i个完整时隙的空时隙以概率（i +1）/ m填充。长期占用的时隙往往会变长, 并且平均搜索时间会增加。
给定一个普通的哈希函数h’：U {0, 1 … m-1}, 线性探测方法使用哈希函数。
h (k, i) = (h' (k) + i) mod m其中’m’是哈希表的大小, 而h’（k）= k mod m。对于i = 0, 1 …. m-1。
给定密钥k, 第一个时隙为T [h’（k）]。我们接下来是时隙T [h’（k）+1], 依此类推, 直到时隙T [m-1]。然后, 我们绕到时隙T [0], T [1] ….直到最后时隙T [h’（k）-1]。由于初始探针位置处理了整个探针序列, 因此仅m个不同的探针序列可用于线性探针。
示例：考虑使用线性探测将键24、36、58、65、62、86插入大小为m = 11的哈希表中, 请考虑主要哈希函数为h’（k）= k mod m。
解决方案：哈希表的初始状态
Insert 24. We know h (k, i) = [h' (k) + i] mod m
Now h (24, 0) = [24 mod 11 + 0] mod 11
= (2+0) mod 11 = 2 mod 11 = 2
Since T [2] is free, insert key 24 at this place.
Insert 36. Now h (36, 0) = [36 mod 11 + 0] mod 11
= [3+0] mod 11 = 3
Since T [3] is free, insert key 36 at this place.
Insert 58. Now h (58, 0) = [58 mod 11 +0] mod 11
= [3+0] mod 11 =3
Since T [3] is not free, so the next sequence is
h (58, 1) = [58 mod 11 +1] mod 11
= [3+1] mod 11= 4 mod 11=4
T [4] is free; Insert key 58 at this place.
Insert 65. Now h (65, 0) = [65 mod 11 +0] mod 11
= (10 +0) mod 11= 10
T [10] is free. Insert key 65 at this place.
Insert 62. Now h (62, 0) = [62 mod 11 +0] mod 11
= [7 + 0] mod 11 = 7
T [7] is free. Insert key 62 at this place.
Insert 86. Now h (86, 0) = [86 mod 11 + 0] mod 11
= [9 + 0] mod 11 = 9
T [9] is free. Insert key 86 at this place.
Thus, 
2.二次探测
假设具有键k的记录R的哈希地址为H（k）= h, 则与其搜索地址为h, h + 1和h + 2的位置, 而不是搜索位置…我们线性搜索具有地址的位置
h, h+1, h+4, h+9...h+i2二次探测使用以下形式的哈希函数
h (k, i) = (h' (k) + c1i + c2i2) mod m其中（与线性探测一样）h’是辅助哈希函数c1, c2≠0是辅助常数, i = 0, 1 … m-1。初始位置为T [h’（k）]；之后探测的位置偏移量, 该数量以二次方式取决于探测编号i。
示例：考虑使用c1 = 1和c2 = 3的二次探测将键74、28、36、58、21、64插入大小为m = 11的哈希表中。进一步考虑主要哈希函数为h’（k）= k mod m。
解决方案：对于二次探测, 我们有
h (k, i) = [k mod m +c1i +c2 i2) mod m
这是哈希表的初始状态
Here c1= 1 and c2=3
h (k, i) = [k mod m + i + 3i2 ] mod m
Insert 74.
h (74, 0)= (74 mod 11+0+3x0) mod 11
= (8 +0+0) mod 11 = 8
T [8] is free; insert the key 74 at this place.
Insert 28.
h (28, 0) = (28 mod 11 + 0 + 3 x 0) mod 11
= (6 +0 + 0) mod 11 = 6.
T [6] is free; insert key 28 at this place.
Insert 36.
h (36, 0) = (36 mod 11 + 0 + 3 x 0) mod 11
= (3 + 0+0) mod 11=3
T [3] is free; insert key 36 at this place.
Insert 58.
h (58, 0) = (58 mod 11 + 0 + 3 x 0) mod 11
= (3 + 0 + 0) mod 11 = 3
T [3] is not free, so next probe sequence is computed as
h (59, 1) = (58 mod 11 + 1 + 3 x12) mod 11
= (3 + 1 + 3) mod 11
=7 mod 11= 7
T [7] is free; insert key 58 at this place.
Insert 21.
h (21, 0) = (21 mod 11 + 0 + 3 x 0)
= (10 + 0) mod 11 = 10
T [10] is free; insert key 21 at this place.
Insert 64.
h (64, 0) = (64 mod 11 + 0 + 3 x 0)
= (9 + 0+ 0) mod 11 = 9.
T [9] is free; insert key 64 at this place.因此, 在插入所有键之后, 哈希表为
3.双重散列
双重散列是可用于开放式寻址的最佳技术之一, 因为产生的排列具有随机选择的排列的许多特征。
双重哈希使用以下形式的哈希函数
h (k, i) = (h1(k) + i h2 (k)) mod m其中h1和h2是辅助哈希函数, m是哈希表的大小。
h1（k）= k mod m’或h2（k）= k mod m’。这里的m’略小于m（例如m-1或m-2）。
示例：考虑使用双哈希将键76、26、37、59、21、65插入大小为m = 11的哈希表中。考虑辅助哈希函数为h1（k）= k mod 11和h2（k）= k mod 9。
解决方案：哈希表的初始状态为
1. Insert 76.
h1(76) = 76 mod 11 = 10
h2(76) = 76 mod 9 = 4
h (76, 0) = (10 + 0 x 4) mod 11
= 10 mod 11 = 10
T [10] is free, so insert key 76 at this place.
2. Insert 26.
h1(26) = 26 mod 11 = 4
h2(26) = 26 mod 9 = 8
h (26, 0) = (4 + 0 x 8) mod 11
= 4 mod 11 = 4
T [4] is free, so insert key 26 at this place.
3. Insert 37.
h1(37) = 37 mod 11 = 4
h2(37) = 37 mod 9 = 1
h (37, 0) = (4 + 0 x 1) mod 11 = 4 mod 11 = 4
T [4] is not free, the next probe sequence is
h (37, 1) = (4 + 1 x 1) mod 11 = 5 mod 11 = 5
T [5] is free, so insert key 37 at this place.
4. Insert 59.
h1(59) = 59 mod 11 = 4
h2(59) = 59 mod 9 = 5
h (59, 0) = (4 + 0 x 5) mod 11 = 4 mod 11 = 4
Since, T [4] is not free, the next probe sequence is
h (59, 1) = (4 + 1 x 5) mod 11 = 9 mod 11 = 9
T [9] is free, so insert key 59 at this place.
5. Insert 21.
h1(21) = 21 mod 11 = 10
h2(21) = 21 mod 9 = 3
h (21, 0) = (10 + 0 x 3) mod 11 = 10 mod 11 = 10
T [10] is not free, the next probe sequence is
h (21, 1) = (10 + 1 x 3) mod 11 = 13 mod 11 = 2
T [2] is free, so insert key 21 at this place.
6. Insert 65.
h1(65) = 65 mod 11 = 10
h2(65) = 65 mod 9 = 2
h (65, 0) = (10 + 0 x 2) mod 11 = 10 mod 11 = 10
T [10] is not free, the next probe sequence is
h (65, 1) = (10 + 1 x 2) mod 11 = 12 mod 11 = 1
T [1] is free, so insert key 65 at this place.
Thus, after insertion of all keys the final hash table is
