开放式寻址技术

本文概述

• 1.线性探测
• 2.二次探测
• 3.双重散列

通常使用三种技术来计算开放寻址所需的探针序列：

1. 线性探测。
2. 二次探测。
3. 双重哈希。

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