Design Patterns & LLD

Design an LRU Cache and a Hash Map

Chaining and resize, a map plus doubly linked list, TTL, and stampede control.

Lesson 0630 min read#lru#hash-map#ttl

In one line: an LRU cache is a hash map plus a doubly linked list: the map finds an entry in O(1), the list keeps the entries in order of use so you can move one to the front, or drop the oldest, in O(1). Build the hash map first (buckets, collisions, resize) and the cache stops being magic.

"Design an LRU cache" is one of the most common coding-plus-design questions. The system-design-primer lists two neighbours of it in its object-oriented section: design a hash map and design a least recently used cache. This lesson does both, then adds the two follow-ups interviewers love: expiry (TTL) and thread safety.

If a term below is new, the data structure lessons come first: hash tables in DSA Lesson 15, Basic Hashing and doubly linked lists in DSA Lesson 35, Building a Linked List. The same LRU as a short whiteboard answer is in Practical Design Problems, Lesson 7, and where caches live in a real system (and the eviction rules LRU, LFU and others) is in System Design, Lesson 16. This lesson is the class design and code view. Pattern names come from Lesson 3, and SOLID from Lesson 0.

What I ran / checked. All code below ran on Node 22.22 (built-in type stripping, so no enums or constructor parameter properties) and the tests use node:test. I read both primer notebooks (hash_table/hash_map and lru_cache) directly. Their constraints: the hash map uses integer keys, chaining, and ignores load factors; the LRU caches web query results and assumes it fits in memory. The primer's LRU code is a sketch: the linked-list methods are # ..., get is missing a colon, and set reads tail.query, a field its Node never has. I wrote and ran my own version instead. Nothing here is benchmarked, so I make no speed claims beyond Big-O.

Words used in this lesson

Hash function turns a key into a whole number. The same key must always give the same number.
Bucket is one slot in the table's array. Collision is when two different keys land in the same bucket.
Chaining is a way to handle collisions: each bucket holds a small list, and you search that list.
Load factor is entries / buckets. When it gets too high, chains get long and lookups slow down.
Resize (rehash) means making a bigger array and putting every entry in again, because hash % bucketCount changes.
Sentinel node is a fake node at each end of a linked list so that "no neighbour" never needs a special case.
TTL (time to live) is how long an entry may stay before it counts as expired.
Cache stampede is when many callers miss the same key at once and all of them go to the slow source.

Part 1. Design a hash map

Requirements (my assumptions): set(key, value), get(key), delete(key), all O(1) on average. Keys are strings or numbers. Collisions use chaining. The table grows by itself.

How it works: index = hash(key) % buckets.length. Each bucket is an array of { key, value }. Lookup walks one short chain. When entries / buckets goes above 0.75, I double the bucket count and place every entry again.

JavaScript

type Entry<K, V> = { key: K; value: V };// FNV-1a: a small, well-known string hash (32-bit).export function fnv1a(s: string): number {  let h = 0x811c9dc5;  for (let i = 0; i < s.length; i++) {    h ^= s.charCodeAt(i);    h = Math.imul(h, 0x01000193) >>> 0;  }  return h;}export class HashMap<K extends string | number, V> {  private buckets: Entry<K, V>[][];  private count = 0;  private readonly maxLoad: number;  private readonly hashFn: (key: K) => number;  constructor(initialBuckets = 8, maxLoad = 0.75, hashFn?: (key: K) => number) {    this.buckets = Array.from({ length: initialBuckets }, () => []);    this.maxLoad = maxLoad;    this.hashFn = hashFn ?? ((k) => (typeof k === "number" ? Math.abs(k | 0) : fnv1a(k)));  }  get size(): number {    return this.count;  }  get bucketCount(): number {    return this.buckets.length;  }  private indexFor(key: K, n = this.buckets.length): number {    return this.hashFn(key) % n;  }  get(key: K): V | undefined {    for (const e of this.buckets[this.indexFor(key)]) if (e.key === key) return e.value;    return undefined;  }  set(key: K, value: V): void {    const chain = this.buckets[this.indexFor(key)];    for (const e of chain) {      if (e.key === key) {        e.value = value; // update in place, size does not change        return;      }    }    chain.push({ key, value });    this.count++;    if (this.count / this.buckets.length > this.maxLoad) this.resize(this.buckets.length * 2);  }  delete(key: K): boolean {    const chain = this.buckets[this.indexFor(key)];    const i = chain.findIndex((e) => e.key === key);    if (i === -1) return false;    chain.splice(i, 1);    this.count--;    return true;  }  // Every key must be placed again, because index = hash % bucketCount changed.  private resize(newSize: number): void {    const next: Entry<K, V>[][] = Array.from({ length: newSize }, () => []);    for (const chain of this.buckets) {      for (const e of chain) next[this.indexFor(e.key, newSize)].push(e);    }    this.buckets = next;  }  longestChain(): number {    return Math.max(...this.buckets.map((c) => c.length));  }}

Points to say out loud:

Why O(1) "on average" and not always: if every key lands in one bucket, the chain has n items and a lookup is O(n). A good hash function and a resize rule keep chains short. The test below forces the bad case on purpose.
Why resize costs O(n) but is still fine: it happens only when the size doubles. Spread over all the inserts, the cost per insert is still O(1) on average. This is called amortised O(1).
The primer's version skips resize (it fixes the table size and says no need to worry about load factors). That is a fair first answer. Adding resize is the senior upgrade.
Keys are compared with ===. That is fine for strings and numbers. For object keys you would need equals and hashCode together. If two keys are equal, their hashes must be equal.
JavaScript already has Map. In an interview you are asked to build one because the point is to show you understand it. In real code, use Map.

Part 2. Design an LRU cache

Requirements: a cache of fixed capacity. get(key) returns the value or nothing, and counts as a use. put(key, value) adds or updates, and counts as a use. When the cache is full and a new key arrives, remove the least recently used entry. Both operations must be O(1).

Why these two structures:

Need	Structure	Cost
Find an entry by key	Hash map: key to node	O(1)
Know which entry is oldest	Linked list ordered by use	O(1) at the ends
Move an entry to "most recent"	Doubly linked list (we hold the node and its two neighbours)	O(1)
Delete the oldest	`tail.prev`	O(1)

A singly linked list cannot unlink a node in O(1), because you do not know the previous node. A plain array cannot move an item in O(1). That is the whole trick.

JavaScript

class Node<K, V> {  key: K;  value: V;  prev: Node<K, V> = this as unknown as Node<K, V>;  next: Node<K, V> = this as unknown as Node<K, V>;  constructor(key: K, value: V) {    this.key = key;    this.value = value;  }}export class LRUCache<K, V> {  private readonly map = new Map<K, Node<K, V>>();  // Two sentinel nodes mean "no neighbour" never needs a special case.  private readonly head = new Node<K, V>(undefined as K, undefined as V); // head.next = most recent  private readonly tail = new Node<K, V>(undefined as K, undefined as V); // tail.prev = least recent  private readonly capacity: number;  constructor(capacity: number) {    if (!Number.isInteger(capacity) || capacity < 1) throw new RangeError("capacity must be an integer >= 1");    this.capacity = capacity;    this.head.next = this.tail;    this.tail.prev = this.head;  }  get size(): number {    return this.map.size;  }  private unlink(n: Node<K, V>): void {    n.prev.next = n.next;    n.next.prev = n.prev;  }  private pushFront(n: Node<K, V>): void {    n.next = this.head.next;    n.prev = this.head;    this.head.next.prev = n;    this.head.next = n;  }  get(key: K): V | undefined {    const n = this.map.get(key);    if (!n) return undefined;    this.unlink(n); // O(1): we hold the node, so we know both neighbours    this.pushFront(n);    return n.value;  }  put(key: K, value: V): void {    const existing = this.map.get(key);    if (existing) {      existing.value = value;      this.unlink(existing);      this.pushFront(existing);      return;    }    if (this.map.size === this.capacity) {      const lru = this.tail.prev;      this.unlink(lru);      this.map.delete(lru.key);    }    const n = new Node(key, value);    this.map.set(key, n);    this.pushFront(n);  }  delete(key: K): boolean {    const n = this.map.get(key);    if (!n) return false;    this.unlink(n);    this.map.delete(key);    return true;  }  keysMostRecentFirst(): K[] {    const out: K[] = [];    for (let n = this.head.next; n !== this.tail; n = n.next) out.push(n.key);    return out;  }}

The two sentinel nodes (head and tail) are worth a sentence: unlink and pushFront have no if (prev === null) cases, so there are fewer bugs. The map stores the node, not the value, so a hit gives us the node to move.

The JavaScript shortcut

A Map remembers insertion order. So "delete the key and set it again" moves it to the end, and map.keys().next().value is the oldest key. That gives an LRU in about 15 lines (MapLRU, shown below). Some interviewers accept it. Others will say "now do it without relying on that", so know both. In the test below I run 20,000 random operations against both versions and check they always agree.

JavaScript

// The short version: a JS Map remembers insertion order, so "delete then set" moves a key to the end.export class MapLRU<K, V> {  private readonly m = new Map<K, V>();  private readonly capacity: number;  constructor(capacity: number) {    this.capacity = capacity;  }  get(key: K): V | undefined {    if (!this.m.has(key)) return undefined;    const v = this.m.get(key)!;    this.m.delete(key);    this.m.set(key, v);    return v;  }  put(key: K, value: V): void {    this.m.delete(key);    this.m.set(key, value);    if (this.m.size > this.capacity) this.m.delete(this.m.keys().next().value as K); // oldest key  }  keysMostRecentFirst(): K[] {    return [...this.m.keys()].reverse();  }}

Running it

JavaScript

import { HashMap } from "./hashmap.ts";import { LRUCache } from "./lru.ts";import { TtlLRU } from "./ttl.ts";const m = new HashMap<string, number>(4);const seen: number[] = [m.bucketCount];for (let i = 0; i < 100; i++) {  m.set("key" + i, i);  if (m.bucketCount !== seen[seen.length - 1]) seen.push(m.bucketCount);}console.log("bucket counts as 100 keys were added:", seen.join(" -> "));console.log("size", m.size, "longest chain", m.longestChain(), "get key42 =", m.get("key42"));const c = new LRUCache<string, number>(3);c.put("a", 1); c.put("b", 2); c.put("c", 3);console.log("order after a,b,c      :", c.keysMostRecentFirst().join(" "));c.get("a");console.log("order after get(a)     :", c.keysMostRecentFirst().join(" "));c.put("d", 4); // evicts b, the least recently usedconsole.log("order after put(d)     :", c.keysMostRecentFirst().join(" "), "| get(b) =", c.get("b"));let t = 0;const ttl = new TtlLRU<string, string>(2, 1000, () => t);let loads = 0;const load = async (k: string) => { loads++; await new Promise((r) => setTimeout(r, 5)); return k.toUpperCase(); };const r = await Promise.all([ttl.getOrLoad("x", load), ttl.getOrLoad("x", load), ttl.getOrLoad("x", load)]);console.log("3 callers got", r.join(","), "with", loads, "load call");t = 999; console.log("t=999 ", ttl.get("x"));t = 1000; console.log("t=1000", ttl.get("x"));

TEXT

$ node demo.tsbucket counts as 100 keys were added: 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 256size 100 longest chain 2 get key42 = 42order after a,b,c      : c b aorder after get(a)     : a c border after put(d)     : d a c | get(b) = undefined3 callers got X,X,X with 1 load callt=999  Xt=1000 undefined

Read the order lines: after a, b, c the most recent is c. get(a) moves a to the front. put(d) has to evict, and the victim is b, the one at the back. So get(b) is undefined.

The bucket line shows the table doubling from 4 up to 256 as 100 keys were added, and the longest chain stayed at 2.

Part 3. The TTL variant

New requirement: each entry expires after a fixed time. A lookup after that time must act as a miss.

Two ways to remove expired entries:

Way	How	Trade-off
Lazy	Check the time when someone calls `get`; if expired, delete it	No background work. Dead entries that nobody asks for stay until the LRU rule pushes them out.
Active sweep	A timer scans for expired entries	Frees memory sooner. Costs CPU, and a full scan is O(n). Needs a way to stop it.

I chose lazy, because it is the simple answer and it still never returns a stale value. If the interviewer asks about memory, I add a sweep, or I keep entries also in a min-heap by expiry time so I can pop the oldest-expiring ones. The clock is injected (now), so tests do not sleep.

JavaScript

import { LRUCache } from "./lru.ts";type Stamped<V> = { value: V; expiresAt: number };// LRU + time to live. Expired entries are removed lazily, when someone asks for them.export class TtlLRU<K, V> {  private readonly inner: LRUCache<K, Stamped<V>>;  private readonly ttlMs: number;  private readonly now: () => number;  private inflight = new Map<K, Promise<V>>();  constructor(capacity: number, ttlMs: number, now: () => number = Date.now) {    this.inner = new LRUCache(capacity);    this.ttlMs = ttlMs;    this.now = now;  }  put(key: K, value: V): void {    this.inner.put(key, { value, expiresAt: this.now() + this.ttlMs });  }  get(key: K): V | undefined {    const hit = this.inner.get(key);    if (!hit) return undefined;    if (this.now() >= hit.expiresAt) {      this.inner.delete(key); // expired: remove it now, do not keep a dead entry      return undefined;    }    return hit.value;  }  // Many callers asking for the same missing key share ONE load (stops a cache stampede).  async getOrLoad(key: K, load: (k: K) => Promise<V>): Promise<V> {    const cached = this.get(key);    if (cached !== undefined) return cached;    let p = this.inflight.get(key);    if (!p) {      p = load(key)        .then((v) => {          this.put(key, v);          return v;        })        .finally(() => this.inflight.delete(key));      this.inflight.set(key, p);    }    return p;  }}

getOrLoad is the second half of this class. If ten requests ask for the same missing key at the same moment, they all share one load promise through the inflight map. This prevents a cache stampede. The demo above printed 3 callers got X,X,X with 1 load call, and t=999 was a hit while t=1000 was a miss. The rule is now >= expiresAt, so an entry with TTL 1000 is gone at 1000.

Thread safety

What "thread safe" means depends on the runtime. I would say this in an interview:

Situation	What can go wrong	Fix
Node, one thread	Every method here is synchronous, so another call cannot run in the middle of `put`. The code is safe as written. But with an `await` between a miss and the `put`, two callers both load.	Share the in-flight promise (`getOrLoad`, above).
Several threads (Java, Go, C++, Node worker threads)	`get` writes too (it moves the node), so even a "read" changes the list. Two threads can corrupt the pointers.	One lock around `get` and `put`, or split the cache into N shards each with its own lock, or use a library cache built for this.
Several processes or servers	Each has its own copy.	A shared cache such as Redis. Then it is a system design question, see the system design series.

I did not write a multi-threaded version here, and I did not run one. The point of the table is to show that you know a read is a write in an LRU.

A common mistake: putting a read-write lock on an LRU. get moves a node, so it is a write. A read lock lets two "readers" change the list at once.

Testing it

The most useful tests are shown here: the random comparison of the two LRU versions, and the TTL edge. Two more tests (not shown) force collisions with a hash function that always returns 7, and set 1,000 keys into a table that starts with 2 buckets to prove resize keeps every key.

JavaScript

test("lru: the linked-list version and the Map version agree on random operations", () => {  let seed = 42; // small deterministic random generator  const rand = (n: number) => ((seed = (Math.imul(seed, 1103515245) + 12345) >>> 0) % n);  const a = new LRUCache<number, number>(5);  const b = new MapLRU<number, number>(5);  for (let i = 0; i < 20000; i++) {    const k = rand(12);    if (rand(2) === 0) { a.put(k, i); b.put(k, i); }    else assert.equal(a.get(k), b.get(k));    assert.deepEqual(a.keysMostRecentFirst(), b.keysMostRecentFirst());  }});test("ttl: entry dies at its expiry time", () => {  let t = 0;  const c = new TtlLRU<string, number>(2, 100, () => t);  c.put("a", 1);  t = 99; assert.equal(c.get("a"), 1);  t = 100; assert.equal(c.get("a"), undefined);});

TEXT

$ node --test --test-reporter=spec lru.test.ts | LC_ALL=C sed 's/\xE2\x9C\x94/pass/; s/\xE2\x84\xB9/#/'pass hash map: set, get, update, delete (2.032633ms)pass hash map: collisions share a bucket and still work (0.290529ms)pass hash map: resize keeps every key (5.084397ms)pass lru: evicts the least recently used (2.073749ms)pass lru: put on an existing key updates and refreshes (0.278921ms)pass lru: capacity 1 and bad capacity (0.651053ms)pass lru: the linked-list version and the Map version agree on random operations (29.321072ms)pass ttl: entry dies at its expiry time (0.469099ms)pass ttl: an expired entry is removed, not just hidden (0.424086ms)pass ttl: getOrLoad shares one load between concurrent callers (8.162222ms)# tests 10# suites 0# pass 10# fail 0# cancelled 0# skipped 0# todo 0# duration_ms 269.276246

All ten tests, including capacity 1, a bad capacity and the shared in-flight load, appear in the output above. The most useful one is the random comparison: a second, simpler implementation is a good judge of a clever one.

Interview questions

Why a doubly linked list and not a singly linked one? (Must know)

To move or remove a node in O(1) I need its previous node. In a doubly linked list the node knows it. In a singly linked list I would have to walk from the head to find the previous node, which is O(n). The map gives me the node directly, so the double link is what makes the whole thing O(1).

Why store nodes in the map and not values? (Must know)

Because on a hit I must move that node to the front, and I need the node itself to do that in O(1). The map entry also lets me delete the right key when I evict: the tail node carries its own key, so I can call map.delete(lru.key). This is the line the primer's sketch gets wrong, since its Node has no key field.

How does a hash map handle collisions? (Must know)

I use chaining: each bucket holds a small list, and I compare keys inside it. The other common way is open addressing, where a collision moves to another slot in the same array (for example the next free one). Chaining is simpler to delete from. Open addressing is friendlier to the CPU cache but needs care with deletes and a lower load factor.

Why do you resize, and what does it cost? (Senior signal)

Without resize, the load factor grows and chains get long, so lookups drift from O(1) toward O(n). I double the bucket count when the load factor goes over 0.75 (a common choice; the exact number is a trade between memory and chain length). Resize touches every entry, so one insert costs O(n), but because the size doubles each time, the average cost per insert stays O(1).

Why must you recompute every index during a resize? (Trap)

Because the index is hash % bucketCount. When the bucket count changes, the same hash gives a different index. Copying the old buckets over would make get look in the wrong place. My test sets 1,000 keys into a table that starts with 2 buckets and reads them all back.

What if the key hashes are all the same? (Trap)

Then everything lands in one chain and the map becomes a linked list: O(n). I forced this in a test with a hash function that returns 7. Real defences are a good hash function, and (in some languages) a random seed so attackers cannot craft colliding keys. I would say the seed point as general knowledge, not something I tested here.

How do you add a TTL? (Must know)

Store expiresAt with each value. On get, compare it with the current time; if it has passed, delete the entry and return a miss. That is lazy expiry. I inject the clock so tests can step time by hand. If memory matters, I add a periodic sweep or a min-heap ordered by expiry.

What is a cache stampede and how do you stop it? (Senior signal)

Many callers miss on the same key together, and all hit the slow source. I keep a map from key to the in-flight promise. The first caller starts the load and stores the promise. Later callers wait on the same promise. After it finishes, the entry is removed from the map. My test shows two concurrent callers causing one load. (In a multi-server setup, this only dedupes within one server.)

Is your LRU thread safe? (Must know)

In Node with one thread, yes, because each method is synchronous. In a multi-threaded language, no. The key detail is that get mutates the list, so a read-write lock does not help. I would use one mutex, or shard the cache by key hash into several smaller caches, each with its own lock. I have not run a multi-threaded version.

LRU, LFU or FIFO? (Senior signal)

LRU removes the entry unused for the longest time. LFU removes the one used the fewest times. FIFO removes the oldest inserted. LRU is the usual default because recent use predicts near-future use for many workloads. It can be hurt by a one-time scan of lots of keys that pushes out the useful ones. LFU keeps frequently used items but can hold old popular items too long. I would choose by looking at the real access pattern, not by habit.

Key takeaways

A hash map is an array of buckets plus a hash function. Collisions share a bucket (chaining). A resize rehashes every key because the index depends on the bucket count.
O(1) on average depends on short chains: a good hash and a load factor limit.
LRU cache = map from key to node + doubly linked list in use order. Sentinel nodes remove edge cases. Store the key inside the node so eviction can clean the map.
A Map-only LRU is a valid short answer. Test it against the long version.
TTL: store expiresAt, check on get, inject the clock. Lazy expiry is simplest.
A cache read changes order, so it is a write. That matters for locks.
Share in-flight loads to avoid stampedes.

What's next

Next: Lesson 7, Design a Vending Machine and an Elevator (State Machines). Practise: add an EvictionPolicy interface to LRUCache, write an LFU version, and run the same random-comparison test against a slow, obviously correct reference.

Published by Jainik · Last updated 11 Oct 2026 · How these lessons are made

Keep learning

Related lessons

Design an LRU Cache, Idempotent Payments and Other Classic Mini-Problems · Practical Design Problems

Part of the study guide

Design Patterns and Low-Level Design Guide

Related series

On this page

Words used in this lesson

Part 1. Design a hash map

Part 2. Design an LRU cache

The JavaScript shortcut

Running it

Part 3. The TTL variant

Thread safety

Testing it

Interview questions

Key takeaways

What's next

Keep learning