LinkedHashMap Implementation in Java

LinkedHashMap is one of the commonly used Map implementations in Java. LinkedHashMap inherits from HashMap and implements Map interface. The basic building block is same as that of HashMap. It will be appropriate to cover HashMap internals before delving into details of LinkedHashMap. I have already discussed HashMap internals here.  This post talks about the delta or extras which LinkedHashMap adds on top of HashMap.

Building Blocks

LinkedHashMap uses the same array structure as used byHashMap. This means that it stores data in the array of Entry objects. Let's cover major aspects of LinkedHashMap.

Entry: HashMap stores objects in random order. Even in LinkedHashMap objects are put in the same way; but with some extra overheads, all these objects are interconnected to maintain a particular order. Let's see how Entry object differs here with respect to HashMap Entry.

   static class Entry<K,V> extends HashMap.Entry<K,V>{

         Entry<K,V> before, after;  

         Entry(int hash, K key, V value, HashMap.Entry<K,V) next){

             super(hash,key,value,next);

         }

   } 

LinkedHashMap's Entry class adds two extra pointers before and after to form a doubly linked list. HashMap.Entry is defined in HashMap internals post.

Header: Stores the head of the doubly linked list. Notice the way it is getting initialized/constructed at below snippet. This means that header is both start as well as end of the doubly linked list. 

       Entry<K,V> header;
       //construction or initialization
       header = new Entry<>(-1, null, null, null);
       header.before = header.after = header;

AccessOrder: This defines the order in which you can iterate a LinkedHashMap. It supports access-order as well as insertion-order. Default constructor supports insertion order (as shown below).
         
        boolean accessOrder;

        public LinkedHashMap(){
             super();
             accessOrder = false;
        } 

Other aspects like size, load factor, capacity, threshold etc remain unchanged.

Introspection

Let's do similar exercise as done in HashMap post, to store fruits inside LinkedHashMap and introspect internal details.  

 import java.lang.reflect.Field;  
 import java.lang.reflect.InvocationTargetException;  
 import java.lang.reflect.Method;  
 import java.util.LinkedHashMap;  
 import java.util.Map;  
   
 public class LinkedHashMapSimul {  
      static Map<String, Integer> map;  
   
      // Actual Method from HashMap library  
      static int indexFor(int h, int length) {  
           return h & (length - 1);  
      }  
   
      // Actual Method from HashMap library  
      static int hash(int h) {  
           h ^= (h >>> 20) ^ (h >>> 12);  
           return h ^ (h >>> 7) ^ (h >>> 4);  
      }  
   
      public static void interrospect() {  
           try {  
                Class<?> c = map.getClass();  
                c = c.getSuperclass();  
                Field f = c.getDeclaredField("size");  
                f.setAccessible(true);  
                int size = f.getInt(map);  
   
                f = c.getDeclaredField("loadFactor");  
                f.setAccessible(true);  
                float loadFactor = f.getFloat(map);  
   
                f = c.getDeclaredField("threshold");  
                f.setAccessible(true);  
                int threshold = f.getInt(map);  
   
                f = c.getDeclaredField("modCount");  
                f.setAccessible(true);  
                int modCount = f.getInt(map);  
   
                Method m = c.getDeclaredMethod("capacity", null);  
                m.setAccessible(true);  
                int capacity = (Integer) m.invoke(map, null);  
   
                System.out.println("Size: " + size + "; LoadFactor: " + loadFactor  
                      + "; Threashold: " + threshold + "; ModCount: " + modCount  
                      + " ; capacity :" + capacity);  
           } catch (SecurityException e) {  
                e.printStackTrace();  
           } catch (NoSuchFieldException e) {  
                e.printStackTrace();  
           } catch (IllegalArgumentException e) {  
                e.printStackTrace();  
           } catch (IllegalAccessException e) {  
                e.printStackTrace();  
           } catch (NoSuchMethodException e) {  
                e.printStackTrace();  
           } catch (InvocationTargetException e) {  
                e.printStackTrace();  
           }  
      }  
   
      public static void main(String[] args) {  
           map = new LinkedHashMap<String, Integer>();  
   
           map.put("guava", indexFor(hash("guava".hashCode()), 16));  
           map.put("mango", indexFor(hash("mango".hashCode()), 16));  
           map.put("pear", indexFor(hash("pear".hashCode()), 16));  
           map.put("banana", indexFor(hash("banana".hashCode()), 16));  
   
           System.out.println(" Map :" + map);  
           interrospect();  
      }  
 } 

Output

 Map :{guava=5, mango=9, pear=15, banana=1}

Size: 4; LoadFactor: 0.75; Threashold: 12; ModCount: 4 ; capacity :16

So the output confirms that the iteration order is the same as insertion. Above class creates default LinkedHashMap; which means initial capacity is 16, the load factor is 0.75 and accessOrder is false. Below diagram shows the mapping of the above items in the Entry array. Note that linked list begins from the header and ends at the header. Also due to this, iteration is more efficient in LinkedHashMap (compared to HashMap). Iteration in LinkedHashMap requires time proportional to the size of the map regardless of its capacity.

Related Post : HashMap Implementation in Java

 TreeMap implementation in Java