How get and put methods of HashMap or Hashtable internally works in Java [Answered]

In this article, I am revisiting a couple of interesting questions 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 a lot of these questions from HashMap, ranging from thread-safety to race conditions, in my post about the internal working of Java HashMap, but I thought to revisit two of those questions, how does get and put 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 the investment banking domain, and preferred choice of the interviewer, while interviewing experienced Java professional in companies like JP Morgan, Barclays, Citibank, Deutsche Bank, Goldman Sachs, Wells Fargo, and Morgan Stanley. 

If these Java 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 HashMap questions again and that's what we will do in this article. 

On a side note, in order to understand these questions, you should have good knowledge of equals and hashcode methods 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.

This is very very important while answering HashMap based questions as both get and put methods make extensive use of equals() and hashcode() methods. If you are not comfortable with this concept then I suggest you join a comprehensive course like The Complete Java Masterclass on Udemy, an 80+ hour course to learn Java in depth.  

And, if you are in hurry then I also suggest reading equals and hashcode chapters from the Effective Java book to learn this concept in depth. This book has the best explanation of equals and hashCode in Java. 



How get() method of Hashtable works in Java

Anyway, let's see those HashMap questions again :

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

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

b) In the 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 the bucket location, then the value from that entry is returned. Pretty straightforward right?

Things get a little tricky, when the Interviewer asks 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 a 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, the 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 entry using keys.equals() until it returns true.

So, we use the equals() method of a key object to find the correct entry and then return the value from that. Remember key.equals() method and this is what the interviewer wants to know.

I have seen many programmers mentioning the value.equals(), which may be due to interview nervousness, but that’s incorrect. Since you don't have the value object passed to get() method, there is no question of calling equals and hashCode method on the value object.

Keeping this knowledge along with general knowledge of hashing algorithm, which revolves around hash function. 

You should also read a proper book or join a comprehensive on data structure and algorithms to learn more about how a hash function works and different strategies to handle collisions in Java. If you need a recommendation then I highly recommend 
Data Structures and Algorithms: Deep Dive Using Java book by Tim Buchalaka on Udemy. It's a great book to revise essential data structures like hash tables for Java programmers. 

How get and put methods of HashMap works in Java



How put(key, value) method of HashMap works in Java

How get works in HashMap and Hashtable in JavaSimilarly, when you store an object using the put(key, value) method then the key object is used to find the bucket location. Java calls the key.hashCode() method to find the bucket location (internally it is passed to another hash function). 

Once the bucket location is found, then the entry object is stored there, which contains both key and value object. If an entry object is already stored in a bucket location then a linked list is created and a new object is added at the tail of the linked list. 

So, you can see that the hashcode method of the key object plays an important role when you call the put method to store the key-value pair, while both equals() and hashCode() methods are used while retrieving values from HashMap in Java. 

By the way, due to this reason, it's a requirement for the 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 the requirement for an object to be used as a key in hash-based Maps like HashMapHashtable, and ConcurrentHashMap

Another optional, but worth mentioning requirement of keys in a hash-based collection is being an Immutable object because if you use a mutable object then if the state of an object is changed while the object is stored in Map then it would be impossible to find the same bucket location as hashCode will return a different value and equals() will also not match with the original object. 

That's all on these two HashMap questions guys. Remember to mention the 
key.hashCode() and key.equals(), whenever someone asks how does get() and put() methods of HashMap or Hashtable works in Java. A value object is not used, it just exists in Entry so that get can return it.

Further Learning
Java In-Depth: Become a Complete Java Engineer
Java Fundamentals: Collections
Data Structures and Algorithms: Deep Dive Using Java


Related Java HashMap tutorials you may like
  • Difference between ConcurrentHashMap and HashMap in Java (answer)
  • 5 Difference between HashMap and Hashtable in Java (answer)
  • How to sort HashMap in Java by keys (example)
  • How to get key from HashMap  by passing values (example)
  • 10 Example of Concurrent HashMap in Java (examples)
  • 21 HashMap Interview questions for Java Programmers (questions)
  • 5 Best Courses to learn Java Collection Framework (courses)
  • 2 ways to sort HashMap in Java? (examples)
  • How to sort HashMap by values in Java 8? (example)
  • Difference between HashMap, LinkedHashMap, and TreeMap in Java (answer)

Thanks for reading this article so far. If you find this Java interview question interesting and my explanation useful then please share it with your friends and colleagues. If you have you have any questions or feedback then please drop a note. 

P. S. - If you are preparing for Java interviews and need more such questions for practice then you can also check out my book, Grokking the Java Interview which contains many such excellent core Java questions and covers all essential core Java topics like Collections, Multithreading, Core Java basics, design patterns, JDBC, and much more. 

14 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
  4. Simple and upto the point explanation.Thanks for sharing

    ReplyDelete
  5. Good for fresher as well experienced..

    ReplyDelete
  6. hi,hashMap find the exact index from bucket for key value pair from hashCode but its not true, Suppose HashCode is 16000 means hashMap store the data at that location, How come its possible as hashMap can not so much in size?

    ReplyDelete
    Replies
    1. The way it fetches the array location or index is using a bitwise operator to compare the key with hashcode, it doesn't directly uses the hashcode to store value.

      Delete
    2. After getting hash code of key it will convert it as an integer value(range would be with in size) by calling hash().

      Delete
  7. Hi to All.
    What happens if i pass a key on a get() which is not available in keySet.

    ReplyDelete
    Replies
    1. you mean Map? it return null.
      As per Javadoc
      get returns the value to which the specified key is mapped, or null if this map contains no mapping for the key

      Delete

Feel free to comment, ask questions if you have any doubt.