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

Question

我有一个大小为 8 的散列 table，我想在其中插入值 (0、1、8、9、5、33)。
我尝试使用具有冲突的哈希算法然后我尝试了双重哈希算法但冲突仍然发生如下：

Hashing = H1(k) = k % 8
Double Hashing = 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

在双重哈希中，您重复第二个哈希步骤，直到找到一个空闲点。过程就是不断地把H2(k)加到上一个索引上（取模大小）生成下一个索引

在您的示例中，这转换为：

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

Attempted spots: 1, 6, 3, 0, 5, 2, 7, 4

因此值 9 将存储在索引 3 处。

Answer 2

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

提到这个很不错article:

Double hashing can be done using :

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

Here hash1() and hash2() are hash functions and TABLE_SIZE is the size of hash table. (We repeat by increasing i when a collision occurs)

给出的示例是（在您的情况下）：

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

其他参考资料：

奖金：

使用双重哈希时最好的二次哈希函数是什么？

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

What if a collision still exists after applying the double hashing algorithm?

hash

hashtable

double-hashing