CODEWITHSUNDEEP
javadata-structures
kisa
kisa

Reputation: 31

What is the purpose of storing hash in Node of HashMap?

static class Node implements Map.Entry {
      final int hash;
      final K key;
      V value;
      Node next;

}

In the internal implementation of HashMap in java, the Node stores hash.

Why it is used ? I don't see a need for this.

Upvotes: 2

Views: 970

Answers (2)

chakwok
chakwok

Reputation: 1040

I believe the main reason is to increase the performance. Calling the equals() can be expensive for some objects. With the help of Short-circuit evaluation, jvm doesn't have to call the equals() if the hash doesn't match already

This is how getNode implemented (called when iterating thru a bucket to search for a node. 

     if (first.hash == hash && 
         ((k = first.key) == key || (key != null && key.equals(k))))

//( Same HashCode AND ((Same Object reference of the Key) OR (equal method says True in Key Object) )

Edit: as mentioned by @moreON, hash is also needed for rehashing

Upvotes: 3

moreON
moreON

Reputation: 2008

For a typical hash table implementation, the hashes will be needed again when rehashing the hash table (that is, when it has its capacity changed typically because it is too full). Because the hash of the key can't change and it could potentially be an expensive operation, storing it is sensible to reduce the time taken for this infrequent but expensive opration.

Other hash map implementations that use open addressing will need the hash more often than this, so for those it is even more important that the hash for existing entries is very fast to find. I'm not sure what collision resolution is used for a java hash map though.

Edit: Also not the excellent point Andy K brings up in his answer (and I completely missed) - when adding items, strict equality comparison needs to be done on the key - with any collision resolution multiple hashes will collide due to the much smaller size of the hash map than the hash function's set of possible results. Using a precomputed hash allows for fast inequality testing here.

Upvotes: 1

Related Questions