CODEWITHSUNDEEP
javahashhashmap
Ankit
Ankit

Reputation: 53

hashcode impementation in hashmap

I was going through the implementation of Hashmap and found below code which calculates the hashcode. Can you please explain me how the value of h is getting calculated below and why it is done in that specific way ?

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

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

Upvotes: 0

Views: 191

Answers (2)

FallAndLearn
FallAndLearn

Reputation: 4135

Hashcode is calculated using the hashCode() function. You have to first look into that function.

The reason after calculating the hashcode it is rehashed again using below

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

is to avoid further collision.

Found the original as

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

See the comments.

Upvotes: 2

cralfaro
cralfaro

Reputation: 5948

This is a way to be sure the hash code for each object is unique, create a seed make some operations to find an unique key and that key will be stored in the map.

As you know a Map store info as pairs key-value. Then the most important line of that method is 

h ^= k.hashCode();

You need to be sure in your code, if decide to override the hashCode() method, that is returning an unique code/id by object, or you could override different objects in the same map.

I hope this clarify a little your doubts

Upvotes: 1

Related Questions