在这种情况下是否有更好的方法来调制哈希值？

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)调制hash值，上面所有的字符串hash到同一个bucket，肯定是NOT我们想要什么。

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

我是不是做错了什么？

Answer 1

通常哈希 table 实现在分配存储桶之前对对象 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 是桶的数量。在大多数哈希 table 实现中，桶的数量是 2 的幂，这样的公式很好用。

最后，为了进一步防止碰撞（意外或故意），在 Java 8 中实施了新算法，该算法在包含太多元素的桶中创建二叉树（如果键是 Comparable).这使得在过度拥挤的存储桶 O(log n) 而不是 O(n).

中进行搜索

在这种情况下是否有更好的方法来调制哈希值？

Is there a better way to modulate the hash value in this case?

java

hash

hashmap

hashcode

hashset