应用双重哈希算法后，如果仍存在冲突，该怎么办？

Question

我有一个大小为8的哈希表，我想插入值(0, 1, 8, 9, 5, 33)。
我尝试了哈希函数，但出现了冲突，然后我尝试了双重哈希算法，但冲突仍然发生，如下所示：

哈希函数 = H1(k) = k % 8
双重哈希算法 = H2(k) = M - (k % M)

H1(0) = 0 % 8 = 0   
H1(1) = 1 % 8 = 1  
H1(8) = 8 % 8 = 0 -----> Needs double hashing ----> 7-(8 % 7)=7-1=6 (we forward 6 steps from the current position which is 0 and it will become 6).  
H1(9) = 9 % 8 = 1----> Needs double hashing ---> 7 - (9%7)=7-2=5(we forward 5 steps from the current position which is 1 and it will become 6 again).  

现在我被卡住了，不知道该怎么办。 注：我不想使用其他方法，只想使用双哈希。 非常感谢您的帮助。

- Abdul Raheem Ghani

---

只是想澄清一下 - 你是否被强制使用H2(k)？或者你可以为二次哈希使用不同的哈希函数吗？ - Rann Lifshitz

如果我两种方法都知道怎么办？ - Abdul Raheem Ghani

那么你就可以开始了。请看下面我详细的回答。这只是一个正确使用双哈希算法的问题，伙计。 - Rann Lifshitz

Answer 1

你必须按照预期使用双重哈希算法。

正如这篇非常好的文章中所提到的：

可以使用双重哈希进行以下操作：

(hash1(key) + i * hash2(key)) % TABLE_SIZE

这里的hash1()和hash2()是哈希函数，TABLE_SIZE是哈希表的大小。当发生冲突时，我们通过增加i来重复尝试插入。

给出的示例（在您的案例中）：

H1(0) = 0 % 8 = 0   
H1(1) = 1 % 8 = 1  
H1(8) = 8 % 8 = 0
   H2(8) = 7 - (8 % 7)= 7-1 = 6
   // double hashing algorithm start : i == 1
   (H1(8) + i*H2(8)) % TABLE_SIZE = (0 + 1*6) % 8 = 6       

H1(9) = 9 % 8 = 1
   H2(9) = 7 - (9 % 7)= 7-2 = 5
   // double hashing algorithm start : i == 1
   (H1(9) + i*H2(9)) % TABLE_SIZE = (1 + 1*5) % 8 = 6 --> collision (increment i to 2)
   (H1(9) + i*H2(9)) % TABLE_SIZE = (1 + 2*5) % 8 = 3 --> no collision

其它参考资料:

• 维基百科：双重哈希
• 双重哈希的例子
• 哈希 - 双重哈希冲突解决

额外福利:

• 使用双重哈希时最佳第二个哈希函数是什么？

- Rann Lifshitz

Answer 2

在双重哈希中，您需要重复第二个哈希步骤，直到找到一个空闲的位置。该过程是将H2(k)添加到最后一个索引（模大小）以生成下一个索引。

在您的示例中，这意味着：

H1(9) = 9 % 8 = 1 H2(9) = 7 - (9 % 7) = 5

尝试的位置：1、6、3、0、5、2、7、4

因此，值为9的元素将存储在索引3处。

- Amit

---

@Amit，我不理解你的回答，请在“尝试点”方面帮助我，我的意思是我想知道如何深入下一步。9将如何变成3？ - Abdul Raheem Ghani