Java HashMap 哈希函数 [英] Java HashMap Hashing function
问题描述
我正在通过 Java 的 HashMap hash() 实现,如下所示
I was going through Java's HashMap hash() implementation , its like below
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
}
我不知道为什么要添加下面的代码,这样做有什么好处?
I am not sure why the below code is added , and what advantage is gained by same ?
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
或者,如果我从实现中删除上述代码,让我重新提出我的问题,有什么缺点?我了解它如何避免碰撞的机会,但不确定确切"如何?
Or Let me re-frame my question if i remove above code from implementation what is the disadvantage ? I understand some how its avoiding chances of collision but not sure "exactly" how ?
有人可以通过举个例子帮助我理解,并解释它在使用和不使用上述代码的情况下如何工作?
can some one help me understand by giving an example , and explain how will it work with and without the above code ?
推荐答案
Java 哈希表实现不是将表的大小设置为素数大小,而是两倍大小.这允许它使用快速位掩码而不是昂贵的余数运算,这通常是一件好事,但缺点是特别糟糕的散列函数可能比平时有更多的冲突.您引用的代码以最小化额外冲突的方式混合了哈希的位.
The Java hash table implementation sizes the table not to a prime size, but to a power of two size. This allows it to use fast bit masking instead of expensive remainder operations, which is generally a good thing, but the drawback is that particularly bad hash functions might have more collisions than usual. The code you cite mixes the bits of the hash in a way that minimizes the extra collisions.
这篇关于Java HashMap 哈希函数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!