Classe Java HashSet | W3Docs Learn Java

HashSet<E> è l'implementazione a cui si ricorre per prima quando si vuole un insieme. È supportata da una tabella hash — internamente è una HashMap con un valore fittizio — quindi add, remove e contains hanno costo atteso O(1): il costo è un hash dell'elemento più uno o due controlli di uguaglianza, indipendentemente da quanti elementi siano già presenti nell'insieme. È questa proprietà che rende gli hash set la risposta giusta per le domande "ho già visto questo?", i passaggi di deduplicazione e qualsiasi controllo di appartenenza che sarebbe quadratico su una List.

Cosa significa davvero "tempo quasi costante"

Il tempo costante non è gratuito; è ammortizzato. Ogni operazione esegue approssimativamente questo:

Calcola e.hashCode(). Mescola i bit alti e bassi in modo che un hash come 0x...0000 non collassi nel bucket 0.
Cerca il bucket a bucketIndex = hash & (table.length - 1).
Scorre la catena collegata del bucket (o, da Java 8, un piccolo albero bilanciato se la catena è diventata lunga) chiamando equals finché non trova l'elemento o raggiunge la fine.

Il passo 3 è dove il costo va storto se hashCode è scadente. Con un hash ragionevole, la catena è lunga uno o due elementi; con un hash costante, è pari a tutti gli elementi mai inseriti. Questa è la differenza tra O(1) e O(n) per operazione.

Capacità, fattore di carico e rihashing

Un HashSet ha un array di bucket di supporto. Due parametri del costruttore lo controllano:

Capacità iniziale — il numero iniziale di bucket. Predefinita a 16. Arrotondata alla potenza di due superiore.
Fattore di carico — il rapporto tra elementi e bucket al quale la tabella raddoppia di dimensione. Predefinito a 0.75.

Quando size / capacity supera il fattore di carico, l'insieme esegue il rihashing: alloca un nuovo array due volte più grande e ri-assegna ogni elemento al bucket corretto. Un rihashing è O(n) — questo è il costo che viene ammortizzato sulle O(1) inserzioni precedenti. Il pre-dimensionamento di un insieme che si sa conterrà circa 1.000.000 di elementi risparmia venti raddoppi:

Set<Long> ids = new HashSet<>(1_500_000); // skip the doublings up to ~1M

Fattori di carico più bassi (ad es. 0.5) sprecano memoria ma riducono le collisioni; quelli più alti (ad es. 0.9) comprimono di più ma allungano le catene. Il valore predefinito 0.75 è un equilibrio calibrato da Sun decenni fa e regge ancora — non toccarlo senza un benchmark.

Null, ordinamento, sicurezza nei thread

Tre regole:

È consentito un elemento null. HashSet lo memorizza nel bucket 0 con un hash speciale di 0. È una comodità deliberata — Map.of/Set.of e TreeSet vietano entrambi null.
Non è garantito alcun ordine di iterazione. L'ordine cambia quando la tabella esegue il rihashing e non è nemmeno coerente tra JVM. Se hai bisogno dell'ordine di inserimento, usa LinkedHashSet; se hai bisogno dell'ordine ordinato, usa TreeSet.
Non è thread-safe. Una mutazione concorrente corromperà la struttura. Per il codice multi-thread usa ConcurrentHashMap.newKeySet() (una vista Set di una mappa concorrente) oppure avvolgi in Collections.synchronizedSet.

`hashCode` è tua responsabilità

Inserire la tua classe in un HashSet funziona solo se si sovrascrivono hashCode e equals in modo coerente. Il contratto di Object:

Se a.equals(b) allora a.hashCode() == b.hashCode().
Se a.hashCode() == b.hashCode(), a.equals(b) può comunque essere false (una collisione).

Violare la prima metà del contratto è la fonte più comune del bug "l'ho aggiunto, ma contains restituisce false". I moderni IDE e la parola chiave record generano entrambi i metodi automaticamente — usali.

record Tag(String name) {}            // hashCode/equals auto-generated
Set<Tag> tags = new HashSet<>();
tags.add(new Tag("java"));
System.out.println(tags.contains(new Tag("java"))); // true

La trappola degli elementi mutabili

Un bug più subdolo: memorizzare un oggetto il cui hashCode dipende da campi mutabili e poi mutarlo dopo l'inserimento. L'hash che ha deciso in quale bucket vive l'elemento è stato calcolato al momento dell'inserimento; una volta che si cambia un campo su cui si basa l'hash, l'oggetto si trova nel bucket "sbagliato" e contains percorre una catena che non lo include — anche se è esattamente lo stesso riferimento.

class Box {
    int n;
    Box(int n) { this.n = n; }
    @Override public boolean equals(Object o) {
        return o instanceof Box b && b.n == n;
    }
    @Override public int hashCode() { return Integer.hashCode(n); }
}

Box box = new Box(1);
Set<Box> set = new HashSet<>();
set.add(box);
box.n = 2;                  // mutate a field hashCode depends on
System.out.println(set.contains(box)); // false — element is now in the wrong bucket

Nota che questo problema si verifica solo quando hashCode legge uno stato mutabile. StringBuilder, ad esempio, usa l'hashing per identità, quindi mutarlo non lo sposta mai tra i bucket — ma fare affidamento su ciò è fragile. La soluzione non è essere furbi; è inserire elementi immutabili negli hash set. String, Integer, i tuoi record, DTO istantaneamente acquisiti. Se hai bisogno di un insieme indicizzato da uno stato mutabile, indicizzalo tramite una proiezione immutabile di esso.

Un esempio pratico: deduplicazione, appartenenza e capacità

Il programma qui sotto dimostra le quattro ragioni per cui si sceglie HashSet: deduplicazione, test di appartenenza veloci, algebra degli insiemi e il costo di un hashCode scadente.

java— editable, runs on the server

import java.util.*;

public class HashSetShowcase {
  // Element whose hashCode depends on a mutable field -- the trap waiting to happen.
  static class Box {
    int n;
    Box(int n) { this.n = n; }
    @Override public boolean equals(Object o) { return o instanceof Box b && b.n == n; }
    @Override public int hashCode() { return Integer.hashCode(n); }
    @Override public String toString() { return "Box(" + n + ")"; }
  }

public static void main(String[] args) {
    // --- 1. Deduplication of a stream of inputs ---
    String[] raw = { "java", "Java", "java", "python", "java", "go", "go" };
    Set<String> unique = new HashSet<>();
    for (String s : raw) unique.add(s);
    System.out.println("input size:  " + raw.length);
    System.out.println("unique size: " + unique.size());
    System.out.println("unique:      " + unique);

// --- 2. Membership against a 1M-element set ---
    Set<Integer> big = new HashSet<>(1_500_000); // pre-sized
    for (int i = 0; i < 1_000_000; i++) big.add(i);
    long t0 = System.nanoTime();
    boolean found = big.contains(999_999);
    long t1 = System.nanoTime();
    System.out.println("\ncontains in 1M-set: " + found + "  (" + (t1 - t0) + " ns)");

// --- 3. The records-as-elements pattern ---
    record Tag(String name) {}
    Set<Tag> tags = new HashSet<>();
    tags.add(new Tag("java"));
    tags.add(new Tag("java")); // duplicate by equals -> not added
    System.out.println("\ntag set: " + tags + "  size=" + tags.size());

// --- 4. The mutable-element trap ---
    Box box = new Box(1);
    Set<Box> bad = new HashSet<>();
    bad.add(box);
    box.n = 2;                 // change a field hashCode depends on
    System.out.println("\nafter mutation, contains(box)? " + bad.contains(box)
        + "   (same object, but now in the wrong bucket)");
  }
}

Cosa ricordare:

Il ciclo di deduplicazione è O(n) — ogni add ha costo costante e il unique.size() finale è il numero di input distinti.
Un contains in un insieme di 1.000.000 di elementi ha risposto in microsecondi. È questa la proprietà che rende HashSet lo strumento di test di appartenenza del JDK.
Il record Tag ottiene equals/hashCode gratuitamente, quindi due oggetti Tag("java") si riducono a un unico elemento.
L'esempio Box è la trappola: lo stesso oggetto, mutato dopo l'inserimento in modo che il suo hashCode sia cambiato, ora riporta contains(box) == false. Inserisci elementi immutabili negli hash set.

Cosa c'è dopo

HashSet non garantisce alcun ordine di iterazione. Se hai bisogno di ricordare l'ordine in cui hai inserito gli elementi — ad esempio stai costruendo un elenco di tag e l'utente si aspetta di vederli nell'ordine in cui sono stati aggiunti — lo strumento giusto è LinkedHashSet. Questo è il capitolo successivo.

Esercitati

Pratica

Inserisci la tua classe `Customer` in un `HashSet`, poi la cerchi e `contains` restituisce `false` per un `Customer` che dovrebbe essere uguale a quello inserito. Qual è la causa più probabile?

`Customer` sovrascrive `equals` ma non `hashCode` (o sono incoerenti), quindi la ricerca finisce in un bucket diverso`HashSet` accetta solo elementi che implementano `Comparable`L'insieme ha eseguito il rihashing durante l'inserimento e ha perso l'elemento`HashSet.contains` usa l'uguaglianza per riferimento, non `equals`