The Codex / Projects / Caching Layer (LRU) / JavaScript
Tier 4 — Advanced

Caching Layer (LRU)

Build a Least-Recently-Used cache that remembers results and evicts the oldest when full — the caching every system uses.

🐍 Python 🟨 JavaScript

1. The Problem

Build an LRU (Least-Recently-Used) cache with a fixed capacity. get returns a stored value and marks it as freshly used; put stores a value and, when over capacity, evicts whichever key was used longest ago.

Why this project? LRU is the eviction policy behind CPU caches, browser caches, and Redis. The trick is tracking usage order cheaply — a real data-structure problem in a real-world wrapper.

2. How to Think About This

JavaScript's Map remembers insertion order, and that is exactly what we exploit: on every access, delete the key and re-insert it so it moves to the "most recent" end. When put pushes the size over capacity, the least-recently-used key is the first one the Map yields — map.keys().next().value — so delete that.

3. The Build

lru.mjs
export class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();   // Map preserves insertion order = usage order
  }

  get(key) {
    if (!this.cache.has(key)) return null;
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);   // move to most-recent end
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const oldest = this.cache.keys().next().value;   // least recently used
      this.cache.delete(oldest);
    }
  }
}

const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a");        // 'a' now most recent
cache.put("c", 3);     // full -> evicts 'b'
console.log("a:", cache.get("a"));   // 1
console.log("b:", cache.get("b"));   // null (evicted)
console.log("c:", cache.get("c"));   // 3

4. Test & Prove

lru.test.mjs
import { LRUCache } from "./lru.mjs";

let pass = 0, fail = 0;
function test(desc, fn) {
  try { fn(); console.log("  \u2713", desc); pass++; }
  catch (e) { console.log("  \u2717", desc, "\u2014", e.message); fail++; }
}
function assert(cond, msg) { if (!cond) throw new Error(msg || "assertion failed"); }

test("a stored value is returned (hit)", () => {
  const c = new LRUCache(2); c.put("a", 1);
  assert(c.get("a") === 1);
});
test("a missing key returns null (miss)", () => {
  assert(new LRUCache(2).get("x") === null);
});
test("the least recently used item is evicted when full", () => {
  const c = new LRUCache(2);
  c.put("a", 1); c.put("b", 2);
  c.get("a");          // 'b' now least recent
  c.put("c", 3);       // evicts 'b'
  assert(c.get("b") === null);
  assert(c.get("a") === 1);
  assert(c.get("c") === 3);
});
test("updating an existing key does not grow the cache", () => {
  const c = new LRUCache(2);
  c.put("a", 1); c.put("a", 99);
  assert(c.cache.size === 1 && c.get("a") === 99);
});

console.log(`\n${pass} passed, ${fail} failed`);

5. The Interface

node lru.mjs

a: 1
b: null
c: 3

6. Run It

node lru.mjs
node lru.test.mjs

🎯 Try this next

  1. Add a hit/miss counter to measure the cache\u2019s effectiveness
  2. Wrap a slow function so its results are memoised through the cache
  3. Add a time-to-live (TTL) so entries expire after N seconds
  4. Switch the eviction policy to LFU (least frequently used) and compare

What you practised

Using Map\u2019s insertion-order guarantee to track recency, the delete+re-insert trick to promote a key, and capacity-based eviction \u2014 the core of every real cache.

Reference: Maps · Functions · Hash Tables

Try It Yourself