Why does HashMap's get() compare both the hash value and key in Java?

  • A+
Category:Languages

I was looking at the implementation of HashMap in JDK8. In the get methods, I saw the below line which is used to find the Node that matches with the given key.

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

Why is there the need to compare the hash value along with key? Why is the line above not written as:

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

Is there any explanation on why it is done this way? Thank you.

 


What seems to be causing your confusion, are two things:

1. Comparing the hash values is (often very much) faster than comparing keys directly.

2. In a == operator, the second condition won't be checked if the first is false.

So first the hash values are compared, which is fast:

  • When they are not equal, you know the keys aren't equal as well, and you are done.

  • When they are equal, you don't know if the keys are equal as well, so you must compare keys, which is (relatively) slow.

Since most keys are not equal, most of the time you only compare hashes. Only when keys are equal (or when hashes are equal due to hash collisions) do you compare the keys, which is rare, and thus you have a performance benefit.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: