How LinkedHashMap Works Internally in Java

Please go through how HashMap works internally in java first before reading further about the internal working of  LinkedHashMap.

Interviewer : What is LinkedHashMap ?

LinkedHashMap is the Hashtable (synchronized HashMap) and linkedlist implementation of the Map interface , with predictable iteration order.

Read Also : HashSet Interview questions

Interviewer :Why do we need LinkedHashMap when we already had TreeMap and HashMap ?

TreeMap and HashMap classes were added in java 1.2 , while LinkedHashMap was added to jdk in java version 1.4  .
HashMap provides constant time performance for basic operations like (add, remove and contains) method but elements are unordered.  In TreeMap elements are naturally sorted but there is increased cost associated with it. Performance of the basic operations (get, remove or put)  in TreeMap is slower in comparison i.e log(n) time.
So, LinkedHashMap addition removes the chaotic ordering provided by HashMap, without incurring the increased cost associated with TreeMap.


Internal Working of LinkedHashMap in Java 


According to Oracle docs ,

LinkedHashMap implementation differs from HashMap in that it maintains a doubly linked list running through all of its entries.

We have already shared  the internal working of HashMap . HashMap maintains a simple linked list while running through all of its entries.


Interviewer : How LinkedHashMap insertion order is maintained ?

The order is maintained based on the keys were inserted into the map .

Interviewer : What happens if we insert a key which is already present in the LinkedHashMap ? Does the order change ?

Insertion order of the LinkedHashMap does not get affected if a key is re-inserted into the LinkedHashMap object.
It first checks containsKey() method  before invoking put() method . If containsKey(K) returns true then the key is not added to the LinkedHashMap.

Interviewer : What is the time complexity of the add , remove and contains operations in LinkedHashMap ?

Time complexity of the add, remove and contains operations is constant time i.e O(1) .







Interviewer : Does LinkedHashMap Iterator behaves  like fail fast iterator or fail-safe iterator ?

LinkedHashMap iterator behaves like fail-fast iterator. As expected it will  throw ConcurrentModificationException. We have already shared fail safe and fail fast iterator explanation.

Interviewer : Can you write an simple example which proves that LinkedHashMap behaves like fail fast iterator ?
LinkedHashMap Example :

import java.util.LinkedHashMap;
import java.util.Iterator;


public class LinkedHashMapExample
{
    
    
    public static void main(String[] args)
    {
        LinkedHashMap<String,String> premiumPhone = new LinkedHashMap<String,String>();
        premiumPhone.put("Apple", "iPhone6");
        premiumPhone.put("HTC", "HTC one");
        premiumPhone.put("Samsung","S6");
        
        Iterator iterator = premiumPhone.keySet().iterator();
        
        while (iterator.hasNext())
        {
            System.out.println(premiumPhone.get(iterator.next()));
            premiumPhone.put("Sony", "Xperia Z");
        }
        
    }
    
}

Output :

iPhone 

Exception in thread "main" java.util.ConcurrentModificationException
        at java.util.HashMap$HashIterator.nextEntry(Unknown Source)
        at java.util.HashMap$KeyIterator.next(Unknown Source)
        at LinkedHashMapExample.main(LinkedHashMapExample.java:20)

Please do mention in the comments in case you have any questions  regarding LinkedHashMap .