Java LinkedHashMap

›Short versionOpen if you only have a minute.

LinkedHashMap is a HashMap plus a doubly linked chain. Lookups stay average constant time.
The default chain is insertion order. Putting an existing key replaces the value and does not move the entry.
The third constructor argument, true, switches the chain to access order.
In access order, get and the compute methods move that entry to the most-recent end.
Override removeEldestEntry to drop the front of the chain. With access order, that front is the least recently used.
Keys still follow the equals and hashCode contract. The chain does not change how a key is found.

A is what you construct when a hash map’s speed is right and its undefined order is not. The no-argument constructor gives . The boolean at the end of the other constructor gives .

Those are different chains. Mixing them up is how a cache fails to evict, or a stable dump starts rearranging itself after a get.

What counts as a touch

In access order the map maintains least-recently-accessed to most-recently-accessed. get moves the entry to the end. So do the compute-family methods. A moves it too, because put is an access. Iterating entrySet does not. A read that must not refresh recency has to avoid those access methods, or the cache policy is lying.

The is whatever currently sits at the front. removeEldestEntry runs after an insertion. Return true when the map is over capacity and the front entry goes away. In access order that front entry is the one you have not touched in the longest time, which is the LRU policy people build by hand and then get slightly wrong.

The is unchanged from HashMap. Access order will happily move an entry and still lose it if you mutate the key’s hash fields.

ℹ️ Ready to modify the LinkedHashMap!

Key#0

USA

Value

Key#1

Value

London

Key#2

Japan

Value

Tokyo

An LRU cache on the chain

LruCache.java

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

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

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

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

LruCache<String, Integer> cache = new LruCache<>(2);
cache.put("A", 1);
cache.put("B", 2);
cache.get("A");       // A moves to the most-recent end
cache.put("C", 3);    // eldest B is removed; chain is A, C

The same two puts and a get run on a LinkedHashMap built with the no-argument constructor. After getting A and then putting C, what is the iteration order, and is anyone evicted?

Insertion order stays A, B, then C. get does not move A. The default removeEldestEntry returns false, so nothing is evicted. Eviction and the move-to-end behavior both require the access-order constructor plus an override that returns true when the cache is over capacity.