How HashMap works internally

Do you know?

How hashMap find the exact index from bucket for key value pair. Its very much important as we growing our carrier and Interviewers expect such details from you. But everyone says its find from hashCode but its not true, Suppose HashCode is 12000 means hashMap store the data at that location, How come its possible as hashMap can not so much in size. Lets understand How HashMap works internally with detail.

Knowledge of HashMap is required if you feel to understand it again, read HashMap in Java.

Example to understand how data is stored and retrieved from HashMap:

How HashMap works internally is much more important to understand with get and put functions. Lets understand it with step by step.

Put Operation in HashMap:

Let us add below keys and its values into HashMap using put function.

scores.put (“Rohit”, 140);

scores.put (“Dinesh”, 70);

scores.put (“Dhoni”, 90);

scores.put (“Kholi”, 100);

scores.put (“Sachin”, 150);

scores.put (“Dravid”, 130);

Let us understand at which location below key value pair will be saved into HashMap.

scores.put (“Rohit”, 140);

 

  • When you call the put function then it computes the hash code of the Key.

using hash(k) function, Lets suppose the Hash code of (“Rohit”) is 2657860.

  • [Most Important] Once the hash code is generated then HashMap find the bucket index value using a modular operation to find out where the key value is going to fit in the HashMap.
    • Index = Reminder of (hash code / size of HashMap which is 16 by default)
    • Index = 2657860%16 => 4
    •  Index = 4, So 4 is the computed bucket index value where the entry will go sit as a node in the HashMap.
  • Now bucket index value computed, so Key and Value pair will save at the bucket index 4 of the hashMap as a node as shown in the below picture, Please note: if the entry is already present then the value will save at next node in the linklist at 4 bucket location.
  • Similarly all other entries will also enter into HashMao with same process of generating a hashcode and computing its corresponding index number.
  • Java HashMap allows Null Keys (Key= Null) for which the hash code will be zero and it will always goes to index zero of the table.
  • Shown below is how a HashMap will look like after entering different sets of Key value pairs.
HashMap Put Operation

How HashMap works internally




Get Operation in HashMap:

Let us retrieve the value for the below key from HashMap using get function.

scores.get (“Rohit”);.

  • So get operation does the same as that of put operation. When the get function is called it basically gets the hash code of the Key.

hash (key), Lets suppose Hash of (“Rohit”) is 2657860

  • Once it gets the hash code then HashMap does the index computation  to find the index number using below formula and the same we already did while putting to HashMap.
    • Index = Reminder of (hash code / size of HashMap which is 16 by default)
    • Index = 2657860%16 => 4
  • Now hashMap lookup at bucket index 4 for the hash code of the key “2657860”.
  • Hash code “2657860” found then it lookup for the Key “Rohit” itself in that node or linklist.
  • When both hash code and key gets matched with the Node then it looks for the Value in that node and returns the value “140” to the caller.
  • When there are multiple entry nodes in a particular index. Like Rohit & Dhoni in same index, now we want to look for Dhoni’s score. It will check the first node for the hash code match, if it does not match then it will look up the second node for the hash code match, similarly it checks all entries/nodes in that index until it gets the hash code match, once it gets the has code match then it lookup for the its Key match.
  • When both hash code and key gets matched with the Node then it is same as that of previous case, it looks for the Value in that node and returns the value “90” to the caller.

So in the above example it is explained how to put and get entries using Java HashMap and its was easy to understand the “How HashMap works internally”

12 Comments

  • Ashok

    i am not understand how will come 4 (Index = 2657859/16 => 4)

    • Content Writer

      Thanks Ashok for point out. We have updated the page.
      The changes was ” [2657860%16], hashCode should be 2657860 instead of 2657859 and the operator shall be Remainder or Modulus which is %”. Now it will come 4 as a index number.

      Let us know if you have any other doubt.

  • But, with each new entry, the size of hashmap will change. So, it will impact Put and Get behaviors (bucket size calculation will be different for the same object with each increase in item)

    How does it handle this situation?

    • Jags

      Mohit, It won’t change the behaviors on every new entry. Behavior will be changed when the size of hashMap increased.

      just a example, hashMap has increased its size from 16 to 32 then all the modular values will be re-arranged for 16 division factor to 32.

  • Nana

    Say the map gets full and increases in size, does it still keep using modular function of maps current size or mak s use of default size (16)?

    • Ish

      Yes Nana,
      It will use the current size, say that hashMap has increased its size from 16 to 32 then all the modular values (reminder) will be re-arranged for 16 division factor to 32

  • Shreyas

    If the size of HashMap while putting Key-value pair “scores.put (“Rohit”, 140);” is not the same when we are fetching “scores.get (“Rohit”);”, in that case the remainder of the modular operation would be different hence the bucket index would be different, So how is it going to fetch the required value ?

    • Sanket patel

      I agree with you

    • Ish

      As per my knowledge.

      The default array/nodes size is 16 in Hashtable.
      There will be a load factor value set to the Hash table. That is 75% or .75

      So when the hash table is 75% full the table size will be doubled from 16 to 32 arrays or nodes.

      Example: When the table’s 12th array is filled the size of the table will double from 16 to 32.

      So all the modular values (reminder) will be re-arranged for 16 division factor to 32 and so when you want to fetch Rohit. Modular/Reminder value of “Hashcode/32” is sent to fetch Rohit. And in hash table also Node holding Rohit data will have “hashcode/32” modular values.

  • Ramesh

    Good and clean explanation.. !

  • Explained very good way,

  • Digambar

    How many entries can be stored on one node?
    e.g. default nodes of hashmap are 16.
    Considering above example node 4. Cureently it has 3 entries of rohit, dhoni and dravid.
    So my question is, how many entries will be stored on one node? what is limit?

    Thank you.

Leave a Reply

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