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

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).  

现在我被困在这里，我不知道该怎么办。注意：我不想使用任何其他方法，我只想使用双重哈希。
提前感谢任何帮助。

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

附加参考资料：

• 维基百科中的双重哈希
• 双重哈希示例
• 散列 - 双散列冲突解决

奖金：

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