实现HashMap：避免compress函数引起的碰撞

Question

我正在实施一个散列映射以包含单词文件中的所有单词（例如 dictionary.txt、bible.txt），但我遇到了冲突问题。我知道那里有很多好的散列函数，但是当我尝试使用此压缩函数压缩散列码时，冲突次数显着增加（我使用 dbj2 作为我的散列函数）。

我的 hashmap 基本上将键转换为其哈希值，并将该哈希值压缩到内部哈希 table 中条目的索引，这是一个数组。如果达到 0.5 的 load factor，它将自身调整为 2 * capacity - 1。发生冲突时，我的哈希图会使用二次探测生成新索引。

这是我当前的压缩函数的样子：

private int compress(int hashCode) {
    return Math.abs(hashCode) % capacity;
}

有什么（有效的）方法可以避免碰撞吗？也接受更改 hashmap 本身的结构。

Answer 1

我建议使用双重哈希算法。

它将通过为冲突的键提供不同的搜索路径来避免聚类
恒定时间搜索/插入
更高的负载系数 (a) 允许您使用更小的 table（压缩）

Answer 2

您对散列码的“压缩”将一个相对较好的散列函数变成了一个较差的散列函数。

基本上只有一个实用的解决方案。停止这样做。只需使用完整的 32 位哈希码。它们不可压缩。您为减小哈希码的大小所做的任何操作都将不可避免地增加冲突率。

将 32 位哈希码映射到数组索引的问题是另一回事。为此，您应该使用 hashcode % array.length.

如果这给你带来了过高的冲突率，那么要么你的原始哈希函数很差，要么你的实现中存在其他错误或设计问题，或者......你只是运气不好。

但这也可能是您收集碰撞统计数据的方式有问题，或者您的期望有问题。

还值得注意的是，您使用的是 open addressing 方案。维基百科文章是这样说的：

A drawback of all these open addressing schemes is that the number of stored entries cannot exceed the number of slots in the bucket array. In fact, even with good hash functions, their performance dramatically degrades when the load factor grows beyond 0.7 or so. For many applications, these restrictions mandate the use of dynamic resizing, with its attendant costs.

事实上，如果您考虑一下，任何开放寻址方案中的冲突影响比使用单独的哈希链时更明显。

最后，从头开始实施高性能哈希表很困难，尤其是 如果您不先阅读有关该主题的文献。（在 Whosebug 上提问并不是进行研究的好方法！）

实现HashMap：避免compress函数引起的碰撞

Implementing HashMap: Avoid collisions caused by compress function

java

hash

hashmap

hash-collision