LRU Caché

Implementación de una caché LRU en Java, en dos versiones: O(n) ingenua y O(1) optimizada.

Autor: Daniel Caravaca García

El problema

Una caché LRU (Least Recently Used) es un algoritmo de gestión de memoria. Funciona descartando primero los datos que no se han solicitado durante más tiempo cuando la memoria se llena, optimizando el espacio para la información nueva y más relevante.

Progresión O(n) → O(1)

Versión ingenua (O(n)): Utiliza una lista dinámica común (un ArrayList). El O(n) viene de que ArrayList.remove(objeto) recorre el array comparando hasta encontrar el elemento y luego desplaza todos los posteriores una posición hacia la izquierda. Al leer o actualizar se busca un elemento en la estructura secuencial, si lo encuentra analiza su prioridad moviendo el elemento al final de la lista. Cuando se quiere insertar un elemento y la capacidad está completa, se busca en la estructura cuál es el elemento con menor uso y lo elimina para insertar el nuevo elemento.

Versión optimizada (O(1)): La versión optimizada logra una velocidad constante de O(1) delegando una sola tarea específica a cada estructura de datos. El HashMap<K, Node> garantiza el acceso en tiempo constante guardando una referencia directa al nodo de cada clave. Al mapear claves a nodos —y no a valores— elimina las búsquedas secuenciales de la versión ingenua: dada una clave, obtienes su nodo sin recorrer nada.

La lista doblemente enlazada mantiene el orden cronológico registrando la frescura de los datos mediante la posición de sus nodos. Cada vez que un dato se lee o se actualiza, la lista desconecta ese nodo de su posición actual y lo reconecta al inicio. El elemento al final de la lista siempre representa el dato menos usado recientemente, siendo el eliminado si la caché se llena. Gracias a los punteros dobles, no es necesario recorrer una lista buscando quién lo precede.

Decisiones de diseño

• Nodos centinela: Son nodos mudos, no contienen datos reales de la caché. Su propósito es delimitar los extremos de la lista doblemente enlazada.
• El nodo guarda su propia clave: Para poder borrar el elemento del HashMap durante la expulsión.
• Capacidad ≤ 0 lanza excepción: Se detectan los errores al arrancar y evita fallos silenciosos. Básicamente evita inicializaciones vacías.

Complejidad

Ambas operaciones, get y put, se ejecutan en O(1) porque el HashMap localiza el nodo de forma inmediata y la lista doblemente enlazada lo reubica o expulsa modificando solo unos pocos punteros, sin importar el tamaño de la caché.

Concurrencia

La versión de un solo hilo asume que solo un hilo la usa, así que sus operaciones no están protegidas contra accesos simultáneos. Por lo tanto se corrompería si hubiera más de un hilo entrando a la vez, haciendo put o get. Con diferentes hilos se intercalarían las operaciones y se perderían punteros y la lista no mantendría la estructura.

Solución: synchronized synchronized solo permite un solo hilo dentro de get/put/size a la vez. Los tres métodos que deben ser synchronized son: get(), put() y size(). Los métodos get() y put() contienen los métodos addFirst() y remove(), como son métodos que manejan la interacción de los punteros con los nodos dando la lógica del orden de integración y expulsión, deben de realizarse de forma completa sin que otro hilo se intercale. put() toca el map y la lista, y ambas deben moverse juntas; si solo protegieras remove(), dos hilos podrían intercalarse entre remove() y addFirst() dentro del mismo put() y corromper igual. El método size() lo necesita porque un hilo podría leer map.size() mientras otro está en mitad de un put(), con el map y la lista en estados que no cuadran momentáneamente. Como lee un estado compartido, no puede ser mutado mientras se lee.

Por qué no un ReadWriteLock Un ReadWriteLock permite varios lectores simultáneos porque las lecturas no modifican nada. Pero en este caso get() modifica moviendo un nodo al frente. Dos get() concurrentes corromperían la lista igual que dos put(). Por eso el método get() necesitaría el lock de escritura, y entonces ReadWriteLock no aporta ninguna ventaja frente a synchronized.

Limitación conocida synchronized serializa todo el acceso, así que con N hilos solo uno trabaja a la vez. La caché es correcta, pero no aprovecha el paralelismo disponible.

Cómo ejecutar

​bash mvn test ​

Los 5 tests cubren las operaciones básicas de escritura, lectura, actualización de valores, el comportamiento de expulsión por límite de capacidad y la validación de errores al inicializar la caché.