开放寻址技术

2025年3月17日 | 阅读 7 分钟

三种技术常用于计算开放寻址所需的探测序列

线性探测。
二次探测。
双重散列。

1. 线性探测

这是计算机编程中解决哈希表中冲突的一种方案。

假设一个新记录 R，其键为 k，要添加到内存表 T 中，但带有哈希地址 H (k) 的内存位置。H 已经满了。

我们解决冲突的自然方法是将 R 交叉到 T (h) 之后的第一个可用位置。我们假设具有 m 个位置的表 T 是循环的，因此 T [i] 位于 T [m] 之后。

上述冲突解决称为“线性探测”。

线性探测易于实现，但它会遇到一个称为主要聚集的问题。被占用槽位的长序列会建立起来，从而增加平均搜索时间。聚集现象的出现是因为由 i 个完整槽位先行的空槽位接下来以概率 (i + 1)/m 填充。被占用槽位的长序列往往会变得更长，并且平均搜索时间会增加。

给定一个普通的哈希函数 h': U {0, 1...m-1}，线性探测方法使用哈希函数。

其中 'm' 是哈希表的大小，对于 i=0, 1....m-1，h' (k) = k mod m。

给定键 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. 二次探测

假设一个记录 R，其键为 k，其哈希地址为 H (k) = h，然后，不是搜索地址为 h、h+1 和 h+ 2... 的位置，我们线性搜索地址为

h, h+1, h+4, h+9...h+i²

二次探测使用以下形式的哈希函数

h (k,i) = (h' (k) + c₁i + c₂i²) mod m

其中（与线性探测一样）h' 是一个辅助哈希函数，c₁ 和 c₂ ≠0 是辅助常数，i=0, 1...m-1。初始位置是 T [h' (k)]；稍后探测到的位置将通过取决于探测编号 i 的二次方式的量来偏移。

示例： 考虑使用二次探测将键 74、28、36、58、21、64 插入到大小为 m =11 的哈希表中，其中 c₁=1 且 c₂=3。进一步考虑主哈希函数为 h' (k) = k mod m。

解决方案： 对于二次探测，我们有

h (k, i) = [k mod m +c₁i +c₂ i²) mod m

这是哈希表的初始状态

Here c₁= 1 and c₂=3
     h (k, i) = [k mod m + i + 3i² ] 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 x1²) 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) = (h₁(k) + i h₂ (k)) mod m

其中 h₁ 和 h₂ 是辅助哈希函数，m 是哈希表的大小。

h₁ (k) = k mod m 或 h₂ (k) = k mod m'。这里 m' 略小于 m（例如 m-1 或 m-2）。

示例： 考虑使用双重散列将键 76、26、37、59、21、65 插入到大小为 m = 11 的哈希表中。考虑辅助哈希函数为 h₁ (k)=k mod 11 和 h₂(k) = k mod 9。

解决方案： 哈希表的初始状态为

1. Insert 76.
         h₁(76) = 76 mod 11 = 10
         h₂(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.
	h₁(26) = 26 mod 11 = 4
          h₂(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.
	h₁(37) = 37 mod 11 = 4
          h₂(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.
	h₁(59) = 59 mod 11 = 4
          h₂(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.
	  h₁(21) = 21 mod 11 = 10
	  h₂(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.
	    h₁(65) = 65 mod 11 = 10
              h₂(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