Internal Working of LinkedHashMap in Java

Learning collection classes are essential as they are heavily used while creating the real-world Application. There are a few important collection classes that I have already covered (HashMap, ConcurrentHashMap, TreeMap). This article is a continuation of that and we’ll deep dive into what, why, and how of the LinkedHashMap class.

What Is LinkedHashMap?

• LinkedHashMap is Hashtable and linked list implementation of the Map interface, with predictable iteration order.
• This implementation differs from HashMap in that, it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion order).
• Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately before the invocation.)
• This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashMap (and Hashtable), without incurring the increased cost associated with TreeMap.
• It can be used to produce a copy of a map that has the same order as the original, regardless of the original map’s implementation.

LinkedHashMap class that extends HashMap and implements Map.

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

LinkedHashMap is defined in java.util Package.

LinkedHashMap Example:

Let’s create a basic LinkedHashMap and add some items to it and see how it stores them.

1       package com.company;
2	
3	import java.util.Iterator;
4	import java.util.LinkedHashMap;
5	
6	public class Main {
7	    public static void main(String[] args) {
8	        LinkedHashMap<String, String> cityPoints = new LinkedHashMap<>();
9	
10	        cityPoints.put("Pune", "Ganesh Temple");
11	        cityPoints.put("Mumbai", "Gateway Of India");
12	        cityPoints.put("Delhi", "Red fort");
13	
14	        Iterator<String> cities = cityPoints.keySet().iterator();
15	        while (cities.hasNext()) {
16	            String city = cities.next();
17	            System.out.println("City name : " + city);
18	        }
19	    }
20	}

City name : Pune
City name : Mumbai
City name : Delhi

Internal Working of LinkedHashMap:

Internally LinkedHashMap class uses a Doubly Linked list(hold on there is a catch. The below static inner class Entry is extending HashMap.Node class and has two extra pointers (before and after) along with all attributes of Nodeclass from HashMap class (attributes: hash, key, value, next). This entry is nothing but a node in a doubly-linked list and stores the key-value pairs with its before and after pointers.

1	    static class Entry<K,V> extends HashMap.Node<K,V> {
2	        Entry<K,V> before, after;
3	        Entry(int hash, K key, V value, Node<K,V> next) {
4	            super(hash, key, value, next);
5	        }
6	    }

Each node of DLL has two pointers (before and after) and this list also has a head pointer that points to the first node(eldest) of the list. Similarly, it also has a tail pointer that points to the last(youngest) node of the list.

transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;

Node class that is being referred from the HapMap class:

1	
2	    /**
3	     * Basic hash bin node, used for most entries.  (See below for
4	     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
5	     */
6	    static class Node<K,V> implements Map.Entry<K,V> {
7	        final int hash;
8	        final K key;
9	        V value;
10	        Node<K,V> next;
11	
12	        Node(int hash, K key, V value, Node<K,V> next) {
13	            this.hash = hash;
14	            this.key = key;
15	            this.value = value;
16	            this.next = next;
17	        }
18	
19	        public final K getKey()        { return key; }
20	        public final V getValue()      { return value; }
21	        public final String toString() { return key + "=" + value; }
22	
23	        public final int hashCode() {
24	            return Objects.hashCode(key) ^ Objects.hashCode(value);
25	        }
26	
27	        public final V setValue(V newValue) {
28	            V oldValue = value;
29	            value = newValue;
30	            return oldValue;
31	        }
32	
33	        public final boolean equals(Object o) {
34	            if (o == this)
35	                return true;
36	            if (o instanceof Map.Entry) {
37	                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
38	                if (Objects.equals(key, e.getKey()) &&
39	                    Objects.equals(value, e.getValue()))
40	                    return true;
41	            }
42	            return false;
43	        }
44	    }

Now the Catch:

LinkedHashMap works on the principle of hashing and linked lists. As you know in the case of HashMap that can get converted to a tree in special scenarios where all the entries are going into the same bucket and crossing the threshold value. Similarly, LinkedHashMap can also be converted to a tree when all the entries are going to the same bucket.

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

Why Do We Need LinkedHashMap?

It can be used to produce a copy of a map that has the same order as the original, regardless of the original map’s implementation:

void foo(Map m) {
 Map copy = new LinkedHashMap(m);
 …
 }

This technique is particularly useful if a module takes a map on input, copies it, and later returns results whose order is determined by that of the copy. (Clients generally appreciate having things returned in the same order they were presented.)

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.