26

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.

durron597
  • 31,968
  • 17
  • 99
  • 158
qnoid
  • 2,346
  • 2
  • 26
  • 45
  • 1
    What version of Java are you using? I can't find any static hash(int) methods anywhere – tom Mar 10 '10 at 02:42
  • I edited the original question to contain more comments from the source, for the benefit of others. – polygenelubricants Mar 10 '10 at 02:54
  • http://java.dzone.com/articles/hashmap-internal - from a deleted answer - has a lot more technical info than the answers here. Archive link https://web.archive.org/web/20141216114220/http://java.dzone.com/articles/hashmap-internal – Jason C Jul 16 '17 at 14:23

2 Answers2

15

>>> 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).

polygenelubricants
  • 376,812
  • 128
  • 561
  • 623
2

I don't know how all the shifting works, but the motivation is laid out in the comments:

The way the HashMap is implemented relies on the hashCode function being sufficiently well implemented. In particular, the lower bits of the hash value should be distributed evenly. If you have many collisions on the lower bits, the HashMap will not perform well.

Because the implementation of hashCode is outside of the control of HashMap (every object can implement their own), they supply an additional hash function that shifts the object's hashCode around a little to ensure that the lower bits are distributed more randomly. Again, I have no idea how this works exactly (or how effective it is), but I assume it depends on at least the higher bits being distributed equally (it seems to mesh the higher bits into the lower bits).

So what this does is to try to minimize collisions (and thus improve performance) in the presence of poorly implemented hashCode methods.

Thilo
  • 257,207
  • 101
  • 511
  • 656