data-structures - 使用双散列解决第二种情况的冲突

Question

当提供第二个碰撞案例时，如何解决？

IE：

假设我们有一个数字数组：

[22、1、13、11、24、-1、-1、-1、-1、-1、-1]

其中 -1 表示数组中为空......

如果我们尝试使用插入 33

h1(key) = key % 11
h2(key) = 7 - (key % 7)

传入 33 将给出 2，其中数组位置 2 已被占用（有 13 个）。我们如何处理这种碰撞情况？我们是否再次将返回的 mod 值传递给 h2 ？我们替换值@那个数组值吗？（我怀疑后者并非如此。）

编辑：在 h2 中添加了括号

Answer 1

使用双重散列，您可以将位置计算为：

pos = (h1 + i * h2) mod table_size

这里的技巧是递增i直到在哈希表中找到一个空位置。因此，计算不仅进行一次，而且多次进行，直到找到一个槽为止。有关详细信息，请参阅维基百科文章。

还有其他类似于双重哈希的开放寻址形式也非常有效，例如布谷鸟哈希和罗宾汉哈希。