Introducción al algoritmo LRU

LRU (Least Recently Used, o Menos Usado Recientemente) es una estrategia de reemplazo de caché muy común en sistemas informáticos. Se basa en el principio de localidad temporal: es probable que los datos accedidos recientemente se vuelvan a acceder pronto, mientras que los datos no accedidos hace tiempo tienen menor probabilidad de ser necesarios. Por lo tanto, al llenarse la caché, se descarta el elemento que no se ha utilizado durante más tiempo.

Este enfoque es especialmente útil en escenarios como la gestión de sesiones de usuario, donde se desea mantener en memoria rápida solo a los usuarios más activos. Implementar un sistema basado en LRU permite identificar y priorizar a estos usuarios sin necesidad de añadir campos de seguimiento adicionales en la base de datos, mejorando así el rendimiento de la aplicación.

Estructura de datos para la implementación

Para una implementación eficiente del algoritmo LRU en Java, se puede combinar un mapa hash (HashMap) con una lista doblemente enlazada. El mapa proporciona acceso rápido O(1) a cualquier nodo mediante su clave. La lista doblemente enlazada permite reordenar los elementos de manera eficiente: cada vez que un elemento se accede o se inserta, se mueve al frente de la lista (representando los elementos más recientemente usados). El elemento al final de la lista es el candidato a ser expulsaod cuando la caché está llena.

Definición de la clase Nodo

El bloque fundamental es el nodo, que almacena una clave, un valor y referencias al nodo anterior y siguiente.

class Nodo<K, V> {
    K clave;
    V valor;
    Nodo<K, V> anterior;
    Nodo<K, V> siguiente;

    public Nodo(K clave, V valor) {
        this.clave = clave;
        this.valor = valor;
    }
}

Clase principal de la caché LRU

La clase de caché gestiona el mapa hash, los punteros a los extremos de la lista (cabeza y cola) y la capacidad máxima.

import java.util.HashMap;
import java.util.Map;

public class CacheLRU<K, V> {
    private final int capacidadMaxima;
    private Map<K, Nodo<K, V>> mapaEntradas;
    private Nodo<K, V> cabeza; // Nodo más recientemente usado
    private Nodo<K, V> cola;   // Nodo menos recientemente usado

    public CacheLRU(int capacidad) {
        this.capacidadMaxima = capacidad;
        this.mapaEntradas = new HashMap<>(capacidad);
    }
}

Operaciones principales

Acceso a un elemento (get)

Al obtener un valor por su clave, si el nodo existe en el mapa, se reubica al inicio de la lista para marcarlo como recién utilizado y se devuelve su valor. Si no existe, se retorna nulo.

public V obtener(K claveBuscada) {
    Nodo<K, V> nodo = mapaEntradas.get(claveBuscada);
    if (nodo == null) {
        return null;
    }
    moverANodoCabeza(nodo);
    return nodo.valor;
}

Inserción de un elemento (put)

Al añadir un par clave-valor, se busca si ya existe. Si existe, se actualiza su valor. Si es nuevo y la caché está llena, se elimina el nodo de la cola (el menos usado). Finalmente, se inserta el nuevo nodo en la cabeza de la lista y en el mapa.

public void insertar(K nuevaClave, V nuevoValor) {
    Nodo<K, V> nodoExistente = mapaEntradas.get(nuevaClave);

    if (nodoExistente != null) {
        nodoExistente.valor = nuevoValor;
        moverANodoCabeza(nodoExistente);
        return;
    }

    if (mapaEntradas.size() >= capacidadMaxima) {
        expulsarElementoMenosUsado();
    }

    Nodo<K, V> nuevoNodo = new Nodo<>(nuevaClave, nuevoValor);
    nuevoNodo.siguiente = cabeza;
    nuevoNodo.anterior = null;

    if (cabeza != null) {
        cabeza.anterior = nuevoNodo;
    }
    cabeza = nuevoNodo;

    if (cola == null) {
        cola = cabeza;
    }
    mapaEntradas.put(nuevaClave, nuevoNodo);
}

Métodos auxiliares

Estos métodos realizan la manipulación de la lista doblemente enlazada de manera encapsulada.

private void moverANodoCabeza(Nodo<K, V> nodoAMover) {
    if (nodoAMover == cabeza) {
        return;
    }
    // Desconectar el nodo de su posición actual
    if (nodoAMover.anterior != null) {
        nodoAMover.anterior.siguiente = nodoAMover.siguiente;
    }
    if (nodoAMover.siguiente != null) {
        nodoAMover.siguiente.anterior = nodoAMover.anterior;
    }
    if (nodoAMover == cola) {
        cola = nodoAMover.anterior;
    }
    // Conectar el nodo como nueva cabeza
    nodoAMover.anterior = null;
    nodoAMover.siguiente = cabeza;
    if (cabeza != null) {
        cabeza.anterior = nodoAMover;
    }
    cabeza = nodoAMover;
    if (cola == null) {
        cola = cabeza;
    }
}

private void expulsarElementoMenosUsado() {
    if (cola == null) {
        return;
    }
    mapaEntradas.remove(cola.clave);
    cola = cola.anterior;
    if (cola != null) {
        cola.siguiente = null;
    } else {
        cabeza = null;
    }
}

Ejemplo de uso y verificación

public static void main(String[] argumentos) {
    CacheLRU<Integer, String> miCache = new CacheLRU<>(3);

    miCache.insertar(1, "Valor_A");
    miCache.insertar(2, "Valor_B");
    miCache.insertar(3, "Valor_C");
    // Estado: [3, 2, 1]

    miCache.obtener(1);
    // Acceso a 1, se mueve a la cabeza. Estado: [1, 3, 2]

    miCache.insertar(4, "Valor_D");
    // Caché llena. Se expulsa el elemento en la cola (clave 2).
    // Estado: [4, 1, 3]

    System.out.println("Valor para clave 1: " + miCache.obtener(1));
    System.out.println("Valor para clave 2 (expulsado): " + miCache.obtener(2));
    System.out.println("Valor para clave 4: " + miCache.obtener(4));
}

La ejecución de este código demostraría que el valor asociado a la clave 2 ya no está disponible, confirmando que el algoritmo LRU descartó el elemento menos recientemente utilizado al necesitar espacio para uno nuevo.