开放式寻址技术开放式寻址技术|算法设计与分

本文概述

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 mNow h (24, 0) = [24 mod 11 + 0] mod 11= (2+0) mod 11 = 2 mod 11 = 2Since 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 = 3Since 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 =3Since 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=4T [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= 10T [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 = 7T [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 = 9T [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=3h (k, i) = [k mod m + i + 3i2 ] mod mInsert 74. h (74, 0)= (74 mod 11+0+3x0) mod 11= (8 +0+0) mod 11 = 8T [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=3T [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 = 3T [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= 7T [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 = 10T [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 = 10h2(76) = 76 mod 9 = 4h (76, 0) = (10 + 0 x 4) mod 11= 10 mod 11 = 10T [10] is free, so insert key 76 at this place.2. Insert 26. h1(26) = 26 mod 11 = 4h2(26) = 26 mod 9 = 8h (26, 0) = (4 + 0 x 8) mod 11= 4 mod 11 = 4T [4] is free, so insert key 26 at this place.3. Insert 37. h1(37) = 37 mod 11 = 4h2(37) = 37 mod 9 = 1h (37, 0) = (4 + 0 x 1) mod 11 = 4 mod 11 = 4T [4] is not free, the next probe sequence is h (37, 1) = (4 + 1 x 1) mod 11 = 5 mod 11 = 5T [5] is free, so insert key 37 at this place.4. Insert 59. h1(59) = 59 mod 11 = 4h2(59) = 59 mod 9 = 5h (59, 0) = (4 + 0 x 5) mod 11 = 4 mod 11 = 4Since, T [4] is not free, the next probe sequence is h (59, 1) = (4 + 1 x 5) mod 11 = 9 mod 11 = 9T [9] is free, so insert key 59 at this place.5. Insert 21.h1(21) = 21 mod 11 = 10h2(21) = 21 mod 9 = 3h (21, 0) = (10 + 0 x 3) mod 11 = 10 mod 11 = 10T [10] is not free, the next probe sequence ish (21, 1) = (10 + 1 x 3) mod 11 = 13 mod 11 = 2T [2] is free, so insert key 21 at this place.6. Insert 65.h1(65) = 65 mod 11 = 10h2(65) = 65 mod 9 = 2h (65, 0) = (10 + 0 x 2) mod 11 = 10 mod 11 = 10T [10] is not free, the next probe sequence ish (65, 1) = (10 + 1 x 2) mod 11 = 12 mod 11 = 1T [1] is free, so insert key 65 at this place.Thus, after insertion of all keys the final hash table is