Internal implementation of HashMap in Java

How HashMap works in Java?

It is one of the favorite questions of the interviewer to check yours in-depth knowledge of core Java.In this post, we are going to see the internal implementation of HashMap.

In one sentence we can answer as "HashMap works on the Hashing principle".So first we have to understand the hashing principle to answer this question in depth.

To make it more clear I am going to take an example where we will see the HashMap internal structure and how the values are getting stored and retrieved from HashMap.


HashMap store the data in the form of a key-value pair in the table array which is of type Entry <K, V> and is called as the bucket.In HashMap class we can find that Entry<K, V> is a static inner class which implements Map.Entry<K, V> and have variables key, value, hash, next of type Entry.This hash value is used to find the bucket number i.e. array index.


    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

Let's create a HashMap and store value in it.

HashMap<String, Integer> hashMap = new HashMap<>();

hashMap.put("abc", 5);

We can see in the debug mode that hashmap got created having the load factor of  0.75 and an array named table (bucket) got created.The default size of this array is 16.
Our data got stored at the index 2.So now how it got stored in the bucket at index 2?

When Put method is called.

When we call put method to insert data into HashMap then the hashcode method is called to get the initial hash value which then passed to other hashing function to get the final hash value with better hashing technique to get the bucket location, the final hash value is then passed to indexFor() method.


  public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        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;
    }

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    final int hash(Object k) {

        int h = hashSeed;

        if (0 != h && k instanceof String) {

            return sun.misc.Hashing.stringHash32((String) k);

        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by

        // constant multiples at each bit position have a bounded

        // number of collisions (approximately 8 at default load factor).

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

    }

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 static int indexFor(int h, int length) {

        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";

        return h & (length-1);

    }

Note: So after this, if the key is already present in the HashMap put() method will override the old value and return the old value.If the key is not present then put() method will returns null.

Depending on the hashcode key-value pair will be stored in the different bucket.

Now it is possible that two objects can have the same hashcode and bucket will remain same,  so in that case linked list is formed at the bucket location and the new entry is stored as next node.This will happen whenever entry with the same hashcode of the key will be inserted in HashMap.

Let's check this with an example.

package com.javainstance;

import java.util.HashMap;

public class JavaBasics {

public static void main(String[] args) {

HashMap<String, Integer> hashMap = new HashMap<>();

hashMap.put("car", 8);

hashMap.put("chr5", 9);

}

}

If we debug above lines of code then we can find that both the values are stored at same index 0.But if go inside index 0 we can see that entry with value 8 is moved to next variable of the second entry and both are in the same bucket.This is how HashMap manages entries with the same hashcode of the key.

When Get method is called.

When get () method is called with the key as a parameter then it internally calls getEntry() method in which hash function is called to get the hash value and find the bucket location and return the value.

    public V get(Object key) {

        if (key == null)

            return getForNullKey();

        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();

    }

    final Entry<K,V> getEntry(Object key) {

        if (size == 0) {

            return null;

        }

        int hash = (key == null) ? 0 : hash(key);

        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 != null && key.equals(k))))

                return e;

        }

        return null;

    }

What if two keys have the same hashcode i.e. both are in the same bucket?

Here equals() method comes into the picture.As highlighted in the above lines if more than one key have the same hashcode then key.equals(k) until it returns true to get the entry.

How to iterate or loop a HashMap?

Give your suggestion in comments.

If you like the post Share with your friends on social network.

Follow us: www.facebook.com/javainstance