Le classi Set: HashSet, LinkedHashSet, TreeSet e EnumSet in Java

Concetti Chiave
  • Le classi Set in Java forniscono strutture dati per memorizzare collezioni di oggetti unici, senza duplicati.
  • HashSet utilizza una tabella hash per l'archiviazione, garantendo operazioni di inserimento, ricerca e rimozione efficienti.
  • LinkedHashSet estende HashSet e mantiene l'ordine di inserimento degli elementi, consentendo iterazioni nell'ordine in cui gli elementi sono stati aggiunti.
  • TreeSet implementa un set ordinato basato su un albero rosso-nero, garantendo che gli elementi siano sempre ordinati secondo il loro ordine naturale o un comparatore specificato.
  • EnumSet è un set specializzato per enumerazioni, che fornisce un modo efficiente per gestire collezioni di costanti enum, con metodi per creare set da enumerazioni e collezioni di enum.

La Classe HashSet

HashSet estende AbstractSet e implementa l'interfaccia Set.

Crea una collezione che usa una tabella hash per l'archiviazione. HashSet è una classe generica che ha questa dichiarazione:

class HashSet<E>

Qui, E specifica il tipo di oggetti che il set conterrà.

In breve, una tabella hash memorizza le informazioni utilizzando un meccanismo chiamato hashing. Nell'hashing, il contenuto informativo di una chiave viene utilizzato per determinare un valore univoco, chiamato il suo codice hash. Il codice hash viene quindi utilizzato come indice in cui vengono memorizzati i dati associati alla chiave.

La trasformazione della chiave nel suo codice hash viene eseguita automaticamente; in Java è raro usare il codice hash di un oggetto in maniera esplicita.

Inoltre, il codice non può indicizzare direttamente la tabella hash. Il vantaggio dell'hashing è che permette al tempo di esecuzione di add(), contains(), remove(), e size() di rimanere costante anche per set di grandi dimensioni.

I seguenti costruttori sono definiti:

HashSet()
HashSet(Collection<? extends E> c)
HashSet(int capacity)
HashSet(int capacity, float loadFactor)
  • La prima forma costruisce un hash set predefinito.
  • La seconda forma inizializza l'hash set utilizzando gli elementi di c.
  • La terza forma inizializza la capacità dell'hash set a capacity; la capacità predefinita è 16.

  • La quarta forma inizializza sia la capacità che il rapporto di riempimento (chiamato anche load factor) dell'hash set dai suoi argomenti.

    Il rapporto di riempimento deve essere tra 0.0 e 1.0, e determina quanto pieno può essere l'hash set prima che venga ridimensionato verso l'alto. Specificamente, quando il numero di elementi è maggiore della capacità dell'hash set moltiplicata per il suo rapporto di riempimento, l'hash set viene espanso. Per i costruttori che non prendono un rapporto di riempimento, viene utilizzato 0.75.

HashSet non definisce alcun metodo aggiuntivo oltre a quelli forniti dalle sue superclassi e interfacce.

È importante notare che HashSet non garantisce l'ordine dei suoi elementi, perché il processo di hashing di solito non si presta alla creazione di set ordinati. Se avete bisogno di archiviazione ordinata, allora un'altra collezione, come TreeSet, è una scelta migliore.

Ecco un esempio che dimostra HashSet:

// Dimostrazione di HashSet.
import java.util.*;

class DemoHashSet {

    public static void main(String[] args) {
        // Crea un hash set di stringhe.
        HashSet<String> hs = new HashSet<String>();

        // Aggiunge elementi all'hash set.
        hs.add("Beta");
        hs.add("Alpha");
        hs.add("Eta");
        hs.add("Gamma");
        hs.add("Epsilon");
        hs.add("Omega");
        System.out.println(hs);
    }

}

Il seguente è l'output di questo programma:

[Gamma, Eta, Alpha, Epsilon, Omega, Beta]

Come spiegato, gli elementi non vengono memorizzati in maniera ordinata, e l'output preciso può variare.

La Classe LinkedHashSet

La classe LinkedHashSet estende HashSet e non aggiunge membri propri. È una classe generica che ha questa dichiarazione:

class LinkedHashSet<E>

Qui, E specifica il tipo di oggetti che l'insieme conterrà. I suoi costruttori sono paralleli a quelli in HashSet.

LinkedHashSet mantiene una lista collegata delle voci nell'insieme, nell'ordine in cui sono state inserite. Questo consente l'iterazione nell'ordine di inserimento sull'insieme. Cioè, quando si scorre attraverso un LinkedHashSet usando un iteratore, gli elementi saranno restituiti nell'ordine in cui sono stati inseriti. Questo è anche l'ordine in cui sono contenuti nella stringa restituita da toString() quando chiamato su un oggetto LinkedHashSet.

Per vedere l'effetto di LinkedHashSet, proviamo a sostituire LinkedHashSet con HashSet nel programma precedente:

// Dimostrazione di HashSet.
// Usa LinkedHashSet invece di HashSet.
import java.util.*;

class DemoHashSet {

    public static void main(String[] args) {
        // Crea un hash set di stringhe.
        HashSet<String> hs = new LinkedHashSet<String>();

        // Aggiunge elementi all'hash set.
        hs.add("Beta");
        hs.add("Alpha");
        hs.add("Eta");
        hs.add("Gamma");
        hs.add("Epsilon");
        hs.add("Omega");
        System.out.println(hs);
    }

}

L'output sarà

[Beta, Alpha, Eta, Gamma, Epsilon, Omega]

che è l'ordine in cui gli elementi sono stati inseriti.

Da notare che per modificare il programma è bastato cambiare la riga:

HashSet<String> hs = new HashSet<String>();

in

HashSet<String> hs = new LinkedHashSet<String>();

Non abbiamo dovuto cambiare il tipo della variabile hs da HashSet a LinkedHashSet. Questo perché LinkedHashSet è una sottoclasse di HashSet, quindi può essere assegnata a una variabile di tipo HashSet.

La Classe TreeSet

TreeSet estende AbstractSet e implementa l'interfaccia NavigableSet.

Crea una collezione che utilizza un albero per la memorizzazione. Gli oggetti sono memorizzati in ordine crescente ordinato. I tempi di accesso e recupero sono piuttosto veloci, il che rende TreeSet una scelta eccellente quando si memorizzano grandi quantità di informazioni ordinate che devono essere trovate rapidamente.

TreeSet è una classe generica che ha questa dichiarazione:

class TreeSet<E>

Qui, E specifica il tipo di oggetti che l'insieme conterrà.

TreeSet ha i seguenti costruttori:

TreeSet()
TreeSet(Collection<? extends E> c)
TreeSet(Comparator<? super E> comp)
TreeSet(SortedSet<E> ss)
  • La prima forma costruisce un insieme ad albero vuoto che sarà ordinato in ordine crescente secondo l'ordine naturale dei suoi elementi.
  • La seconda forma costruisce un insieme ad albero che contiene gli elementi di c.
  • La terza forma costruisce un insieme ad albero vuoto che sarà ordinato secondo il comparatore specificato da comp. Studieremo i comparatori nelle prossime lezioni.
  • La quarta forma costruisce un insieme ad albero che contiene gli elementi di ss.

Ecco un esempio che dimostra l'uso di un TreeSet:

// Dimostrazione di TreeSet.
import java.util.*;

class DemoTreeSet {

    public static void main(String[] args) {
        // Crea un TreeSet di stringhe.
        TreeSet<String> ts = new TreeSet<String>();

        // Aggiunge elementi al TreeSet.
        ts.add("C");
        ts.add("A");
        ts.add("B");
        ts.add("E");
        ts.add("F");
        ts.add("D");

        // Stampa il TreeSet in ordine naturale.
        System.out.println(ts);

        // Ottiene tutti gli elementi *minori* di "D".
        SortedSet<String> ss = ts.headSet("D");
        System.out.println("Elementi minori di 'D': " + ss);

        // Ottiene tutti gli elementi
        // compresi tra C (incluso) e F (escluso).
        ss = ts.subSet("C", "F");
        System.out.println("Elementi tra 'C' e 'F': " + ss);
    }

}

L'output di questo programma è mostrato qui:

[A, B, C, D, E, F]
Elementi minori di 'D': [A, B, C]
Elementi tra 'C' e 'F': [C, D, E]

Come spiegato, poiché TreeSet memorizza i suoi elementi in un albero, essi saranno automaticamente disposti in modo ordinato, come conferma l'output.

Poiché TreeSet implementa l'interfaccia NavigableSet, è possibile utilizzare i metodi definiti da NavigableSet per recuperare elementi di un TreeSet. Ad esempio, ritornando al programma precedente, la seguente istruzione utilizza subSet() per ottenere un sottoinsieme di ts che contiene gli elementi tra C (incluso) e F (escluso). Quindi visualizza l'insieme risultante.

System.out.println(ts.subSet("C", "F"));

L'output di questa istruzione è mostrato qui:

[C, D, E]

La Classe EnumSet

EnumSet estende AbstractSet e implementa Set. È specificamente progettata per l'uso con elementi di tipo enum.

È una classe generica che ha questa dichiarazione:

class EnumSet<E extends Enum<E>>

Qui, E specifica gli elementi. Si noti che E deve estendere Enum<E>, il che impone il requisito che gli elementi devono essere del tipo enum specificato.

EnumSet non definisce costruttori. Invece, utilizza i metodi factory mostrati nella Tabella seguente per creare oggetti:

Metodo Descrizione
static <E extends Enum<E>> EnumSet<E> allOf(Class<E> t) Crea un EnumSet che contiene gli elementi nella'enumerazione specificata da t.
static <E extends Enum<E>> EnumSet<E> complementOf(EnumSet<E> e) Crea un EnumSet che è composto da quegli elementi non memorizzati in e.
static <E extends Enum<E>> EnumSet<E> copyOf(EnumSet<E> c) Crea un EnumSet dagli elementi memorizzati in c.
static <E extends Enum<E>> EnumSet<E> copyOf(Collection<E> c) Crea un EnumSet dagli elementi memorizzati in c.
static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> t) Crea un EnumSet che contiene gli elementi che non sono nell'enumerazione specificata da t, che è un insieme vuoto per definizione.
static <E extends Enum<E>> EnumSet<E> of(E v, E ... varargs) Crea un EnumSet che contiene v e zero o più valori di enumerazione aggiuntivi.
static <E extends Enum<E>> EnumSet<E> of(E v) Crea un EnumSet che contiene v.
static <E extends Enum<E>> EnumSet<E> of(E v1, E v2) Crea un EnumSet che contiene v1 e v2.
static <E extends Enum<E>> EnumSet<E> of(E v1, E v2, E v3) Crea un EnumSet che contiene v1 fino a v3.
static <E extends Enum<E>> EnumSet<E> of(E v1, E v2, E v3, E v4) Crea un EnumSet che contiene v1 fino a v4.
static <E extends Enum<E>> EnumSet<E> of(E v1, E v2, E v3, E v4, E v5) Crea un EnumSet che contiene v1 fino a v5.
static <E extends Enum<E>> EnumSet<E> range(E start, E end) Crea un EnumSet che contiene gli elementi nell'intervallo specificato da start e end.
Tabella 1: Metodi definiti da EnumSet

Tutti i metodi possono lanciare NullPointerException. I metodi copyOf() e range() possono anche lanciare IllegalArgumentException. Notare che il metodo of() è sovraccaricato più volte. Questo è nell'interesse dell'efficienza. Passare un numero noto di argomenti può essere più veloce che utilizzare un parametro vararg quando il numero di argomenti è piccolo.

Ecco un esempio che dimostra EnumSet:

// Dimostrazione di EnumSet.
import java.util.*;

// Una enumerazione che rappresenta i giorni della settimana.
enum Giorno {
    LUNEDI,
    MARTEDI,
    MERCOLEDI,
    GIOVEDI,
    VENERDI,
    SABATO,
    DOMENICA
}

public class EnumSetDemo {
    public static void main(String[] args) {
        // Crea un EnumSet contenente alcuni giorni della settimana.
        EnumSet<Giorno> giorni = EnumSet.of(
            Giorno.LUNEDI,
            Giorno.MARTEDI,
            Giorno.GIOVEDI
        );

        // Stampa i giorni selezionati.
        System.out.println("Giorni selezionati: " + giorni);

        // Aggiunge un giorno all'EnumSet.
        giorni.add(Giorno.SABATO);
        System.out.println("Dopo l'aggiunta di SABATO: " + giorni);

        // Rimuove un giorno dall'EnumSet.
        giorni.remove(Giorno.MARTEDI);
        System.out.println("Dopo la rimozione di MARTEDI: " + giorni);

        // Verifica se un giorno è presente nell'EnumSet.
        if (giorni.contains(Giorno.VENERDI)) {
            System.out.println("VENERDI è presente nell'EnumSet.");
        } else {
            System.out.println("VENERDI non è presente nell'EnumSet.");
        }
    }

}

L'output di questo programma è mostrato qui:

Giorni selezionati: [LUNEDI, MARTEDI, GIOVEDI]
Dopo l'aggiunta di SABATO: [LUNEDI, MARTEDI, GIOVEDI, SABATO]
Dopo la rimozione di MARTEDI: [LUNEDI, GIOVEDI, SABATO]
VENERDI non è presente nell'EnumSet.

Come si può vedere, EnumSet consente di creare un insieme di elementi di tipo enum e fornisce metodi per aggiungere, rimuovere e verificare la presenza di elementi nell'insieme.