java - 数组中的双散列表示

Question

我一直在尝试进行双重哈希，但是我对使用双重哈希函数 h' 时会发生什么感到困惑。

当第一个散列函数发生冲突时，是否会将辅助散列函数的值添加到第一个散列函数的值中？

我已经尝试了很多方法并且无法解决这个问题，有问题的问题是以下链接中的图像：

http://postimg.org/image/k6ko6e0gp/

双重哈希如何解决这个问题？数组中已经有 3 个元素，还需要插入 3 个元素

Answer 1

双散列是一种解决冲突的方法（多个键散列到单个索引）。在双重哈希中，将使用两个哈希函数；如果发生冲突，将使用第二个散列函数来查找应该在表中搜索空单元格以放置密钥的步长。此链接概述了可能的冲突解决方法。http://www.cs.utexas.edu/users/mitra/csSpring2016/cs313/lectures/hash.html

在您的情况下，在检查附加的图像后，很明显键 16 会与索引 6 中的其他键发生冲突，因此，您必须应用第二个哈希函数来确定步长。从第一个哈希的索引中，每个（步长）元素都应检查是否有空单元格。一旦找到一个空单元格，密钥将被放置在该单元格中。例如，第一个哈希索引为 0，步长为 2，则应检查索引 0、2、4 ..。请记住，有时，探测需要绕到表格的开头以找到空单元格。

因此，根据所附图像，键 16 的步长为 2。因此，从 6 开始，步长为 2，下一个可用插槽是索引 1，它是免费的 :)

如果在这种情况下找不到空单元格，则应使用新容量调整哈希表的大小。这称为重新散列，这通常是一项昂贵的操作，因为它需要重新散列表中的所有元素。一旦表格达到一定的大小阈值，就应该这样做。