Classe Java LinkedHashSet | W3Docs Learn Java

LinkedHashSet<E> è HashSet<E> con una garanzia in più: durante l'iterazione, gli elementi vengono restituiti nell'ordine in cui sono stati inseriti per la prima volta. Il meccanismo della tabella hash è identico — stessi bucket, stesso fattore di carico, stesse operazioni add, remove, contains quasi costanti — ma ogni elemento memorizza due puntatori aggiuntivi (before, after) che collegano le voci in una lista doppiamente concatenata man mano che vengono aggiunte. L'iterazione percorre quella lista, non l'array dei bucket.

Se vuoi le prestazioni di un hash set e un ordine di iterazione deterministico e prevedibile, LinkedHashSet è la risposta. È quasi un upgrade gratuito per i casi in cui l'ordine non specificato di HashSet ti ha creato problemi.

La regola "vince il primo inserimento"

L'ordine è fissato dalla prima volta che un elemento viene inserito. Reinserire un elemento già presente non lo sposta:

Set<String> s = new LinkedHashSet<>();
s.add("a");
s.add("b");
s.add("c");
s.add("a");   // already present — returns false, order unchanged
System.out.println(s);   // [a, b, c]

Questo lo rende lo strumento giusto per "ricordare l'ordine di arrivo dei tag" o "registrare eventi unici in ordine cronologico." Se rimuovi un elemento e lo reinserisci, finisce in fondo alla lista — la posizione era legata all'inserimento corrente, e il nuovo è l'unico rimasto.

Il costo: puntatori e ancora puntatori

Il meccanismo di ordinamento aggiuntivo ha un costo. Ogni voce memorizza non solo (hash, key, next-in-bucket) come HashSet, ma (hash, key, next-in-bucket, before, after). Questo significa due riferimenti extra per elemento — circa 16 byte in più su una JVM a 64 bit. Per un set di 10 milioni di Long, sono circa 160 MB extra. Per la maggior parte del codice applicativo non è nulla; per strutture dati di dimensioni cache, conta.

In cambio, ottieni O(1) su ogni operazione (come HashSet) più un ordine di iterazione stabile che non dipende dal fattore di carico, dal rehash, dalla distribuzione degli hash o dalla versione della JVM.

Il costo di iterazione è proporzionale alla dimensione, non alla capacità

C'è un vantaggio sottile rispetto a HashSet: percorrere un LinkedHashSet segue la lista concatenata, quindi visita esattamente size voci. Iterare un HashSet percorre ogni bucket, visitando circa capacity slot — inclusi quelli vuoti. Per un set scarsamente popolato, questa può essere una differenza significativa. Se costruisci un set, lo espandi ben oltre gli elementi che manterrai e poi itero spesso, LinkedHashSet può in realtà iterare più velocemente.

Quando sceglierlo

Il flusso decisionale:

L'ordine non importa, hai solo bisogno di una verifica rapida dell'appartenenza → HashSet. Più piccolo, più semplice.
Vuoi che l'ordine di inserimento venga ricordato → LinkedHashSet. Stessa velocità per add/contains, iterazione prevedibile.
Vuoi un ordine ordinato → TreeSet. Algoritmo diverso, operazioni in tempo logaritmico.

Il motivo più comune per scegliere LinkedHashSet è difensivo: stai costruendo una API pubblica che restituisce un Set, e non vuoi che chi la usa dipenda dall'ordine arbitrario di HashSet. Un LinkedHashSet è la scelta più cortese — ha lo stesso contratto di un Set, ma l'iterazione è riproducibile tra esecuzioni e JVM diverse, il che rende l'output visibile all'utente stabile e i test più facili da scrivere.

Un esempio pratico: tag unici in ordine di arrivo

Il programma seguente costruisce due set dallo stesso flusso di input di tag: uno con HashSet, uno con LinkedHashSet. L'ordine di iterazione di HashSet dipende dalla JVM (è stabile ma arbitrario per una data JVM); l'ordine di LinkedHashSet è esattamente l'ordine in cui gli elementi unici sono comparsi per la prima volta. Poi mostra la regola "rimuovi e reinserisci", e infine costruisce un deduplicatore che preserva l'ordine in sole due righe.

java— editable, runs on the server

import java.util.*;
import java.util.stream.*;

public class LinkedHashSetShowcase {
  public static void main(String[] args) {
    String[] events = { "login", "view", "purchase", "view", "logout", "login", "view" };

Set<String> hashed = new HashSet<>();
    Set<String> linked = new LinkedHashSet<>();
    for (String e : events) { hashed.add(e); linked.add(e); }

System.out.println("input:    " + Arrays.toString(events));
    System.out.println("HashSet:        " + hashed + "   (order may be anything)");
    System.out.println("LinkedHashSet:  " + linked + "   (first-insertion order)");

// --- The 'first-insertion wins' rule ---
    Set<String> demo = new LinkedHashSet<>();
    demo.add("a"); demo.add("b"); demo.add("c");
    demo.add("a");                 // already there — order unchanged
    System.out.println("\nre-add 'a':       " + demo);
    demo.remove("a"); demo.add("a"); // gone then back — moves to end
    System.out.println("remove+re-add 'a': " + demo);

// --- Order-preserving deduplicator in two lines ---
    List<Integer> noisy = List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);
    List<Integer> deduped = noisy.stream()
        .collect(Collectors.toCollection(LinkedHashSet::new))
        .stream().toList();
    System.out.println("\nnoisy:    " + noisy);
    System.out.println("deduped:  " + deduped + "   (order preserved)");

// --- Iteration cost: LinkedHashSet visits size entries, not capacity slots ---
    Set<Integer> big = new LinkedHashSet<>(2_000_000); // huge capacity, few elements
    for (int i = 0; i < 10; i++) big.add(i);
    long t0 = System.nanoTime();
    int sum = 0;
    for (int x : big) sum += x;
    long t1 = System.nanoTime();
    System.out.println("\nsum of " + big.size() + " elements in a " + 2_000_000
        + "-bucket set: " + sum + "  in " + (t1 - t0) + " ns");
  }
}

Cosa leggere dall'esecuzione:

Il LinkedHashSet ha stampato gli eventi unici nell'ordine in cui sono comparsi per la prima volta. L'HashSet li ha stampati in un ordine completamente diverso — quello imposto dalla disposizione dei bucket.
Reinserire "a" non ha cambiato nulla nell'ordine. Rimuoverlo e reinserirlo lo ha spostato in fondo. È il primo inserimento che fissa la posizione.
Il deduplicatore che preserva l'ordine è una riga sola una volta che conosci il trucco: raccogliere in un LinkedHashSet, poi tornare a una lista.
La scansione di 10 elementi in un LinkedHashSet da 2 000 000 bucket ha percorso esattamente 10 voci; un HashSet della stessa forma avrebbe scansionato tutti i bucket vuoti nel mezzo.

Cosa c'è dopo

La terza implementazione standard di Set ti offre qualcosa che né HashSet né LinkedHashSet possono darti: iterazione ordinata e la possibilità di fare domande su intervalli come "ogni tag tra a e m." TreeSet è il prossimo.

Esercitati

Pratica

Cosa offre `LinkedHashSet` rispetto al normale `HashSet`?

Iterazione nell'ordine in cui gli elementi sono stati inseriti per la prima volta, al costo di due riferimenti extra per voceIterazione ordinata tramite l'ordinamento naturale degli elementiOperazioni thread-safe tramite lock interniRicerca in O(log n) invece di O(1), con ordine stabile come effetto collaterale