How it works
The spec models a Map as a list of records, [[MapData]]. Four algorithm details make the LRU work:
Map.prototype.set walks the list; if a live entry has the same key (SameValueZero, after CanonicalizeKeyedCollectionKey turns -0 into +0), it overwrites [[Value]] and returns. Only otherwise does it append a new record.
Map.prototype.delete doesn't remove the record. It sets the entry's key and value to the spec value empty, a tombstone. A note says implementations may physically remove it instead.
CreateMapIterator walks the list from index 0 and skips empty entries, so the first value it yields is the oldest live key.
- Sublinear access. The section intro says the list is only a description of observable behaviour and that real implementations must give sublinear average access time.
So "delete then set" really is "move to the end", and "first iterated key" really is "least recently used":
const m = new Map([['a', 1], ['b', 2]]);
m.set('a', 10);
console.log([...m.keys()]); // → [ 'a', 'b' ]
m.delete('a');
m.set('a', 10);
console.log([...m.keys()]); // → [ 'b', 'a' ]
In V8 (from its source, not the spec), Map and Set use OrderedHashTable, based on the "deterministic hash table" design: hash buckets point into a data table where entries sit in insertion order. A new entry is written at the end of the data table; a deleted entry leaves a hole and increments a deleted-element count. When the data table is full, V8 rehashes into a new table, at the same capacity if at least half the slots are holes, otherwise doubled. An LRU's churn fills the table with holes that a rehash eventually clears.
The cost shows up in eviction. V8's iterator builtin (NextSkipHashTableHoles) starts at slot 0 and steps over every hole, and an LRU deletes its oldest key on every eviction, so holes pile up exactly at the front. Measured on Node 24.19 (V8 13.6) with a 20,000-entry Map, keys().next() took about 90 ns; after the first 10,000 keys were deleted, about 7 µs. An eviction-heavy benchmark of the example's class went from about 0.5 µs per set at capacity 1,000 to about 8.5 µs at 10,000, while the linked-list version below stayed near 0.1 µs. These numbers are one machine's, but the trend follows from the source.
Edge cases
- Stored
undefined. get returns undefined for both a miss and a cached undefined; callers who need the distinction need a has method on the cache, or a sentinel.
- Key equality is SameValueZero.
NaN works as a key and -0/+0 are one key. Objects compare by identity, so two equal-looking argument arrays are two keys; that's the same keying problem memoization has.
- Capacity validation. A capacity of 0 or
NaN would make set evict immediately or never; throwing a RangeError in the constructor is clearer than either.
- Iterating while mutating. Map iterators are live: a key moved to the end during a
for...of over the Map is visited again, so "touch every entry" in a loop never ends. Snapshot with [...map.keys()] first.
Real-world scenario
A memoized function with unbounded storage leaks: every distinct argument stays forever. Bounding it with an LRU keeps the hot results and drops the rest, which suits lookups with a skewed access pattern (recently used keys are likely to be reused): parsed templates, compiled regexes, resolved module paths, formatted dates. Swap the memo Map for an LRUCache with the same get/set/has surface and the memoizer doesn't change.
When the interviewer asks for guaranteed O(1), says "don't rely on Map ordering", or the cache is large and eviction-heavy, write the textbook version. The Map is only an index; order lives in a doubly linked list with sentinel nodes, so every operation is a constant number of pointer updates:
class LinkedLRU {
#capacity;
#index = new Map(); // key → node: lookup only, never order
#head = {}; // sentinel before the least recent node
#tail = {}; // sentinel after the most recent node
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;
}
#append(node) {
node.prev = this.#tail.prev;
node.next = this.#tail;
node.prev.next = node;
this.#tail.prev = node;
}
get(key) {
const node = this.#index.get(key);
if (!node) return undefined;
this.#unlink(node);
this.#append(node);
return node.value;
}
set(key, value) {
const existing = this.#index.get(key);
if (existing) this.#unlink(existing);
const node = { key, value };
this.#index.set(key, node);
this.#append(node);
if (this.#index.size > this.#capacity) {
const oldest = this.#head.next;
this.#unlink(oldest);
this.#index.delete(oldest.key);
}
return this;
}
}
Trade-offs
The Map version is about 20 lines and hard to get wrong; it leans on spec-defined ordering and on the engine's hash table. A get costs up to four hash operations (has, get, delete, set); drop the has when undefined is never a valid value. It's a fine answer for small caches. The linked-list version costs one node object per entry and more code, but its constant-time bound doesn't depend on how the engine treats deleted entries, and it ports to any language. Both are single-threaded structures with no notion of entry size; caches that bound memory rather than count, or need TTLs and statistics, usually come from a maintained library.