Construire un cache LRU à partir de zéro

Un cache LRU (least-recently-used, « le moins récemment utilisé ») conserve un nombre fixe d'éléments et, lorsqu'il est plein et qu'un nouvel élément doit être ajouté, évince celui qui n'a pas été touché depuis le plus longtemps. On le retrouve partout : gestion des onglets du navigateur, pools de tampons de bases de données, functools.lru_cache en Python, caches mémoire de réponses d'API. C'est aussi l'une des structures de données les plus instructives à construire soi-même, car la version naïve est facile, tandis que la version efficace exige de combiner deux structures d'une manière précise.

La version naïve, et pourquoi elle ne suffit pas

L'implémentation évidente est un tableau de paires { key, value } : à chaque accès, on trouve l'élément, on le déplace en tête, et si le cache dépasse sa capacité, on supprime le dernier élément.

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

Cela fonctionne, mais findIndex et splice sont tous deux en O(n). Pour un cache de quelques centaines d'entrées, ce n'est pas gênant ; mais l'intérêt d'un cache LRU est généralement de se trouver sur un chemin critique, et un cache en O(n) perd beaucoup de son intérêt quand n grandit.

La version en O(1) : table de hachage + liste doublement chaînée

L'implémentation efficace combine deux structures :

• Une table de hachage qui associe une clé à un nœud, pour une recherche en O(1).
• Une liste doublement chaînée qui ordonne les nœuds du plus au moins récemment utilisé, pour un réordonnancement et une éviction en O(1).

La table donne un accès instantané à n'importe quel nœud ; la liste chaînée permet de déplacer ce nœud en tête, ou de supprimer la queue, sans rien décaler d'autre. Aucune des deux structures seule ne donne les deux propriétés : un tableau offre l'ordre mais pas la recherche par clé en O(1), et une table seule offre la recherche mais pas l'ordre.

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

Chaque opération (get, put et l'éviction) est en O(1). Les nœuds sentinelles head et tail sont une petite astuce qui mérite d'être soulignée : sans eux, ajouter à une liste vide ou retirer le seul nœud restant exige de traiter des cas particuliers de null partout. Avec eux, head.next est toujours « le nœud réel le plus récent ou la queue », si bien que la liste n'est jamais vraiment vide du point de vue du code.

À l'essai

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

Un raccourci JavaScript à connaître

Si vous êtes dans un environnement où il n'est pas nécessaire de tout écrire à la main, Map en JavaScript conserve déjà l'ordre d'insertion et permet de réinsérer une clé pour la déplacer à la fin, ce qui fait la majeure partie du chemin vers un LRU avec beaucoup moins de code :

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

C'est aussi du O(1) par opération, car la suppression suivie de la réinsertion dans une Map est en O(1), et parcourir .keys().next() pour trouver la clé la plus ancienne est en O(1) (il n'y a pas de balayage : cela renvoie simplement la première entrée dans l'ordre d'insertion). Pour la plupart des usages réels, c'est la version qui vaut la peine d'être livrée ; la version à liste chaînée ci-dessus vaut la peine d'être construite une fois à la main pour comprendre ce que Map fait pour vous en coulisses.

À retenir

Le LRU naïf à base de tableau convient jusqu'au moment où il ne convient plus : dès que votre cache se trouve sur un chemin critique et atteint une taille significative, le coût en O(n) de la recherche et du réordonnancement apparaît dans les profils. La combinaison table de hachage plus liste chaînée est la solution standard, et c'est un bon exemple d'un schéma plus général : quand une structure offre une recherche rapide, qu'une autre offre un ordre rapide et que vous avez besoin des deux, vous n'en choisissez pas une : vous les combinez et vous les gardez synchronisées.