How HashMap works in Java

This is one of the most common java interview questions. This question is generally asked like "How HashMap works in java", "How get and put method of HashMap work internally". Almost everybody who worked in Java knows about HashMap, where to use HashMap. Introduction of ConcurrentHashMap and other concurrent collections has also made this questions as starting point to delve into more advanced feature.

In this tutorial, I'll try to explain internal functionality with an easy example. Instead of writing only theory, I'll explain it with the help of an example also so that you will get better understanding and then we will see how get and put function work in java.

How Hashmap works in Java

HashMap works on the principle of Hashing. To understand Hashing, we should understand the three terms first i.e Hash Function, Hash Value and Bucket.

What is Hash Function and Hash Value?

hashCode() method which returns an integer value is the Hash function. The value returns by hashCode() method is Hash Value.

public native int hashCode();

What is bucket?

A bucket is simply a fast-access location (like an array index) that is the the result of the hash function. The idea with hashing is to turn a complex input value into a different value which can be used to rapidly extract or store data.

So, HashMap works on principle of hashing, we use put(key, value) and get(key) method for storing and retrieving objects from HashMap. When we pass Key and Value object to put() method of HashMap, then HashMap calls hashCode() method on Key object and applies returned hashcode into its own hashing function to find a bucket location for storing Map.Entry object.

The important point is that HashMap in Java stores both key and value object as Map.Entry in bucket which is essential to understand the retrieving logic. If you fails to recognize this and say it only stores value in the bucket they will fail to explain the retrieving logic of any object stored in Java HashMap.

So, when we call get(Key k) method on the HashMap object. First, it checks that whether key is null or not. There can only be one null key in HashMap. If key is null, then Null keys always map to hash 0, thus index 0. If key is not null then, it calls hashCode() method on the key object

int hash = hash(hashValue);

Now, hash value is used to find the bucket location at which the Map.Entry object is stored. Entry object stores in the bucket.

Map.Entry Class

HashMap stores elements as Map.Entry objects. Map.Entry class has key and value mapping stored as attributes. Key has been marked as final. Map.Entry looks like

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//More code goes here
}

Now, I explain more about HashMap working by using below example:

package com.gsms.console;
 
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
 
public class HashMapTest {
    public static void main(String[] args) {
        try {
            Map map = new HashMap();
            map.put("India", "New Delhi");
            map.put("Australia", "Sydney");
            map.put("France", "Paris");

            Iterator itr = map.entrySet().iterator();

            while (itr.hasNext()) {
                Map.Entry entry = (Map.Entry) itr.next();
                System.out.println(entry.getKey() + " : " + entry.getValue());
            }
        } 
        catch (Exception e) {
            System.out.println(e.toString());
        }
    }
}

When we debug the program and check HashMap object then we found following structure of HashMap object.

From above diagram, you can observe following points:

• There is an Entry[] array called table which has size 16.
• This table stores Entry class’s object. HashMap class has a inner class called Entry.
• 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 Enrty object get stored(exact position in table). The answer is, hash code is calculated for a key by calling hascode() method. This hash code is used to calculate index for above Entry[] table.

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

HashMap put() method

Before going into put() method’s implementation, it is very important to learn that instances of Entry class are stored in an array. HashMap class defines this variable as:

transient Entry[] table;

Lets see implementation of put method:

/**
* Associates the specified value with the specified key in this map. If the
* map previously contained a mapping for the key, the old value is
* replaced.
*
* @param key
*     key with which the specified value is to be associated
* @param value
*     value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
* if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return
* can also indicate that the map previously associated
* <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
    if (key == null)
       return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Now, lets understand it step by step:

• 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.
• A hash value is calculated using key’s hash code by calling its hashCode() method. This hash value is used to calculate index in array for storing Entry object. JDK designers well assumed that there might be some poorly written hashCode() functions that can return very high or low hash code value. To solve this issue, they introduced another hash() function, and passed the object’s hash code to this hash() function to bring hash value in range of array index size.
• indexFor(hash,table.length) is used to calculate exact index in table array for storing the Entry object.
• 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.

So, in case of collision, Entry objects are stored in LinkedList form. When an Entry object needs to be stored in particular index, HashMap checks whether there is already an entry? If there is no entry, Entry object is stored in this location.

If there is already an object sitting on calculated index, its next attribute is checked. If it is null, and current Entry object becomes next node in LinkedList. If next variable is not null, procedure is followed until next is evaluated as null.

What if we add the another value object with same key as entered before. Logically, it should replace the old value. How it is done? Well, after determining the index position of Entry object, while iterating over LinkedList on calculated index, HashMap calls equals method on key object for each Entry object. All these Entry objects in LinkedList will have similar hash code but equals() method will test for true equality. If key.equals(k) will be true then both keys are treated as same key object. This will cause the replacing of value object inside Entry object only. In this way, HashMap ensure the uniqueness of keys.

HashMap get() method

Now we have got the idea, how key-value pairs are stored in HashMap. Next big question is : what happens when an object is passed in get method of HashMap? How the value object is determined?
Answer we already should know that the way key uniqueness is determined in put() method , same logic is applied in get() method also. The moment HashMap identify exact match for the key object passed as argument, it simply returns the value object stored in current Entry object.
If no match is found, get() method returns null.
Lets see implementation of get() method:

/**
* Returns the value to which the specified key is mapped, or {@code null}
* if this map contains no mapping for the key.
*
* More formally, if this map contains a mapping from a key {@code k} to a
* value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* A return value of {@code null} does not <i>necessarily</i> indicate that
* the map contains no mapping for the key; it's also possible that the map
* explicitly maps the key to {@code null}. The {@link #containsKey
* containsKey} operation may be used to distinguish these two cases.
*
* @see #put(Object, Object)
*/

public V get(Object key) {
    if (key == null) {
        return getForNullKey();
    }
    int hash = hash(key.hashCode());
    for (Entry<k , V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            return e.value;
        }
    }
    return null;
}

Above code is same as put() method till if (e.hash == hash && ((k = e.key) == key || key.equals(k))), after this simply value object is returned.

• Key object is checked for null. If key is null then value of Object resides at table[0] will be returned.
• Key object’s hashcode() method is called and hash code is calculated.
• indexFor(hash,table.length) is used to calculate exact index in table array using generated hashcode for getting the Entry object.
• 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 Notes

• HashMap has a inner class called Entry which stores key-value pairs.
• Above Entry object is stored in Entry[ ](Array) called table.
• A particular index location in array is referred as bucket, because it can hold the first element of a LinkedList of Entry objects.
• 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.
• Hash code for null keys is always zero, and such Entry object is always stored in zero index in Entry[].

I tried my best to describe the working of HashMap. If you find any mistake or want to give any suggestion and feedback, please drop a comment.