How LinkedHashMap works in Java

In my previous posts, I explained how HashMap work in Java and TreeMap work in Java. I recommend you to please go through above posts before reading this. All classes HashMap, TreeMap and LinkedHashMap are the different implementations of Map interface.

First lets see the problem with HashMap and TreeMap.

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class MapEx {
 private static void displayMap(Map<String, String> map) {
  Set<String> keys = map.keySet();

  for (String country : keys) {
   System.out.println(country + " : " + map.get(country));
  }
 }

 public static void main(String args[]) {
  Map<String, String> countryHashMap = new HashMap<>();
  Map<String, String> countryTreeMap = new TreeMap<>();

  countryHashMap.put("Malaysia", "Kuala Lumpur");
  countryHashMap.put("Namibia", "Windhoek");
  countryHashMap.put("United States of America", "Washington, D.C.");
  countryHashMap.put("India", "New Delhi");
  countryHashMap.put("Lebanon", "Beirut");

  countryTreeMap.put("Malaysia", "Kuala Lumpur");
  countryTreeMap.put("Namibia", "Windhoek");
  countryTreeMap.put("United States of America", "Washington, D.C.");
  countryTreeMap.put("India", "New Delhi");
  countryTreeMap.put("Lebanon", "Beirut");

  System.out.println("Data in HashMap");
  System.out.println("********************");
  displayMap(countryHashMap);

  System.out.println("\nData in TreeMap");
  System.out.println("********************");
  displayMap(countryTreeMap);
 }
}

Output

Data in HashMap
********************
Lebanon : Beirut
Namibia : Windhoek
United States of America : Washington, D.C.
Malaysia : Kuala Lumpur
India : New Delhi

Data in TreeMap
********************
India : New Delhi
Lebanon : Beirut
Malaysia : Kuala Lumpur
Namibia : Windhoek
United States of America : Washington, D.C.

Observe the output, data in HashMap, TreeMap is not displayed in the order that I inserted. It is because HashMap stores data based on hashCode value of the keys, where as TreeMap store data based on Red-black tree principle. There are situation, where you need to get the data from map in same way you inserted and not affecting the performance. Here LinedHashMap come into picture. LinkedHashMap maintains a double-linked list running through all of its entries. Since LinkedHashMap maintains a double-linked list structure to maintain the order of entries, it is less memory efficient.

Following is the source code of Entry object in LinkedHashMap class. As you observe, Entry instance maintains two extra references after, before. Entry reference ‘before’ points to the previous inserted Entry and reference ‘after’ points to next inserted entry after this.

static class Entry<K, V> extends HashMap.Node<K, V> {
 Entry<K, V> before, after;

 Entry(int hash, K key, V value, Node<K, V> next) {
  super(hash, key, value, next);
 }
}

Lets see how LinkedHashMap stores following information.

Key	Value
1	1
-20	400
332	110224
40	1600

Let us assume HashTable has 5 buckets.

Step 1: Lets insert First <Key, Value> pair (<1, 1>). Assume based on hashCode of key value 1, it is pointed to bucket 2. We should create an entry and let the bucket 2 point to this new entry. This is the first entry, so head pointer points to this node.

Step 2: Lets insert second <Key, Value> pair (<-20, 400>) into LinkedHashMap. Assume as per the hashCode of the key -20, it is also pointed to bucket 2.

‘header.next’ points to new entry Node in the same bucket, 'header.after' points to new Entry object, 'header.before' points to null, since there is no previous entry for header.

'NewEntryNode.before points' to first Entry object and 'NewEntryNode.next', 'NewEntryNode.after' points to null.

Step 3: Lets insert third <Key, Value> entry <332,110224>, Assume as per the hashcode, it is pointed to bucket 4.

The diagram changed like below.

Step 4:  Lets insert third <Key, Value> entry <40,1600>, Assume as per the hashcode, it is pointed to bucket 2. Diagram changed like below.

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class MapDemo {
    private static void displayMap(Map<Integer, Integer> map) {
        Set<Integer> keys = map.keySet();

        for (Integer country : keys) {
            System.out.println(country + " : " + map.get(country));
        }
    }

    public static void main(String args[]) {
        Map<Integer, Integer> countryHashMap = new HashMap<>();
        Map<Integer, Integer> countryTreeMap = new TreeMap<>();
        Map<Integer, Integer> countryLinkedHashMap = new LinkedHashMap<>();

        countryHashMap.put(1, 1);
        countryHashMap.put(-20, 400);
        countryHashMap.put(332, 110224);
        countryHashMap.put(40, 1600);

        countryTreeMap.put(1, 1);
        countryTreeMap.put(-20, 400);
        countryTreeMap.put(332, 110224);
        countryTreeMap.put(40, 1600);

        countryLinkedHashMap.put(1, 1);
        countryLinkedHashMap.put(-20, 400);
        countryLinkedHashMap.put(332, 110224);
        countryLinkedHashMap.put(40, 1600);

        System.out.println("Data in HashMap");
        System.out.println("********************");
        displayMap(countryHashMap);

        System.out.println("\nData in TreeMap");
        System.out.println("********************");
        displayMap(countryTreeMap);

        System.out.println("\nData in LinkedHashMap");
        System.out.println("********************");
        displayMap(countryLinkedHashMap);
    }
}

Output

Data in HashMap
********************
1 : 1
-20 : 400
40 : 1600
332 : 110224

Data in TreeMap
********************
-20 : 400
1 : 1
40 : 1600
332 : 110224

Data in LinkedHashMap
********************
1 : 1
-20 : 400
332 : 110224
40 : 1600

Note that insertion order is not affected if a key is re-inserted into the map.

You may like

Reading and Writing system properties in java

Varargs:Variable number of arguments

How to increase Heap size in java

Command Line Arguments

Java8 Enhancement to interfaces

                                                 Home