Caché LRU: hash map y lista enlazada trabajando juntos

Una caché tiene lugar para $k$ elementos y en algún momento se llena. Ahí aparece la pregunta que define todo: cuál se tira. La política LRU —least recently used— tira el que hace más tiempo que nadie toca.

Suena simple hasta que hay que implementarla: para saber cuál se usó hace más tiempo hace falta un orden, y para encontrar una clave hace falta un índice. Ninguna estructura sola da las dos cosas en tiempo constante.

Por qué una estructura sola no alcanza

La clave está en la tercera fila: mover un nodo al frente de una lista doblemente enlazada cuesta $O(1)$ si ya tenés el nodo en la mano. Y el hash map es exactamente lo que te lo pone en la mano.

El invariante

La estructura sostiene una sola promesa, y todas las operaciones la mantienen:

De ahí salen las tres operaciones:

La caché, paso a paso

La implementación

Toda la complejidad está en dos funciones privadas: desenganchar un nodo y engancharlo al frente. El resto es combinarlas.

interface CacheNode<K, V> {
  key: K;
  value: V;
  previous: CacheNode<K, V> | null;
  next: CacheNode<K, V> | null;
}

class LruCache<K, V> {
  private readonly nodesByKey = new Map<K, CacheNode<K, V>>();
  private head: CacheNode<K, V> | null = null;
  private tail: CacheNode<K, V> | null = null;

  constructor(private readonly capacity: number) {
    if (capacity < 1) throw new Error('Una caché necesita capacidad para al menos un elemento.');
  }

  get(key: K): V | undefined {
    const node = this.nodesByKey.get(key);
    if (!node) return undefined;
    this.detach(node);
    this.attachToFront(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.nodesByKey.get(key);
    if (existing) {
      existing.value = value;
      this.detach(existing);
      this.attachToFront(existing);
      return;
    }
    if (this.nodesByKey.size === this.capacity) this.evictLeastRecentlyUsed();
    const node: CacheNode<K, V> = { key, value, previous: null, next: null };
    this.nodesByKey.set(key, node);
    this.attachToFront(node);
  }

  private evictLeastRecentlyUsed(): void {
    const leastUsed = this.tail;
    if (!leastUsed) return;
    this.detach(leastUsed);
    this.nodesByKey.delete(leastUsed.key);
  }

  private detach(node: CacheNode<K, V>): void {
    if (node.previous) node.previous.next = node.next;
    else this.head = node.next;
    if (node.next) node.next.previous = node.previous;
    else this.tail = node.previous;
    node.previous = null;
    node.next = null;
  }

  private attachToFront(node: CacheNode<K, V>): void {
    node.next = this.head;
    if (this.head) this.head.previous = node;
    this.head = node;
    this.tail ??= node;
  }
}

Qué cuesta

LRU no siempre es la política correcta

Cierre