LRU cache in 40 lines

Implement a Least Recently Used (LRU) cache with O(1) get and set. The insight: JavaScript’s Map maintains insertion order, making the eviction logic trivial.

The Problem

An LRU cache holds up to N items. When a new item is inserted and the cache is full, the least recently used item is evicted. Any time an item is accessed (get or set), it becomes the most recently used.

Classic implementations use a doubly-linked list + hashmap. JavaScript’s Map replaces both.

The Implementation

class LRUCache {
  #capacity;
  #cache;

  constructor(capacity) {
    this.#capacity = capacity;
    this.#cache = new Map();
  }

  get(key) {
    if (!this.#cache.has(key)) return -1;
    const value = this.#cache.get(key);
    this.#cache.delete(key);
    this.#cache.set(key, value);
    return value;
  }

  set(key, value) {
    if (this.#cache.has(key)) {
      this.#cache.delete(key);
    } else if (this.#cache.size >= this.#capacity) {
      const oldest = this.#cache.keys().next().value;
      this.#cache.delete(oldest);
    }
    this.#cache.set(key, value);
  }
}

Why Map Works

Map.keys() returns keys in insertion order. The first key is always the oldest. When we need to evict, .keys().next().value gives it in O(1).

To “refresh” an item (mark it as recently used), delete it and re-insert. Since we re-insert at the end, it becomes the newest.

Usage

const cache = new LRUCache(3);
cache.set("a", 1);
cache.set("b", 2);
cache.set("c", 3);
cache.get("a"); // 1 — 'a' is now most recent
cache.set("d", 4); // evicts 'b' (least recently used)

Why It Matters

LRU caches appear in every system that needs bounded memoization — API response caches, database query caches, image caches. Understanding the pattern makes you comfortable reasoning about any cache.