LinkedHashMap in Java: How It Works and LRU Cache - Quiz

LinkedHashMap extends HashMap: key lookups go through the same hash table, but every entry also keeps before and after links to its neighbors in a doubly linked list, and the map remembers the list head and tail. Iteration follows the list, so the order is predictable: insertion order by default, or last-access order with accessOrder = true.

Putting an existing key again only changes the value and keeps its position; after remove() and a new insert, the key goes to the end. get() and put() stay O(1) on average, and iteration depends only on size(), not on the table capacity as in HashMap. The price is two extra references per entry and slightly slower put()/remove(). LinkedHashMap does not sort keys; that is the job of TreeMap.

The flag can only be set with the constructor new LinkedHashMap<>(initialCapacity, loadFactor, true). In this mode every access to an existing key moves its entry to the end of the list, so the head holds the pair that has gone unused the longest.

Access means get() and getOrDefault() (if the key is found), put() and putIfAbsent(), compute*() and merge(), replace() (if the value is actually replaced) and putAll(). It does not include containsKey(), containsValue() or iterating over keySet(), values() and entrySet(), including entry.setValue().

In this mode get() is a structural change: it increments modCount, so calling get() inside a keySet() loop throws ConcurrentModificationException (iterate over entrySet() instead), and in multithreaded code even reads must be synchronized.

Create the map with accessOrder = true and override the protected method removeEldestEntry() so that it returns true once the size exceeds the limit. After a new key is inserted, the map removes the least recently used pair, which is the first entry of the list:

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

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

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

Without the accessOrder flag (plain super()) you get a FIFO cache: the oldest inserted pair is evicted, and get() does not affect the order.

removeEldestEntry(eldest) is called by put(), putAll(), putIfAbsent(), computeIfAbsent(), compute() and merge(), but only when a new key has been added. The eldest parameter is the first entry of the list. By default the method returns false and removes nothing. Updating an existing key adds no new pair, so nothing is evicted.

Limitations of such a cache: it is not thread-safe (wrap it in Collections.synchronizedMap(), and synchronize reads too, because get() changes the order); the limit is a number of entries, not bytes; entries have no time to live (TTL); and inheritance exposes the whole LinkedHashMap API. Heavily loaded caches with TTL and concurrent access use the Caffeine library.

Since Java 21 (JEP 431), LinkedHashMap implements SequencedMap and has methods for both ends of the map: firstEntry() and lastEntry() return the first and last pair without removing them, pollFirstEntry() and pollLastEntry() remove them (all four return null on an empty map), putFirst() and putLast() insert a pair at the start or the end (an existing key moves there), reversed() returns a live reverse-ordered view, and sequencedKeySet(), sequencedValues() and sequencedEntrySet() return ordered views.

Before Java 21 the only way to get the last pair was a full iteration. The methods are declared in SequencedMap, so the variable must be typed as SequencedMap or LinkedHashMap: with the type Map, a call to firstEntry() does not compile.