Un set è semplicemente una raccolta di oggetti unici. Univoco significa che due oggetti non possono avere gli stessi valori. A seconda dell'implementazione del set, può essere ordinato o meno. Il set Java, come tipo di dati astratto (ADT), ha alcune operazioni chiave (dove T rappresenta qualsiasi tipo di dati, ad esempio int, String o qualsiasi oggetto di classe):
boolean add(T item): restituisce true se l'elemento è stato aggiunto correttamente all'insieme e false se l'elemento era già nell'insieme.
boolean remove(T item): restituisce true se l'elemento è stato rimosso con successo dal set e false in caso contrario (se l'elemento non era nel set).
boolean contains(T item): restituisce true se l'elemento è nel set e false in caso contrario.
boolean isEmpty(): restituisce vero se l'insieme è vuoto e falso altrimenti.
I set in Java hanno firme di funzioni piuttosto autoesplicative (come dovrebbero). Se aggiungi due elementi identici a un set, solo il primo elemento aggiunto sarà nel set. Tutti i successivi tentativi di aggiungere lo stesso elemento verrebbero ignorati a meno che l'elemento non venga prima rimosso. Una delle operazioni sugli insiemi più comunemente utilizzate è il controllo se un elemento si trova all'interno di un determinato insieme. La contains()funzione offre un ottimo runtime per questo: complessità temporale O(1) o O(log n) a seconda che l'implementazione utilizzata sia a HashSeto aTreeSet, rispettivamente. Quindi per cosa potrebbe essere usato un set? Bene, se hai mai bisogno di tenere traccia di molti oggetti distinti, come ID, nomi o altri identificatori univoci, e controllare frequentemente se un elemento esiste in una tale raccolta, allora un set è probabilmente una buona scelta. Ecco un esempio di caso d'uso di un set: immagina di avere un elenco di Studentoggetti che rappresentano tutti gli studenti di una determinata classe. Ognuno Studentpotrebbe avere un nome univoco (stringa) e un grado (int) per questa classe. Se volessi fare frequentemente riferimento a un elenco di tutti gli studenti A (voto >=90), sarebbe noioso scorrere questo elenco e controllare ogni volta il voto di ogni studente. Invece, potresti usare a HashSetof strings che tiene traccia di tutti gli studenti A della classe, in questo modo:
Ogni volta che i voti degli Studenti vengono aggiornati, puoi semplicemente controllare se il nuovo voto dello Studente è maggiore o uguale a 90 oppure no.
In tal caso, aggiungili all'insieme degli studenti A che utilizzanoadd()
Se erano già studenti A, questa operazione viene semplicemente ignorata.
In caso contrario, rimuovili dall'insieme degli studenti A che utilizzanoremove()
Se a questo punto non erano studenti A, questa operazione viene semplicemente ignorata.
Con un tale sistema, avresti sempre un insieme aggiornato di tutti gli studenti "A" della tua classe. Se volevi controllare se Johnny Appleseed stava andando bene nella tua classe, potresti farlo facilmente chiamando contains(“Johnny Appleseed”)sul set. Naturalmente, questo è solo un esempio di caso d'uso per un set e questo problema specifico di tenere traccia degli studenti A potrebbe essere risolto in altri modi.
Implementazioni: HashSet in Java e Java TreeSet Esempi
Sia HashSetin Java che TreeSetin Java sono disponibili nel formato java.utils package. Puoi importarli come tali:
// imports everything from Java's util package, including HashSet and TreeSet
import java.util.*;
O
import java.util.HashSet; // imports only the Java HashSet
import java.util.TreeSet; // imports only the Java TreeSet
La differenza fondamentale tra Java HashSete Java TreeSetè che TreeSetè ordinato, mentre HashSetnon lo è. Questo è il motivo per cui TreeSetha complessità temporale O(log n) per le operazioni chiave, mentre HashSetha complessità temporale O(1) o costante; il TreeSetdeve mantenere l'ordine in ogni momento. Oltre alle operazioni sugli insiemi di chiavi menzionate in precedenza, sia HashSete TreeSetin Java hanno alcune altre funzioni utili:
void clear(): cancella l'insieme di tutti gli oggetti.
int size(): restituisce il numero di oggetti nell'insieme.
Object clone(): restituisce una copia superficiale dell'insieme.
Iterator iterator(): restituisce un iteratore all'insieme, a partire dal primo oggetto.
Puoi immaginare di trovare usi per queste funzioni nell'esempio "elenco di studenti A": potresti chiamare size()se vuoi vedere quanti studenti 'A' hai avuto, o clear()se vuoi cancellare l'elenco alla fine del semestre. Potresti usare clone()per creare e conservare un clone dell'elenco degli studenti A in un momento specifico, ad esempio durante i rapporti intermedi (in questo modo il clone non rimane aggiornato insieme all'originale).
Esempio di hashset Java
Ecco un breve esempio di a HashSetof Strings utilizzato in Java:
import java.util.HashSet;
class HashSetDemo {
public static void main(String[] args)
{
// create a HashSet of Strings
HashSet<String> hs = new HashSet<String>();
// Add elements using the add() method
hs.add("Collin");
hs.add("Bob");
hs.add("Abigail");
// Duplicates will ignored; this statement is useless
hs.add("Collin");
System.out.println(hs);
System.out.println("Bob is in the set (T/F): " + hs.contains("Bob"));
System.out.println("Max is in the set (T/F): " + hs.contains("Max"));
}
}
Produzione: --------
[Collin, Bob, Abigail]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Esempio Java TreeSet
L'esempio del set Java potrebbe aiutarti a comprendere la teoria. Ecco il breve esempio di a TreeSetof Strings utilizzato in Java:
import java.util.TreeSet;
class TreeSetDemo {
public static void main(String[] args)
{
// create a TreeSet of Strings
TreeSet<String> ts = new TreeSet<String>();
// Add elements using the add() method.
ts.add("Collin");
ts.add("Bob");
ts.add("Abigail");
// Duplicates will ignored; this statement is useless
ts.add("Collin");
// printing the set prints the names in alphabetical order!
System.out.println(ts);
System.out.println("Bob is in the set (T/F): " + ts.contains("Bob"));
System.out.println("Max is in the set (T/F): " + ts.contains("Max"));
System.out.println("Size of the set: " + ts.size());
ts.clear();
System.out.println("Size of the set after clear(): " + ts.size());
}
}
Produzione: -------
[Abigail, Bob, Collin]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Size of the set: 3
Size of the set after clear(): 0
GO TO FULL VERSION