What you should do next
Once you have the data structure — manual DLL or LinkedHashMap — the correctness baseline for thread safety is synchronized on every public method. Nothing else changes. Start here before reaching for ReadWriteLock, striping, or ring buffers.
The simplest thread-safe LRU
Add synchronized to every public method. Nothing else changes.
class LRUCache {
private final HashMap<Integer, Node> map;
private final int capacity;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.map = new HashMap<>();
this.capacity = capacity;
}
public synchronized int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
moveToTail(node);
return node.value;
}
public synchronized void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
moveToTail(node);
return;
}
if (map.size() == capacity) {
map.remove(head.key);
head = head.next;
if (head != null) head.prev = null;
else tail = null;
}
Node node = new Node(key, value);
map.put(key, node);
// ... append to tail
}
}The same pattern applies to a LinkedHashMap subclass — synchronized on get and put — shown in the previous chapter.
What synchronized actually gives you
Putting synchronized on a method acquires the intrinsic lock of this on entry and releases it on exit. That one lock provides three guarantees simultaneously:
Mutual exclusion — only one thread executes inside any synchronized method at a time. No two threads can interleave their pointer rewires.
Memory visibility — on lock release, all writes made inside the synchronized block are flushed to main memory. On lock acquisition, the thread’s CPU cache is invalidated and it reads fresh values. Thread B will never see a stale node.value written by Thread A.
Happens-before ordering — the Java Memory Model guarantees that everything Thread A did before releasing the lock is visible to Thread B after it acquires the same lock. This prevents instruction reordering from breaking initialization sequences.
Why it is correct
Every get and put is an atomic unit from the perspective of all other threads. No thread can observe the cache mid-operation — the map and the linked list always move together. The size check, eviction, and insertion in put are never interrupted.
The cost
The intrinsic lock on this is one lock for the entire cache. Every operation — read or write — contends on it.
Thread 1: get(A) → acquires lock ──────────────── releases lock
Thread 2: get(B) → waits ───────── acquires lock ─ releases lock
Thread 3: put(C) → waits ──────────────── waits ─ ...Even two independent reads that would not interfere at all are forced to execute serially. On a 16-core machine, throughput is bounded by a single thread — the cache becomes a bottleneck under any meaningful concurrency.
When this is the right answer
- Cache is accessed infrequently (config lookups, per-request caches).
- Simplicity and correctness matter more than throughput.
- Used in the same thread or with external synchronization.
- Starting point before measuring whether the lock is actually contended.
Always start here. Optimize only after profiling confirms the lock is the bottleneck.