Java HashMap Hashing function [closed]

问题:

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 ?

回答1:

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.