Understanding LinkedHashMap Order and LRU Cache Implementation in Java

The Java Map family includes many implementations; HashMap and ConcurrentHashMap are most common, while LinkedHashMap is less used but provides a predictable order—either insertion order or access order.

To achieve insertion order, LinkedHashMap adds a doubly linked list where each node corresponds to a bucket in the hash table, allowing iteration in the order elements were added at the cost of extra memory.

For access order, the same linked list is used but each read operation moves the accessed entry to the tail, enabling the structure to serve as a basis for an LRU (Least Recently Used) cache.

Example usage:

LinkedHashMap
map = new LinkedHashMap<>(16, 0.75f, true);
for (int i = 0; i < 10; i++) {
    map.put(i, i);
}
for (Map.Entry entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}
map.get(3);
System.out.println();
for (Map.Entry entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

The printed result shows the initial insertion order, then after accessing key 3 the entry moves to the end, demonstrating access‑order behavior.

The constructor’s third boolean parameter accessOrder determines whether the map maintains insertion order (false) or access order (true).

Looking at the source, LinkedHashMap maintains two transient fields:

transient LinkedHashMap.Entry<K,V> head; // oldest entry
transient LinkedHashMap.Entry<K,V> tail; // most recent entry

Each entry is a subclass of HashMap.Node that adds before and after links:

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);
    }
}

When a new node is created, newNode links it at the tail:

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

The get method checks accessOrder and, if true, calls afterNodeAccess to move the accessed node to the tail:

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;
}

void afterNodeAccess(Node<K,V> e) {
    // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>) e, b = p.before, a = p.after;
        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;
    }
}

After each insertion, afterNodeInsertion may remove the eldest entry when eviction is required:

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

A typical removeEldestEntry implementation returns true when the map size exceeds a predefined capacity, enabling automatic removal of the least‑recently‑used entry:

public boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return size() > capacity;
}

LinkedHashMap also overrides methods such as containsValue to iterate the linked list directly, providing a space‑for‑time trade‑off that speeds up value‑lookup operations.

In summary, LinkedHashMap maintains a doubly linked list to support insertion‑order or access‑order iteration; setting accessOrder to true enables LRU‑style caching when removeEldestEntry is overridden to define the eviction policy.