How HashMap works internally in Java

One of the most popular and important java interview question is how Hashmap will works and how it is different from Hashtable.

Hashmap will work on hashing principle. But it is not as easy as it seems. Hashing is mechanism to assigning unique hashcode to variable or attribute using algorithm for easy retrieve of elements. Hence best hashing algorithm should return same hashcode every time when it is applied on same object.
We will see below how hashing helps to store and retrieve elements from hashmap?.
Hashing uses hash functions to link key and value in Hashtable. We will store elements using put(key, value) and retrieve using get(key) methods from Hashmap.

When we call put method on Hashmap, hashcode() method of key is called and map will find the bucket location buy using hash function and stores value object in bucket. Here bucket is nothing but index of an internal array and it is known as table. Hashmap internally stores mapping in the form of Map.Entry object which contains both key and value objects.

Put method implementaion:

/**
     * 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<K,V> 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;
    }

And when we try to retrieve elements by using get() method, we need to pass key value and here key object will generate same hashcode(generated when storing and it is mandatory to generate same hashcode to retrieve object. This is the reason Hashmap keys are immutable Ex: Strings) so that we can get the bucket location. If  we have only one Map.entry object, we can get it and this is object we stored earlier. But if we have any collision here, it will require more understanding to retrieve elements from same bucket location.

Get Method implementation:

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>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.)
     *
     * <p>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;
    }

Internal array of Hashmap as fixed size and if we are adding more elements into the map, we will get same bucket location for other objects at some point of time. i.e same bucket will return for two different keys and it will store both Map.Entry objects in same bucket. In this case it uses LinkedList inside the same bucket to store the entry objects. i.e it will store new entry object in next node of same bucket.

If we try to retrieve elements from collision bucket, we require one more check to get correct value and it uses equals() method on key value to return correct entry object.  If we get one bucket from key hashing mechanism and if t has two nodes for two entry objects and if we want to get correct entry, Hashmap compares the entry key Object using equals() method and if it return true, then map returns corresponding entry object.

Overridden of value if key is duplicate: Consider below hashmap sample:

package com.sample.java.testing;

import java.util.HashMap;

public class HashMapTest {

    public static void main(String[] args) {

        HashMap hashMap = new HashMap<>();
        hashMap.put("Course", "Java");
        hashMap.put("Course", "J2EE");
        hashMap.put("Course", "Spring");
        hashMap.put("Subject", "Servlet");
        System.out.println(hashMap);
    }

}

Here we will get output as {Course=Spring, Subject=Servlet} because Course Key will override all previous values. Why because all entries will be stored ad linked list if hashcode bucket is same for multiple keys and in that case it uses key.equals("Course") method on keys to inserting/retrieving data. Hence it replace the old values as equals() method will give true if key is same.

Null as Key: If we put null as key in Hashmap it will go to first index of table i.e 0th bucket because hashcode of null is Zero.