Thursday, October 30, 2008

equals() & hashcode() relation in Java

I assume that you have an idea about equals() and hashCode() methods present in Object class. What you may not know, is that a relation(or perhaps a contract) exists between them.

Remember the following points:
  • If you override equals(), then you must override hashCode()
  • equals() & hashCode() must be evaluated based on same fields
  • If two objects are equal using equals() then they must have same hashCode() value, but vice-versa need not be true.
Since hashCode() value of an object determines how it will be stored and located when it is used with collections like HashMap & HashSet, so it becomes necessary that equal objects must have same hashCode() value. 
So, implementing hashCode() when your program deals with collections become really important for reasons such as efficiency and correctness.

To give an analogy to this hashing process, imagine a sequence of buckets to be your hashtable. Now, to retrieve an element, we do
1. Locate the right bucket using hashCode() value
2. Search the bucket for the element using equals()

Now, if two equals objects (which would be present in one bucket) have different hashcodes, you would never be able to retrieve them back correctly, because you are not looking in the right bucket. 

Although, it is legal to have same hashCode() value for different (read unequal) objects, but it will hurt the efficiency as it would make it a bit slow to locate the correct bucket.

Also, if two objects have different hashCode() values, then they must not be equal using equals() i.e.
if x.hashCode() != y.hashCode() then x.equals(y) == false.

This also helps in clearing a popular misconception about hashcodes that they identify an element uniquely. They can be used as an object ID but they are not necessary unique.

Still interested in more details, read this article to get more insight. :-)