LinkedHashMap

1. What It Is

• Implemented using a doubly linked list + HashMap (array + linked list + red-black tree).
• Compared with HashMap, it preserves order.
  • The iteration output order can be:
    • insertion order;
    • access order (LRU).

2. Usage

• Output in insertion order:

public class LinkedHashMapTest
{
    public static void main(String[] args)
    {
        LinkedHashMap<String,Object> map = new LinkedHashMap<>();
        map.put("name","zsk");
        map.put("age",24);
        map.put("height", 172L);

        Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
        while (iterator.hasNext())
        {
            Map.Entry<String, Object> entry = iterator.next();
            /* The output order is the insertion order:
            *   name=zsk
                age=24
                height=172
            * */
            System.out.println(entry);
        }
        // The output above is the same as this one

        for (Map.Entry<String, Object> entry : map.entrySet())
        {
            /* The output order is the insertion order:
            *   name=zsk
                age=24
                height=172
            * */
            System.out.println(entry);
        }

        System.out.println(map.containsKey("name"));//true
        System.out.println(map.get("name"));//zsk
        map.remove("name");
        System.out.println(map.containsKey("name"));//false
    }
}

• Output in access order:

public class LinkedHashMapTest
{
    public static void main(String[] args)
    {
        LinkedHashMap<String, Object> map = new LinkedHashMap<>(2, 0.75F, true);
        map.put("1", "a");
        map.put("2", "b");
        map.put("3", "c");


        Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
        while (iterator.hasNext())
        {
            Map.Entry<String, Object> entry = iterator.next();
            //            1=a
            //            2=b
            //            3=c
            System.out.println(entry);
        }
        // The output above is the same as this one

        for (Map.Entry<String, Object> entry : map.entrySet())
        {
            //            1=a
            //            2=b
            //            3=c
            System.out.println(entry);
        }

        System.out.println(map.get("1"));// Access 1, so the node containing 1 is moved to the end of the list
        for (Map.Entry<String, Object> entry : map.entrySet())
        {
            // The most recently accessed node is moved to the end of the list
            //            2=b
            //            3=c
            //            1=a
            System.out.println(entry);
        }
    }
}

3. Implementation

3.1. UML

It extends HashMap and is cloneable and serializable.

3.2. Constructor

public class LinkedHashMap<K,V>
    extends HashMap<K,V>// Extends HashMap
    implements Map<K,V>
{
    // Nodes in the linked list. Doubly linked list
     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);
            }
        }


    // Head and tail nodes of the doubly linked list
    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;

    // true means maintain access order; false means maintain insertion order
    final boolean accessOrder;
    public LinkedHashMap() {
        // Call HashMap's constructor
        super();
        accessOrder = false;
    }
}

LinkedHashMap extends HashMap, so methods such as get, set, and remove call HashMap methods. LinkedHashMap also enhances HashMap’s Node, defines its own Entry, and adds a doubly linked list.

3.3. put

It essentially calls HashMap’s put method to insert a new node or replace a value, with some additional operations.

• HashMap.put

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // LinkedHashMap overrides newNode
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // The node already exists; only update value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // Need to maintain the order in the doubly linked list
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    // When removeEldestEntry returns true, delete the head node [least recently accessed node]
    afterNodeInsertion(evict);
    return null;
}

Pay attention to the following points:

• Line 12: LinkedHashMap overrides newNode.
• Lines 35-42: after updating a value, the order in the doubly linked list must be maintained.
• Line 48: whether inserting a new node or updating a value, it may be necessary to delete the head node according to the situation (whether removeEldestEntry returns true).

3.3.1. Create LinkedHashMap’s Enhanced Node — Entry [Both a Node-Array Node and a Doubly Linked List Node]

• LinkedHashMap.newNode

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // Create LinkedHashMap's enhanced Entry
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // Insert it at the end of the linked list
    linkNodeLast(p);
    return p;
}

3.3.1.1. Insert the Node at the End of the Doubly Linked List When It Is Created

• linkNodeLast

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // Insert the current node at the end of the linked list
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

3.3.2. For a Node Updated by put (Not Newly Inserted, Only value Updated), Maintain the Doubly Linked List Order [Output Order]

// The node already exists; only update value
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        // Need to maintain the order in the doubly linked list
        afterNodeAccess(e);
        return oldValue;
    }

3.3.2.1. Move This Node to the End of the Doubly Linked List

• afterNodeAccess

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // Access order is enabled and the current node is not the tail [that is, it is not a newly inserted node]
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // The following operations move the current node to the end of the doubly linked list
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

3.3.3. After put (Whether Newly Inserted or value Updated), Determine Whether to Delete the Head Node [Least Recently Accessed Node]

• afterNodeInsertion

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // When removeEldestEntry returns true
    // [for example, in an LRU algorithm, delete the least recently accessed node after capacity is exceeded]
    if (evict && (first = head) != null && removeEldestEntry(first)) {
       // Delete the head node
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

3.4. get

It essentially calls HashMap’s getNode to obtain the node and then calls LinkedHashMap’s afterNodeAccess to place the currently accessed node at the end of the linked list.

• LinkedHashMap.get

public V get(Object key) {
    Node<K,V> e;
    // Call HashMap.getNode to obtain the node
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // If access order is enabled
    if (accessOrder)
        afterNodeAccess(e);

    return e.value;
}

• Lines 7-8: if access order is enabled, call LinkedHashMap’s afterNodeAccess to move the currently accessed node to the end of the doubly linked list (the newest node).

3.4.1. After get, Maintain the Doubly Linked List Order [Output Order]

// If access order is enabled
if (accessOrder)
    afterNodeAccess(e);

3.4.1.1. Move the Currently Accessed Node to the End of the Linked List

• LinkedHashMap.afterNodeAccess

Just like the put operation, move the currently accessed node to the end of the linked list.

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        // p is the current node, a is the next node, b is the previous node
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // The previous node's next points to the next node
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;

        // The next node's prev points to the previous node
        if (a != null)
            a.before = b;
        else
            last = b;

        // The current node's prev points to the tail, and the tail's next points to the current node
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        // Update the tail to the current node
        tail = p;
        ++modCount;
    }
}

3.5. containsKey

It simply calls HashMap’s containsKey.

public boolean containsKey(Object key) {
    // Still HashMap.getNode; nothing special here
    return getNode(hash(key), key) != null;
}

3.6. containsValue

It overrides HashMap’s method and is more efficient.

public boolean containsValue(Object value) {
    // Traverse the doubly linked list, O(N), unlike HashMap's O(N2)
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

3.7. remove

It essentially calls HashMap’s remove to delete the node, and then calls LinkedHashMap’s afterNodeRemoval to remove the current node from the doubly linked list.

• HashMap.remove

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            // After deleting the node, maintain the doubly linked list
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

3.7.1. After remove, Delete the Node from the Doubly Linked List

• LinkedHashMap.afterNodeRemoval

void afterNodeRemoval(Node<K,V> e) { // unlink
    // The following operations delete the current node from the doubly linked list
    // p is the current deleted node, b is p's previous node, and a is p's next node
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    // Modify the previous node's next pointer
    if (b == null)
        head = a;
    else
        b.after = a;
    // Modify the next node's prev pointer
    if (a == null)
        tail = b;
    else
        a.before = b;
}

3.8. entrySet

3.8.1. Code to Study

Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();

• LinkedHashMap.entrySet

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    // When is this entrySet field set?
    // Return LinkedEntrySet
    return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}

Calling map.entrySet() returns LinkedEntrySet, as follows.

3.8.2. LinkedHashMap.entrySet() Returns LinkedEntrySet

• LinkedEntrySet

final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    public final Iterator<Map.Entry<K,V>> iterator() {
        // The iterator is LinkedEntryIterator
        return new LinkedEntryIterator();
    }
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED |
                                        Spliterator.DISTINCT);
    }
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

Then calling LinkedEntrySet.iterator returns LinkedEntryIterator.

3.8.3. LinkedHashMap.entrySet().iterator() Returns LinkedEntryIterator

final class LinkedEntryIterator extends LinkedHashIterator// Extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        // Override next and call LinkedHashIterator.nextNode
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

This LinkedEntryIterator extends LinkedHashIterator, as follows.

3.8.3.1. LinkedEntryIterator Extends LinkedHashIterator

• LinkedHashIterator

 abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;

    LinkedHashIterator() {
        // Start traversal from the head of the linked list
        next = head;
        expectedModCount = modCount;
        current = null;
    }

    public final boolean hasNext() {
        return next != null;
    }

    // next calls this method
    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        // The next node after the current node in the linked list
        current = e;
        next = e.after;
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        // HashMap.removeNode
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

It can be seen that iteration outputs entries from head to tail, meaning older nodes are printed first, then newer nodes.

4. Summary

It is implemented as HashMap + a doubly linked list.

Iterating over LinkedHashMap means looping from the head of the internally maintained doubly linked list.

The order of nodes in the doubly linked list is updated during LinkedHashMap’s get and put operations, so that it can support output by insertion order or by access order.

5. References

• Difference between HashMap, LinkedHashMap and TreeMap - Stack Overflow
• Interview Essential: LinkedHashMap Source Code Analysis (JDK 8) - Juejin