Thursday, February 18, 2016

Java Equals Hashcode Contract Example

This the one of the most common question we used to face during Core Java interview, however its understanding is bit tricky. I will rather take unique approach to make the understanding simple.

So, what is the contract between hashcode and equals to be used as a key to HashMap / HashSet?

Java specification says that if you want to use any object as key to a hashmap or hashset or any other hashing, the contract is that
If two objects are equal according to the equals method, then its hashCode method on each of the two objects must return the same integer result.

Why so?

To understand why this contract even come into picture, we need to understand how hashmap works. Usually in best possible scenario, the time complexity to retrieve an object from hashmap is o(1). In other words, if you ask to retrieve an object by providing key from a map of millions, it just know where exactly it is and goes directly to that object and fetch it without iterating other objects. Thats the beauty of hashing technique.

Hashing Technique:

To understand hashing technique in simple terms, consider you have written a letter to me to be delivered.
Does the postman passes goes to each person and ask his name to find me?
Definitely not. He sends your post to the pincode and then it searches among the pincode. Since in best possible scenario, there is only one person per pincode, the letter reaches to me directly. This the way hashing technique works.
When you store an object to an hashmap, its stores on the key hashcode (also known as bucket). So, while retrieving in one shot, it requires the key hashcode again and thats why it is required to have same hashcode integer result every time. If it is going to give different hashcode, HashMap stores element on different code/bucket and trying to retrieve from different code/bucket, hence unable to retrieve object even-if it is present in hashmap on different bucket / hashcode / pincode.

No comments:

Post a Comment