An LFU (least frequently used) cache makes a different bet than LRU Cache's. LRU evicts whoever's gone longest without being touched — a bet on recency. LFU evicts whoever's been touched the fewest times overall — a bet on popularity. A key hit a thousand times an hour ago and a key hit once a second ago are tied under LRU's rule the moment a third key arrives untouched since either; LFU keeps the thousand-hit key around regardless of how long ago that was, on the theory that something genuinely popular is more likely to be asked for again than something merely recent.
That bet costs more bookkeeping. LRU only has to know one thing per key — where it sits in a
single recency-ordered chain. LFU has to know a key's exact hit count and be able to find,
in O(1), the single key with the globally lowest count — and if several keys share
that lowest count, break the tie by recency among just those, the same way LRU breaks it among
everyone. The trick is the same shape as LRU's map-plus-list pairing, just one level deeper: instead
of one doubly linked list, keep one per frequency, each ordered most-recently-used to
least exactly like LRU's own chain, plus a plain integer tracking the current lowest frequency in
use anywhere in the cache.
The capacity below is 3. get a key to look it up (and, if found, bump its frequency by one); put a key/value to insert or update it, which also counts as a use. Each row below is one frequency bucket, lowest first; within a bucket, most-recently-used sits on the left. The highlighted chip is the one that would be evicted next — the least-recently-used key in the lowest-numbered bucket.
key, it's a miss,
O(1). If it does, that's a use: unlink the node from its current frequency's list,
increment its frequency, and relink it at the most-recently-used end of the new
frequency's list (creating that list if it doesn't exist yet) — all O(1). If this
emptied the old frequency's list and that frequency was the current minFreq, the new
minimum is exactly minFreq + 1, since every other key already had a frequency at
least that high.key is already present, update its value
and bump its frequency exactly like get does; updating an existing entry still
counts as a use. Otherwise, if the cache is at capacity, evict the least-recently-used node in the
minFreq list (its tail) from both that list and the key map. Either way, insert the
new key at the most-recently-used end of the frequency-1 list and reset minFreq to 1
— a brand-new key is, by definition, the newest member of the lowest possible frequency.class LFUCache {
#capacity;
#map = new Map(); // key -> node {key, value, freq, prev, next}
#freqMap = new Map(); // freq -> { head, tail, size } (sentinel doubly linked list)
#minFreq = 0;
constructor(capacity) {
this.#capacity = capacity;
}
#getList(freq) {
if (!this.#freqMap.has(freq)) {
const head = { prev: null, next: null };
const tail = { prev: null, next: null };
head.next = tail;
tail.prev = head;
this.#freqMap.set(freq, { head, tail, size: 0 });
}
return this.#freqMap.get(freq);
}
#unlink(node, freq) {
node.prev.next = node.next;
node.next.prev = node.prev;
const list = this.#freqMap.get(freq);
list.size--;
if (list.size === 0) {
this.#freqMap.delete(freq);
if (this.#minFreq === freq) this.#minFreq++;
}
}
#insertFront(node, freq) {
const list = this.#getList(freq);
node.next = list.head.next;
node.prev = list.head;
list.head.next.prev = node;
list.head.next = node;
list.size++;
}
#touch(node) {
this.#unlink(node, node.freq);
node.freq++;
this.#insertFront(node, node.freq);
}
get(key) {
if (!this.#map.has(key)) return undefined;
const node = this.#map.get(key);
this.#touch(node);
return node.value;
}
put(key, value) {
if (this.#capacity === 0) return;
if (this.#map.has(key)) {
const node = this.#map.get(key);
node.value = value;
this.#touch(node);
return;
}
if (this.#map.size >= this.#capacity) {
const list = this.#freqMap.get(this.#minFreq);
const victim = list.tail.prev;
this.#unlink(victim, this.#minFreq);
this.#map.delete(victim.key);
}
const node = { key, value, freq: 1, prev: null, next: null };
this.#map.set(key, node);
this.#insertFront(node, 1);
this.#minFreq = 1;
}
}
Every list here uses the same two-sentinel trick as LRU Cache's own chain — a fixed
head/tail pair that's never real data, so #unlink and
#insertFront never special-case an empty or single-node bucket. Verified with 20,000
randomized interleaved get/put trials (capacities 1-5, small key spaces to force frequent eviction
and frequency ties) against a naive array-of-entries reference model that linearly scans for
(min freq, oldest-touched) on every eviction — checking the returned value from every
get and the exact key set present after every single operation — plus edge cases
(capacity 0, capacity 1, a repeated put on the same key counting as a use, and a direct
check that frequency ties break by recency rather than arbitrarily). The Try-it demo above runs a
second, independent implementation (plain arrays per frequency bucket instead of linked lists,
simpler to read for a small on-page demo) — re-verified against the same naive model over another
10,000 trials to confirm the simpler demo code and the class above always agree. See
/tmp/lfu_test.js and /tmp/lfu_demo_verify.js, scratch, not committed.
Forgetting that put on an existing key is also a use. It's tempting
to treat an update as "just overwrite the value" and skip the frequency bump, since nothing about
updating a value obviously demands it. But an LFU cache that doesn't count updates as uses will
systematically undercount keys that get written to often but read rarely — a counter being
incremented in place, say — making them look artificially evictable. The contract (and the one this
page's own reference implementation and demo both follow) is: any touch that confirms a key is
still in use, read or write, counts.
Letting minFreq go stale. The whole point of tracking it as a plain
integer instead of scanning for the minimum every time is that it's cheap to maintain incrementally
— but only if every place a frequency-1 (or frequency-minFreq) bucket can empty out
actually updates it. Miss the update inside #unlink specifically (say, by only setting
it on eviction and not on the ordinary promotion that happens inside get) and
minFreq can point at a frequency with no keys left in it at all — the next eviction
reads this.#freqMap.get(this.#minFreq), gets undefined, and throws trying
to read .tail off it.
Breaking frequency ties the wrong way. "Evict the least frequently used key"
is ambiguous the instant two keys share the minimum frequency — which is often, right after a
batch of brand-new keys all start at frequency 1. Picking an arbitrary one of them (whichever a
plain for...of over a Map happens to visit first, say) isn't wrong in the
sense of violating "lowest frequency," but it isn't LFU either — two correct-looking
implementations would then evict different keys from the identical sequence of operations, because
only one of them is also breaking the tie by recency the way this page's reference implementation
does (the list's own tail is always the least-recently-used member of that frequency, not just any
member). An interview-style "is this LFU" check needs to test the tie case specifically, not just
confirm the globally most-used key never gets evicted.
Measure it instead of taking "map plus per-frequency lists buys you O(1)" on faith.
The naive approach this page's own verification tests against — scan every entry for
(min freq, oldest-touched) on each eviction — is correct but O(capacity)
per put, not O(1). This race fills a cache to capacity, then runs
capacity more rounds of put-ing a brand-new key (every one of them a
guaranteed eviction, the same workload shape as LRU Cache's own race), and counts every real
element or pointer touched: the linear-scan version against the map-plus-frequency-buckets
LFUCache class shown above.
At capacity = 1,000 — 1,000 fills, then 1,000 more one-time-use puts — the linear-scan version
touches 1,003,000 elements (every eviction scans the full cache); the
map-plus-frequency-buckets class touches 24,003 (a fixed handful of pointer writes
and map operations per call, regardless of capacity) — a 41.8x difference. Unlike
LRU Cache's version of this same race, the ratio here isn't close to linear in capacity: it's
8.5x at capacity = 200, 41.8x at 1,000, 83.5x at
2,000, and 208.5x at 5,000 — growing faster than capacity itself, because the
naive side's per-eviction scan cost is O(capacity) while its fill phase is also
O(capacity) puts, compounding the two linear terms into something closer to quadratic
against the real side's flat per-call cost.
Time: both get and put are O(1) — one map
lookup plus a constant number of pointer relinks, regardless of how many entries or distinct
frequencies the cache currently holds. Space: O(capacity) — one map
entry and one node per cached key, plus at most one sentinel pair per distinct frequency value in
use (never more than capacity of those, since each one needs at least one key to
exist at all).
The two sibling caches on this site make opposite bets on the same question — which key is "least valuable" when something has to go — and neither is strictly better: LRU is cheaper to reason about (one list, not a map of lists) and wins whenever access patterns cluster in time; LFU costs an extra layer of bookkeeping but wins whenever a key's total popularity is a better predictor of future use than how recently it was last touched. Picking between them is a bet about the real workload, not something either page's own complexity bound can settle.
Choosing a Cache Eviction Policy takes that bet literally: it runs both pages' own shipped classes against two synthetic workloads, one built to favor each, and measures the real hit rates — including a workload where this page's own policy can get permanently stuck at a literal 0% hit rate on a newly-popular set, not just a slow-to-adapt one.