我正在研究 Java 的 HashMap hash() 实现,如下所示
final int hash(Object k) {
// some checks
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
// >>> is Unsigned right shift
}
我不知道为什么添加下面的代码,以及这样做有什么好处?
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
或者让我重新构建我的问题,如果我从实现中删除上面的代码有什么缺点?我了解一些如何避免碰撞的机会,但不确定“到底”如何?
有人可以通过举一个例子来帮助我理解,并解释使用和不使用上述代码时它将如何工作吗?
最佳答案
Java 哈希表实现的大小不是素数大小,而是 2 的幂大小。这使得它可以使用快速位掩码而不是昂贵的余数操作,这通常是一件好事,但缺点是特别糟糕的哈希函数可能会比平常有更多的冲突。您引用的代码以最小化额外冲突的方式混合散列的位。
关于Java HashMap 哈希函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52031980/