¿Cómo funcionan realmente las políticas de desalojo LRU y LFU, y cuándo conviene usar una sobre la otra?

#Por qué existen las políticas de desalojo

Una caché es finita por definición — eso es lo que la hace rápida, y también es lo que obliga a tomar una decisión en el momento en que se llena: cuando una entrada nueva necesita espacio, ¿cuál entrada existente se descarta? Acertar la respuesta mantiene a la caché absorbiendo la mayor parte de tu tráfico; equivocarla te hace pagar el costo de memoria de cachear sin obtener el beneficio en la tasa de aciertos, porque terminas desalojando cosas justo antes de que fueran a reutilizarse. LRU y LFU son las dos políticas que aparecen constantemente en entrevistas, y optimizan para dos señales genuinamente distintas.

#LRU: Least Recently Used (menos usado recientemente)

La apuesta de LRU es por la recencia: lo que se tocó más recientemente es lo más probable que se vuelva a tocar pronto (esto es "localidad temporal", y se cumple sorprendentemente seguido en cargas de trabajo reales — un usuario navegando la página de un producto probablemente entre a páginas relacionadas en los próximos segundos, no cinco horas después). La implementación clásica combina un hash map (para búsqueda O(1)) con una lista doblemente enlazada (para rastrear el orden de recencia): el frente de la lista es el elemento usado más recientemente, el final es el usado menos recientemente, y cada acceso mueve ese elemento al frente. Cuando la caché está llena, se desaloja el elemento del final — sin necesidad de recorrer nada, porque ya está exactamente en el lugar que hay que eliminar.

class DLLNode<K, V> {
  key: K;
  value: V;
  prev: DLLNode<K, V> | null = null;
  next: DLLNode<K, V> | null = null;

  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
  }
}

class LRUCache<K, V> {
  private capacity: number;
  private map = new Map<K, DLLNode<K, V>>();
  // Nodos centinela: head.next es la entrada más recientemente usada,
  // tail.prev es la entrada menos recientemente usada.
  private head = new DLLNode<K, V>(null as unknown as K, null as unknown as V);
  private tail = new DLLNode<K, V>(null as unknown as K, null as unknown as V);

  constructor(capacity: number) {
    this.capacity = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private detach(node: DLLNode<K, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private attachToFront(node: DLLNode<K, V>): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  get(key: K): V | undefined {
    const node = this.map.get(key);
    if (!node) return undefined;

    this.detach(node);
    this.attachToFront(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.detach(existing);
      this.attachToFront(existing);
      return;
    }

    if (this.map.size >= this.capacity) {
      const leastRecentlyUsed = this.tail.prev!;
      this.detach(leastRecentlyUsed);
      this.map.delete(leastRecentlyUsed.key);
    }

    const node = new DLLNode(key, value);
    this.map.set(key, node);
    this.attachToFront(node);
  }
}

Tanto get como put son O(1): el map da acceso instantáneo al nodo, y separar/reinsertar un nodo en una lista doblemente enlazada es una cantidad fija de actualizaciones de punteros sin importar el tamaño de la lista — sin desplazamientos, sin recorridos.

#LFU: Least Frequently Used (menos usado frecuentemente)

LFU apuesta por una señal distinta: el conteo total de accesos en vez de la recencia. Un elemento accedido 500 veces se queda, aunque su último acceso haya sido hace una hora; un elemento accedido una sola vez queda fuera de prioridad aunque se haya tocado hace treinta segundos. La implementación común en O(1) mantiene un hash map de clave a nodo (como antes), más una segunda estructura: un mapa de conteo de frecuencia a una lista doblemente enlazada con todas las claves que actualmente tienen esa frecuencia, junto con un puntero minFrequency que se mantiene actualizado. En cada acceso, el nodo de una clave se mueve de su bucket de frecuencia actual al bucket frecuencia + 1 (insertado al frente de ese bucket, así los empates dentro de la misma frecuencia se siguen resolviendo por recencia); el desalojo elimina el final del bucket de minFrequency, y minFrequency se incrementa cuando ese bucket se vacía.

#Dónde falla cada una

La debilidad de LRU aparece con la contaminación por escaneo (scan pollution): un único barrido de una sola vez sobre un dataset grande — una exportación por lotes, un job de analítica que hace un full table scan — toca cada fila exactamente una vez, y bajo LRU puro esas lecturas de una sola vez empujan fuera de la caché a todo lo genuinamente caliente, aunque ninguna de las filas escaneadas se vuelva a leer. Por esto exactamente las bases de datos de producción rara vez usan LRU puro para sus buffer pools: PostgreSQL? usa un algoritmo de clock-sweep, y muchos sistemas usan variantes segmentadas o "LRU-K" específicamente para que un solo toque no baste para ganar el lugar de máxima prioridad.

La debilidad de LFU es la imagen espejo: la popularidad obsoleta. Un elemento que se accedió constantemente la semana pasada pero que no se ha tocado desde entonces mantiene un conteo de frecuencia alto y puede negarse a ser desalojado aunque ahora esté completamente frío — mientras tanto, un elemento recién popular arranca en frecuencia 1 y es desalojado antes de tener oportunidad de demostrar su valor. Las implementaciones de LFU en producción típicamente agregan envejecimiento (aging) o decaimiento — reduciendo a la mitad periódicamente todos los conteos de frecuencia, o ponderando más los accesos recientes que los antiguos — específicamente para corregir esto.

#Comparando ambas

Los ingenieros de Java también pueden obtener una caché LRU funcional casi gratis desde la biblioteca estándar: LinkedHashMap soporta un flag accessOrder en el constructor y un hook removeEldestEntry que se puede sobrescribir, que juntos implementan el mismo comportamiento de ordenamiento por recencia sin construir la lista enlazada a mano. Es un atajo perfectamente válido en producción — solo que no conviene ofrecerlo como primera respuesta en una entrevista que pide explícitamente explicar cómo funciona LRU, ya que oculta exactamente el mecanismo que la pregunta busca evaluar.