Tech Master Tutorials
Email Facebook Google LinkedIn Pinterest Twitter
Home Java Java 8 Java Interview Questions Java Programming

LinkedHashMap

Before understanding the internals of LinkedhashMap, it is recommended to go through Map : Map Interface and HashMap internals : HashMap Internal

LinkedHashMap is also one of the child classes of the Map interface like HashMap which is used to store key-value pair objects. But unlike HashMap, LinkedHashMap preserves the order of insertion into the internal hash table.
Entry class for LinkedHashMap forms a doubly linked-list with before and after references to the Entries.
Using the before and after pointers we can traverse the entries in the order of insertion.

Internal Implementation details of LinkedHashMap:

Entry for LinkedHashMap class :

Entry for LinkedHashMap class is a subclass of the HashMap.Node class. LinkedHashMap Entry also has the same fields as HashMap Node class (key,value, hashcode and next fields) along with before and after references.

The field – next, maintains the singly linkedlist chaining for a particular hashtable bucket.
The reference fields before and after maintains a doubly linked list for all the entries of the LinkedHashMap. Using before and after fields, we can traverse all the entries of a LinkedHashMap.

In case of traversal, cost is reduced as it does not depend on the total capacity of the LinkedHashMap like in case of HashMap, it depends only on the total number of entries.
We can just start with the head reference field of the LinkedHashMap class and can traverse until the after of the Entry is null(In case of last inserted Entry).

Entry class of LinkedHashMap :

    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);
        }
    }
LinkedHashMap Entry has two additional Entry references – before and after.
Find the other fields below that are inherited from the HashMap.Node class.
HashMap.Node class :
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

TreeNode ( Addition was made as part of the Java 8 updates) :
Usually a HashMap bucket has a LinkedList for key-value pairs. But if the number of entries goes beyond a particular limit that is defined as TREEIFY_THRESHOLD, then LinkedListed is converted into a Binary Tree( a Red-Black binary Tree). Using a binary tree decreases the lookup time for a node.
As in case of linked list lookup time complexity is O(n) but in case of binary tree it will be O(log n).
TreeNode Definition :
    /**
     * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
     * extends Node) so can be used as extension of either regular or
     * linked node.
     */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

Important LinkedHashMap Parameters :

LinkedHashMap’s internal hash table is is created only after the first use. Initially the hash table is null. Table is initialized only when the first intertion call is made for the HashMap instance.

            transient Node<K,V>[] table;

The two parameters that affect the performance of LinkedHashMap are – initial capacity and load factor. Initial capacity is the initial size of the hash table and load factor is is a measure of how full the hash table is allowed to get before its capacity is automatically increased. Using the below LinkedHashMap constructor, initialCapacity and loadFactor can be passed by a programmer.

	public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }


LinkedHashMap constructor internally calls the below HashMap constructor.

	public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

Using the initial capacity and load factor, threshold is calculated. Threshold is the size limit after which table is resized/rehashed. The value of the threshold is (int)(capacity * loadFactor).)

Threshold and loadFactor fields :

    int threshold;
    final float loadFactor;
    

Deafult value for initial capacity is 16 and default load factor is 0.75.

		static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    	static final float DEFAULT_LOAD_FACTOR = 0.75f;
		


Growing the Map bucket :

Using the initial capacity and load factor, threshold is calculated. Threshold is the size limit after which table is resized/rehashed. The value of the threshold is (int)(capacity * loadFactor).)




Adding key-value pair to the map using put method : Adding a key-value pair is same as HashMap, in case of LinkedHash map we are keeping additional details with the help of the before and after references.
Since we add an entry for each key value pair so while adding the entry, updating the before and after references also. A doubly linked-list is formed with the before and after references. Using the before and after pointers we can traverse the entries in the order of insertion.
We can start at the head node ( the first node ) added to the LinkedHashMap and traverse using the after pointer until after is null.





Getting the value from the LinkedHashMap :
We can get the value for a specific key then using get method which accepts a key as parameter. Internally, get method calls getNode() method. getNode method takes the key and the hashcode of the key as parameters and returns the corresponding node. Then from the get method, corresponding value is returned. If node is null or the stored value is null then null is returned.
If node is null or the stored value is null then null is returned.

   public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }



   final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }