skip to content

How do you build a bounded LRU cache using LinkedHashMap and removeEldestEntry?

level: seniorimportance: must knowfreq 75%

answer

  1. Access-order (3rd arg true) + override removeEldestEntry
  2. Return size() > capacity
  3. Hook runs after insert; evicts head (LRU)
  4. size init ~ capacity/0.75 + 1
  5. Not thread-safe → wrap or use Caffeine

basics

~10 s

Create a LinkedHashMap in access-order mode and override removeEldestEntry to return true once the map grows past your size limit. After each insert, the map then automatically drops the least-recently-used entry.

solid answer

~50 s

An LRU (least-recently-used) cache keeps only the N most-recently-used entries. LinkedHashMap gives you this almost for free. First, construct it in access-order mode (third constructor arg `true`) so every get/put moves the touched entry to the tail and the head stays the least-recently-used. Then subclass it and override `protected boolean removeEldestEntry(Map.Entry eldest)` to return `true` when `size() > capacity`. After every `put`/`putAll`, LinkedHashMap calls this hook; returning true makes it remove the eldest (head) entry — the LRU one. So the map self-trims to the bound. Capture the capacity in a field and use it in the override. Set the initial capacity to about `capacity / 0.75 + 1` so the backing table never needs to resize. Note this is not thread-safe; wrap with `Collections.synchronizedMap` or, for production, prefer Caffeine/Guava which add concurrency, TTL, and weighting.

code

java · 21 lines
java
class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruCache(int capacity) {
        super(capacity * 4 / 3 + 1, 0.75f, true); // access-order = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // evict head once over the bound
    }
}

LruCache<Integer, String> cache = new LruCache<>(2);
cache.put(1, "a");
cache.put(2, "b");
cache.get(1);        // refresh 1 -> now MRU; 2 is LRU
cache.put(3, "c");   // size 3 > 2 -> evicts 2 (the LRU)
System.out.println(cache.containsKey(2)); // false
System.out.println(cache.keySet());       // [1, 3]

go deeper

for a junior

Recognizes that LinkedHashMap can implement an LRU cache and that removeEldestEntry triggers eviction.

for a middle

Writes the subclass correctly with access-order and the size()>capacity override, and explains why each piece is needed.

for a senior

Handles the off-by-one, initial-capacity sizing, the after-insert timing of the hook, and the thread-safety caveat; contrasts LRU vs FIFO eviction.

for a principal

Decides when a hand-rolled LinkedHashMap cache suffices vs adopting Caffeine for concurrency/TTL/weighting/metrics, and reasons about hit-rate, memory pressure, and eviction policy alternatives (LFU, W-TinyLFU).

## What an LRU cache is A **cache** stores recently computed/fetched values so you can return them fast next time. It must be **bounded** (limited size) or it grows forever. An **LRU (Least-Recently-Used)** cache, when full, evicts the entry that was *used* longest ago — the bet being that recently used things are likely to be used again. ## Two ingredients LinkedHashMap provides 1. **Access-order mode.** Constructing `new LinkedHashMap<>(cap, 0.75f, true)` (third arg `true`) makes the map move any accessed entry (`get`, or a `put`/`compute` on an existing key) to the **tail** of its internal doubly-linked list. So the **head** is always the least-recently-used entry — exactly the eviction candidate. 2. **The `removeEldestEntry` hook.** After every insertion, LinkedHashMap calls `protected boolean removeEldestEntry(Map.Entry<K,V> eldest)`, passing the current head (eldest) entry. The base implementation always returns `false` (never auto-remove). If you **override** it to return `true`, LinkedHashMap removes that eldest entry immediately. So the recipe is: return `true` exactly when the map has grown beyond your capacity. ## Putting it together ```java class LruCache<K,V> extends LinkedHashMap<K,V> { private final int capacity; LruCache(int capacity) { super(capacity * 4 / 3 + 1, 0.75f, true); // access-order this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K,V> e) { return size() > capacity; } } ``` Now every `put` of a *new* key beyond the limit triggers one eviction of the head (LRU) entry, keeping size at `capacity`. Every `get`/`put` of an existing key refreshes recency by moving that entry to the tail, so it survives longer. ## Subtleties - **Why `size() > capacity` not `>=`?** `removeEldestEntry` runs *after* the new entry is inserted. When the map is allowed to hold `capacity` entries, an insert that pushes it to `capacity + 1` should evict one, bringing it back to `capacity`. `> capacity` does exactly that. - **Initial capacity sizing.** Hash maps resize when `size > capacity * loadFactor`. Passing `capacity / 0.75 + 1` as the initial table capacity avoids a resize for a cache that hovers at its bound — a small perf win. - **Eldest = head = LRU** only because we used access-order. If you forgot the `true` flag, you'd build an *insertion-order* (FIFO) eviction cache instead, which is a different, usually worse, policy. - **You can add side effects.** Override `removeEldestEntry` to also close a resource or write a metric when evicting, but don't call `remove()` yourself inside it — return `true` and let LinkedHashMap remove it. - **Not thread-safe.** Reads mutate order, so concurrent use corrupts the list. Wrap with `Collections.synchronizedMap(new LruCache<>(n))` and synchronize iteration, or use **Caffeine/Guava Cache** which provide concurrency, TTL/expiry, size weighting, and async loading out of the box. For interview purposes, the LinkedHashMap version is the classic 'implement an LRU cache' answer; for production, name Caffeine.

  • Why use access-order mode instead of the default for an LRU cache?
    Because LRU eviction must remove the entry used longest ago. Access-order keeps the head as the least-recently-used; the default (insertion order) would evict the oldest-inserted entry, i.e. a FIFO cache, ignoring usage.
  • Should you call remove() inside removeEldestEntry?
    No. The hook is a decision function: return true and LinkedHashMap removes the eldest for you. Removing manually inside it can corrupt the map or double-remove. You may add logging or resource cleanup, but not the removal itself.
  • How would you make this LRU cache thread-safe?
    Wrap it with Collections.synchronizedMap and synchronize externally during iteration, since even get mutates order. In practice prefer a concurrent cache like Caffeine, which gives lock-free reads, TTL, and size-based eviction.

Imagine a small shelf that holds exactly N books, and every time you read a book you move it to the right end. When you bring home a new book and the shelf is full, you toss the leftmost one — the book you haven't read in the longest time.

saying these in an interview costs you the question

  • Forgetting access-order mode — that yields FIFO eviction, not LRU.
  • Returning size() >= capacity (off-by-one) so the cache holds capacity-1 entries.
  • Calling remove() manually inside removeEldestEntry instead of just returning true.
  • Claiming the LinkedHashMap LRU cache is thread-safe by default.
  • Thinking removeEldestEntry runs before insertion (it runs after).

context

resolving links…