Java LinkedHashMap

LinkedHashMap<K, V> è una HashMap<K, V> con una lista doppiamente concatenata che attraversa ogni voce. La tabella hash svolge il suo compito abituale — put, get, remove in O(1) — e la lista concatenata garantisce un ordine di iterazione prevedibile. Per impostazione predefinita quell'ordine è l'ordine di inserimento; attivando un flag nel costruttore diventa l'ordine di accesso, il mattone fondamentale di una cache LRU (least-recently-used).

Due ordinamenti, una sola classe

I costruttori rispecchiano quelli di HashMap, con uno in più:

new LinkedHashMap<>();                              // insertion order
new LinkedHashMap<>(16, 0.75f, false);              // insertion order, explicit
new LinkedHashMap<>(16, 0.75f, true);               // ACCESS order

Il terzo boolean è il flag accessOrder. Con il valore false (impostazione predefinita), ogni put di una nuova chiave aggiunge la voce in fondo alla lista concatenata, mentre il put ripetuto di una chiave esistente lascia invariata la sua posizione. Con il valore true, ogni get, put o getOrDefault che tocca una chiave sposta quella voce alla fine della lista — la voce acceduta più di recente è sempre l'ultima; quella acceduta meno di recente è sempre la prima.

Questa seconda modalità è rara nel codice applicativo, ma l'unico posto in cui la si incontra è esattamente quello in cui ne hai più bisogno: l'implementazione di una cache.

L'iterazione in ordine di inserimento è l'uso più comune

Il 90% delle volte si ricorre a LinkedHashMap perché si desidera un output stabile. Esempi:

• Restituire una Map<String, Object> da un endpoint di serializzazione JSON e voler vedere i campi nell'ordine in cui sono stati inseriti.
• Registrare il contenuto di una mappa in un ordine deterministico per confronti.
• Costruire configurazioni in cui l'ordine è importante (ad esempio: catena di middleware, ordine degli header, pipeline di validazione).
• Restituire una Map da un'API pubblica senza che i chiamanti dipendano dall'ordine arbitrario di HashMap.

Il costo rispetto a HashMap consiste in due riferimenti aggiuntivi per ogni voce (i puntatori before e after). Per mappe di dimensioni tipiche di una configurazione non fa differenza; nei cicli stretti su mappe molto grandi potresti preferire una HashMap se puoi farne a meno.

L'iterazione è proporzionale alla dimensione

Un vantaggio collaterale: iterare una LinkedHashMap percorre la lista concatenata, che contiene esattamente size voci. Iterare una HashMap percorre ogni slot dei bucket — compresi quelli vuoti. Per una mappa scarsamente popolata la differenza è significativa.

Costruire una cache LRU

La caratteristica distintiva dell'ordine di accesso è il hook protected removeEldestEntry. Viene chiamato dopo ogni put e, se restituisce true, la mappa rimuove la sua prima voce (la più vecchia). Combinando i due elementi:

class LruCache<K, V> extends LinkedHashMap<K, V> {
  private final int max;
  LruCache(int max) { super(16, 0.75f, true); this.max = max; }
  @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > max;
  }
}

Dodici righe per una cache LRU non thread-safe ma pienamente funzionale. Ogni get riordina la voce in fondo; ogni put chiama removeEldestEntry; non appena la dimensione supera max, la voce in testa (quella acceduta meno di recente) viene espulsa.

Per una cache LRU thread-safe si usa Collections.synchronizedMap oppure — meglio — una libreria di caching dedicata (Caffeine), perché gli aggiornamenti dell'ordine di accesso rendono ogni get una scrittura sotto il cofano e il semplice wrapper sincronizzato serializza tutte le letture. Ma per il codice single-thread, questo è il trucco classico che vale la pena conoscere.

Null e il resto delle regole

Stesse regole di HashMap: una chiave null, un numero qualsiasi di valori null. Non thread-safe. L'uguaglianza è quella strutturale definita da Map — una LinkedHashMap e una HashMap con le stesse voci sono equals. L'ordine di iterazione non fa parte dell'uguaglianza; è semplicemente ciò che si ottiene iterando.

Un esempio pratico: ordine di inserimento, ordine di accesso e una cache LRU

Il programma seguente costruisce una piccola catena di middleware in ordine di inserimento, confronta l'iterazione di HashMap e LinkedHashMap sugli stessi dati, poi implementa una piccola cache LRU e osserva le espulsioni.

Cosa osservare dall'esecuzione:

• La pipeline itera nell'ordine log → auth → rateLimit → handler — esattamente l'ordine di inserimento. Una semplice HashMap conterrebbe comunque tutte e quattro le voci, ma l'ordine sarebbe arbitrario.
• HashMap e LinkedHashMap contenenti gli stessi dati stampano in ordini diversi; la LinkedHashMap corrisponde a keys, la HashMap no.
• La cache LRU si è riordinata quando è stato chiamato get(\"a\") — a è passata in fondo alla lista, rendendo b la nuova voce più vecchia. Il successivo put(\"d\", \"D\") ha provocato l'espulsione di b, non di a. Questa è la regola dell'ordine di accesso in azione.

Cosa viene dopo

La terza implementazione standard di Map offre qualcosa che nessuna delle due basate su hash può fornire: iterazione ordinata per chiave e query su intervallo (subMap, headMap, tailMap, firstKey, lastKey). TreeMap è il prossimo argomento; la struttura è identica a quella di TreeSet — usano letteralmente lo stesso codice ad albero rosso-nero.

Pratica