java - 双重哈希与第一个和第二个哈希函数的冲突-java

Question

对于双重哈希，如果与第一个哈希函数发生冲突，您将使用第二个哈希函数，但如果仍然存在冲突怎么办？例如，假设哈希表的大小为 15，哈希函数为(key + 3) % 15，第二个哈希函数为((key % 8) / 3) + 2。假设“插入 59”通过第一个哈希函数进入索引 2，但那里已经有一个键。第二个哈希函数会将其变为 3，但假设那里也已经有一个值。59 会插入哈希表的什么位置，为什么？谢谢

我特别想使用双重哈希，而不是链式哈希或线性探测。

Answer 1

这不是我们计算第二个哈希函数的方式，因为对于每个探测（插槽不可用），您都需要一个新的哈希函数，这是不可行的。

通用第二哈希函数将是类型，

H1(x) - 第一个哈希函数，H2(x) - 第二个哈希函数

我们第一次尝试以下插槽 - H1(x)，

下一个探测将是 - H1(x)+H2(x)，

下一个探针 H1(x)+2*H2(x) ........ H1(x)+n*H2(x)

Answer 2

这是特定于实现的，但通常您会使用链表或其他灵活的数据结构来管理碰撞数据。

从 java.util.HashMap javadoc：

它使用哈希桶方法；也就是说，哈希冲突是通过将新节点与预先存在的节点（或节点列表）链接起来来处理的。以这种方式，避免了诸如线性探测（可能导致初级聚类）和重新散列（与 Java 的预计算哈希码方法不太匹配）之类的技术。在理想情况下（没有冲突），HashMap 在大多数操作上提供 O(1) 性能（containsValue()当然是 O(n)）。在最坏的情况下（所有键都映射到相同的哈希码——不太可能），大多数操作都是 O(n)。