10

Can someone explain the significance of these constants and why they are chosen?

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);
    }

source: java-se6 library

DNA
  • 42,007
  • 12
  • 107
  • 146
Phoenix
  • 8,695
  • 16
  • 55
  • 88
  • 1
    Not a duplicate, nor an answer, but you may find this interesting reading if you're looking into this stuff: http://stackoverflow.com/questions/2538092/why-does-a-hashmap-rehash-the-hashcode-supplied-by-the-key-object – Duncan Jones Sep 03 '12 at 20:38
  • 4
    possible duplicate of [Understanding strange Java hash function](http://stackoverflow.com/questions/9335169/understanding-strange-java-hash-function) – jhurtado Sep 03 '12 at 20:41
  • You are very unlikely to get an answer to this question on this site. The best people to ask would be the designers of the `HashMap` class: Doug Lea, Josh Bloch, Arthur van Hoff, and Neal Gafter. Although, if I had to guess I would say these numbers were determined empirically. – Jeffrey Sep 03 '12 at 20:52
  • 1
    These were definitely chosen experimentally. – Louis Wasserman Sep 03 '12 at 21:08

2 Answers2

2

Understanding what makes for a good hash function is tricky, as there are in fact a great many different functions that are used and for slightly different purposes.

Java's hash tables work as follows:

  1. They ask the key object to produce its hash code. The implementation of the hashCode() method is likely to be of distinctly variable quality (in the worst case, returning a constant value!) and will definitely not be adapted to the particular hash table you're working with.
  2. They then use the above function to mix the bits up a bit, so that information present in the high bits also gets moved down to the low bits. This is important because next …
  3. They take the mod of the hash code (w.r.t. the number of hash table array entries) to get the index into the array of hash table chains. There's a distinct possibility that the hash table array will have size equivalent to a power of 2, so the mixing down of the bits in step 2 is important to ensure that they don't just get thrown away.
  4. They then traverse the chain until they get to the entry with an equal key (according to the equals() method).

To complete the picture, the number of entries in the hash table array is non-constant; if the chains get too long the array gets replaced with a new larger array and everything gets rehashed. That's relatively fast and has good performance implications for normal use patterns (e.g., lots of put()s followed by lots of get()s).

The actual constants used are fairly arbitrary (and are probably chosen by experiment with some simple corpus including things like large numbers of Integer and String values) but their purpose is not: getting the information in the whole value spread to most of the low bits in the value ensures that such information as is present in the output of the hashCode() is used as well as possible.

(You wouldn't do this with perfect hashing or cryptographic hashing; despite the similar names, they have very different implementation strategies. The former requires knowledge of the key space so that collisions are avoided/reduced, and the latter needs information to be moved about in all directions, not just to the low bits.)

Donal Fellows
  • 133,037
  • 18
  • 149
  • 215
0

I have also wondered about such "magic" numbers. As far as I know they are magic numbers.
It has been proven by extensive testing that odd and prime numbers have interesting priorities that could be used in hashing (avoid primary/secondary clustering etc).
I believe that most of the numbers come after research and testing that prove statistically to give good distributions. Why specifically these numbers do that, I have no idea but I have the impression (hopefully collegues here can correct me if I am way off) neither the implementers know why these specific numbers present these qualities

Cratylus
  • 52,998
  • 69
  • 209
  • 339