LinkedHashMap and LRU caches

the picture

you know how a HashMap prints its keys in a seemingly random order? LinkedHashMap fixes that by keeping a second structure on the side. same entries, same buckets, plus two extra pointers per entry (before and after) that string them together in the order you care about.

think of a cloakroom where coats hang on numbered hooks (the buckets), but there's also a string tied from coat to coat in the order people arrived. to find your coat: hook number. to hand coats back in arrival order: follow the string.

each entry also points back at the one before it (before), so unlinking from the middle is O(1). those backward pointers aren't drawn, to keep the picture readable.

the cost: two more references per entry. a HashMap.Node is 32 bytes (12 header + hash + key, value, next, padded), a LinkedHashMap.Entry is 40. that's the price of order.

insertion order

the default. iteration follows the order keys were first inserted. re-putting an existing key doesn't move it.

void main() {
    var hash = new HashMap<String, Integer>();
    var linked = new LinkedHashMap<String, Integer>();
    for (String k : List.of("pear", "apple", "fig", "banana", "kiwi")) {
        hash.put(k, k.length());
        linked.put(k, k.length());
    }
    linked.put("pear", 0);
    IO.println(hash.keySet());
    IO.println(linked.keySet());
    linked.putFirst("kiwi", 9);
    linked.putLast("apple", 9);
    IO.println(linked);
}

[banana, apple, pear, kiwi, fig]
[pear, apple, fig, banana, kiwi]
{kiwi=9, pear=0, fig=3, banana=6, apple=9}

notice pear stayed first even after put("pear", 0). the last two lines are the java 21 sequenced methods: putFirst and putLast do move an existing key, to the front or the back.

this makes LinkedHashMap the go-to when you want a map that behaves predictably: JSON objects that keep field order, config that prints the way it was written, tests that don't flake on ordering.

access order

pass true as the third constructor argument and the list is reordered on every access: get, getOrDefault, compute, and a put on an existing key all move that entry to the tail. so the head is always the least recently used entry.

new LinkedHashMap<>(16, 0.75f, true);   // capacity, load factor, accessOrder

that's half an LRU cache. the other half is a hook: after every insertion, LinkedHashMap calls removeEldestEntry(head), and if it returns true, the head gets removed. the default returns false. override it:

class Lru<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
 
    Lru(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
 
void main() {
    var cache = new Lru<String, Integer>(3);
    cache.put("a", 1);
    cache.put("b", 2);
    cache.put("c", 3);
    cache.get("a");
    cache.put("d", 4);
    IO.println(cache.keySet());
}

[c, a, d]

get("a") saved a by making it the most recent, so when d pushed the size to 4, b was the eldest and got evicted. play with it:

var cache = new Lru<String, Integer>(3);  // the class above
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
cache.get("a");
cache.put("d", 4);
IO.println(cache.keySet());

the gotchas

it also means an access-ordered map needs locking even for reads if more than one thread touches it: two "reads" can both rewire the list at once. wrapping it in Collections.synchronizedMap works for a small cache. anything serious, use a real caching library (Caffeine is the usual pick), which handles concurrency, expiry and smarter eviction than plain LRU.