在这种情况下，有没有更好的方法来调制哈希值

Question

我注意到一个包含特定字符的奇数的字符串，比如"b"的哈希值

kM+r

其中 k 和 r 是整数，M 是 2 的幂。例如，如果调制M M是 2 的幂(例如 16(，则以下所有字符串在调制后都会产生相同的值：

"b"          hashCode("b") = 98,            98%16 = 2
"bbb"        hashCode("bbb") = 97314,       97314%16 = 2
"bbbbb"      hashCode("bbbbb") = 293521890, 293521890%16 = 2
...

如果我使用以下公式(参考(来调制哈希值，则上述所有字符串都哈希到同一个存储桶，这绝对不是我们想要的。

int bucket_id = (hashCode(str) & 0x7fffffff) % M;

我在这里做错了什么吗？

Answer 1

通常，

哈希表实现会在分配存储桶之前对对象 hashCode 执行额外的转换。例如，以下是它在OpenJDK 8 java.util.HashMap中的实现方式：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这使得分布更加均匀。Java-7使用了更复杂的转换，如下所示：

int h = key.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

似乎发现它不必要地复杂，因为Java-8简化了它。

此外，确定存储桶只是具有hash(key) & (n-1)其中n是存储桶的数量。与大多数哈希表实现一样，桶的数量是 2 的幂，这样的公式效果很好。

最后，为了防止冲突(意外或故意(，在Java 8中实现了新算法，该算法在包含太多元素的存储桶中创建二叉树(如果键Comparable(。这使得在过度拥挤的存储桶中进行搜索O(log n)而不是O(n)。