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哈希表实现将表的大小设置为不是素数，而是2的幂。这允许它使用快速位掩码，而不是昂贵的余数操作，这通常是一件好事，但缺点是特别坏的哈希函数可能比平常更多的冲突。您引用的代码以最小化额外冲突的方式混合了散列的位。

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屋！