System Design

LRU Cache Design

Understand how an LRU cache works, how Java LinkedHashMap can implement it, and what interviewers expect beyond the code.

CachingJavaHashMapLinkedHashMapSystem Design

Simple Java Design with LinkedHashMap

An LRU cache stores a limited number (capacity) of key-value pairs and evicts the least recently used entry when capacity is exceeded.

Java already provides a very convenient implementation building block with LinkedHashMap.

If accessOrder = true, then successful get() and put() operations move entries to the most recently used position.

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

public class LruCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

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

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

Minimal Usage Example

java
public class Main {

    public static void main(String[] args) {

        LruCache<Integer, String> cache =
            new LruCache<>(2);

        cache.put(1, "A");
        cache.put(2, "B");

        cache.get(1);

        // evicts key 2
        cache.put(3, "C");

        System.out.println(cache);
    }
}

How It Works

  • LinkedHashMap internally maintains a doubly linked list.
  • With accessOrder = true, accessed entries move to the end.
  • The least recently used item naturally becomes the eldest entry.
  • removeEldestEntry() is called after insertion.
  • Returning true evicts the least recently used entry.

What Interviewers Are Looking For

Core Understanding

You understand that LRU requires both fast lookup and fast recency updates.

HashMap Limitation

You know a HashMap alone cannot efficiently track usage order.

Linked List Purpose

You understand why a doubly linked list allows O(1) removal and insertion.

Classic Design

You can explain the classic HashMap plus doubly linked list solution.

Library Knowledge

You know LinkedHashMap already combines these concepts internally.

Concurrency Awareness

You recognize that this implementation is not thread-safe.

The Classic Manual Design

In many interviews, the interviewer eventually wants the manual implementation rather than the built-in Java solution.

The classic approach uses:

  • A HashMap<K, Node> for O(1) lookup.
  • A doubly linked list for maintaining recency order.
  • The head represents most recently used.
  • The tail represents least recently used.

Common Follow-Ups

Why not just use a queue?

Because updating recency for an existing item would not be O(1).

Why a doubly linked list?

Because nodes can be removed and reinserted in O(1).

Is LinkedHashMap acceptable in interviews?

Usually yes, but interviewers still expect you to understand the underlying design.

Is this thread-safe?

No. Concurrent access requires synchronization or a production-grade cache library.

Production Note

Real production caches often need more than simple LRU eviction.

Additional concerns may include:

  • TTL expiration
  • memory limits
  • distributed invalidation
  • cache stampede prevention
  • metrics and observability
  • thread safety