HashSet in Java: valori unici, appartenenza e operazioni sugli insiemi

Un set memorizza valori unici

Un HashSet (di java.util) è una collezione che contiene ogni valore al massimo una volta. Non ci sono chiavi e valori abbinati come in una HashMap: solo un contenitore di elementi distinti. Il suo compito è rispondere in fretta a una sola domanda: "questa cosa è qui dentro?"

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("java");   // duplicato: viene ignorato

        System.out.println(tags.contains("java"));     // true
        System.out.println(tags.contains("frontend")); // false
        System.out.println(tags.size());               // 2
    }
}

C'è un solo parametro di tipo, <ElementType>. Come per ArrayList e HashMap, di solito dichiari la variabile con l'interfaccia Set e costruisci un HashSet.

add ti dice se il valore era nuovo

add non si limita a memorizzare il valore: restituisce un boolean che ti dice se l'insieme è effettivamente cambiato. Aggiungere un valore già presente restituisce false e lascia l'insieme invariato.

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();

        System.out.println(seen.add(7));  // true: 7 era nuovo
        System.out.println(seen.add(7));  // false: c'era già
        System.out.println(seen);
    }
}

Quel valore di ritorno è davvero utile: if (!seen.add(x)) { /* x is a repeat */ } ti permette di rilevare i duplicati in una sola riga mentre procedi.

Rimuovere i duplicati da una lista

Dato che un set rifiuta le ripetizioni, il modo più veloce per eliminare i duplicati da una collezione è riversarla in un set. Il costruttore di HashSet accetta qualsiasi altra collezione:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ada", "Boris", "Ada", "Chen", "Boris"));

        Set<String> unique = new HashSet<>(names);
        System.out.println(unique);          // ogni nome una volta
        System.out.println(unique.size());   // 3

        // ti serve di nuovo una List?
        List<String> deduped = new ArrayList<>(unique);
        System.out.println(deduped.size());  // 3
    }
}

È il motivo più comune per cui i principianti usano un set. Sappi solo che nel passaggio perdi l'ordine originale: usa LinkedHashSet se l'ordine conta (ne parliamo più sotto).

contains, remove e size

Le operazioni di tutti i giorni rispecchiano quelle delle altre collezioni:

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("api");

        System.out.println(tags.contains("api"));  // true
        System.out.println(tags.size());           // 3

        tags.remove("backend");
        System.out.println(tags.contains("backend")); // false

        tags.clear();
        System.out.println(tags.isEmpty());         // true
    }
}

Il grande vantaggio rispetto a un ArrayList è contains. Una lista deve scorrere ogni elemento per rispondere (O(n)); un HashSet arriva quasi direttamente alla risposta (circa O(1)). Quando ti ritrovi a chiamare list.contains(...) dentro un ciclo, di solito è il segnale per passare a un set.

Operazioni sugli insiemi: unione, intersezione, differenza

I set danno il meglio quando li combini. I metodi si leggono in modo naturale una volta capito quale fa cosa:

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);            // tutto ciò che sta in uno dei due
        System.out.println(union);  // 1 2 3 4 5 6

        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);  // solo ciò che sta in entrambi
        System.out.println(intersection); // 3 4

        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);    // in a ma non in b
        System.out.println(difference);   // 1 2
    }
}

La trappola principale: addAll, retainAll e removeAll modificano l'insieme su cui vengono chiamati. Ecco perché ogni esempio copia prima a in un nuovo HashSet: altrimenti distruggeresti l'originale. Crea un nuovo set per ogni risultato.

HashSet non mantiene l'ordine

Come HashMap, un HashSet non garantisce alcun ordine di iterazione, e l'ordine può cambiare da un'esecuzione all'altra. Se ti serve prevedibilità:

• LinkedHashSet mantiene l'ordine di inserimento, cioè l'ordine in cui hai aggiunto gli elementi.
• TreeSet tiene gli elementi ordinati secondo l'ordine naturale (o secondo un Comparator che fornisci tu).

import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> insertion = new LinkedHashSet<>();
        insertion.add("gamma");
        insertion.add("alpha");
        insertion.add("beta");
        System.out.println(insertion);  // [gamma, alpha, beta]

        Set<String> sorted = new TreeSet<>(insertion);
        System.out.println(sorted);      // [alpha, beta, gamma]
    }
}

Tutte e tre implementano l'interfaccia Set, quindi passare dall'una all'altra è una modifica di una riga al costruttore.

Gli elementi devono essere hashabili

Dietro le quinte un HashSet si appoggia a una HashMap, quindi vale la stessa regola: trova gli elementi calcolandone l'hash, il che significa che hashCode() ed equals() di un elemento devono essere coerenti. I tipi predefiniti come String e Integer lo fanno già correttamente, ed è per questo che le stringhe "java" duplicate qui sopra vengono unite correttamente. Se memorizzi istanze di una tua classe, fai l'override sia di equals sia di hashCode: altrimenti due oggetti "uguali" nel significato verranno trattati come distinti, e contains e la rimozione dei duplicati falliranno in silenzio.

Prossimo passo: scorrere le collezioni

Ora conosci le tre collezioni fondamentali: ArrayList, HashMap e HashSet. Ognuna si scorre in modo un po' diverso, e ci sono trappole sottili (come modificare una collezione mentre la stai scorrendo). Nella prossima pagina metteremo tutto insieme e vedremo come scorrere le collezioni in modo pulito con il ciclo for-each, gli iteratori e forEach.