数据结构中双重哈希

---

在本节中，我们将了解开放寻址方案中的双重哈希技术是什么。有一个普通的哈希函数 h´(x) : U → {0, 1, . . ., m – 1}。在开放寻址方案中，当空间不为空时采用普通的哈希函数 h’(x)，然后执行另一个哈希函数来获取某些插入空间。

$$h_{1}(x)=x\:mod\:m$$

$$h_{2}(x)=x\:mod\:m^{\prime}$$

$$h(x,i)=(h^{1}(x)+ih^{2})\:mod\:m$$

i 的值为 0、1、…。、m – 1。因此，我们从 i = 0 开始，并增加此值，直到得到一个空闲空间。因此，最初当 i = 0 时，h(x, i) 与 h´(x) 相同。

示例

假设我们有一个大小为 20 的列表 (m = 20)。我们想要以线性探测方式放置一些元素。元素为 {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

$$h_{1}(x)=x\:mod\:20$$

$$h_{2}(x)=x\:mod\:13$$

x h(x, i) = (h1 (x) + ih2(x)) mod 20 

 

哈希表