LRU Cache in 3 Lines: How LinkedHashMap Does the Heavy Lifting

Why HashMap Alone Fails for LRU

A plain HashMap only stores key-value pairs; it does not track access order. When capacity is exceeded, the naive approach clears the entire map, destroying hit rates, or lets the cache grow until OOM. To implement LRU manually, you would need a doubly-linked list plus a HashMap indexing nodes for O(1) moves — about 30+ lines of pointer manipulation (see the LRUHandWritten example, which mirrors the standard LeetCode 146 solution).

LinkedHashMap's Two Ordering Modes

LinkedHashMap

extends HashMap by adding before / after pointers on each node, forming a separate doubly-linked list. Iteration follows this list, not the hash buckets. The ordering is controlled by the accessOrder constructor parameter: accessOrder = false (default): insertion order. Re-inserting an existing key does not change its position. accessOrder = true: access order. Every get or put (on an existing key) moves the node to the tail. The head then points to the least-recently-used entry.

For LRU we need access order, so we instantiate:

Map<String, Object> cache = new LinkedHashMap<>(16, 0.75f, true);

This gives us the correct recency list, but no capacity limit yet.

How Order Is Maintained Internally

HashMap

provides three hook methods — afterNodeAccess, afterNodeInsertion, afterNodeRemoval — which LinkedHashMap overrides to maintain the doubly-linked list:

On put hit: afterNodeAccess moves the node to tail.

On put new entry: afterNodeInsertion appends to tail and may call removeEldestEntry to evict the head.

On any removal: afterNodeRemoval unlinks the node.

The simplified afterNodeAccess logic shows the pointer rearrangement: unlink the node from its current position and attach it before tail, all in O(1) without touching hash buckets.

Three-Line LRU Implementation

Subclass LinkedHashMap, enable accessOrder, and override removeEldestEntry:

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);
        this.maxSize = maxSize;
    }

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

Line 1: inheritance brings all LinkedHashMap mechanics. Line 2: constructor passes initial capacity, load factor (default 0.75f), and accessOrder=true. Line 3: eviction trigger — when size exceeds maxSize, the eldest (head) entry is removed. No need to override get or put; accessOrder=true already wires the correct behavior.

Key Implementation Details

maxSize

stored as private final because removeEldestEntry compares against it; the constructor's first argument is actually initialCapacity, but using the same value avoids an early rehash.

Load factor 0.75f is the HashMap default; it controls bucket resizing, independent of LRU eviction.

Do not override get — afterNodeAccess already handles recency, and a custom get would miss the put -hit path.

Inheritance vs. Composition

Inheritance is concise but exposes all public LinkedHashMap methods ( clear, clone, replace, etc.). For a controlled component, composition hides internals:

class LruCacheCombo<K, V> {
    private final int maxSize;
    private final LinkedHashMap<K, V> map;

    public LruCacheCombo(int maxSize) {
        this.maxSize = maxSize;
        this.map = new LinkedHashMap<>(maxSize, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> e) {
                return size() > maxSize;
            }
        };
    }
    public V get(K k) { return map.get(k); }
    public void put(K k, V v) { map.put(k, v); }
    public int size() { return map.size(); }
    // clear, clone, etc. are not exposed
}

Composition adds a wrapper class and delegation but prevents callers from bypassing LRU logic.

Runnable Verification Example

public static void main(String[] args) {
    LRUCache<String, Integer> cache = new LRUCache<>(3);
    cache.put("a", 1);
    cache.put("b", 2);
    cache.put("c", 3);
    cache.get("a");          // a moves to tail
    cache.put("d", 4);        // size becomes 4 > 3, evict head
    System.out.println(cache.keySet());
}

Execution trace:

After puts a, b, c: list order a → b → c (a is LRU). get("a") triggers afterNodeAccess; order becomes b → c → a. put("d") makes size 4; removeEldestEntry returns true, evicts head b.

Output: [c, a, d] — b evicted, c, a, d retained, matching LRU semantics. Note keySet() iterates from head (oldest) to tail (newest).

Edge-Case Behaviors

Put hit counts as access: Updating an existing key moves it to tail. If business logic requires "write-only not read", a custom implementation is needed.

containsKey / containsValue do not update recency: Only get and put (on hit) call afterNodeAccess.

Capacity boundary: size() > maxSize is strict; exactly maxSize entries cause no eviction. The maxSize+1 -th insertion evicts the first.

putAll evicts repeatedly: Inserting a batch of 5 into a capacity-3 cache evicts until only the last 3 remain (example shows [z, u, v] after putting x, y, z, u, v).

Logging evictions: Override removeEldestEntry to log eldest.getKey() before returning true.

Caveats and Limitations

Not thread-safe: LinkedHashMap has no locks; get mutates the list. Concurrent access corrupts the list or causes infinite loops. Options: Collections.synchronizedMap (coarse lock), a custom read-write lock wrapper (shown), or switch to Caffeine.

removeEldestEntry must be fast: It runs synchronously inside put. Avoid I/O, heavy computation, or remote calls; push evicted entries to an async queue instead.

Serialization resets access order: The before / after pointers are transient. After deserialization, the list rebuilds in insertion order, losing recency. Persist the key sequence separately if order must survive restarts.

Strong references retain large values: Each entry adds two extra pointers (~48–64 bytes overhead). With 10,000 entries averaging 1 KB values, heap usage starts around 15–20 MB. Size limit alone does not bound total memory if values are large.

When to Upgrade to Caffeine

The three-line LRUCache suits single-process, low-concurrency, fixed-capacity, pure-LRU scenarios (e.g., startup dictionaries, test stubs). It becomes insufficient when you need:

Time-based expiration (TTL / TTI)

Weak/soft references for GC-friendly caching

Hit-rate statistics

Asynchronous loading / refresh

Weight-based capacity (e.g., bytes instead of entry count)

High-throughput concurrent access

Caffeine uses W-TinyLFU (windowed TinyLFU) which outperforms pure LRU on scan-resistant workloads and offers near-lock-free reads/writes. The comparison:

Eviction policy: LinkedHashMap LRU — LRU only; Guava Cache — LRU / Segmented LRU; Caffeine — W-TinyLFU

TTL / TTI: LinkedHashMap LRU — No; Guava Cache — Yes; Caffeine — Yes

Weak/soft refs: LinkedHashMap LRU — No; Guava Cache — Yes; Caffeine — Yes (weak key / soft value)

Hit-rate stats: LinkedHashMap LRU — None; Guava Cache — Yes; Caffeine — Yes (richer)

Async refresh: LinkedHashMap LRU — No; Guava Cache — Yes; Caffeine — Yes

High concurrency: LinkedHashMap LRU — Manual locking; Guava Cache — Striped locks; Caffeine — Near lock-free

Extra dependency: LinkedHashMap LRU — None (JDK); Guava Cache — Guava; Caffeine — Caffeine

Scan vulnerability: A full-table scan (e.g., nightly export) touches every entry, promoting them to MRU and evicting true hot spots. W-TinyLFU mitigates this with frequency-aware admission.

Adding TTL (Lazy Expiration)

A minimal TTL extension records write timestamps and checks on get:

class TtlLRU<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    private final long ttlMs;
    private final Map<K, Long> writeAt = new HashMap<>();

    TtlLRU(int maxSize, long ttlMs) {
        super(maxSize, 0.75f, true);
        this.maxSize = maxSize;
        this.ttlMs = ttlMs;
    }

    @Override
    public V get(Object k) {
        V v = super.get(k);
        long born = writeAt.getOrDefault((K) k, 0L);
        if (v != null && System.currentTimeMillis() - born > ttlMs) {
            remove(k);
            return null;
        }
        return v;
    }

    @Override
    public V put(K k, V v) {
        writeAt.put(k, System.currentTimeMillis());
        return super.put(k, v);
    }

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

This only expires on access; a background sweeper is needed for idle entries. Once you add stats, weights, listeners, the code grows beyond "three lines" — prefer Caffeine.

Local LRU vs. Distributed Cache

LinkedHashMap

caches live in the JVM heap: process restart loses data; multiple instances have disjoint caches and may diverge. It fits "single-process, rebuildable, loss-tolerant" acceleration layers (method memoization, dictionary tables). For cross-instance sharing, persistence, or centralized rate limiting, use Redis instead.

Decision guide:

Need capacity limit, no OOM, clear logic, zero dependencies → three-line LinkedHashMap LRU.

Need high concurrency, expiration, observability, scan resistance → Caffeine.

Need multi-instance sharing, restart durability, centralized counting → Redis.