LinkedHashSet/LinkedHashMap

1. Che cosa sono LinkedHashSet e LinkedHashMap?

Nella libreria standard di Java ci sono diverse implementazioni delle collection Set e Map. Le più note — sono HashSet e HashMap. Queste strutture forniscono accesso rapido agli elementi tramite hash, ma non garantiscono alcun ordine nell’iterazione degli elementi. Quando l’ordine di attraversamento è importante — vengono in aiuto LinkedHashSet e LinkedHashMap.

• LinkedHashSet — è un Set che ricorda l’ordine di inserimento degli elementi.
• LinkedHashMap — è una Map che ricorda l’ordine di inserimento delle coppie chiave–valore (oppure, a scelta, l’ordine di accesso).

Sono implementati come «normali» HashSet/HashMap, ma con l’aggiunta di una lista doppiamente collegata per mantenere l’ordine degli elementi.

2. Ordine di inserimento e ordine di accesso

Ordine di inserimento

Per impostazione predefinita LinkedHashSet e LinkedHashMap garantiscono che, durante l’iterazione, gli elementi vengano restituiti nell’ordine in cui sono stati inseriti (for-each/iteratore).

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// Stamperà: A B C

Map<Integer, String> map = new LinkedHashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
for (Integer key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}
// Stamperà: 1 -> one, 2 -> two, 3 -> three

Ordine di accesso (solo per LinkedHashMap)

La LinkedHashMap dispone di una modalità di ordine per ultimo accesso (access order). Se alla creazione della mappa si passa true come terzo parametro del costruttore, a ogni accesso a un elemento (get/put) questo viene spostato alla fine della lista.

Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put(1, "one");
lruMap.put(2, "two");
lruMap.put(3, "three");

lruMap.get(2); // Accesso alla chiave 2

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// Stamperà: 1 3 2 (2 — ultimo, perché è stato appena consultato)

Cache LRU tramite removeEldestEntry

La principale «chicca» di LinkedHashMap è la semplice implementazione di una cache LRU (Least Recently Used, «meno recentemente utilizzato»). È sufficiente sovrascrivere il metodo removeEldestEntry(Map.Entry<K,V> eldest): se restituisce true, l’elemento più «vecchio» viene rimosso all’aggiunta di un nuovo elemento.

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true — ordine per accesso
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// Utilizzo:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // Rende 1 il più "recente"
cache.put(4, "four"); // Verrà rimosso il 2 (il più vecchio)
System.out.println(cache.keySet()); // [3, 1, 4]

3. Costo in memoria e prestazioni: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

Come funziona

All’interno — quasi come i normali HashSet/HashMap, ma ogni elemento è memorizzato anche in una lista doppiamente collegata. Questa struttura aggiuntiva «ricorda» l’ordine di inserimento/accesso.

Costo in memoria

A causa dei riferimenti prev/next su ogni nodo è necessaria più memoria. Per milioni di elementi questo è sensibile; per i casi tipici — è un costo ragionevole in cambio di un ordine deterministico.

Costo in velocità

Le operazioni di base di inserimento/ricerca/rimozione restano ammortizzate O(1). L’iterazione è leggermente più lenta a causa del passaggio attraverso la lista, ma nella maggior parte dei casi la differenza è minima. E lo scenario «rimuovi il più vecchio» (LRU) è molto efficiente, perché l’elemento «più anziano» è sempre in testa alla lista.

In sintesi: se l’ordine è importante — scegli LinkedHashSet/LinkedHashMap. Se occorre risparmiare memoria e l’ordine non serve — basta HashSet/HashMap.

4. Caching, output deterministico, test stabili

Caching (LRU)

LinkedHashMap — una base ideale per cache con limite di dimensione e rimozione automatica degli elementi «vecchi». Usata in librerie/framework, nella gestione di file, immagini, risultati di calcolo.

Output deterministico

Per report, export e serializzazione, dove è cruciale una rappresentazione dei dati prevedibile, usa LinkedHashSet/LinkedHashMap. È particolarmente importante per i test — l’ordine non «balla» da un’esecuzione all’altra.

Test stabili

Nei test unitari spesso si confrontano le collection attese con quelle ottenute. Se l’ordine non è garantito, i test possono «flappare». Con le implementazioni «linked» — il determinismo garantisce stabilità.

Esempio: confronto tra HashMap e LinkedHashMap

Map<Integer, String> hashMap = new HashMap<>();
Map<Integer, String> linkedMap = new LinkedHashMap<>();

for (int i = 1; i <= 5; i++) {
    hashMap.put(i, "val" + i);
    linkedMap.put(i, "val" + i);
}

System.out.println(hashMap.keySet());   // L’ordine può essere qualsiasi!
System.out.println(linkedMap.keySet()); // Sempre 1, 2, 3, 4, 5

5. LinkedList vs ArrayDeque per le code

LinkedList

• Implementa le interfacce List, Deque, Queue.
• Lista doppiamente collegata: inserimenti/rimozioni veloci all’inizio e alla fine.
• Può essere usata come coda (FIFO), stack (LIFO), coda doppia.

ArrayDeque

• Implementa Deque, Queue (ma non List).
• Basata su array, si espande automaticamente.
• Spesso più veloce di LinkedList per operazioni di coda/stack; overhead minore.
• Non supporta l’elemento null.

Quando usare cosa?

• Code e stack — quasi sempre ArrayDeque.
• Molti inserimenti/rimozioni in mezzo e serve anche una lista — LinkedList.
• Set/Map con ordine — LinkedHashSet/LinkedHashMap.

Esempio: coda di task

Queue<String> queue = new ArrayDeque<>();
queue.add("task1");
queue.add("task2");
System.out.println(queue.poll()); // task1

Esempio: stack

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second

Conclusione:
— Per code e stack — ArrayDeque.
— Per liste con inserimenti frequenti in mezzo — LinkedList.
— Per Set/Map con ordine — LinkedHashSet/LinkedHashMap.

6. Errori tipici nell’uso di LinkedHashSet/LinkedHashMap

Errore n. 1: aspettarsi che HashSet/HashMap preservino l’ordine.
HashSet/HashMap non garantiscono alcun ordine. Se è importante — usa LinkedHashSet/LinkedHashMap.

Errore n. 2: LinkedHashMap per cache senza override di removeEldestEntry.
Per LRU bisogna sovrascrivere removeEldestEntry, altrimenti la mappa crescerà senza limiti.

Errore n. 3: usare LinkedList per code/stack senza necessità.
Nella maggior parte dei casi ArrayDeque è più veloce ed economica.

Errore n. 4: aspettarsi l’ordinamento da LinkedHashMap.
LinkedHashMap preserva l’ordine di inserimento/accesso, ma non ordina per chiave. Per l’ordinamento — TreeMap.

Errore n. 5: inserire null in ArrayDeque.
ArrayDeque non supporta elementi null — verrà lanciata NullPointerException.

Errore n. 6: confrontare le collection senza considerare l’ordine.
Confrontando LinkedHashSet/LinkedHashMap con i normali HashSet/HashMap, tieni conto delle differenze nell’ordine degli elementi.