The LFU Cache: O(1) Eviction of Your Least-Used Keys

The core idea and the invariant

An LFU cache stores at most capacity key–value pairs. Every get(key) and successful put(key, val) increments that key's access frequency. When the cache is full and a brand-new key arrives, LFU evicts the key with the lowest frequency count. If several keys tie at the minimum frequency, the standard rule breaks the tie with LRU among them — evict the least recently used of the coldest keys.

The whole design hangs on one invariant that must hold after every operation:

• minFreq invariant: the integer minFreq always equals the smallest frequency count of any key currently in the cache. Eviction is therefore just "remove one key from bucket minFreq" — no search required.

Maintaining that invariant in O(1) is the entire trick. It's cheap to raise because a hit moves exactly one key up by one; it's the potential lowering after an insert (a new key enters at frequency 1) and the potential raising after a bucket empties that you must handle without scanning.

The O(1) data structure: two levels of linked lists

The canonical structure — popularized by the 2010 paper "An O(1) Algorithm for Implementing the LFU Cache Eviction Scheme" by Shah, Mitra, and Matani — nests two hash maps over doubly linked lists:

• nodeMap: key → Node. Each Node holds {key, value, freq} plus prev/next pointers. This gives O(1) lookup by key.
• freqMap: frequency → doubly linked list of Nodes. Every node in bucket f has been accessed exactly f times. Within a bucket, order encodes recency: insert at the head (most recent), evict from the tail (least recent). That's how the LRU tie-break falls out for free.
• minFreq: an integer tracking the smallest non-empty bucket.

Each frequency bucket is an ordered list, so a bucket is really a mini-LRU. The two-level nesting — a map of frequencies, each mapping to a recency-ordered list — is what makes both dimensions (how often, how recently) O(1) to update. Some implementations replace the frequency hash map with a linked list of "frequency groups" so you can walk to the next-higher frequency in O(1); the map version is simpler and just as fast in practice.

Step-by-step: get and put

Promotion — the shared helper that bumps a node's frequency by one:

promote(node):
  f = node.freq
  freqMap[f].remove(node)            # O(1), we hold the node
  if f == minFreq and freqMap[f].empty():
    minFreq += 1                     # minFreq bucket drained → next is f+1
  node.freq = f + 1
  freqMap[f+1].pushFront(node)       # head = most recent

get(key):

• If key ∉ nodeMap, return −1 (miss).
• Otherwise fetch the node, call promote(node), and return its value.

put(key, value):

• If capacity == 0, do nothing.
• If key exists: overwrite the value and promote it.
• If it's new and the cache is full: evict the tail of freqMap[minFreq] (least-recently-used among least-frequent) and delete it from nodeMap.
• Insert the new node at freq = 1, push it to the front of freqMap[1], and — crucially — set minFreq = 1, because any freshly inserted key is by definition the new minimum.

Notice the two places minFreq changes: it can only rise inside promote (when the min bucket empties) and it snaps back to 1 on every fresh insert. There is no scan anywhere.

Why it's O(1): the amortization that isn't needed

Unlike a dynamic-array or splay-tree cache, LFU's constant time here is worst-case, not amortized. Every operation touches a bounded number of pointers:

• Hash lookups in nodeMap and freqMap are O(1) expected (O(n) pathological, same caveat as any hash table).
• Doubly-linked-list splices — remove a node given its pointer, push to a head, pop a tail — are each O(1) because we never search a list; the node's address comes straight from nodeMap.
• minFreq maintenance is O(1): it increments by at most one per promotion and resets to 1 on insert. It never decreases below 1 and never needs to search for "the next smallest bucket," because a drained min bucket is always followed by f+1, which the promoted node just populated.

Space is Θ(capacity): one node per cached key, one small hash-table entry per key, and one bucket-list header per distinct live frequency (at most capacity of them). No structure grows with the total number of requests, only with the number of resident keys. Contrast the heap-based LFU: it also needs O(n) space but pays O(log n) per access because a hit is an increase-key that must sift through the heap — asymptotically worse and with far chattier cache-line behavior.

LFU vs LRU: when frequency beats recency

LRU and LFU answer different questions. LRU asks "who was used longest ago?"; LFU asks "who was used least often?" The right choice depends on whether your workload's popularity is stable or drifting.

• LFU wins on skewed, stable popularity. Under a Zipfian request distribution — CDN objects, DB page buffers, DNS records — a small hot set accounts for most traffic. LFU pins those high-count keys and resists scan / flush pollution: a one-off sweep of cold keys (a backup job, a full-table scan) enters at frequency 1 and gets evicted first, without disturbing the hot set. LRU, by contrast, is famously wrecked by a sequential scan that touches everything once and pushes the whole working set out.
• LRU wins on temporal locality and phase changes. If access patterns shift over time — yesterday's hot key is today's cold key — LFU's problem surfaces: stale high counts. A key that was hammered for an hour and then abandoned keeps a huge count and refuses to leave, wasting a slot. LRU adapts instantly because recency is self-correcting.

This is exactly why production caches rarely ship pure LFU. Real systems use aging / decay (periodically halve every count, or use a windowed count) so old popularity fades, or hybrid policies like LFU-with-Dynamic-Aging (LFUDA), LRFU (a tunable blend), and ARC (adaptive replacement).

Where LFU runs in the wild

Approximate, aged LFU is one of the most deployed cache policies in modern infrastructure — almost never in its textbook form, because exact per-key counters cost memory and pure LFU can't forget.

• Redis offers allkeys-lfu / volatile-lfu eviction. It doesn't store a full 32-bit count per key; it packs an 8-bit logarithmic counter (whose growth rate is tuned by the lfu-log-factor parameter) plus a decay timer into the object's 24-bit LRU field, giving probabilistic increments and time-based aging in a few bits.
• Caffeine (the Java caching library behind Spring, Cassandra, and others) uses Window-TinyLFU: a Count-Min Sketch estimates frequencies in sublinear space, an admission filter compares a candidate's estimated frequency against the eviction victim's, and periodic reset (halving) ages the sketch. It routinely beats LRU's hit ratio on real traces.
• Database buffer pools and CDNs lean on LFU-family policies (LFUDA, GDSF) to keep hot pages/objects resident against scan-heavy analytical queries.
• LeetCode 460 "LFU Cache" is the interview canon — implement get/put in O(1) with the frequency-bucket design above, tie-breaking on recency.

Pitfalls, edge cases, and variants

The O(1) LFU is unforgiving of small mistakes — a mis-tracked minFreq silently evicts the wrong key.

• capacity = 0. Guard it: put must be a no-op and never insert. A forgotten check dereferences an empty min bucket on the next eviction.
• Tie-break correctness. When two keys share minFreq, you must evict the least recently used — the tail of the bucket. Reversing head/tail conventions silently flips the policy; test with a case where LRU is the discriminator (LeetCode 460's sample exercises exactly this).
• Updating minFreq on hit. Only bump minFreq when the promoted node was in the minFreq bucket and that bucket is now empty. Bumping it unconditionally corrupts the invariant.
• put on an existing key. It's an update, not an insert — overwrite the value and promote; do not re-run eviction and do not reset minFreq = 1.
• Cold-start / one-hit-wonder bias. New items enter at frequency 1 and are evicted before they can prove worth, so a genuinely-about-to-be-popular key can be killed prematurely. TinyLFU's admission policy addresses this by only admitting a newcomer if its sketch-estimated frequency exceeds the victim's.
• Counter overflow & unbounded growth. Exact 64-bit counters won't overflow in practice, but they never decay — hence real systems use logarithmic or windowed counters plus periodic halving to bound values and let popularity drift.

Eviction policies and LFU implementation strategies compared by cost and behavior

Approach	get	put / evict	Extra space	Notes
LFU — linear scan	O(1)	O(n) to find min	O(n)	Simple but eviction dominates
LFU — min-heap by count	O(log n)	O(log n)	O(n)	Increase-key needed on every hit
LFU — freq-bucket DLL	O(1)	O(1)	O(n)	Optimal; the canonical answer
LRU — hash + DLL	O(1)	O(1)	O(n)	Recency, not frequency; scan-vulnerable
TinyLFU (Caffeine)	O(1)	O(1)	O(n) sketch	Approximate counts via Count-Min sketch