Cairn
data structures · hash map + doubly linked list · O(1) get and put

↩ back to Hash-Based

LRU Cache

An LRU (least recently used) cache is a fixed-size box that remembers a limited number of key/value pairs, and when it's full and something new comes in, it evicts whichever entry has gone longest untouched. The trick is doing both halves of that job — "look up a key instantly" and "know instantly which entry is oldest" — at the same time, in O(1), using two structures already on this site that are individually weak at the other's strength.

A hash map alone gives you O(1) lookup by key, but no memory of order — nothing about a plain map tells you which entry hasn't been touched in the longest time without scanning all of it. A linked list alone gives you O(1) reordering — unlink a node, relink it at the front — but finding that node by key means walking the chain, O(n). Put them together: the map stores key → node so any node is reachable in O(1), and a doubly linked list (each node points both prev and next) lets that node unlink itself and jump to the front in O(1) once found — no walking required, since the map skipped straight to it.

Try it

The capacity below is 3. get a key to look it up (and, if found, promote it to most-recently-used); put a key/value to insert or update it. The chain runs most-recently-used (left) to least-recently-used (right) — when a put would push the cache over capacity, the rightmost node is evicted. The map beneath it lists exactly the keys currently findable in O(1), independent of chain order.

Loaded with capacity 3 and keys 1, 2, 3 inserted in order, then key 1 looked up — that's why 1 is most-recently-used even though it was inserted first. Try put("4", "d") next and watch which key gets evicted.

Core operations

Reference implementation

class LRUCache {
  #capacity;
  #map = new Map();      // key -> node
  #head = { prev: null, next: null };  // sentinel: head.next is most-recently-used
  #tail = { prev: null, next: null };  // sentinel: tail.prev is least-recently-used

  constructor(capacity) {
    this.#capacity = capacity;
    this.#head.next = this.#tail;
    this.#tail.prev = this.#head;
  }

  #unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  #insertAtFront(node) {
    node.next = this.#head.next;
    node.prev = this.#head;
    this.#head.next.prev = node;
    this.#head.next = node;
  }

  get(key) {
    if (!this.#map.has(key)) return undefined;
    const node = this.#map.get(key);
    this.#unlink(node);
    this.#insertAtFront(node);
    return node.value;
  }

  put(key, value) {
    if (this.#map.has(key)) {
      const node = this.#map.get(key);
      node.value = value;
      this.#unlink(node);
      this.#insertAtFront(node);
      return;
    }
    const node = { key, value, prev: null, next: null };
    this.#map.set(key, node);
    this.#insertAtFront(node);
    if (this.#map.size > this.#capacity) {
      const lru = this.#tail.prev;
      this.#unlink(lru);
      this.#map.delete(lru.key);
    }
  }
}

The two sentinel nodes (#head and #tail, never holding real data) exist so #unlink and #insertAtFront never have to special-case an empty list or a list with one node — there's always a real node on both sides of any relink, even when the cache is empty. Verified with 20,000 randomized interleaved get/put trials (small key space, small capacities to force frequent eviction) against a naive array-of-entries reference model, checking the returned value from every get, the exact set of keys present, and the most-recently-used-to-least order after every single operation, plus edge cases (capacity 1, repeated put on the same key, get on an empty cache, filling to exactly capacity with no eviction). Then re-verified by extracting the page's own shipped get/put logic (the array-based model driving the demo above) verbatim out of the HTML and running an equivalent 20,000-trial pass directly against it, confirming the shipped page and the class above agree on every observable outcome. See /tmp/lru_test.js and /tmp/lru_page_verify.js, scratch, not committed.

Pitfalls

Forgetting that get also has to move the node. It's tempting to treat get as read-only and only promote on put — but a cache that never refreshes recency on read isn't tracking usage at all, just insertion order. The whole point of LRU is that reading something protects it from eviction; skip the promotion in get and you've quietly built a different (and usually worse) eviction policy while still calling it "LRU."

Relinking only one direction. A doubly linked list's whole advantage is that either neighbor can be reached from a node directly — but that means every unlink or insert has to fix up both the prev and next pointers on both sides. Fix only one direction (say, update node.prev.next but forget node.next.prev) and the list looks fine walked forward while being silently broken walked backward — exactly the kind of bug that survives casual testing and shows up later as a node that won't unlink cleanly.

Letting the map and the list disagree. Every mutation touches both structures — insert a node, and it must go in the map and the chain; evict a node, and it must come out of the map and the chain. Update one and not the other (evict from the chain but forget map.delete, say) and get on the evicted key returns a node that's no longer really part of the cache — this site's own "keep it in sync" trap that the linked list page's tail-pointer pitfall warns about in miniature, just with two structures to keep honest instead of one pointer.

Measure it instead of taking "map + list buys you O(1)" on faith. The demo above is driven by exactly the kind of array a beginner reaches for first — order.findIndex(e => e.key === key) plus splice/unshift — which is correct but O(capacity) per call, not O(1). This race fills a cache to capacity, then runs capacity more rounds of put-ing a brand-new key — a one-time-use key stream with no repeats, so every lookup before insertion is a guaranteed miss across the whole array — and counts every real element touched: the array-scan version above against the map-plus-sentinel-nodes LRUCache class shown in the Reference implementation.

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 array-scan version touches 2,999,000 elements (every call scans up to the full array and shifts it on insert); the map-plus-list class touches 16,000 (a fixed handful of pointer writes and map operations per call, regardless of capacity) — a 187.4x difference. That ratio isn't fixed: at capacity = 200 it's 37.4x, and at capacity = 5,000 it's 937.4x, growing roughly linearly with capacity because the array version's cost per call is O(capacity) while the map-plus-list version's stays flat — the same "looks like O(1), isn't" shape the stated complexity below depends on actually being true, not just asserted.

Where LRU caches show up

Recency isn't the only bet a fixed-size cache can make about which entry to evict. LFU Cache bets on total popularity instead — evict whoever's been touched the fewest times overall, not whoever's gone longest untouched — at the cost of one doubly linked list per frequency value instead of this page's single chain.

Complexity

Time: both get and put are O(1) — one map lookup plus a constant number of pointer relinks, regardless of how many entries the cache holds. Space: O(capacity) — one map entry and one node per cached key, plus the two fixed sentinel nodes. The whole point of the pairing is that neither structure alone gets you O(1) on both operations, but together they do, at the cost of keeping two structures instead of one perfectly in sync.

That bound says nothing about hit rate, though — see Choosing a Cache Eviction Policy for a measured workload where this page's own eviction rule costs real hits that LFU Cache wouldn't, and one where the reverse is dramatically true instead.

This site's guide, Choosing a Hash Table Collision Strategy, sets this entry aside from the four it actually compares: it's a policy built on top of a hash table (paired with a doubly linked list for eviction order) rather than another way to resolve a collision inside one.