How LinkedHashMap works?

In this post, I will explain working of LinkedHashMap, that is how LinkedHashMap works internally.

LinkedHashMap explained:

HashMap does not maintains insertion order, hence does not maintains any doubly linked list.

Most salient feature of LinkedHashMap is that it maintains insertion order of key-value pairs. LinkedHashMap uses doubly Linked List for doing so.

Entry of LinkedHashMap looks like this-

static class Entry<K,V>{

     K key;
     
     V value;

     Entry<K,V> next;
     Entry<K,V> before, after;       // For maintaining insertion order

     public Entry(K key, V value, Entry<K,V> next){

           this.key = key;
           this.value = value;
           this.next = next;


     }


}

By using before and after - we keep track of newly added entry in LinkedHashMap, which helps us in maintaining insertion order.

‘Before’ refers to previous entry and ‘after’ refers to next entry in LinkedHashMap.

Explanation:

Putting 5 key-value pairs in LinkedHashMap:

Initially, we have bucket of capacity = 4. All indexes of bucket are pointing to null. i.e. 0,1,2,3 are pointing to null.

Lets put 1st key-value pair in LinkedHashMap:

Key =  21, value = 12.

New Entry object will be formed like this:

We will calculate hash by using our hash(Key k) method. In this case , it returns key%capacity = 21%4 = 1.

So, 1 will be the index of bucket on which New Entry object will be stored.

For maintaining insertion order,  we will update Header, it will start pointing to New Entry object.

At completion of this step, our HashMap will  look like this:

Lets put 2nd key-value pair in LinkedHashMap:

Key = 25, value = 121.

New Entry object will be formed like this:

We will calculate hash by using our hash(Key k) method. In this case , it returns key%capacity = 25%4 = 1.

So, 1 will be the index of bucket on which New Entry object will be stored.

We'll go to 1st index , it contains entry with key = 21, we will compare two keys (i.e. compare 21 with 25 by using equals() method), as two keys are different  we check whether entry with key=21's next is null or not. If next is null, we will put our new entry object on next.

Additionally, for maintaining insertion order, update header.after. It will start pointing to new Entry object (i.e.make Entry with key=21's after point to New Entry object.) and also make new Entry object's before point to header.

At the completion of this step, our HashMap will look like this:

Let's put 3rd key-value pair in LinkedHashMap.
Key = 30, value = 151

hash will be 30%4 = 2;

Our LinkedHashMap will look like this now:

Our 4th key - value for LinkedHashMap is:
Key = 33, value = 15.

And our LinkedHashMap now will be:

Let's put 5th Key-value pair:

Key =  35, value = 89.

Repeat above mentioned steps:

I hope, this explanation has left no doubt on LinkedHashMap.

Please hit 'Like' on this page.

Thanks.