Sunday, June 2, 2013

How get method of HashMap or Hashtable works internally in Java

In this article, I am revisiting couple of interesting question related to internal working of HashMap in Java, mostly asked to senior Java developers, ranging from 4 to 6 and upto 8 years of experience. I did cover lot of these questions from HashMap, ranging from thread-safety to race conditions, in my post about internal working of Java HashMap, but I thought to revisit two of those questions, How get method of HashMap or Hashtable works internally in Java and What happens if two different keys return same hashCode, how do you return value form HashMap in that case. These are the question, which is highly popular in investment banking domain, and preferred choice of interviewer, while interviewing experienced Java professional. If these questions are still being asked, it means not many are answering them in the clarity and confidence they are looking for. This motivates me to revisit these questions again. On a side note, in order to understand these questions, you should have good knowledge of equals and hashcode method as well. At least you should know that :

1) Two unequal object may return same hashcode.
2) When two objects are equal by equals(), they must have same hashcode.


How get works in HashMap and Hashtable in JavaI also suggest reading equals and hashcode chapters from Effective Java book to filling your gaps. By the way due to f this reason, it's a requirement for key object in HashMap to implement both equals() and hashCode(), in fact that is also one of the popular question among experienced Java programmers, asked as what is requirement for an object to be used as key in hash based collection e.g. HashMap, Hashtable and ConcurrentHashMap. Another optional, but worth mentioning requirement of keys in hash based collection is being Immutable object. Keeping this knowledge along with general knowledge of hashing algorithm, which revolves around hash function, let's see those HashMap questions again :

1) How does get(Key key) method works internally in HashMap, and Hashtable in Java?
Here are steps, which happens, when you call get() method with key object to retrieve corresponding value from hash based collection

a) Key.hashCode() method is used to find the bucket location in backing array. (Remember HashMap is backed by array in Java) Though hashcode() is not used directly, but they are passed to internal hash() function.

b) In backing array or better known as bucket, key and values are stored in form of a nested class called Entry.  If there is only one Entry at bucket location, than value from that entry is returned. Pretty straightforward right?

Things get little tricky, when Interviewer ask second question, What happens if two keys has same hashCode? If multiple keys has same hashCode, than during put() operation collision had occurred, which means multiple Entry object stored in a bucket location. Each Entry keep track of another Entry, forming a linked list data structure there. Now, if we need to retrieve value object in this situation, following steps will be followed :

1) Call hashCode() method of key to find bucket location.

2) Traverse thought linked list, comparing keys in each entries using keys.equals() until it return true.

So, we use equals() method of key object to find correct entry and than return value from that. Remember key.equals() method, and this is what Interviewer want to know. I have seen many programmer mentioning value.equals(), which may be due to interview nervousness, but that’s incorrect. Since you don't have value object passed to get() method, there is no question of calling equals and hashCode method on value object.

That's all on these two HashMap questions guys. Remember to mention about key.hashCode() and key.equals(), whenever some one ask how get method of HashMap or Hashtable works in Java. Value object is not used, it's just exist in Entry, so that get can return it.

Related Java HashMap tutorials you may like

1 comment:

  1. Most difficult part of understanding internal working of HashMap is re-sizing of internal array. I know that when re-sizing happens, entries from old array is copied into new array, but I am more worried about how linked list in a certain index is copied. Anyone can please explains that point.. , thanks.

    ReplyDelete

Java67 Headline Animator