How LinkedHashMap works internally - Internal implementation of LinkedHashMap

LinkedHashMap is one of the concrete implementation of Map (an associative array data structure).The main agenda of this post is to discuss internal structure of class LinkedHashMap and its internal working.Before going into delve of internal working of LinkedHashMap one should understand internal working of HashMap which  is discussed here.

In layman terminology LinkedHashmap is combination of both LinkedList and HashMap.In other words, LiknedHashMap maintain a linkedList of elements in order of being inserted or being accessed along with storing elements(key and value) in HashMap.

Internal building blocks of LinkedHashMap is similar to HashMap with extra overhead for maintaining a linkedList(or interconnecting all elements in a perticular order). LinkedHashMap uses an array of Entry objects (Entry[] table) to store elements and maintain two referenes(Entry<K,V> before, after;) to form a doubly linkedList. Please note HashMap also uses Entry objects to store key/value then what makes LinkedHashMap Entry class different.We will walk through the sample code from java.util.LinkedHashMap to find differences:

 static class Entry extends HashMap.Entry{
  Entry before, after;  
  Entry(int hash, K key, V value, HashMap.Entry next){
   super(hash,key,value,next);
  }
 }

As we can see the visible difference, above Entry class extends HashMap Entry class and add two references for interconnecting elements to be added in map via put method. super(hash,key,value,next) is used to instantiate HashMap entry objects. HashMap Entry object looks like this :

 static class Entry{
        final K key;
        V value;
        Entry next;
        final int hash;
  } 

We have now fair idea how Entry object is created and stored in Entry[] table.Now question arises how does linkedList is maintained using before and after references ?

For maintaining a doubly linkedList, LinkedHashMap uses a reference head of Entry type and initializes it before any entries are inserted into the map.

  private transient Entry header;
  //Called by superclass constructors and pseudoconstructors before
 //any entries are inserted into the map.Initializes the chain.
 void init() {
        header = new Entry(-1, null, null, null);
        header.before = header.after = header;
  }

When we do put operation, call is redirected to a method called addEntry and it add elemets at end of the linkedlist and maintains references before/after.Similarly, on remove of an element referenes are reset and pointed to correct Entry object.

One important point that need special mention is that, by default LinkedHashMap maintains linkedList in insertion order or Linkedlist is iterated in same order how elements were inserted. However, it can be changed by using appropriate constructor. The iteration ordering is controlled by accessOrder(a boolean field maintained by LinkedHashMap).
for access-order    ----> accessOrder = true
for insertion-order-----> accessOrder =false
We have two constructor below: first constructor is default one and it supports insertion order. However second constructor uses a argument value for setting accessOrder.(Same shown below)

  private final boolean accessOrder;
 //First default constructor 
 public LinkedHashMap(){
             super();
             accessOrder = false;
        }
 //second constructor :
 public LinkedHashMap(int initialCapacity,
   float loadFactor, boolean accessOrder) {
 super(initialCapacity, loadFactor);
 this.accessOrder = accessOrder;
}

Consider we have created a LinkedHashMap by using default constructor and inserted 4 elements[(1,"Nikhil"),(2,"ranjan"),(3,"Oracle"),(4,"java")]. Following diagram depicts how it will be stored internally :(Assuming index is calculated and it comes out as 5 for key 1, 9 for key 2, and so on)

When first element <1,"Nikhil"> is inserted, it is stored in index position 5 and  head's after start pointing to Nikhil and Nikhil before pointing to head. After that when <2, "Ranjan">  is added  Nikhil's after pointing to Ranjan. similarly all elements are added and  before/after is updated accordingly.
This is all about LinkedHashMap and it's detailed code can be found here.
======================End of article==========================

References :
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b27/java/util/LinkedHashMap.java