Cache Eviction
01 / The shared mechanism
A fixed-capacity store with O(1) get and put. The trick is the data structure: every eviction policy is a different answer to which entry do I drop when the cache is full? Two classic ones share the same O(1) trick — LRU pairs a hash map with a doubly-linked list so the just-touched key can be moved to the front in constant time; LFU tracks per-key frequency in buckets so the lowest-frequency bucket is always reachable in O(1).
02 / The one-sentence essence
The just-touched node moves to the head; the tail is the eviction candidate. Hash map gives O(1) lookup; doubly-linked list gives O(1) splice. Together: O(1) per op.
Problemdesign an LRU cache with O(1) get / putcap4ops8
Empty cache, capacity 4. About to run 8 ops.
step
0 / 12
op
—
size / cap
0 / 4
0 / 12
03 / The pattern signature
# state: capacity, map: key → node, list: head ↔ … ↔ taildef get(k):if k not in map: return −1node ← map[k]splice(node); pushFront(node)return node.valdef put(k, v):if k in map:node ← map[k]; node.val ← vsplice(node); pushFront(node); returnnode ← Node(k, v); map[k] ← nodepushFront(node)if len(map) > capacity: # overflowevicted ← popBack(); del map[evicted.key]
04 / When to recognize this pattern
"fixed capacity + O(1) get/put"
The textbook signature of an LRU cache. If a problem hand-waves about caching but insists both operations are constant-time, that's a tell — a single hash map or a single list won't do it. You need both, wired into each other.
"least-recently-used eviction"
The recency signal lives in the list order, not in any timestamp. Every read or write moves the touched node to the head, so the tail is always the one that hasn't been touched in the longest. No timestamps, no scanning — the list does the ordering for you.
"move-to-front feel"
LC 432 (All O`one), LC 1756 (Most Recently Used Queue) — different problems, same rhythm: a hash map points into a linked structure so the touched element can jump to a known end in O(1). The trick generalizes well past LRU.
05 / Common pitfalls
Forgetting to delete the map entry after eviction.
When the tail gets popped, you must also
del map[evicted.key] — otherwise the map still claims the cache holds that key, and a later get happily returns a stale node that no longer lives in the list. The list and the map have to stay in lock-step.Off-by-one on the capacity check.
The eviction trigger is
size > capacity, not ≥. Insert first, then evict if overflowed — that way you always have room for the new node. Flip the order or the comparison and you either lose the newly inserted entry or never evict at all.Skipping the splice on a put-update.
Updating an existing key still counts as a touch — the LRU policy doesn't care whether the operation read or wrote, only that it happened. Forget to move the updated node to the head and your eviction order drifts away from real recency, quietly. The bug shows up only when a later put overflows.
06 / Go practice — on LeetCode
Four problems. LRU Cache is the canonical implementation. LFU Cache keeps the same map + linked-list trick but stacks one more layer to track frequency. All O`one generalizes the move-to-front mechanic to handle both min and max in O(1). First Unique Number applies the same hash + linked structure to a streaming uniqueness problem.
— / When to use which
LRU
Use when recency is the signal that matters — the entry you used most recently is the one most likely to be used again. Hash map maps key → node; doubly-linked list keeps the order. Get and put each touch O(1) pointers and one map lookup.
hashmap + doubly-linked list · LC 146
LFU
Use when frequency matters — a hot key with many recent hits should survive even if a never-touched-again key was inserted last. Hash map → node; per-frequency bucket lists; a `minFreq` pointer to the bucket holding the next eviction candidate. O(1) at the cost of more bookkeeping.
hashmap + frequency buckets · LC 460