Thread-Safe LRU Cache

TreeMap & LinkedHashMap already covered the single-threaded removeEldestEntry() LRU trick. This lesson is the natural follow-up interviewers ask: make it thread-safe.

Base implementation via LinkedHashMap

class LRUCache<K, V> {
    private final int capacity;
    private final LinkedHashMap<K, V> cache;

    LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(16, 0.75f, true) { // accessOrder = true
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
        };
    }

    V get(K key) { return cache.get(key); }
    void put(K key, V value) { cache.put(key, value); }
}

Adding thread safety: why a plain synchronized method isn't quite enough

class ThreadSafeLRUCache<K, V> {
    private final LinkedHashMap<K, V> cache; // as above
    private final ReentrantLock lock = new ReentrantLock();

    V get(K key) {
        lock.lock();
        try { return cache.get(key); } finally { lock.unlock(); }
    }
    void put(K key, V value) {
        lock.lock();
        try { cache.put(key, value); } finally { lock.unlock(); }
    }
}

The subtlety worth naming explicitly: get() on an access-ordered LinkedHashMap is not read-only — it mutates the internal linked-list ordering (moving the accessed entry to the most-recently-used position). This means get() can't just be wrapped in a shared read lock the way a genuinely read-only operation could; it needs the same exclusive lock as put(), because it's structurally a write.

Would ReadWriteLock help here? No — and that's the actual interview insight

// LOOKS reasonable, IS INCORRECT for this specific case:
private final ReadWriteLock rwLock = new ReentrantReadWriteLock();

V get(K key) {
    rwLock.readLock().lock(); // WRONG — get() mutates access order, this isn't a true read
    try { return cache.get(key); } finally { rwLock.readLock().unlock(); }
}

ReadWriteLock (see synchronized and Locks) is the right tool specifically when reads genuinely don't mutate shared state, allowing multiple concurrent readers. Here, get() does mutate state (the LRU ordering) — using a shared read lock for it would let two threads concurrently call get() and race on updating the same internal linked-list pointers, corrupting the LRU order (or, in pathological cases, LinkedHashMap's internal structure itself). This is exactly the kind of question where an interviewer expects you to recognize why a seemingly-obvious optimization (ReadWriteLock for a "read" operation) is actually wrong for this specific data structure's true read/write semantics — a plain exclusive ReentrantLock (or synchronized) is the correct answer here, not a premature optimization mistake.

Eviction callback hooks

interface EvictionListener<K, V> { void onEvict(K key, V value); }

class ThreadSafeLRUCache<K, V> {
    private final EvictionListener<K, V> evictionListener;
    private final LinkedHashMap<K, V> cache;

    ThreadSafeLRUCache(int capacity, EvictionListener<K, V> evictionListener) {
        this.evictionListener = evictionListener;
        this.cache = new LinkedHashMap<>(16, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                boolean shouldEvict = size() > capacity;
                if (shouldEvict) evictionListener.onEvict(eldest.getKey(), eldest.getValue());
                return shouldEvict;
            }
        };
    }
}

A common, genuinely useful follow-up extension: notify something when an entry gets evicted (e.g. releasing a resource the cached value held, like a file handle or a pooled connection — connecting directly to Connection Pool Design's own resource-lifecycle concerns). removeEldestEntry() is exactly the right hook point, since it's already called precisely once per eviction, with the evicted entry passed in directly.

Follow-up questions this topic invites — and their answers

Q: Could ConcurrentHashMap be used instead of a lock-wrapped LinkedHashMap? A: Not directly for LRU specifically — ConcurrentHashMap has no built-in access-order/eviction concept the way LinkedHashMap does; achieving LRU semantics with it would require building the ordering structure (a doubly-linked list) yourself alongside it, which is considerably more implementation work than wrapping LinkedHashMap in a single lock.

Q: Why might a single global lock become a bottleneck, and what's the fix? A: Under high concurrent read/write load, a single lock serializes every operation regardless of which keys are involved — a common mitigation is sharding the cache into N independent LRUCache instances, each with its own lock, keyed by hash(key) % N (the same sharding idea as HashMap Concurrency Variants' segment-based ConcurrentHashMap predecessor), trading perfect global LRU ordering for much better concurrent throughput.

Q: What happens if EvictionListener.onEvict() throws an exception? A: Since it's called from inside removeEldestEntry(), which LinkedHashMap calls from inside put(), an uncaught exception there would propagate up through put() itself — a production implementation should catch and log exceptions from the listener internally, so a misbehaving eviction callback can't break the cache's own put() operation.

Q: Is accessOrder=true always the right choice, or are there cases you'd want insertion order instead? A: LRU specifically requires access order (recency of use, not creation) — but if the goal were a different eviction policy like FIFO (evict oldest-inserted regardless of access pattern, see the Distributed Cache case's eviction policy comparison), insertion order (the LinkedHashMap default, accessOrder=false) would be the correct choice instead.