Explanation of HashMap#hash(int) method

Question

Can someone please explain to me the static HashMap#hash(int) method?

What's the justification behind it to generate uniformly distributed hashes?

/**  * Applies a supplemental hash function to a given hashCode, which  * defends against poor quality hash functions.  This is critical  * because HashMap uses power-of-two length hash tables, that  * otherwise encounter collisions for hashCodes that do not differ  * in lower bits. Note: Null keys always map to hash 0, thus index 0.  */ static int hash(int h) {     // 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); } 

An example would make it easier to digest.

Clarification I'm aware of the operators, truth tables and bitwise operations. I just can't really decode the implementation nor the comment really. Or even the reasoning behind it.

Answer 1

>>> is the logical right shift (no sign-extension) (JLS 15.19 Shift Operators), and ^ is the bitwise exclusive-or (JLS 15.22.1 Integer Bitwise Operators).

As to why this is done, the documentation offers a hint: HashMap uses power-of-two length tables, and hashes keys by masking away the higher bits and taking only the lower bits of their hash code.

// HashMap.java -- edited for conciseness static int indexFor(int h, int length) {     return h & (length-1); }  public V put(K key, V value) {     int hash = hash(key.hashCode());     int index = indexFor(hash, table.length);     // ... } 

So hash() attempts to bring relevancy to the higher bits, which otherwise would get masked away (indexFor basically discards the higher bits of h and takes only the lower k bits where length == (1 << k)).

Contrast this with the way Hashtable (which should have NOT a power-of-two length table) uses a key's hash code.

// Hashtable.java -- edited for conciseness public synchronized V get(Object key) {     int hash = key.hashCode();     int index = (hash & 0x7FFFFFFF) % table.length;     // ... } 

By doing the more expensive % operation (instead of simple bit masking), the performance of Hashtable is less sensitive to hash codes with poor distribution in the lower bits (especially if table.length is a prime number).