java在这种情况下有没有更好的方法来调整哈希值？

Question

我注意到一个字符串包含一个特定字符的奇数，比如“b”，它的散列值是

kM+r

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

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

如果我使用下面的公式（reference）来调整散列值，那么上面的所有字符串都散列到同一个bucket，这肯定是而不是我们想要的

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

我做错什么了吗

Answer 1

通常，哈希表实现在分配bucket之前对对象哈希代码执行额外的转换。例如，以下是它在OpenJDK 8java.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是存储桶的数量。在大多数哈希表实现中，bucket的数量是2的幂，这样的公式很好用

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