How get method of HashMap or Hashtable works internally in Java

In this article, I am revisiting a couple of interesting question related to the internal working of HashMap in Java, mostly asked senior Java developers, ranging from 4 to 6 and up to 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 the same hashCode, how do you return value from 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 objects may return the same hashcode.
2) When two objects are equal by equals(), they must have the same hashcode.





How get method of Hashtable works in Java

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 questions 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 a hash-based collection is being an Immutable object. Keeping this knowledge along with general knowledge of hashing algorithm, which revolves around hash function. 

You should read a proper book on data structure and algorithms to learn more about how a hash function works and different strategies to handle collisions in Java. One of such book is Introduction to Algorithms by Thomas Cormen, perfect for any programmer interested in learning more about algorithms and data structures. 


How get method of HashMap internally works in Java


Anyway, 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 the bucket, key and values are stored in the form of a nested class called Entry.  If there is only one Entry at bucket location, then the value from that entry is returned. Pretty straightforward right?

Things get little tricky, when Interviewer ask the second question, What happens if two keys have the same hashCode? If multiple keys have the same hashCode, then during put() operation collision had occurred, which means multiple Entry objects stored in a bucket location. Each Entry keeps track of another Entry, forming a linked list data structure there.  

How hashtable internally works in Java

This has also changed from Java 8, where after a threshold is crossed then a binary tree is used instead of linked list to lift the worst case performance from O(n) to O(logN). You can see how HashMap and LinkedHashMap handle collision in Java to learn more about this change. 

Now, if we need to retrieve value object in this situation, following steps will be followed :

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

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

So, we use equals() method of a key object to find correct entry and then return value from that. Remember key.equals() method, and this is what Interviewer want to know. I have seen many programmers 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 someone asks how to get method of HashMap or Hashtable works in Java. A value object is not used, it just exists in Entry so that get can return it.

Related Java HashMap tutorials you may like

7 comments:

  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
  2. From Java 8 onwards, working of get() method has changed little bit. Now if number of elements in a bucket linked list grows beyond a thresold, it will automatically be converted into a tree structure. This will reduce worst case performance of get() call from O(n) to O(nLogN), which is quite a significant perofrmance improvement.

    ReplyDelete
  3. O(n) to O(nLogN) ?? isn't O(nLogN) worse than O(n)?

    ReplyDelete
    Replies
    1. I think its just O(logN) and not O(nLogN), because you are right O(NLogn) is worse than O(n) in terms of performance.

      Delete