LinkedHashMap fue introducido en Java 1.4 como una estructura de datos híbrida que combina la búsqueda promedio O(1) de HashMap con una lista doblemente enlazada que proporciona un orden de iteración determinista, ya sea por orden de inserción o por orden de acceso. Su diseño introdujo el método de plantilla removeEldestEntry, permitiendo a las subclases implementar políticas de desalojo LRU (Least Recently Used) al devolver true cuando el mapa excede un tamaño deseado. Sin embargo, la implementación nunca estuvo destinada a su uso concurrente; hereda la naturaleza no segura para hilos de HashMap y añade la complejidad de mantener punteros before y after bidireccionales en todas las entradas, incluyendo aquellas dentro de cubos estructurados en árbol.
Bajo la modificación estructural concurrente, como un hilo insertando mientras otro elimina o redimensiona, los punteros de la lista enlazada pueden actualizarse de manera no atómica, lo que lleva a una estructura gráfica corrupta donde las entradas forman referencias circulares o quedan huérfanas de la cadena principal. Por ejemplo, si el Hilo A actualiza el puntero after de una entrada para apuntar a la Entrada B, pero el Hilo B elimina la Entrada B y actualiza su puntero before de forma concurrente, la lista puede terminar con A apuntando a B mientras B apunta a C, saltándose efectivamente A o creando un ciclo. Esta corrupción provoca que los iteradores giren infinitamente (consumiendo el 100% de CPU) o salten entradas válidas silenciosamente, lo que hace que la política removeEldestEntry sea poco fiable porque el puntero "eldest" puede ya no reflejar la verdadera cabeza de la lista.
Para usar LinkedHashMap de manera segura en contextos multihilo, debes sincronizar externamente todas las operaciones. Para cachés con accessOrder=true, incluso get() es una modificación estructural (reordena la lista enlazada), así que las optimizaciones estándar de ReadWriteLock para operaciones de solo lectura no son válidas; debes tratar todas las operaciones como escrituras o utilizar un mutex global. El enfoque más seguro es Collections.synchronizedMap, aunque debes sincronizar manualmente en el mapa al iterar. Sin embargo, para sistemas de producción, sustituye LinkedHashMap por Caffeine o CacheBuilder de Guava, que proporcionan algoritmos de desalojo sin contención global o con bloqueo por franjas.
public class SafeLRUCache<K, V> { private final Map<K, V> map; public SafeLRUCache(int maxSize) { // LinkedHashMap NO es seguro para hilos; sincronizar externamente this.map = Collections.synchronizedMap(new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }); } // Todos los métodos deben sincronizar en el mapa public V get(K key) { synchronized (map) { return map.get(key); } } public void put(K key, V value) { synchronized (map) { map.put(key, value); } } // La iteración requiere sincronización explícita public void forEach(BiConsumer<K, V> action) { synchronized (map) { map.forEach(action); } } }
Un servicio de backend para una plataforma de comercio electrónico requería una caché en memoria para datos de precios de productos para reducir la carga de la base de datos. La implementación inicial utilizó LinkedHashMap con accessOrder=true y sobreescribió removeEldestEntry para hacer cumplir un límite de 1,000 elementos, asumiendo que el mapa simple eliminaría automáticamente las entradas antiguas. Durante la prueba de baja carga, esto funcionó correctamente; sin embargo, bajo el tráfico de producción con cuarenta hilos concurrentes manejando ventas flash, el servicio experimentó picos intermitentes de CPU al 100% y eventual inanición de hilos.
Los volcado de hilos revelaron múltiples hilos atascados dentro de iteradores de LinkedHashMap, atravesando referencias circulares en la lista doblemente enlazada causadas por modificaciones concurrentes. Específicamente, un hilo estaba redimensionando la tabla interna mientras otro actualizaba el orden de acceso de una entrada, causando que el puntero after de un nodo Entry hiciera referencia a sí mismo, creando un bucle infinito durante la iteración. Además, el callback de removeEldestEntry a veces eliminaba la entrada incorrecta porque el puntero "eldest" había sido corrompido por un reordenamiento concurrente, llevando a un desgaste de la caché donde los artículos accedidos recientemente eran desalojados en lugar de los que estaban obsoletos.
El equipo primero consideró envolver el mapa con Collections.synchronizedMap. Pros: Esto requiere cambios mínimos en el código y asegura la atomicidad de las operaciones individuales al envolverlas en métodos synchronized. Cons: Introduce un monitor global, serializando todas las lecturas y escrituras, lo que reduce el rendimiento de 20,000 operaciones por segundo a menos de 3,000 bajo contención. Además, los iteradores aún requerían bloques explícitos synchronized(map), que los desarrolladores a veces olvidaban, llevando a ConcurrentModificationException.
A continuación, evaluaron el uso de ConcurrentHashMap paired con un ConcurrentLinkedQueue para rastrear la recencia y un hilo de limpieza en segundo plano. Pros: Esto ofrece alta concurrencia para lecturas y escrituras. Cons: Implementar LRU correctamente es propenso a errores; eliminar la entrada más antigua no es atómico con la inserción, permitiendo que la caché exceda temporalmente su límite de tamaño significativamente bajo alta carga. Además, actualizar la cola en cada get() requiere una operación de escritura, creando puntos de contención similares y complejidad para mantener la consistencia entre la cola y el mapa.
Finalmente, evaluaron Caffeine, una biblioteca de caché de alto rendimiento. Pros: Utiliza un BoundedLocalCache con bandas de bloqueo y un búfer de escritura para desalojos, permitiendo lecturas concurrentes sin bloqueo y escrituras de alto rendimiento. Maneja el desalojo LRU/W-TinyLFU de forma atómica sin sincronización explícita. Cons: Añade una dependencia externa y requiere aprender una nueva API (por ejemplo, CacheLoader).
El equipo seleccionó Caffeine después de que las pruebas de carga demostraran que sostenía más de 80,000 operaciones por segundo con una latencia p99 de menos de 1ms, mientras que el LinkedHashMap sincronizado se estancaba en 5k ops/sec con p99 a 500ms. La migración involucró reemplazar el mapa por Caffeine.newBuilder().maximumSize(1000).build() y registrar un listener de eliminación para la lógica de limpieza.
El monitoreo posterior al despliegue mostró un uso estable de CPU y cero bloqueos de hilos. La tasa de aciertos de la caché mejoró del 85% al 94% porque el desalojo se volvió determinista y libre de condiciones de carrera. El incidente destacó que LinkedHashMap es una estructura de datos de un solo hilo inadecuada para cachés LRU concurrentes a pesar de su API conveniente.
¿Cómo mantiene LinkedHashMap el orden LRU para las entradas que se han trasladado a cubos estructurados en árbol (árboles rojo-negro) debido a altas colisiones de hash?
LinkedHashMap utiliza una clase interna especializada Entry que extiende HashMap.Node e incluye punteros before y after. Cuando un cubo se estructura en árbol, LinkedHashMap sobreescribe newTreeNode para crear instancias de TreeNode que aún heredan de LinkedHashMap.Entry (a través de LinkedHashMap.TreeNode). Por lo tanto, incluso cuando las entradas se almacenan en una estructura de árbol para resolución de colisiones O(log n), siguen siendo nodos en la lista doblemente enlazada global. El método afterNodeAccess actualiza estos punteros después de cada acceso, asegurando que la cadena LRU recorra las entradas independientemente de si residen en listas enlazadas o árboles dentro de la tabla hash.
¿Por qué llamar a get() en un LinkedHashMap con accessOrder=true provoca un ConcurrentModificationException si se realiza durante la iteración, mientras que la misma operación en un HashMap estándar no lo hace?
En modo accessOrder, LinkedHashMap trata a get() como una modificación estructural porque mueve la entrada accedida a la cola de la lista doblemente enlazada, incrementando modCount. El iterador fail-fast verifica este contador y lanza inmediatamente al detectar el cambio. En contraste, un HashMap estándar solo incrementa modCount en inserciones, eliminaciones y redimensionamientos; get() es de solo lectura en relación con la estructura de la tabla. Esta distinción significa que incluso las operaciones lógicas "solo de lectura" pueden invalidar los iteradores en LinkedHashMap, necesitando sincronización para todas las operaciones, incluidas las lecturas, al iterar concurrentemente.
¿Qué corrupción específica de punteros ocurre durante la redimensión concurrente (rehashing) en LinkedHashMap que es imposible en un HashMap estándar?
Durante la redimensión, HashMap transfiere nodos a un nuevo array de tabla, arriesgando bucles infinitos en los cubos si se realiza de forma concurrente. LinkedHashMap además corre el riesgo de corrupción de los punteros before y after que forman la lista enlazada auxiliar. Si el Hilo A está reconectando las entradas para preservar el orden en la nueva tabla mientras el Hilo B modifica la lista (por ejemplo, a través de remove), el Hilo A puede enlazar una entrada a un sucesor que el Hilo B ya ha desvinculado, creando una referencia colgante o un ciclo. Específicamente, el puntero after del nodo cabecera podría apuntar a una entrada cuyo puntero before fue anulado por otro hilo, rompiendo la invariante de la lista y causando que los iteradores giren para siempre cuando next() sigue la cadena rota.