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

Could someone tell me that why this hash method designned like this?What is the benefit?

huashui
  • 1,758
  • 2
  • 16
  • 24
  • Where is this code from? What is the input value? – Brad Jul 22 '13 at 04:52
  • It is java's HashMap's method. the input value is the Object's hashcode – huashui Jul 22 '13 at 04:54
  • So it's hashing a hash? I don't think that makes sense... – Brad Jul 22 '13 at 06:11
  • @Brad Unless you don't trust the hash you are given. Have a look at the Integer.hashCode() and consider for a small map it just takes the lower 4 bits. – Peter Lawrey Jul 22 '13 at 07:08
  • BTW You can extend this to other bot sizes. The first line divides the bits into 3 slightly unequal sections and the second divide this range into 3. This means one bit can toggle 9 bits of the result. – Peter Lawrey Jul 22 '13 at 07:12

1 Answers1

3

If you see the Open JDK Source,

This method have the comments...

/**
          * 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.
 */
Suresh Atta
  • 120,458
  • 37
  • 198
  • 307
  • 1
    +1 This is done because some hashCode functions are very simple. For example Integer.hashCode or Inet4Addess.hashCode() As the HashMap is a power of 2 in size, it takes just the lower bits. This means that all keys with the same lower bits would be a collision, Something very easy to do for IP addresses. – Peter Lawrey Jul 22 '13 at 07:10