Cairn
data structures · hash map + per-frequency doubly linked lists · O(1) get and put

↩ back to Hash-Based

LFU Cache

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.

Try it

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.

Loaded with capacity 3 and keys a, b, c put in order, then a looked up twice and c looked up once — that's why a sits alone at freq 3, c alone at freq 2, and b is the lone (and so lowest-frequency) occupant of freq 1, marked as the next eviction. Try get("b") and watch it move up to freq 2 next to c.

Core operations

Reference implementation

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.

Pitfalls

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.

Press "Run race" to count real element touches for both implementations over a fill-then-churn workload held at the chosen capacity.

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.

Where LFU caches show up

Complexity

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.