Einen LRU-Cache von Grund auf bauen

Ein LRU-Cache (Least Recently Used) hält eine feste Anzahl von Einträgen und wirft, wenn er voll ist und ein neuer Eintrag hinzukommen soll, den Eintrag hinaus, der am längsten nicht angefasst wurde. Man findet ihn überall – Browser-Tab-Verwaltung, Datenbank-Buffer-Pools, functools.lru_cache in Python, In-Memory-Caches für API-Antworten – und er ist zugleich eine der lehrreicheren Datenstrukturen zum Selbstbauen, weil die naive Version einfach ist und die effiziente Version erfordert, zwei Strukturen auf eine bestimmte Weise zu kombinieren.

Die naive Version und warum sie nicht gut genug ist

Die naheliegende Implementierung ist ein Array aus { key, value }-Paaren: Bei jedem Zugriff den Eintrag finden, nach vorne schieben, und wenn der Cache über der Kapazität liegt, den letzten Eintrag entfernen.

class NaiveLRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.items = []; // most recently used at the front
  }

  get(key) {
    const index = this.items.findIndex((item) => item.key === key);
    if (index === -1) return undefined;
    const [item] = this.items.splice(index, 1);
    this.items.unshift(item);
    return item.value;
  }

  put(key, value) {
    const index = this.items.findIndex((item) => item.key === key);
    if (index !== -1) this.items.splice(index, 1);
    this.items.unshift({ key, value });
    if (this.items.length > this.capacity) this.items.pop();
  }
}

Das funktioniert, aber findIndex und splice sind beide O(n). Bei einem Cache mit ein paar hundert Einträgen tut das nicht weh, aber der Sinn eines LRU-Caches ist meist, auf einem Hot Path zu sitzen – ein O(n)-Cache untergräbt viel von seinem eigenen Zweck, sobald n wächst.

Die O(1)-Version: Hash-Map + doppelt verkettete Liste

Die effiziente Implementierung kombiniert zwei Strukturen:

• Eine Hash-Map von Schlüssel auf Knoten, für O(1)-Lookup.
• Eine doppelt verkettete Liste, die Knoten vom zuletzt bis zum am längsten nicht genutzten ordnet, für O(1)-Umsortierung und -Verdrängung.

Die Map gibt sofortigen Zugriff auf jeden Knoten; die verkettete Liste erlaubt es, diesen Knoten nach vorne zu verschieben oder den Schwanz abzutrennen, ohne etwas anderes zu verschieben. Keine der beiden Strukturen allein liefert beide Eigenschaften – ein Array gibt eine Reihenfolge, aber kein O(1)-Lookup per Schlüssel, und eine Map allein gibt Lookup, aber keine Reihenfolge.

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // key -> Node

    // Sentinel head/tail nodes remove the need for null-checks at the edges.
    this.head = new Node(null, null);
    this.tail = new Node(null, null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  #remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  #addToFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.#remove(node);
    this.#addToFront(node);
    return node.value;
  }

  put(key, value) {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.#remove(existing);
      this.#addToFront(existing);
      return;
    }

    if (this.map.size >= this.capacity) {
      const lru = this.tail.prev;
      this.#remove(lru);
      this.map.delete(lru.key);
    }

    const node = new Node(key, value);
    this.map.set(key, node);
    this.#addToFront(node);
  }
}

Jede Operation – get, put und Verdrängung – ist O(1). Die Sentinel-Knoten head und tail sind ein kleiner Trick, den man hervorheben sollte: Ohne sie erfordert das Hinzufügen zu einer leeren Liste oder das Entfernen des letzten verbliebenen Knotens überall Sonderbehandlung mit null-Prüfungen. Mit ihnen ist head.next immer „der jüngste echte Knoten oder der Tail", die Liste ist aus Sicht des Codes also nie wirklich leer.

Ausprobieren

const cache = new LRUCache(3);

cache.put('a', 1);
cache.put('b', 2);
cache.put('c', 3);
cache.get('a');       // touches 'a' — order is now b, c, a
cache.put('d', 4);    // capacity exceeded — evicts 'b', the actual least-recently-used

cache.get('b'); // undefined — evicted
cache.get('a'); // 1 — still present
cache.get('d'); // 4 — still present

Eine JavaScript-Abkürzung, die man kennen sollte

Wenn du in einer Umgebung bist, in der du das nicht von Hand bauen musst: Die Map in JavaScript bewahrt bereits die Einfügereihenfolge und erlaubt es, einen Schlüssel erneut einzufügen, um ihn ans Ende zu verschieben – damit kommt man mit deutlich weniger Code den Großteil des Weges zu einem LRU:

class SimpleLRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value); // re-insert = move to the "most recent" end
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.capacity) {
      this.map.delete(this.map.keys().next().value); // oldest key
    }
    this.map.set(key, value);
  }
}

Auch das ist O(1) pro Operation, weil das Löschen und Wiedereinfügen bei Map O(1) ist und das Iterieren über .keys().next(), um den ältesten Schlüssel zu finden, O(1) ist (es scannt nicht – es gibt nur den ersten Eintrag in Einfügereihenfolge zurück). Für die meisten realen Einsätze ist das die Version, die man tatsächlich ausliefern sollte; die Variante mit verketteter Liste oben lohnt sich einmal von Hand, damit man versteht, was Map hinter den Kulissen für einen tut.

Fazit

Der naive Array-basierte LRU ist in Ordnung, bis er es nicht mehr ist – in dem Moment, in dem dein Cache auf einem Hot Path eine nennenswerte Größe hat, tauchen die O(n)-Kosten für Lookup und Umsortierung in Profilen auf. Die Kombination aus Hash-Map und verketteter Liste ist die Standardlösung und ein gutes Beispiel für ein allgemeineres Muster: Liefert eine Struktur schnellen Lookup und eine andere schnelle Reihenfolge und man braucht beides, wählt man nicht eine aus – man kombiniert sie und hält sie synchron.