Building an LRU Cache

The plain-language idea

An LRU (Least Recently Used) cache holds a fixed number of items. Once it's full, adding a new one has to evict something — and the something it picks is whatever hasn't been read or written in the longest time. It's the policy your browser cache, a CDN, and Redis's allkeys-lru mode all use: keep what's hot, throw away what's gone cold.

The interesting part isn't the eviction rule — it's building get and put so both run in O(1). Reach for a plain array and you're stuck doing indexOf or a manual scan to find "least recently used," which is O(n). The trick in JavaScript is that Map already keeps its keys in insertion order, and lets you delete and re-insert a key cheaply. Insertion order becomes recency order, for free.

See it in a real thing: an LRUCache class

class LRUCache {
  #capacity;
  #map = new Map();

  constructor(capacity) {
    this.#capacity = capacity;
  }

  get(key) {
    if (!this.#map.has(key)) return -1;
    const value = this.#map.get(key);
    // Move it to the "most recent" end: delete then re-insert.
    this.#map.delete(key);
    this.#map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.#map.has(key)) this.#map.delete(key);
    this.#map.set(key, value);
    if (this.#map.size > this.#capacity) {
      // The first key iterated is the oldest untouched one.
      const oldestKey = this.#map.keys().next().value;
      this.#map.delete(oldestKey);
    }
  }
}

const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a");        // touches "a" — now "b" is the oldest
cache.put("c", 3);     // evicts "b", not "a"
cache.get("b");        // -1, it's gone

Every operation here — has, get, delete, set, and reading the first key via the iterator — is O(1) on a Map. No scanning, no sorting, no second data structure to track order separately.

What people usually miss

Watch out

• A get is a mutation, not just a read. Reading a value counts as "using" it, so get has to re-insert the key too — miss this and your eviction order silently tracks insertion time instead of actual recency.
• Checking capacity in the wrong order. Insert first, then evict if over capacity — not the reverse. Evicting before inserting can wrongly kick out an item when the cache had room the whole time.
• Reaching for an array and indexOf. It works, but every get becomes an O(n) linear scan to find and reorder the item. The whole point of this exercise is realizing Map's ordering guarantee turns that into O(1).

The genealogy: caching with a policy, not caching forever

This is the same instinct as memoization — trade memory for avoiding repeated work — but memoization typically caches every result forever and never throws anything away. An LRU cache adds the piece memoization skips: a size limit, and a rule for what to evict once you hit it. Real systems almost always need that second part; unbounded memoization is a memory leak waiting for enough distinct inputs.