LinkedHashMap and building an LRU cache

Think of it as a hotel key rack with a fast lookup table behind it. The front desk can find room 418 by room number, but it also keeps the keys in a visible left-to-right order. That second order is what turns a plain map into a small LRU cache.

For this lesson, we'll focus on how LinkedHashMap extends HashMap.Node, how the before and after links maintain insertion order or access order, the hooks afterNodeAccess, afterNodeInsertion and removeEldestEntry, Java 21 SequencedMap, and two LRU implementations: the short library version and the interview version you build with a HashMap plus a doubly linked list. Interviewers love this because the API is tiny, but the details reveal whether you can connect a map, a list and an eviction policy.

01Picture it first: one entry, two neighborhoods

A LinkedHashMap entry lives in two neighborhoods at once. It sits in a hash bucket so get(key) can find it by hash. The same entry is also part of a doubly linked list so iteration can start at head and follow after until tail.

The picture below is the one I draw in interviews. Buckets find nodes; before/after orders nodes.

Fig. 1

A LinkedHashMap has a HashMap bucket table for lookup and a separate before-after linked list from head through A, C and B to tail using the same entry objects

Notice that there is no second copy of the key or value in the linked list. The entry object is shared by both structures. That is why moving an entry to the tail is pointer work, not a rehash.

02LinkedHashMap under the hood

HashMap.Node has the fields needed for hashing: cached hash, key, value and the next pointer inside a bucket. LinkedHashMap.Entry adds before and after pointers. The map itself keeps head and tail references.

Map<String, Integer> scores = new LinkedHashMap<>(16, 0.75f, true);
scores.put("Asha", 10);
scores.put("Ravi", 20);
scores.put("Mina", 30);

scores.get("Asha");
scores.put("Ravi", 25);

System.out.println(scores.keySet());

It prints [Mina, Asha, Ravi]. The get("Asha") moves Asha to the tail. Updating Ravi's existing mapping also counts as an access in access-order mode, so Ravi moves behind Asha.

Conceptually, the important classes look like this:

class HashMapNode<K, V> {
    final int hash;
    final K key;
    V value;
    HashMapNode<K, V> next;       // bucket chain
}

class LinkedHashMapEntry<K, V> extends HashMapNode<K, V> {
    LinkedHashMapEntry<K, V> before;
    LinkedHashMapEntry<K, V> after;
}

Notice three things:

• next is for collision handling inside one hash bucket. before and after are for encounter order across the whole map.
• Replacing the value for an existing key does not create a new node. In access-order mode, it can still move the existing node.
• Iteration cost is O(n) in the number of entries, regardless of table capacity, because it walks the linked list rather than scanning empty buckets.

The hook names are worth saying out loud. afterNodeAccess runs after an access and moves the node to the tail when accessOrder is true. afterNodeInsertion runs after adding a new node and gives removeEldestEntry a chance to evict the head. afterNodeRemoval unlinks the removed node from the order list.

03Insertion order, access order and Java 21 SequencedMap

The default constructor gives insertion order. Re-inserting an existing key updates its value but does not change its position. That makes LinkedHashMap useful for predictable output, such as serializing fields in first-seen order.

Access order is different. Pass true as the third constructor argument and the map tracks recency. The least recently used entry is at the head, and the most recently used entry is at the tail.

LinkedHashMap<Integer, String> pages = new LinkedHashMap<>(16, 0.75f, true);
pages.put(1, "home");
pages.put(2, "pricing");
pages.put(3, "checkout");

pages.get(1);             // order: 2, 3, 1
pages.getOrDefault(2, ""); // order: 3, 1, 2

In Java 21, LinkedHashMap implements SequencedMap. That gives names to operations people used to fake with iterators.

Here's the catch: explicit positioning methods such as putFirst and putLast are not the same as normal access-order reads. They place the entry where you ask. Use them when order itself is your API, not when you are trying to let ordinary cache reads drive recency.