Interfaccia Set in Java
Collezioni di elementi unici in Java con l'interfaccia Set e le sue principali implementazioni.
Set<E> è una Collection<E> con una regola aggiuntiva: nessun duplicato. L'interfaccia in sé aggiunge quasi nessun metodo nuovo — eredita add, remove, contains, size, iterator e il resto. Ciò che cambia sono le garanzie di quei metodi: add(e) restituisce false (e non modifica nulla) se un elemento uguale è già presente nel set; due set sono equals se contengono gli stessi elementi indipendentemente dall'ordine; e hashCode è la somma degli hash degli elementi, in modo che set uguali abbiano sempre lo stesso valore.
Quel piccolo contratto — "gli elementi sono unici" — si rivela essere esattamente ciò di cui hai bisogno per test di appartenenza, deduplicazione, intersezione/unione e mille altri pattern che con una List risulterebbero difficili da leggere.
Cosa conta come duplicato
Un Set determina la duplicazione tramite equals (e, nei set basati su hash, hashCode come funzione di bucketing). Non è uguaglianza per riferimento, né "sembra uguale quando stampato." Se inserisci la tua classe in un Set devi fare l'override di entrambi i metodi insieme; il capitolo su equals e hashCode ha trattato il contratto.
Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("java"); // add returns false; the set still has one element
tags.add(new String("java")); // also false — equals, not referenceUn'insidia comune: inserire elementi mutabili e poi modificarli mentre si trovano in un set basato su hash. L'hash dell'elemento cambia, il set lo cerca nel bucket sbagliato e contains inizia a mentire. La regola: se inserisci un oggetto in un hash set, trattalo come effettivamente immutabile da quel momento in poi. TreeSet ha la stessa trappola con compareTo.
Le quattro implementazioni standard
java.util fornisce quattro implementazioni di Set che coprono quasi ogni caso d'uso:
| Classe | Struttura sottostante | Ordinamento | Elementi null | Utilizzo tipico |
|---|---|---|---|---|
HashSet | tabella hash | nessuno | un null consentito | quella predefinita — test di appartenenza più veloci |
LinkedHashSet | tabella hash + lista doppiamente collegata | ordine di inserimento | un null consentito | quando l'ordine di iterazione deve corrispondere all'ordine di inserimento |
TreeSet | albero rosso-nero | ordine naturale / comparatore | nessun null | quando si necessita di iterazione ordinata o query su intervalli |
EnumSet | vettore di bit | ordine di dichiarazione enum | nessun null | un Set<MyEnum> — compatto, veloce, ordinato |
Le prime tre sono trattate nei tre capitoli successivi; EnumSet è trattato più avanti nel libro insieme a EnumMap.
Le operazioni bulk: unione, intersezione, differenza
Un Set eredita quattro operazioni bulk da Collection, e su un Set assumono i significati della teoria degli insiemi:
addAll(other)— unione (in loco). Dopo la chiamata,acontiene ogni elemento di entrambi i lati.retainAll(other)— intersezione (in loco). Dopo la chiamata,acontiene solo gli elementi presenti anche inother.removeAll(other)— differenza (in loco). Dopo la chiamata,acontiene solo gli elementi che non erano inother.containsAll(other)— test di sottoinsieme. Restituiscetruese ogni elemento diotherè presente ina.
Queste operazioni modificano il ricevente. Se hai bisogno di una versione non distruttiva, copia prima: Set<E> u = new HashSet<>(a); u.addAll(b);.
Uguaglianza e codici hash dei set
Il contratto Set per equals è insolito: due set sono uguali se contengono gli stessi elementi, indipendentemente dall'ordine o dal tipo di implementazione. Un HashSet, un LinkedHashSet e un TreeSet con gli stessi elementi risultano tutti uguali tra loro.
Set<Integer> a = new HashSet<>(List.of(1, 2, 3));
Set<Integer> b = new TreeSet<>(List.of(3, 2, 1));
System.out.println(a.equals(b)); // trueEcco perché le operazioni bulk e i metodi factory immutabili possono passare liberamente tra implementazioni — viene osservata solo la regola "stessi elementi".
Factory di sola lettura e immutabili
Da Java 9 il modo più semplice per creare un set piccolo e fisso è Set.of(...):
Set<String> primary = Set.of("red", "green", "blue");Set.of restituisce un set immutabile che rifiuta elementi null e lancia un'eccezione se si passa un duplicato al momento della costruzione. Per uno snapshot difensivo di un set esistente, usa Set.copyOf(existing) — anch'esso immutabile e che rifiuta i null.
Per una vista che nasconde le mutazioni (l'originale può ancora essere modificato, ma i chiamanti non possono aggiungere tramite la vista) usa Collections.unmodifiableSet(s). Il capitolo sulle collezioni non modificabili più avanti in questa parte spiega quando scegliere quale opzione.
Un esempio pratico: deduplicazione, algebra degli insiemi e ordinamento
Il programma seguente utilizza tutte e quattro le implementazioni, dimostra le operazioni bulk su dati reali e mostra come l'ordine di iterazione differisce tra HashSet, LinkedHashSet e TreeSet.
Cosa ricavare dall'esecuzione:
addha restituitofalseper ogni\"java\"duplicato — ecco come si scrive un deduplicatore in due righe.- Unione, intersezione e differenza si ottengono ciascuna con un solo
addAll/retainAll/removeAll— copia prima se non vuoi perdere l'originale. - Le tre implementazioni contengono gli stessi elementi e risultano uguali, ma iterano in ordini molto diversi. Scegli l'implementazione in base all'ordine di cui hai bisogno, non per abitudine.
Cosa c'è dopo
L'implementazione di Set più comune — quella a cui si ricorre salvo motivi specifici — è basata su tabella hash. HashSet è il prossimo argomento; tratteremo il fattore di carico, il rehash e cosa significa "tempo quasi costante" in pratica.