Un set este pur și simplu o colecție de obiecte unice. Unic înseamnă că două obiecte nu pot avea aceeași valoare(e). În funcție de implementarea setului, acesta poate fi comandat sau nu. Setul Java, ca tip de date abstracte (ADT), are câteva operații cheie (unde T reprezintă orice tip de date, de exemplu int, String sau orice obiect de clasă):
boolean add(T item): returnează true dacă elementul a fost adăugat cu succes la set și false dacă elementul a fost deja în set.
boolean remove(T item): returnează adevărat dacă elementul a fost eliminat cu succes din set și fals în caz contrar (dacă elementul nu a fost în set).
boolean contains(T item): returnează true dacă elementul este în set și false în caz contrar.
boolean isEmpty(): returnează adevărat dacă setul este gol și fals în caz contrar.
Seturile din Java au semnături de funcții destul de explicite (cum ar trebui). Dacă adăugați două articole identice la un set, atunci doar primul articol adăugat va fi în set. Toate încercările ulterioare de a adăuga același element vor fi ignorate, cu excepția cazului în care elementul este mai întâi eliminat. Una dintre cele mai frecvent utilizate operațiuni de set este verificarea dacă un articol se află într-un anumit set. Funcția contains()oferă o durată de rulare excelentă pentru aceasta: complexitatea timpului O(1) sau O(log n) în funcție de dacă implementarea utilizată este a HashSetsau aTreeSet, respectiv. Deci, la ce ar putea fi folosit un set? Ei bine, dacă trebuie vreodată să urmăriți multe obiecte distincte - cum ar fi ID-uri, nume sau alți identificatori unici - și să verificați frecvent dacă un articol există într-o astfel de colecție, atunci un set este probabil o alegere bună. Iată un exemplu de caz de utilizare al unui set: Imaginați-vă că aveți o listă de Studentobiecte reprezentând toți elevii dintr-o clasă dată. Fiecare Studentar putea avea un nume unic (șir) și un grad (int) pentru această clasă. Dacă doriți să faceți referire frecvent la o listă cu toți studenții A (nota >=90), atunci ar fi plictisitor să parcurgeți această listă și să verificați de fiecare dată nota fiecărui elev. În schimb, ați putea folosi un șir HashSetde caractere care ține evidența tuturor elevilor A din clasă, ca atare:
De fiecare dată când notele elevilor sunt actualizate, puteți verifica pur și simplu dacă noua notă a Studentului este mai mare sau egală cu 90 sau nu.
Dacă da, adăugați-le la setul de elevi A care folosescadd()
Dacă erau deja un student A, atunci această operație este pur și simplu ignorată.
Dacă nu, atunci eliminați-le din setul de elevi A care folosescremove()
Dacă nu erau elevi A în acest moment, atunci această operație este pur și simplu ignorată.
Cu un astfel de sistem, veți avea întotdeauna un set actualizat de toți elevii „A” din clasa dumneavoastră. Dacă ai vrut să verifici dacă Johnny Appleseed se descurcă bine în clasa ta, ai putea face asta cu ușurință sunând contains(“Johnny Appleseed”)pe platou. Desigur, acesta este doar un exemplu de caz de utilizare pentru un set, iar această problemă specifică de a ține evidența elevilor A ar putea fi rezolvată în alte moduri.
Implementări: HashSet în Java și exemple Java TreeSet
Atât HashSetîn Java cât și TreeSetîn Java vin în java.utils package. Le puteți importa ca atare:
// imports everything from Java's util package, including HashSet and TreeSet
import java.util.*;
sau
import java.util.HashSet; // imports only the Java HashSet
import java.util.TreeSet; // imports only the Java TreeSet
Diferența cheie dintre Java HashSetși Java TreeSeteste că TreeSeteste sortat, în timp ce HashSetnu este. Acesta este motivul pentru care TreeSetare O(log n) complexitate în timp pentru operațiile cheie, în timp ce HashSetare O(1) sau complexitate în timp constantă; trebuie TreeSetsă mențină ordinea în orice moment. În plus față de operațiunile setului de chei menționate mai devreme, atât în Java HashSetcât și TreeSetîn Java au câteva alte funcții utile:
void clear(): șterge setul de toate obiectele.
int size(): returnează numărul de obiecte din set.
Object clone(): returnează o copie superficială a setului.
Iterator iterator(): returnează un iterator la set, începând de la primul obiect.
Vă puteți imagina că găsiți utilizări pentru aceste funcții în exemplul „lista studenților A”: puteți suna size()dacă doriți să vedeți câți studenți „A” aveți sau clear()dacă doriți să ștergeți lista la sfârșitul semestrului. Puteți clone()să creați și să păstrați o clonă a listei de studenți A la un moment dat, cum ar fi în timpul rapoartelor intermediare (în acest fel, clona nu rămâne la zi împreună cu originalul).
Exemplu Java HashSet
Iată un scurt exemplu de utilizare a HashSeta din s în Java:String
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"));
}
}
Ieșire: --------
[Collin, Bob, Abigail]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Exemplu Java TreeSet
Exemplul de set Java vă poate ajuta să înțelegeți teoria. Iată un scurt exemplu de utilizare TreeSeta a din s în Java:String
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());
}
}
Ieșire: -------
[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