How HashMap works internally in Java

This question is asking in most of the java interviews. Let’s see the story of HashMap.

How HashMap works in Java?  

It works based on hashing.

Hashing is nothing but, Creating and Assigning a unique code to the object.

There is a method called “hash (int h) “in HashMap class to do this.

From Java API:

 

Entry Interface:  A key-value pair is called one Entry. This interface is included in Map interface.

Entry class: HashMap holds Entry class in which it implements Map.Entry.

From HashMap class:

 Let’s see HashMap’s put method:

From Java API:

  • HashMap allows only one Null key. First it checks if key is null, store the null in table [0]. Null key always stored in first position of Hash map.
  • Next it calculates key’s hashcode by using hashCode() method and find the hash value. The hash value is used to find index for the array to store entry object.
  • indexFor(hash,table.length) , will find an index/position to store an Entry object.
  • Before going to further discussion, we should know about the hashCode() and equal() contraditction in Java.

If two objects are equals by equals () method, then their hashcode should be same.

If two objects are not equals by equals () method, then their hashcode can be same or different.

 

  • So, now we got the index to store the Entry object (Which is nothing but key-value object).

And we know that two objects which are not equal by equals () method can have same hash code. So we have two objects but only one location to store both the objects? So how it will store? HashMap stores these in the same location. That is called Bucket.  If you see Entry class, we have next attribute (Entry<K, V> next ;). So the two objects will be stored in the same index/same bucket. (Kind of Linked List form.)

  • Now what happens for below case

map.put(“Yuvaraj”, “70”);

map.put(“Yuvaraj”, “68”);

First 70 will be stored for the key “Yuvvraj”.

If you add new value to the same key, it replaces old value with the new value.

So the value for “Yuvaraj” key is 68.

(See if loop in put method to know how it replaces).

This is the way hash map ensures the uniqueness of keys.

 Get method of HashMap from Java API:

 

We already know how put method works and how it maintains the uniqueness of keys.

Once you ask the value based on key, it checks the equality of the key and returns the value of that key.

 Notes:

  • Data structure of HashMap is an Entry class array . transient Entry[] table;
  • Bucket: Particular index location/position in Entry array
  • Key object’s hashCode() has to be calculated, to find the index of an Entry object.
  • Key object’s equals () method is used to enable the uniqueness of key.

Posted in collections and tagged , .

One Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">