An LRU-Cache von Grund auf bauen

A LRU-Cache (least-recently-used) hoit a feste Anzoi an Einträgen und, wenn er voll is und a neicher Eintrag dazukommen soi, schmeißt er den Eintrag raus, der am längsten ned angriffn worn is. Er taucht überoi auf - Browser-Tab-Verwaltung, Datenbank-Buffer-Pools, functools.lru_cache in Python, In-Memory-API-Response-Caches - und er is a eine der lehrreicheren Datenstrukturen zum Söbabauen, weil die naive Version leicht is und die effiziente Version verlangt, zwoa Strukturen auf bestimmte Art zu kombiniern.

Die naive Version, und warum sie ned gnua is

Die offensichtliche Implementierung is a Array aus { key, value }-Paaren: Bei jedem Zugriff den Eintrag finden, nach vorn schiebn, und wenn da Cache über der Kapazität is, den letzten Eintrag wegschmeißen.

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();
  }
}

Des funktioniert, aber findIndex und splice sand beide O(n). Bei am Cache mit a poar hundert Einträge tut des ned weh, aber der Sinn von am LRU-Cache is meistens, in oam Hot Path zum sitzn - a O(n)-Cache untergräbt viel von seinem eigenen Zweck, sobois n wachst.

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

Die effiziente Implementierung kombiniert zwoa Strukturen:

• Oane Hash Map von Key zu Node, für O(1)-Lookup.
• Oane doppelt verkettete Liste, die Nodes vom meist- bis zum wenigst-kürzlich-genutzten ordnet, für O(1)-Umordnung und -Verdrängung.

De Map gibt dir sofortigen Zugriff auf jeden Node; die verkettete Liste lasst dich den Node nach vorn schiebn oder den Tail wegnehmen, ohne sonst wos zu verschiebn. Koane von beiden Strukturen alloa gibt dir beide Eigenschaften - a Array gibt dir Ordnung, aber ka O(1)-Lookup per Key, und a Map alloa gibt dir Lookup, aber koa Ordnung.

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 - is O(1). Die Sentinel-Nodes head und tail sand a klaner Trick, der erwähnenswert is: Ohne sie verlangt das Einfügen in a leere Liste oda das Entfernen vom letzten Node überoi Sonderfälle mit null-Checks. Mit ihnen is head.next imma "der jüngste echte Node oda der Tail", sodass die Liste aus Code-Sicht nie wirklich leer is.

Ausprobiern

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

A JavaScript-Abkürzung, die ma kennen soit

Wennst in a Umgebung bist, wo du des ned von Hand bauen muasst, behoit Map in JavaScript scho die Einfügereihenfolge und lasst dich an Key neu einfügen, um ihn ans Ende zu schiebn - des bringt dich mit viel weniger Code fost zum 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);
  }
}

Des is a O(1) pro Operation, weil Maps Löschen-und-Neu-Einfügen O(1) is und .keys().next() zum Finden vom ältesten Key O(1) is (es scannt ned - es gibt einfach den ersten Eintrag in Einfügereihenfolge zruck). Für die meisten echten Einsätze is des die Version, die man wirklich ausliefern soit; die Listen-Version oben zahlt si zum einmal Söbabauen aus, damit du vasteht, wos Map unter da Haubn für dich mocht.

Fazit

Da naive Array-basierte LRU is in Ordnung, bis er's ned mehr is - in dem Moment, wo dein Cache am Hot Path hängt und a relevante Größe hot, taucht der O(n)-Lookup- und Umordnungsaufwand in den Profilen auf. Die Kombination aus Hash Map und verketteter Liste is die Standardlösung, und a gutes Beispiel für a allgemeineres Muster: Wenn oane Struktur dir schnelles Lookup gibt und a ondere schnelle Ordnung, und du beides brauchst, wählst ned oane aus - du kombinierst sie und hoitst sie synchron.