LinkedHashMap”, “prove it is O(1)”, “now make it thread-safe” — are where the real answer is tested. This page gives you the short answer first, then everything underneath it, as lru cache java code that was compiled, tested and benchmarked rather than recalled.
Here is the order: the 30-second answer you can say out loud, the contract, three implementations (LinkedHashMap; HashMap plus a hand-rolled doubly linked list; a thread-safe family of three), the O(1) argument as a dry-run table, the concurrency trap that sinks most answers, an honest benchmark, and what to use in production instead of any of it. Deeper material sits in the collapsed sections, so you can read straight through or open only what you need.
Versions this was built and run against. JDK 25.0.5+8 (Temurin, LTS), JUnit 6.1.3, JMH 1.37 (latest GA on Maven Central; released August 2023), Caffeine 3.3.1 (latest GA on Maven Central; the project’s release page lists it as Latest, 13 October 2026). Everything quoted below comes from a committed file in the lru-cache module of the java-interview-lab repository. The benchmark ran on a shared 2-vCPU sandbox with a load average above 20, so treat its numbers as indicative; the page says where that matters.
The 30-second answer
Say this, then write the code.- What it is: a fixed-size cache that, when full, throws away the entry that was used longest ago. “Used” means read or written.
- The data structure: a hash map for O(1) lookup plus a doubly linked list that keeps entries in recency order. The map points at list nodes. A hit unlinks its node and relinks it at the front; an insert into a full cache drops the node at the back and forgets its key. Every step is a handful of pointer writes, so
getandputare O(1). - The shortcut: Java already ships that combination.
LinkedHashMapwithaccessOrder=trueand an overriddenremoveEldestEntryis an LRU cache in about ten lines. - The trap:
getchanges the list, so even reads need exclusive access. AReadWriteLockdoes not help. Use one lock (synchronizedorReentrantLock) or stripe the cache, and accept that striping makes eviction approximate. - The production answer: do not hand-roll it. Use Caffeine (
Caffeine.newBuilder().maximumSize(n).build()).
LinkedHashMapLruCache.java):
/** The classic interview class, shown on its own so the article can quote it. */
static final class Lru<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
Lru(int capacity) {
// 3rd argument true = access order. Load factor 1.0f + capacity+1 slots: the map
// never needs to resize, because removeEldestEntry trims it back to `capacity`.
super(capacity + 1, 1.0f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}If you only remember one sentence for the thread-safety follow-up: “get mutates the recency list, so it is a write; a read-write lock would let two readers rewrite the same four pointers at once, so I use a single lock, and I would reach for Caffeine in production.” The rest of this page earns that sentence.
What the cache must do before you write any code
Interviewers watch for whether you pin down the contract first. The one used here, and enforced by a shared test suite that every implementation must pass, is small:- Fixed capacity chosen at construction; zero or negative capacity is rejected.
get(k)returns the value ornull; a hit makeskthe most recently used.put(k, v)inserts or replaces, makeskthe most recently used, and evicts the least recently used entry if the cache would exceed capacity. Replacing an existing key never evicts anything.- Null keys and null values are rejected with
NullPointerException, so anullfromgetcan only mean “not here”.
LruCache.java. Before the implementations, the picture that explains all of them: two structures that share the same nodes.
Implementation 1: LinkedHashMap does it for you
LinkedHashMap is a HashMap whose entries are also threaded onto a doubly linked list. By default the list is in insertion order. Pass true as the third constructor argument and it switches to access order: every access moves the entry to the end of the list. The eldest entry is then, by definition, the least recently used one. removeEldestEntry is a hook the map calls right after every insertion; if you return true, the eldest entry is removed. The class above is the whole implementation.
Two details are worth saying out loud in an interview. The constructor is super(capacity + 1, 1.0f, true): the map briefly holds capacity + 1 entries between the insertion and the eviction, so the table is sized for that and, at load factor 1.0, never has to grow. And the check is size() > capacity, not ==, which is the safer habit.
Which calls count as an “access”? The Javadoc lists put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent and merge. I ran five of those plus the calls that should not count, and the test asserts each result (LinkedHashMapBehaviourTest.java; the transcript is output/03-linkedhashmap-access-order.txt):
LinkedHashMap(accessOrder=true), start [1, 2, 3] (LRU -> MRU): does the call move key 1?
========================================================================================
get(1) -> order [2, 3, 1] key 1 moved to MRU end: true
put(1, "x") (existing key) -> order [2, 3, 1] key 1 moved to MRU end: true
getOrDefault(1, "-") -> order [2, 3, 1] key 1 moved to MRU end: true
putIfAbsent(1, "x") (key present) -> order [2, 3, 1] key 1 moved to MRU end: true
computeIfAbsent(1, k -> "x") (key present) -> order [2, 3, 1] key 1 moved to MRU end: true
containsKey(1) -> order [1, 2, 3] key 1 moved to MRU end: false
keySet() iteration -> order [1, 2, 3] key 1 moved to MRU end: false
entrySet() iteration -> order [1, 2, 3] key 1 moved to MRU end: false
size() -> order [1, 2, 3] key 1 moved to MRU end: falseA read that is a structural modification. In access-order modegetrelinks the entry, and the Javadoc says so in as many words: “merely querying the map withgetis a structural modification”. The consequence needs no second thread at all — a single-threaded loop that callsgetwhile iterating the key set throwsConcurrentModificationException. It is also the reason the thread-safety section below exists.
In access-order mode get() is a structural modification (single thread, no concurrency)
=======================================================================================
for (Integer k : accessOrderMap.keySet()) accessOrderMap.get(k);
-> java.util.ConcurrentModificationException
same loop on an insertion-order LinkedHashMap -> completes normallyoutput/04-get-is-structural.txt, written by the same test that asserts the exception.
Going deeper: what the interviewer is probing with LinkedHashMap
- “Why not just extend
LinkedHashMapin production?” You get an unsynchronized cache with no statistics, no expiry and no loading. It is fine for a small, single-threaded, bounded memo table. Anywhere else it is a liability. - “Is
removeEldestEntrycalled onget?” No. The Javadoc says it is invoked byputandputAll, after inserting a new entry. Agetreorders but never evicts. - Composition or inheritance? The repository wraps the subclass inside a final class that implements
LruCache, so callers cannot reach the inheritedMapmethods and break the null-rejecting contract. The inheritance version above is what you write on a whiteboard. - Not the same as sorting by time. There are no timestamps anywhere; recency is purely the list position.
Implementation 2: HashMap plus a doubly linked list, by hand
“Now do it withoutLinkedHashMap” means: build the picture above yourself. You need a node that holds a key, a value and two neighbours; a HashMap<K, Node>; and two operations on the list, unlink a node and link a node right after the head. Here are the node, the fields and the pointer counter (HashMapLruCache.java):
static final class Node<K, V> {
K key;
V value;
Node<K, V> prev, next;
Node(K key, V value) { this.key = key; this.value = value; }
}
private final int capacity;
private final Map<K, Node<K, V>> index;
private final Node<K, V> head = new Node<>(null, null);
private final Node<K, V> tail = new Node<>(null, null);
/** Counts every pointer assignment made on a node. Lets a test prove the cost per operation. */
long pointerWrites;head and tail, never hold data. They exist so that no operation ever has to ask “is there a previous node?”. With sentinels an empty list is just head ↔ tail, a one-element list is head ↔ n ↔ tail, and unlinking or inserting is the same four lines in every case. Without them, every method grows if (n.prev == null) branches, and those branches are where whiteboard solutions go wrong.
Now the operations. This is the heart of the answer, taken verbatim from the same file:
@Override
public V get(K key) {
Objects.requireNonNull(key);
Node<K, V> n = index.get(key); // O(1) expected
if (n == null) return null;
unlink(n); // O(1): 2 pointer writes
linkAfterHead(n); // O(1): 4 pointer writes
return n.value;
}
@Override
public void put(K key, V value) {
Objects.requireNonNull(key);
Objects.requireNonNull(value);
Node<K, V> n = index.get(key);
if (n != null) { // existing key: replace value, make it MRU
n.value = value;
unlink(n);
linkAfterHead(n);
return;
}
if (index.size() == capacity) { // full: evict the node just before the tail sentinel
Node<K, V> lru = tail.prev;
unlink(lru);
index.remove(lru.key); // the node must remember its key, or this is impossible
}
n = new Node<>(key, value);
index.put(key, n);
linkAfterHead(n);
}
private void unlink(Node<K, V> n) {
n.prev.next = n.next;
n.next.prev = n.prev;
pointerWrites += 2;
}
private void linkAfterHead(Node<K, V> n) {
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
pointerWrites += 4;
}get first: look up the node, unlink it, link it at the front, return the value. put has three cases — existing key (replace and move), full cache (evict the node before tail, and remove its key from the map), and the ordinary insert. The picture below shows what “move to the front” costs in pointer writes.
Going deeper: the four bugs that sink hand-rolled versions
- The node does not store its key. When you evict the tail node you hold a node, not a key, and
index.remove(?)has nothing to pass. The key lives in the node for exactly this reason. - Updating an existing key by inserting a second node. The old node stays in the list; the map forgets it; the list now has a ghost.
putmust check the map first. - Evicting before checking whether the key already exists. A
putthat only replaces a value must not evict anything. The shared contract testputExistingKeyReplacesValueAndRefreshescatches this. - Wrong order of pointer writes. In
linkAfterHead,head.next.prev = nmust run beforehead.next = n, or you lose the old first node. Writing the four lines in the order shown, from the node outwards to its neighbours, avoids the question.
checkInvariants() that walks the list forwards, checks every prev against every next, and compares the length with the index. See LruContractTest.java.
Why every operation is O(1): a dry run and a measurement
Here is the argument as a table. Capacity 3; each row is one call; the last column is how many list-pointer writesHashMapLruCache made for it, counted by the field you saw above. The test also runs the same ten operations against the LinkedHashMap version and asserts that both give the same return value and the same order after every row (DryRunTranscriptTest.java; transcript output/01-dry-run-capacity-3.txt):
Dry run, capacity 3: state after each operation (keys listed LRU -> MRU)
========================================================================
# operation returns LRU -> MRU ptr-writes same as LinkedHashMap?
1 put(1,A) - [1] 4 yes
2 put(2,B) - [1,2] 4 yes
3 put(3,C) - [1,2,3] 4 yes
4 get(1) A [2,3,1] 6 yes
5 put(4,D) - (evicts 2) [3,1,4] 6 yes
6 get(2) null [3,1,4] 0 yes
7 put(3,C2) - (replace, refresh) [1,4,3] 6 yes
8 put(5,E) - (evicts 1) [4,3,5] 6 yes
9 get(4) D [3,5,4] 6 yes
10 get(1) null [3,5,4] 0 yes
ptr-writes = pointer assignments on list nodes made by HashMapLruCache for that operation.
A miss costs 0, a hit costs 6 (unlink 2 + link 4), a new insert 4 (+2 for the eviction unlink). None depends on the cache size.get(1): key 1 was oldest, so the order goes from [1,2,3] to [2,3,1] at a cost of 6 writes. Row 5, put(4,D) on a full cache: key 2 (now the oldest) is dropped, which is two writes to unlink it plus four to link the new node — 6 again. Row 6 is a miss and touches no list node at all.
A dry run on three entries proves little about 100,000. So the second test fills caches of 10, 1,000 and 100,000 entries and measures the pointer writes for each operation type, using the oldest key for the hit — the case a naive list scan would hate (ConstantCostTest.java; output/02-constant-cost-per-operation.txt):
Pointer writes per HashMapLruCache operation, by cache size
===========================================================
capacity get(hit) get(miss) put(new) put(new, evicts LRU)
10 6 0 4 6
1000 6 0 4 6
100000 6 0 4 6
get(hit) is measured on the OLDEST key (position n from the front). Cost is 6 writes anyway: the node is reached through the hash index, not by walking the list.HashMap.get and put, is O(1) expected, as it is for any hash map.
Going deeper: the honest fine print on “O(1)”
- Expected, not worst case. A
HashMapis O(1) expected when keys hash well. If every key has the samehashCode, lookups degrade; since Java 8 a long bucket chain is converted to a balanced tree, so the worst case is O(log n) for keys that areComparableand worse for those that are not. The list part stays O(1) regardless. - Space is O(capacity) and each entry costs a map entry plus a list node.
LinkedHashMapstores both in one object (its entry carriesbefore/afterlinks), which is one reason it is the lighter choice in practice. - What the table does not measure: allocation (one
Nodeper new key), memory locality (a linked list chases pointers), and the cost of boxingIntegerkeys. Big-O hides all three; the benchmark section shows what they add up to. - Counting writes is a proxy, deliberately. It is a deterministic one, so it can be asserted in a test. Wall-clock time cannot.
Making it thread-safe: why reads are writes
Everything so far is single-threaded. Put either class behind two request threads and it corrupts silently. The interesting part is which locking strategy is correct, because the tempting one is wrong. The tempting design says: caches are read-heavy, so use aReadWriteLock — many concurrent readers, one writer. It would be right for a cache whose get only reads. An LRU cache’s get is the six-write operation from the diagram above. Two threads holding the read lock are allowed to run it at the same time, on shared nodes.
get (BrokenReadWriteLockLruCache.java):
@Override public V get(K key) {
rw.readLock().lock(); // BUG: get() is a write to the recency list
try { return delegate.get(key); } finally { rw.readLock().unlock(); }
}get) against it and against the correct synchronized version, then runs the structural invariant check (BrokenLockDemo.java; output output/09-broken-readwritelock-demo.txt). This is a race, so it is a measurement and not an assertion; the file is the output of the run I made:
cores=2 threads=4 opsPerThread=400000 capacity=64 keys=128
workload: 90% get, 10% put, uniform random keys
round 1
ReadWriteLock, get under READ lock worker exceptions=0; size=64/64; INVARIANT BROKEN: list length 17 != index size 64
synchronized (correct) worker exceptions=0; size=64/64; invariants OK
round 2
ReadWriteLock, get under READ lock worker exceptions=0; size=64/64; INVARIANT BROKEN: list node not in index: 94
synchronized (correct) worker exceptions=0; size=64/64; invariants OK
round 3
ReadWriteLock, get under READ lock worker exceptions=0; size=64/64; invariants OK
synchronized (correct) worker exceptions=0; size=64/64; invariants OK
round 4
ReadWriteLock, get under READ lock worker exceptions=0; size=64/64; INVARIANT BROKEN: list node not in index: 125
synchronized (correct) worker exceptions=0; size=64/64; invariants OK
round 5
ReadWriteLock, get under READ lock worker exceptions=0; size=64/64; invariants OK
synchronized (correct) worker exceptions=0; size=64/64; invariants OKsynchronized version passed all five. Because the outcome depends on timing, a clean round proves nothing, which is also why the proper test is the structural invariant check and not “did it crash”.
StampedLock does not rescue you either. Its optimistic-read mode is also for read-only critical sections that can be validated and retried. Agetthat rewrites pointers is not that. The rule is general: a lock’s read mode protects operations that do not write to shared state, and an LRUgetalways does.
The three correct answers
A. One coarse lock,synchronized. Every method takes the same monitor. This is the answer to give first (SynchronizedLruCache.java):
public final class SynchronizedLruCache<K, V> implements LruCache<K, V> {
private final HashMapLruCache<K, V> delegate;
public SynchronizedLruCache(int capacity) { this.delegate = new HashMapLruCache<>(capacity); }
@Override public synchronized V get(K key) { return delegate.get(key); }
@Override public synchronized void put(K key, V value) { delegate.put(key, value); }
@Override public synchronized int size() { return delegate.size(); }
@Override public int capacity() { return delegate.capacity(); }
@Override public synchronized List<K> keysLruFirst() { return delegate.keysLruFirst(); }
public synchronized void checkInvariants() { delegate.checkInvariants(); }
}ReentrantLock. The same critical section spelled with an explicit lock (ReentrantLockLruCache.java). It buys you tryLock, timeouts, interruptibility and an optional fairness policy. It does not buy parallelism: there is still one lock and every operation still takes it.
@Override public V get(K key) {
lock.lock();
try { return delegate.get(key); } finally { lock.unlock(); }
}
@Override public void put(K key, V value) {
lock.lock();
try { delegate.put(key, value); } finally { lock.unlock(); }
}StripedLruCache.java). Threads touching different stripes do not contend. The price is that LRU order now exists per stripe, not globally:
private SynchronizedLruCache<K, V> segmentFor(K key) {
return segments[selector.index(Objects.requireNonNull(key).hashCode(), segments.length)];
}
@Override public V get(K key) { return segmentFor(key).get(key); }StripedAndCaffeineTest.java; output/06-striped-is-not-global-lru.txt):
StripedLruCache(capacity 4, 2 stripes): even keys -> stripe 0, odd keys -> stripe 1
===================================================================================
put(1) put(0) put(2) put(4) // key 1 is the globally least recently used
get(0) -> null (evicted: stripe 0 held {0,2} and was full)
get(1) -> present (a strict global LRU would have evicted it instead)
size() = 3 of capacity 4 (evicted while not full)A real bug I wrote and then measured. My firstsegmentForwas the obvious one: take the key’s hash, spread it,floorModby the number of stripes. With 16 stripes that sends every key with the same low four bits to the same stripe — and inside the stripe, theHashMappicks a bucket from the same low bits. So the 128 keys of one stripe used 8 of its 128 buckets. The cache was correct and slower than the coarse lock in every timing I took (roughly two to three times in a quick loop, with the same 50% hit ratio). The fix is to choose the stripe from different bits (multiply by the golden-ratio constant, take the high bits). Both selectors are kept in the repository so you can see the difference (output/08-stripe-selector-buckets.txt):
Keys 0..2047 that land in segment 0 of 16: how many distinct buckets of that segment's 128-slot HashMap do they use?
====================================================================================================
(bucket = (h ^ (h >>> 16)) & 127, the formula java.util.HashMap uses; computed arithmetically, not by reflection)
LOW_BITS keys in segment 0: 128 buckets used: 8 of 128 longest bucket: 16 keys
MIXED keys in segment 0: 129 buckets used: 65 of 128 longest bucket: 4 keys
Each of those 8 buckets holds 16 keys: past the treeify threshold of 8 (the table has >= 64 slots), so java.util.HashMap turns them into trees.StripedLruCache.java):
public enum Selector {
LOW_BITS { @Override int index(int hash, int stripes) { return Math.floorMod(hash ^ (hash >>> 16), stripes); } },
MIXED { @Override int index(int hash, int stripes) { return Math.floorMod((hash * 0x9E3779B9) >>> 16, stripes); } };
abstract int index(int hash, int stripes);
/** Public for the bucket-distribution test. */
public int select(int hash, int stripes) { return index(hash, stripes); }
}The stress test that actually asserts something
“I ran it with 8 threads and it did not crash” is not evidence. The stress test in the repository runs 8 threads x 60,000 operations (80%get, 20% put) against a 64-entry cache over 256 keys, so eviction fires constantly, while a separate monitor thread polls size() as fast as it can. Then it asserts five facts (ConcurrencyStressTest.java):
assertEquals(0, exceptions.get(), name + ": worker threw");
assertEquals(0, wrongValues.get(), name + ": get returned another key's value");
assertFalse(oversize.get(), name + ": size() exceeded capacity");
c.check();
assertTrue(cache.size() <= cache.capacity());
String post = "n/a (per-segment LRU)";
if (globalLru) {
// After the storm, one thread inserts `capacity` brand-new keys: they must be exactly what remains, in order.
List<Integer> expected = new ArrayList<>();
for (int k = 1000; k < 1000 + CAPACITY; k++) { cache.put(k, valueFor(k)); expected.add(k); }
assertEquals(expected, cache.keysLruFirst());
c.check();
post = "ok";
}k is always k * 31 + 7, so a get that returns another key’s value is detected, not just a thrown exception. The last check is the strongest: after the storm, a single thread inserts exactly capacity new keys and the cache must contain precisely those, in order, with a valid list. A corrupted list or index would fail it. The result (output/05-concurrency-stress.txt):
8 threads x 60000 ops (80% get / 20% put), capacity 64, 256 keys
================================================================
implementation exceptions wrong values size>capacity seen? invariants post-stress LRU check
SynchronizedLruCache 0 0 no ok ok
ReentrantLockLruCache 0 0 no ok ok
StripedLruCache(8) 0 0 no ok n/a (per-segment LRU)
Hit/miss counts are deliberately not printed: they differ on every run and nothing asserts them.Going deeper: what is still not atomic, and the ConcurrentHashMap approach
- Check-then-act is still yours to handle.
if (cache.get(k) == null) cache.put(k, load(k))is two separately locked calls. Two threads can both miss and both load the same value (a cache stampede for expensive loads). Caffeine solves it withcache.get(key, mappingFunction), which computes at most once per key. size()across stripes is not a snapshot.StripedLruCache.size()adds the segment sizes one after another while other threads keep working.Collections.synchronizedMap(new LinkedHashMap<>(.., true))is the zero-code coarse-lock version. It is correct for single calls and is included in the benchmark. Iterating over it still needs a manualsynchronizedblock, and iteration while another thread callsgethits the structural-modification rule above.- The ConcurrentHashMap approach was not built. The usual sketch is a
ConcurrentHashMapfor lookup plus aConcurrentLinkedDequefor order. Its trouble is that moving a key to the front means removing it from the middle of the deque, andremove(Object)has to search for it, so a hit is O(n). That reasoning comes from the API shape, not from a run, and the repository does not contain that variant. The designs that avoid the problem — buffering access events and replaying them under a lock, as Caffeine does — are a library, not an interview answer. synchronizedand virtual threads. JEP 491 (JDK 24) lets a virtual thread unmount while blocked on a monitor, so the old reason to preferReentrantLockwith virtual threads no longer applies on JDK 24 and later. See the multithreading interview programs for the wider locking toolbox.
How fast is each? A short, honest JMH run
Correctness comes first, speed second, and here speed comes with a large caveat. The harness (LruBenchmark.java) measures the cache-aside pattern: get, and on a miss put, with keys uniform over twice the capacity so about half the lookups hit. JMH 1.37, one fork, 3 warm-up and 5 measured iterations per cell. The sandbox it ran on is shared by ten jobs and had a load average around 24 on 2 vCPUs when the run started, so the figures below are indicative only. Full output: output/10-jmh-indicative.txt.
JMH 1.37 / openjdk version "25.0.5" 2026-10-20 LTS
cores=2 loadavg-at-start=24.40 26.08 18.95 (shared sandbox: INDICATIVE)
workload: get; on miss put. Keys uniform over 2048, capacity 1024. ops/microsecond, higher is better.
### 1 thread, all implementations
Benchmark (impl) Mode Cnt Score Error Units
LruBenchmark.lookupThenFillOnMiss linkedhashmap-unsafe thrpt 5 4.908 ± 0.912 ops/us
LruBenchmark.lookupThenFillOnMiss dll-unsafe thrpt 5 3.946 ± 3.172 ops/us
LruBenchmark.lookupThenFillOnMiss synchronizedMap(LinkedHashMap) thrpt 5 2.619 ± 3.358 ops/us
LruBenchmark.lookupThenFillOnMiss synchronized thrpt 5 2.832 ± 1.957 ops/us
LruBenchmark.lookupThenFillOnMiss reentrantlock thrpt 5 3.089 ± 1.593 ops/us
LruBenchmark.lookupThenFillOnMiss striped16 thrpt 5 2.389 ± 1.758 ops/us
LruBenchmark.lookupThenFillOnMiss striped16-lowbits thrpt 5 1.337 ± 0.436 ops/us
LruBenchmark.lookupThenFillOnMiss caffeine thrpt 5 1.307 ± 2.076 ops/us
### 2 threads, thread-safe implementations only
Benchmark (impl) Mode Cnt Score Error Units
LruBenchmark.lookupThenFillOnMiss synchronizedMap(LinkedHashMap) thrpt 5 2.807 ± 1.557 ops/us
LruBenchmark.lookupThenFillOnMiss synchronized thrpt 5 2.609 ± 1.794 ops/us
LruBenchmark.lookupThenFillOnMiss reentrantlock thrpt 5 2.665 ± 2.561 ops/us
LruBenchmark.lookupThenFillOnMiss striped16 thrpt 5 1.769 ± 1.727 ops/us
LruBenchmark.lookupThenFillOnMiss striped16-lowbits thrpt 5 1.048 ± 0.400 ops/us
LruBenchmark.lookupThenFillOnMiss caffeine thrpt 5 2.248 ± 4.427 ops/us
### 4 threads, thread-safe implementations only
Benchmark (impl) Mode Cnt Score Error Units
LruBenchmark.lookupThenFillOnMiss synchronizedMap(LinkedHashMap) thrpt 5 5.475 ± 5.365 ops/us
LruBenchmark.lookupThenFillOnMiss synchronized thrpt 5 4.926 ± 3.010 ops/us
LruBenchmark.lookupThenFillOnMiss reentrantlock thrpt 5 4.230 ± 3.008 ops/us
LruBenchmark.lookupThenFillOnMiss striped16 thrpt 5 2.399 ± 1.785 ops/us
LruBenchmark.lookupThenFillOnMiss striped16-lowbits thrpt 5 1.256 ± 0.635 ops/us
LruBenchmark.lookupThenFillOnMiss caffeine thrpt 5 1.821 ± 1.796 ops/us- The unsynchronised
LinkedHashMapcache scored highest at one thread (4.9 ops/µs), as expected from doing the least work. synchronized,ReentrantLockandCollections.synchronizedMapare indistinguishable here. That matches the reasoning above: three spellings of one lock.- Throughput did not fall as threads went from 1 to 4 for the coarse locks (4 threads even scored higher). On a 2-vCPU machine under heavy external load, that is noise and scheduling, not a finding. Do not conclude that contention is free.
- The one gap I trust for a reason other than this table is the striped cache with the naive selector (
striped16-lowbits), which was the slowest thread-safe hand-written variant at every thread count. The bucket-distribution transcript above explains why, and a separate throw-away timing loop I ran while debugging showed the same direction; the JMH intervals alone do overlap. - Caffeine scored low here. This workload is half misses, each followed by a write, on a loaded 2-vCPU machine with Caffeine’s default executor. Caffeine is designed around read-heavy hit paths and I did not tune or investigate this result, so it says nothing about Caffeine in your service.
scripts/run-jmh.sh on an idle machine with at least as many cores as your threads, raise the iteration counts, and replace the uniform key distribution with one that resembles your traffic.
What to use in production: Caffeine
Everything above is an exercise. In a real service you want expiry, statistics, a loading function that computes once per key, and an eviction policy chosen for hit rate. That is Caffeine. The latest GA on Maven Central at the time of writing is 3.3.1, and it was the version used here. Its adapter in the repository is five lines (CaffeineLru.java):
public CaffeineLru(int capacity, boolean sameThread) {
this.capacity = capacity;
Caffeine<Object, Object> b = Caffeine.newBuilder().maximumSize(capacity);
if (sameThread) b.executor(Runnable::run);
this.cache = b.build();
}
public CaffeineLru(int capacity) { this(capacity, false); }maximumSize(3) with a same-thread executor, so the result is deterministic (output/07-caffeine-same-ops.txt):
Caffeine 3.3.1 maximumSize(3) given the dry-run operations (same-thread executor, cleanUp after each)
====================================================================================================
put(1,A) -> resident keys (unordered): [1]
put(2,B) -> resident keys (unordered): [1, 2]
put(3,C) -> resident keys (unordered): [1, 2, 3]
get(1) -> resident keys (unordered): [1, 2, 3]
put(4,D) -> resident keys (unordered): [1, 2, 4]
get(2) -> resident keys (unordered): [1, 2, 4]
put(3,C2) -> resident keys (unordered): [1, 2, 3]
put(5,E) -> resident keys (unordered): [1, 2, 5]
get(4) -> resident keys (unordered): [1, 2, 5]
get(1) -> resident keys (unordered): [1, 2, 5]
A strict LRU of capacity 3 ends this sequence with [3, 5, 4] (see 01-dry-run-capacity-3.txt).Caffeine is a better cache, not a faster LRU. If an interviewer asks for an LRU, give them an LRU. If a service asks for a cache, give it Caffeine. Mixing the two up — shipping a hand-rolled LRU, or expecting strict LRU order from Caffeine — is the mistake.
Should you even build this yourself? Only for an interview, a teaching exercise, or a tiny single-threaded memo table where LinkedHashMap is plenty. Not for anything shared across request threads. The coarse-lock version is correct but serialises every call; the striped version needs careful hashing and gives up exact LRU; and neither has expiry, metrics or stampede protection. The benchmark above was run on a heavily loaded sandbox and cannot settle which is fastest on your hardware — measure with your own key distribution before choosing anything over the coarse lock, and use a library when the cache matters.
FAQ
What is an LRU cache?
A bounded cache that evicts the least recently used entry when it is full. Both reads and writes count as use.
How do you implement an LRU cache in Java?
The shortest way is LinkedHashMap with accessOrder=true and removeEldestEntry returning size() > capacity. Without it, combine a HashMap from key to node with a doubly linked list that keeps nodes in recency order, using sentinel head and tail nodes.
Why is LRU cache get and put O(1)?
The hash map finds a node in expected O(1) time, and a doubly linked list can unlink and relink a node in a fixed number of pointer writes because each node knows both neighbours. In the repository’s measurement a hit costs 6 pointer writes at 10, 1,000 and 100,000 entries.
Why use a doubly linked list instead of a singly linked list?
To remove a node from the middle in O(1) you need its predecessor. A singly linked list would have to search for it; a doubly linked list stores it.
Is LinkedHashMap thread-safe?
No. In access-order mode even get modifies the structure, so concurrent use needs external synchronisation, for example Collections.synchronizedMap or a lock around your own wrapper.
Can I use a ReadWriteLock for an LRU cache?
Not for get. A hit rewrites list pointers, so it must run under an exclusive lock. In this page’s demo, a read-locked get left the cache with a broken structure in several rounds out of five.
synchronized or ReentrantLock for a thread-safe LRU cache?
They give the same parallelism here, which is none: one lock guards everything. Choose ReentrantLock only if you need tryLock, timeouts or fairness. Since JDK 24, synchronized no longer pins virtual threads either.
What is the best LRU cache library for Java?
Caffeine. It is bounded, thread-safe and has expiry and loading built in, but it uses Window TinyLFU rather than strict LRU.
Further reading
- Companion code, tests, transcripts and JMH harness: java-interview-lab / lru-cache
- Understanding LinkedHashMap in Java
- HashMap vs ConcurrentHashMap in Java
- Java Multithreading Programs for Interviews
- Java Collections Framework: Choosing the Right Data Structure
- LinkedHashMap, Java SE 25 API
- Caffeine: Efficiency (Window TinyLFU)
- JEP 491: Synchronize Virtual Threads without Pinning
- JMH, the Java Microbenchmark Harness
No Comments yet!