HashMap: Internal Implementation

How HashMap works internally is the most asked interview question in Java interviews. And the reason is that it is difficult to understand the inner workings of HashMap. In this lesson, we will try to understand every aspect of HashMap.

The basic principle used by a HashMap to store elements is Hashing. Hashing is a way to assign a unique code for any variable or object after applying any formula to its properties. The unique code is called HashCode.

Some of the properties of HashCode are:

1. If two objects are equal, then they should have the same hashcode.
2. If two objects have the same hashcode, then it is not necessary for them to be equal.

Creating a HashMap

We already know that the HashMap stores key-value pairs. HashMap has a nested static class called Node as shown below.

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

This class has a key and a value field. It also has a next field that is used to point to the next Node.

HashMap also has a field called table as shown below. It is basically an array of Node objects that are not yet initialized.

transient Node<K,V>[] table;

When we create a HashMap using the no-arg constructor, then the only thing that happens is that the loadFactor is assigned DEFAULT_LOAD_FACTOR, which is $.75$.

The table array that we discussed above is not initialized at the time of the creation of HashMap.

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

Inserting into a HashMap

When an element is inserted into the Hashmap for the first time, the array table is initialized with size 16. So now there are 16 buckets from index 0 to 15.

If the key that we are inserting is null, then it is inserted at index 0 because the hashcode of null is 0. If the key is not null, then the hash of the key is calculated, and based on the hash value the bucket is decided.

If there is no other element in that bucket, then a new Node is created, and it is inserted in that bucket.