LinkedHashMap è stato introdotto in Java 1.4 come una struttura dati ibrida che combina l'O(1) di ricerca media di HashMap con una lista doppiamente collegata che fornisce un ordine di iterazione deterministico, sia in base all'ordine di inserimento che all'ordine di accesso. Il suo design ha introdotto il metodo template removeEldestEntry, consentendo alle sottoclassi di implementare politiche di espulsione LRU (Least Recently Used) restituendo true quando la mappa supera una dimensione desiderata. Tuttavia, l'implementazione non era mai intesa per usi concorrenti; eredita la natura non thread-safe di HashMap e aggiunge la complessità di mantenere puntatori bi-direzionali before e after tra tutte le voci, comprese quelle all'interno dei bucket alberificati.
Durante una modifica strutturale concorrente—come un thread che inserisce mentre un altro elimina o ridimensiona—i puntatori della lista collegata possono essere aggiornati in modo non atomico, portando a una struttura grafica corrotta in cui le voci formano riferimenti circolari o diventano orfane dalla catena principale. Ad esempio, se il Thread A aggiorna il puntatore after di una voce per puntare all'Entry B, ma il Thread B rimuove l'Entry B e aggiorna il proprio puntatore before contemporaneamente, la lista potrebbe finire con A che punta a B mentre B punta a C, saltando effettivamente A o creando un ciclo. Questa corruzione causa agli iteratori di girare all'infinito (consumando il 100% della CPU) o di saltare silenziosamente voci valide, rendendo la politica di removeEldestEntry inaffidabile perché il puntatore "eldest" potrebbe non riflettere più la vera testa della lista.
Per utilizzare in modo sicuro LinkedHashMap in contesti multi-threaded, è necessario sincronizzare esternamente tutte le operazioni. Per le cache con accessOrder=true, anche il get() è una modifica strutturale (riordina la lista collegata), quindi le ottimizzazioni standard di ReadWriteLock per operazioni di sola lettura sono nulle; è necessario trattare tutte le operazioni come scritture o utilizzare un mutex globale. L'approccio più sicuro è Collections.synchronizedMap, anche se è necessario sincronizzare manualmente sulla mappa durante l'iterazione. Tuttavia, per i sistemi di produzione, sostituire LinkedHashMap con Caffeine o CacheBuilder di Guava, che forniscono algoritmi di espulsione a strisce di blocco o completamente concorrenti senza contesa globale.
public class SafeLRUCache<K, V> { private final Map<K, V> map; public SafeLRUCache(int maxSize) { // LinkedHashMap NON è thread-safe; sincronizza esternamente this.map = Collections.synchronizedMap(new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }); } // Tutti i metodi devono sincronizzarsi sulla mappa public V get(K key) { synchronized (map) { return map.get(key); } } public void put(K key, V value) { synchronized (map) { map.put(key, value); } } // L'iterazione richiede sincronizzazione esplicita public void forEach(BiConsumer<K, V> action) { synchronized (map) { map.forEach(action); } } }
Un servizio backend per una piattaforma di e-commerce richiedeva una cache in memoria per i dati sui prezzi dei prodotti per ridurre il carico del database. L'implementazione iniziale utilizzava LinkedHashMap con accessOrder=true e sovrascriveva removeEldestEntry per imporre un limite di 1.000 voci, assumendo che la mappa avrebbe semplicemente rimosso automaticamente le vecchie voci. Durante il test a basso carico, questo funzionava correttamente; tuttavia, sotto traffico di produzione con quaranta thread concorrenti che gestivano vendite lampo, il servizio ha subito picchi di CPU intermittenti fino al 100% e una successiva fame di thread.
I thread dump hanno rivelato che più thread si erano bloccati all'interno degli iteratori di LinkedHashMap, attraversando riferimenti circolari nella lista doppiamente collegata causati da modifiche concorrenti. In particolare, un thread stava ridimensionando la tabella interna mentre un altro stava aggiornando l'ordine di accesso di una voce, causando che il puntatore after di un nodo Entry facesse riferimento a se stesso, creando un ciclo infinito durante l'iterazione. Inoltre, il callback di removeEldestEntry a volte rimuoveva la voce sbagliata perché il puntatore "eldest" era stato corrotto da un riordino concorrente, portando a uno stravolgimento della cache in cui gli elementi appena accessibili venivano espulsi invece di quelli obsoleti.
Il team ha inizialmente considerato di racchiudere la mappa con Collections.synchronizedMap. Pro: Questo richiede modifiche minime al codice e garantisce l'atomicità delle singole operazioni racchiudendole in metodi synchronized. Contro: Introduce un monitor globale, serializzando tutte le letture e scritture, il che riduce il throughput da 20.000 operazioni al secondo a meno di 3.000 sotto contesa. Inoltre, gli iteratori richiedevano ancora blocchi espliciti synchronized(map), che gli sviluppatori a volte dimenticavano, portando a ConcurrentModificationException.
Successivamente, hanno valutato l'uso di ConcurrentHashMap abbinato a una ConcurrentLinkedQueue per tracciare la recenza e un thread di pulizia in background. Pro: Questo offre alta concorrenza per letture e scritture. Contro: Implementare correttamente LRU è soggetto a errori; rimuovere l'elemento più anziano non è atomico con l'inserimento, consentendo alla cache di superare temporaneamente di molto il limite di dimensione sotto carico elevato. Inoltre, l'aggiornamento della coda ad ogni get() richiede un'operazione di scrittura, creando punti simili di contesa e complessità nel mantenere la coerenza tra la coda e la mappa.
Infine, hanno testato Caffeine, una libreria di caching ad alte prestazioni. Pro: Usa una BoundedLocalCache con strisce di blocco e un buffer di scrittura per le espulsioni, consentendo letture concorrenti senza blocchi e scritture ad alta capacità. Gestisce l'espulsione LRU/W-TinyLFU in modo atomico senza una sincronizzazione esplicita. Contro: Aggiunge una dipendenza esterna e richiede di imparare una nuova API (ad es. CacheLoader).
Il team ha selezionato Caffeine dopo che il load testing ha dimostrato che sosteneva oltre 80.000 operazioni al secondo con una latenza p99 inferiore a 1 ms, mentre il LinkedHashMap sincronizzato ha avuto un collo di bottiglia a 5k ops/sec con picchi p99 fino a 500 ms. La migrazione ha comportato la sostituzione della mappa con Caffeine.newBuilder().maximumSize(1000).build() e la registrazione di un listener di rimozione per la logica di pulizia.
Il monitoraggio post-deploy ha mostrato un utilizzo stabile della CPU e zero blocchi dei thread. Il tasso di successo della cache è migliorato dall'85% al 94% perché l'espulsione è diventata deterministica e priva di condizioni di gara. L'incidente ha evidenziato che LinkedHashMap è una struttura dati monothread inadeguata per cache LRU concorrenti nonostante la sua API conveniente.
Come mantiene LinkedHashMap l'ordine LRU per le voci che sono state spostate in bucket alberificati (alberi rosso-neri) a causa di elevate collisioni hash?
LinkedHashMap utilizza una classe interna specializzata Entry che estende HashMap.Node e include puntatori before e after. Quando un bucket diventa alberificato, LinkedHashMap sovrascrive newTreeNode per creare istanze di TreeNode che ereditano comunque da LinkedHashMap.Entry (tramite LinkedHashMap.TreeNode). Di conseguenza, anche quando le voci sono memorizzate in una struttura ad albero per la risoluzione delle collisioni O(log n), rimangono nodi nella lista doppiamente collegata globale. Il metodo afterNodeAccess aggiorna questi puntatori dopo ogni accesso, garantendo che la catena LRU attraversi le voci indipendentemente dal fatto che si trovino in liste collegate o in alberi all'interno della tabella hash.
Perché chiamare get() su un LinkedHashMap con accessOrder=true attiva una ConcurrentModificationException se eseguito durante l'iterazione, mentre la stessa operazione su un normale HashMap non lo fa?
In modalità accessOrder, LinkedHashMap tratta get() come una modifica strutturale perché sposta la voce accessibile alla coda della lista doppiamente collegata, incrementando modCount. L'iteratore fail-fast verifica questo contatore e lancia immediatamente un'eccezione al rilevamento della modifica. Al contrario, un normale HashMap incrementa modCount solo su inserimenti, eliminazioni e ridimensionamenti; get() è a sola lettura rispetto alla struttura della tabella. Questa distinzione significa che anche le operazioni logiche "a sola lettura" possono invalidare gli iteratori in LinkedHashMap, rendendo necessaria la sincronizzazione per tutte le operazioni, comprese le letture, durante l'iterazione in modo concorrente.
Quale specifica corruzione dei puntatori si verifica durante un ridimensionamento concorrente (rihash) in LinkedHashMap che è impossibile in un normale HashMap?
Durante il ridimensionamento, HashMap trasferisce nodi a un nuovo array di tabelle, rischiando cicli infiniti nei bucket se fatto in modo concorrente. LinkedHashMap rischia inoltre la corruzione dei puntatori before e after che formano la lista collegata ausiliaria. Se il Thread A sta ripristinando i collegamenti delle voci per preservare l'ordine nella nuova tabella mentre il Thread B modifica la lista (ad es. tramite remove), il Thread A potrebbe collegare un'entry a un successore che il Thread B ha già scollegato, creando un riferimento appeso o un ciclo. In particolare, il puntatore after del nodo intestazione potrebbe puntare a un'entry il cui puntatore before è stato annullato da un altro thread, rompendo l'invariante della lista e causando agli iteratori di girare per sempre quando next() segue la catena rotta.