How do you build a bounded LRU cache using LinkedHashMap and removeEldestEntry?
answer
- Access-order (3rd arg true) + override removeEldestEntry
- Return size() > capacity
- Hook runs after insert; evicts head (LRU)
- size init ~ capacity/0.75 + 1
- Not thread-safe → wrap or use Caffeine
basics
~20 sCreate a LinkedHashMap in access-order mode and override removeEldestEntry to return true once the map grows past your size limit. When a new key pushes it past that limit, the map drops the least-recently-accessed entry.
solid answer
~50 sAn 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<K,V> eldest)` to return `true` when `size() > capacity`. After a `put` or `putAll` inserts a new entry, 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 should not need to grow. Note this is not thread-safe; wrap with `Collections.synchronizedMap` or, for production, reach for Caffeine, a concurrent cache library with expiry and weighted size bounds.
code
java · 21 linesclass 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
Recognizes that LinkedHashMap can implement an LRU cache and that removeEldestEntry triggers eviction.
Writes the subclass correctly with access-order and the size()>capacity override, and explains why each piece is needed.
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.
Decides when a hand-rolled LinkedHashMap cache suffices vs adopting Caffeine for concurrency/TTL/weighting/metrics, and reasons about hit-rate, memory pressure, and frequency-aware eviction alternatives.
## 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 the least-recently-used entry — exactly the eviction candidate. 2. **The `removeEldestEntry` hook.** After a new entry goes in through `put`, `putAll` or another method that adds a key, LinkedHashMap calls `protected boolean removeEldestEntry(Map.Entry<K,V> eldest)`, passing the current head (eldest) entry. A `put` that only replaces a value makes no call, and neither do the copy constructor, `clone` or deserialization, so a capped subclass built by the copy constructor can start over its limit. 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 policy. - **You can add side effects.** Override `removeEldestEntry` to also close a resource or write a metric when evicting, then return `true` and let LinkedHashMap remove the entry. The Javadoc does permit modifying the map inside the method, but then it must return `false`, because "the effects of returning true after modifying the map from within this method are unspecified". - **`putFirst` does not fit this recipe.** Since Java 21 `putFirst` links a new entry at the head before the hook runs, so a capped map can evict the entry it just added. - **Not thread-safe.** Reads mutate order, so concurrent use can corrupt the list. Wrap with `Collections.synchronizedMap(new LruCache<>(n))` and synchronize iteration, or use **Caffeine**, a dedicated cache library with concurrent access, expiry, weighted size bounds and asynchronous loading; Guava's `CacheBuilder` documentation says to prefer it over Guava's own caching API. For interview purposes, the LinkedHashMap version is the classic 'implement an LRU cache' answer; for production, say you would reach for 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?Usually not. The normal use is to return true and let LinkedHashMap remove the eldest. The Javadoc does permit modifying the map inside the method, but then it must return false, and returning true after modifying has unspecified effects. Logging and resource cleanup are fine either way.
- How would you make this LRU cache thread-safe?Wrap it with Collections.synchronizedMap and synchronize externally during iteration, since even get mutates order. That one lock serializes every read, so for a busy shared cache use a concurrent cache library such as Caffeine instead.
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.
- 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() inside removeEldestEntry and then also returning true, whose effects are unspecified.
- Claiming the LinkedHashMap LRU cache is thread-safe by default.
- Thinking removeEldestEntry runs before insertion (it runs after).
- LinkedHashMap access order and removeEldestEntry
- Java 1.4
Assumes JDK 27; LinkedHashMap.java is byte-identical at JDK 25. The recipe dates from the class's arrival in 1.4; putFirst, which does not fit it, is since Java 21.
context
- LinkedHashMap (Java SE 27 & JDK 27)docs.oracle.com
- LinkedHashMap.java at jdk-27-gagithub.com
- Evictiongithub.com