LinkedHashMap in Java: How It Works and LRU Cache

Here is a bug that surprises even experienced developers. Create Map<String, Integer> m = new LinkedHashMap<>(16, 0.75f, true);, add three entries and run an ordinary loop: for (String k : m.keySet()) System.out.println(k + "=" + m.get(k));. The program prints the first pair and then crashes with ConcurrentModificationException: in access-order mode, even get() rearranges the map. This lesson explains why, and how the same behavior gives you an LRU cache in about ten lines.

LinkedHashMap (linked hash map) is an implementation of the Map interface from java.util that extends HashMap and additionally links all entries into a doubly linked list. Thanks to that list, a LinkedHashMap iterates over its entries in a predictable order: insertion order by default, or access order (least recently accessed first) when created with accessOrder = true. get() and put() stay O(1) on average, just like in a HashMap.

How LinkedHashMap works internally

A LinkedHashMap works like a regular HashMap hash table, but every entry also stores two references, before and after, to its neighbors in a doubly linked list, and the map remembers the list's head and tail. Key lookups go through the hash table, while iteration walks the list, which is why the order is predictable.

The internal entry class looks like this (simplified from the JDK source):

static class Entry<K, V> extends HashMap.Node<K, V> {
    Entry<K, V> before, after;   // neighbors in the doubly linked list
    // hash, key, value, next are inherited from HashMap.Node
}

transient LinkedHashMap.Entry<K, V> head;  // the eldest entry
transient LinkedHashMap.Entry<K, V> tail;  // the youngest entry
final boolean accessOrder;                  // false - insertion order, true - access order

When a new key is inserted, its entry goes both into a bucket of the hash table and to the end of the list. When it is removed, it is unlinked from both. How the hash table picks a bucket, and what collisions and resizing are, is covered in HashMap internals in Java — LinkedHashMap inherits all of that unchanged.

Example: insertion order is preserved, a repeated put() of an existing key changes only the value, and a key that was removed and put back goes to the end.

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, Double> salaries = new LinkedHashMap<>();

        salaries.put("Smith", 123.22);
        salaries.put("Jones", 1378.00);
        salaries.put("Brown", 3434.34);
        salaries.forEach((key, value) -> System.out.println(key + ": " + value));

        salaries.put("Smith", 200.0);      // existing key: the value changes, the position does not
        System.out.println(salaries);

        salaries.remove("Jones");
        salaries.put("Jones", 1500.0);     // removed and re-added: goes to the end
        System.out.println(salaries);
    }
}

Output:

Smith: 123.22
Jones: 1378.0
Brown: 3434.34
{Smith=200.0, Jones=1378.0, Brown=3434.34}
{Smith=200.0, Brown=3434.34, Jones=1500.0}

The price of the list is memory: two extra references per entry, plus slightly slower put() and remove(), because the links have to be maintained. LinkedHashSet uses the same trick — it is backed by a LinkedHashMap (see LinkedHashSet in Java).

Iteration order: HashMap vs LinkedHashMap vs TreeMap

The three main Map implementations give different answers to the question “in what order will I get the entries back?”: HashMap guarantees no order, LinkedHashMap returns entries in insertion (or access) order, and TreeMap sorts them by key. This is the property to choose by.

import java.util.*;

public class OrderCompare {
    public static void main(String[] args) {
        Map<Integer, String> hash = new HashMap<>();
        Map<Integer, String> linked = new LinkedHashMap<>();
        Map<Integer, String> tree = new TreeMap<>();

        for (Map<Integer, String> m : List.of(hash, linked, tree)) {
            m.put(30, "a");
            m.put(5, "b");
            m.put(17, "c");
        }
        System.out.println("HashMap:       " + hash);
        System.out.println("LinkedHashMap: " + linked);
        System.out.println("TreeMap:       " + tree);
    }
}

Output:

HashMap:       {17=c, 5=b, 30=a}
LinkedHashMap: {30=a, 5=b, 17=c}
TreeMap:       {5=b, 17=c, 30=a}

The HashMap order here comes from bucket indexes (17 → 1, 5 → 5, 30 → 14 with a capacity of 16). That is an implementation detail of current JDKs, not a guarantee: after a resize or on another version it may change.

Keeping insertion order is not the same as sorting (see Ordered vs sorted collections in Java). If you need sorted keys, that is a job for TreeMap: see TreeMap, SortedMap and NavigableMap. The remaining implementations (Hashtable, ConcurrentHashMap, EnumMap, IdentityHashMap and others) are compared in Map Interface in Java.

LinkedHashMap constructors

LinkedHashMap has five constructors and, since Java 19, the static factory newLinkedHashMap(int). Four constructors mirror those of HashMap; the fifth takes an accessOrder flag, and it is the only way to switch on the access order needed for an LRU cache.

The copy constructor is handy for “freezing” the current order of any map: new LinkedHashMap<>(treeMap) keeps the sorted order of the TreeMap, but later insertions go to the end, without sorting.

Access order: accessOrder = true

In access-order mode (accessOrder = true), a LinkedHashMap moves an entry to the end of the list every time an existing key is accessed. The entry that has gone unused the longest stays at the head — exactly the one an LRU (Least Recently Used) cache evicts.

Map<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
System.out.println(map);   // {a=1, b=2, c=3}

map.get("a");              // access: "a" moves to the end
System.out.println(map);   // {b=2, c=3, a=1}

map.containsKey("b");      // NOT an access: order unchanged
System.out.println(map);   // {b=2, c=3, a=1}

map.put("b", 20);          // put on an existing key is an access too
System.out.println(map);   // {c=3, a=1, b=20}

Which operations count as an “access” is defined in the class Javadoc:

removeEldestEntry() and an LRU cache

An LRU cache on top of LinkedHashMap takes about ten lines: create the map with accessOrder = true and override the protected removeEldestEntry() method so that it returns true once the size exceeds the limit. After every insertion of a new key, the map then removes the least recently used entry on its own.

The method signature:

protected boolean removeEldestEntry(Map.Entry<K, V> eldest)

It is called by put(), putAll(), putIfAbsent(), computeIfAbsent(), compute() and merge() — but only when a new key has been added. The eldest parameter is the head of the list. In LinkedHashMap itself the method always returns false, so nothing is ever removed.

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LruCache(int capacity) {
        super(16, 0.75f, true);          // true - access order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;        // over the limit - drop the eldest entry
    }

    public static void main(String[] args) {
        LruCache<Integer, String> cache = new LruCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        System.out.println(cache);

        cache.get(1);                    // 1 becomes the most recently used
        cache.put(4, "four");            // evicts 2 - it has gone unused the longest
        System.out.println(cache);

        cache.put(3, "THREE");           // existing key: update + access, no eviction
        System.out.println(cache);

        cache.put(5, "five");            // evicts 1
        System.out.println(cache);
        System.out.println(cache.get(2)); // 2 is already gone
    }
}

Output:

{1=one, 2=two, 3=three}
{3=three, 1=one, 4=four}
{1=one, 4=four, 3=THREE}
{4=four, 3=THREE, 5=five}
null

Create the same map without the flag (super(16, 0.75f, false) or just super()) and you get a FIFO cache instead: it evicts the entry that was added first, not the one used least recently, and get() has no effect on the order.

Limitations of this cache

• Not thread-safe. For shared use, wrap it: Map<K, V> safe = Collections.synchronizedMap(new LruCache<>(100));. Reads need synchronization too, because get() changes the order. Iteration over the wrapper still has to be enclosed in synchronized (safe) { ... }.
• The limit counts entries, not bytes, and there is no time-to-live (TTL). For high-load caches with TTL, statistics and concurrent access, use the Caffeine library.
• Inheritance exposes the whole LinkedHashMap API. If that is undesirable, keep the map in a private field of your cache class and expose only get()/put().

An overview of thread-safe collections (ConcurrentHashMap, ConcurrentSkipListMap and others) is in Thread-safe collections in Java.

LinkedHashMap and SequencedMap (Java 21)

Since Java 21 (JEP 431), LinkedHashMap implements the SequencedMap interface, which gives it methods for working with both ends: firstEntry(), lastEntry(), pollFirstEntry(), pollLastEntry(), putFirst(), putLast() and reversed(). Before Java 21, the only way to get the last entry was to iterate over the whole map.

import java.util.LinkedHashMap;

public class SequencedMapExample {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> steps = new LinkedHashMap<>();
        steps.put("build", 1);
        steps.put("test", 2);
        steps.put("deploy", 3);

        System.out.println(steps.firstEntry());      // build=1
        System.out.println(steps.lastEntry());       // deploy=3

        steps.putFirst("checkout", 0);
        System.out.println(steps);                   // {checkout=0, build=1, test=2, deploy=3}

        steps.putLast("build", 1);                   // existing key moves to the end
        System.out.println(steps);                   // {checkout=0, test=2, deploy=3, build=1}

        System.out.println(steps.reversed());        // {build=1, deploy=3, test=2, checkout=0}
        System.out.println(steps.pollFirstEntry());  // checkout=0
        System.out.println(steps);                   // {test=2, deploy=3, build=1}
    }
}

Where developers get tripped up

The most common LinkedHashMap mistake is calling get() inside a loop over a map created with accessOrder = true: it is a structural modification, so the iterator throws ConcurrentModificationException. Other slips come from expecting sorting and from misunderstanding when removeEldestEntry() fires.

What does this code print?

Map<String, Integer> m = new LinkedHashMap<>(16, 0.75f, true);
m.put("a", 1);
m.put("b", 2);
m.put("c", 3);

for (String k : m.keySet()) {
    System.out.println(k + "=" + m.get(k));
}

a=1
Exception in thread "main" java.util.ConcurrentModificationException

m.get("a") moves “a” to the end and increments modCount; on the next step the iterator detects the change and throws. The fix is to iterate over entrySet(): the value is read from the entry itself, and the order does not change.

for (Map.Entry<String, Integer> e : m.entrySet()) {
    System.out.println(e.getKey() + "=" + e.getValue());
}
// Output:
// a=1
// b=2
// c=3

How iterators detect concurrent changes is explained in Iterator in Java. Other common mistakes:

• Expecting sorted keys. LinkedHashMap only remembers insertion order; keys 30, 5, 17 stay in exactly that order. For sorting you need a TreeMap.
• Using a constructor without the flag and then wondering why the “LRU” cache evicts hot keys. Without accessOrder = true you get FIFO.
• Expecting eviction on update. put() on an existing key adds no new entry, so removeEldestEntry() is not called and the size does not grow.
• Comparing maps with order in mind. Map.equals() ignores order: a LinkedHashMap {a=1, b=2} equals a LinkedHashMap {b=2, a=1}, and even a HashMap with the same pairs.