How HashMap works in java

Most common interview questions are <code>How HashMap works in java</code>, “How get and put method of HashMap work internally”. Here I am trying to explain internal functionality with an easy example. HashMap  is one of the most used Collections in java.Rather than going through theory, we will start with example first, so that you will get better understanding and then we will see how get() and put() function work in java.

Let’s take a very simple example. I have a Country  class, we are going to use Country class object as key and its capitalname (string) as value. Below example will help you to understand, how these key value pair will be stored in hashmap.

1. Country.java

If you want to understand more about hashcode and equals method of object, you may refer hashcode() and equals() method in java

2. HashMapStructure.java(main class)

Now put debug point at line 24 and right click on project->debug as-> java application. Program will stop execution at line 24 then right click on countryCapitalMap  then select watch.You will be able to see structure as below.
Now From above diagram, you can observe the following points
    1. There is an Entry[]  array called table which has size 16.
    2. This table stores Entry class’s object. HashMap class has an inner class called Entry . This Entry have key value as an instance variable. Let’s see structure of entry class Entry Structure.

  1. Whenever we try to put any key value pair in hashmap, Entry class object is instantiated for key value and that object will be stored in above mentioned Entry[] (table). Now you must be wondering, where will above created Entry object get stored(exact position in table). The answer  is, hash code is calculated for a key by calling Hascode() method. This hashcode is used to calculate index for above Entry[] table.
  2. Now, If you see at array index 10 in above diagram, It has an Entry object named HashMap$Entry .
  3. We have put 4 key-values in Hashmap but it seems to have only 2!!!! This is because if two objects have same hashcode, they will be stored at same index. Now the question arises how? It stores objects in the form of LinkedList (logically).

So how hashcode of above country key-value pairs are calculated.

Below diagram will explain LinkedList concept clearly.

So now if you have good understanding of Hashmap  structure,Lets go through put and get method.


Put

Let’s see the implementation of put method:

now lets understand above code step by step
  1. Key object is checked for null. If key is null then it will be stored at table[0]  because hashcode for null is always 0.
  2. Key object’s hashcode() method is called and hash code is calculated. This hashcode is used to find index of array for storing Entry object. It may happen sometimes that, this hashcode function is poorly written so JDK designer has put another function called hash() which takes above-calculated hash value as argument. If you want to learn more about hash() function, you can refer hash and indexFor method in hashmap.
  3. indexFor(hash,table.length)  is used to calculate exact index in table array for storing the Entry object.
  4. As we have seen in our example, if two key objects have same hashcode(which is known as collision) then it will be stored in form of linkedlist.So here, we will iterate through our linkedlist.
    • If there is no element present at that index which we have just calculated then it will directly put our Entry object at that index.
    • If There is element present at that index then it will iterate until it gets Entry->next  as null.
    • What if we are putting same key again, logically it should replace old value. Yes, it will do that. While iterating it will check key equality by calling equals()  method(key.equals(k)), if this method returns true then it replaces value object with current Entry’s value object.
    • If it did not find the duplicate key, then current Entry  object will become first node in linkedlist and current Entry -> next will become an existing first node on that index.

Get

 Lets see implementation of get now:

As you got the understanding on put functionality of hashmap. So to understand get functionality is quite simple. If you pass any key to get value object from hashmap.
  1. Key object is checked for null. If key is null then value of Object resides at table[0]  will be returned.
  2. Key object’s hashcode() method is called and hash code is calculated.
  3. indexFor(hash,table.length)  is used to calculate exact index in table array using generated hashcode for getting the Entry object.
  4. After getting index in table array, it will iterate through linkedlist and check for key equality by calling equals() method and if it returns true then it returns the value of Entry object else returns null.

Key points to Remeber

  • HashMap has a inner class called Entry  which stores key-value pairs.
  • Above Entry object is stored in Entry[ ](Array) called table
  • An index of table is logically known as bucket and it stores first element of LinkedList .
  • Key object’s hashcode() is used to find bucket of that Entry  object.
  • If two key object ‘s have same hashcode  , they will go in same bucket of table array.
  • Key object ‘s equals()  method is used to ensure uniqueness of key object.
  • Value object  ‘s equals() and hashcode() method is not used at all

Java HashMap

Please go through  core java interview questions and java interview questions for more interview questions.

import_contacts

You may also like:

Related Posts

  • 02 October

    Initialize ArrayList with values in Java

    In this article, we will learn to initialize ArrayList with values in Java. ArrayList is an implementation class of List interface in Java. It is used to store elements. It is based on a dynamic array concept that grows accordingly. We can Initialize ArrayList with values in several ways. Let’s see some of them with […]

  • 17 March

    PriorityQueue in Java 8

    In this post, we will see about Java 8 PriorityQueue. When the objects are supposed to be processed on the basis of their priority, in that scenario we use PriorityQueue. It’s a special type of queue (also, unbound queues) where the elements can be ordered either as per their natural ordering or based on a […]

  • 06 October

    2d Arraylist java example

    In this post, we will see how to create 2d Arraylist in java. Best way to create 2d Arraylist is to create list of list in java. [crayon-6001e1c0dfaf3500455951/] Let’s create a program to implement 2d Arraylist java. [crayon-6001e1c0dfaf7985199626/] Output: 2nd element in list3 : List3_Str2 3nd element in list1 : List1_Str3 1st element in list2 […]

  • 21 October

    How to Sort HashSet in Java

    In this post, we will see how to sort HashSet in java. HashSet is a collection which does not store elements in any order. You might come across a situation where you need to sort HashSet. There can be many ways to sort HashSet, we will see two methods here. Using TreeSet You can use […]

  • 20 October

    Java Array to Set

    In this post, we will learn java array to set conversion. There are many ways to convert array to set. 1. Using Java 8’s Stream If you are using Java 8, I would recommend using this method. [crayon-6001e1c0dfc87337114120/] Output [John, Martin, Mary] 2. Using HashSet constructor() We can directly call HashSet‘s constructor for java set […]

  • 10 August

    Java Set to Array

    In this post, we will learn java set to array conversion. There are many ways to convert set to an array. 1. Using Java 8’s Stream If you are using Java 8, I would recommend using this method. [crayon-6001e1c0dfd66214249588/] Output [John, Martin, Mary] 2. Using toArray() We can directly call toArray method on set object […]

Leave a Reply

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

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.