如果在应用双哈希算法后仍然存在冲突怎么办？
如果在应用双哈希算法后仍然存在冲突怎么办？
提问于 2018-05-20 04:48:27
我有一个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). 现在我被困在这里，我不知道该怎么做。注意:我不想使用任何其他方法，我只想使用双哈希。
任何帮助，我们都会提前表示感谢。
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-05-20 05:11:53
您必须按照预期使用双哈希算法。
正如在这个非常好的文章中提到的
可以使用以下方法完成双哈希：
(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其他参考资料：
奖励：
Stack Overflow用户
发布于 2018-05-20 04:59:12
在双散列中，重复第二个散列步骤，直到找到一个空闲点。这个过程是将H2(k)添加到最后一个索引(模块大小)中，以生成下一个索引。
在您的示例中，这将转换为：
H1(9) =9%8=1 H2 (9 ) =7-(9% 7) =5 尝试点: 1，6，3，0，5，2，7，4
因此，9值将存储在索引3处。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50431760
复制相关文章
相似问题
腾讯云开发者
