↩ 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.

Core operations

• get(key) — if the map doesn't have key, it's a miss, O(1). If it does, the map hands back the node in O(1); unlink it from wherever it sits in the chain and relink it at the most-recently-used end, also O(1). Reading an entry counts as using it — that's what makes this least recently used rather than least recently inserted.
• put(key, value) — if key is already in the map, update its node's value and promote it exactly like get does. Otherwise, create a new node, insert it at the most-recently-used end, and add it to the map. If that push the cache over capacity, drop the node at the least-recently-used end and remove its key from the map too — both structures have to agree, or the map would hand back a node that's no longer really in the cache.

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.

Where LRU caches show up

• In-process memoization and lookup caches. Anywhere a program caches expensive results (parsed templates, computed hashes, database rows) but can't afford to keep every result forever, an LRU cache bounds memory use while keeping whatever's actually being reused hot.
• Browser and CDN caches. A fixed disk or memory budget for cached pages/ assets, evicting whatever hasn't been requested in the longest time to make room for something new — the same shape as the demo above, just with far more entries.
• Database buffer pools. Databases keep a fixed number of disk pages in memory and need to decide which to evict when a query needs a page that isn't cached; LRU (or a close approximation of it — many real systems trade a little accuracy for cheaper bookkeeping) is a common default policy.
• Language runtime and library caches. Regex compilation caches, DNS resolution caches, and many @memoize-style decorators are LRU caches under the hood, often built exactly this way — a hash map plus a doubly linked list.

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.

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.