Java HashSet clasa implementează interfața Set, susținută de un tabel hash care este de fapt o instanță HashMap. Nu se face nicio garanție în ceea ce privește ordinea de iterație a seturilor hash, ceea ce înseamnă că clasa nu garantează ordinea constantă a elementelor în timp. Această clasă permite elementul nul. Clasa oferă, de asemenea, performanță constantă în timp pentru operațiunile de bază, cum ar fi adăugarea, eliminarea, conținutul și dimensiunea, presupunând că funcția hash dispersează elementele în mod corespunzător printre găleți, ceea ce vom vedea mai departe în articol.
Caracteristici Java HashSet
Câteva caracteristici importante ale HashSet sunt menționate mai jos:
- Implementări Setați interfața .
- Structura de date de bază pentru HashSet este Hashtable .
- Deoarece implementează interfața Set, valorile duplicat nu sunt permise.
- Nu se garantează că obiectele pe care le introduceți în HashSet vor fi inserate în aceeași ordine. Obiectele sunt inserate pe baza codului lor hash.
- Elementele NULL sunt permise în HashSet.
- HashSet implementează și Serializabil și Clonabil interfețe.
Declarația HashSet
public class HashSet extends AbstractSet implements Set, Cloneable, Serializable>
Unde ȘI este tipul de elemente stocate într-un HashSet.
Exemplu Java HashSet
Java
// Java program to illustrate the concept> // of Collection objects storage in a HashSet> import> java.io.*;> import> java.util.*;> > class> CollectionObjectStorage {> > >public> static> void> main(String[] args)> >{> >// Instantiate an object of HashSet> >HashSet set =>new> HashSet();> > >// create ArrayList list1> >ArrayList list1 =>new> ArrayList();> > >// create ArrayList list2> >ArrayList list2 =>new> ArrayList();> > >// Add elements using add method> >list1.add(>1>);> >list1.add(>2>);> >list2.add(>1>);> >list2.add(>2>);> >set.add(list1);> >set.add(list2);> > >// print the set size to understand the> >// internal storage of ArrayList in Set> >System.out.println(set.size());> >}> }> |
java pentru tipuri de bucle
>
>Ieșire:
1>
Înainte de a stoca un obiect, HashSet verifică dacă există o intrare existentă folosind metodele hashCode() și equals(). În exemplul de mai sus, două liste sunt considerate egale dacă au aceleași elemente în aceeași ordine. Când invocați hashCode() pe cele două liste, ambele ar da același hash, deoarece sunt egale.
Notă: HashSet face nu stocați articole duplicat , dacă dați două Obiecte care sunt egale, atunci îl stochează doar pe primul, aici este list1.
Ierarhia lui HashSet este următoarea:
Funcționarea internă a unui HashSet
Toate clasele interfeței Set sunt susținute intern de Map. HashSet folosește HashMap pentru a-și stoca obiectul intern. Trebuie să vă întrebați că pentru a introduce o valoare în HashMap avem nevoie de o pereche cheie-valoare, dar în HashSet, transmitem o singură valoare.
Stocare în HashMap: De fapt, valoarea pe care o inserăm în HashSet acționează ca o cheie pentru obiectul hărții și pentru valoarea sa, java folosește o variabilă constantă. Deci, în perechea cheie-valoare, toate valorile vor fi aceleași.
Implementarea HashSet în Java doc
private transient HashMap map; // Constructor - 1 // All the constructors are internally creating HashMap Object. public HashSet() { // Creating internally backing HashMap object map = new HashMap(); } // Constructor - 2 public HashSet(int initialCapacity) { // Creating internally backing HashMap object map = new HashMap(initialCapacity); } // Dummy value to associate with an Object in Map private static final Object PRESENT = new Object();> Dacă ne uităm la adăuga() metoda clasei HashSet:
public boolean add(E e) { return map.put(e, PRESENT) == null; }> Putem observa că metoda add() a clasei HashSet apelează intern a pune() metoda de susținere a obiectului HashMap prin trecerea elementului pe care l-ați specificat ca cheie și constanta PRESENT ca valoare. elimina() metoda funcționează, de asemenea, în același mod. Apelează intern metoda de eliminare a interfeței Map.
public boolean remove(Object o) { return map.remove(o) == PRESENT; }> HashSet nu stochează doar obiecte unice, ci și o colecție unică de obiecte ca ArrayList , LinkedList , Vector ,..etc.
Constructorii clasei HashSet
Pentru a crea un HashSet, trebuie să creăm un obiect din clasa HashSet. Clasa HashSet este formată din diverși constructori care permit crearea posibilă a HashSet-ului. Următorii sunt constructorii disponibili în această clasă.
1. HashSet()
Acest constructor este folosit pentru a construi un obiect HashSet gol în care capacitatea inițială implicită este 16 și factorul de încărcare implicit este 0,75. Dacă dorim să creăm un HashSet gol cu numele hs, atunci acesta poate fi creat ca:
HashSet hs = new HashSet();>
2. HashSet(int initialCapacity)
Acest constructor este folosit pentru a construi un obiect HashSet gol în care initialCapacity este specificată în momentul creării obiectului. Aici, loadFactor implicit rămâne 0,75.
HashSet hs = new HashSet(int initialCapacity);>
3. HashSet(int initialCapacity, float loadFactor)
Acest constructor este folosit pentru a construi un obiect HashSet gol în care initialCapacity și loadFactor sunt specificate în momentul creării obiectului.
HashSet hs = new HashSet(int initialCapacity, float loadFactor);>
4. HashSet(Colecție)
Acest constructor este folosit pentru a construi un obiect HashSet care conține toate elementele din colecția dată. Pe scurt, acest constructor este folosit atunci când este necesară orice conversie de la orice obiect Collection la obiectul HashSet. Dacă dorim să creăm un HashSet cu numele hs, acesta poate fi creat ca:
HashSet hs = new HashSet(Collection C);>
Mai jos este implementarea subiectelor de mai sus:
Java
// Java program to Demonstrate Working> // of HashSet Class> > // Importing required classes> import> java.util.*;> > // Main class> // HashSetDemo> class> GFG {> > >// Main driver method> >public> static> void> main(String[] args)> >{> > >// Creating an empty HashSet> >HashSet h =>new> HashSet();> > >// Adding elements into HashSet> >// using add() method> >h.add(>'India'>);> >h.add(>'Australia'>);> >h.add(>'South Africa'>);> > >// Adding duplicate elements> >h.add(>'India'>);> > >// Displaying the HashSet> >System.out.println(h);> >System.out.println(>'List contains India or not:'> >+ h.contains(>'India'>));> > >// Removing items from HashSet> >// using remove() method> >h.remove(>'Australia'>);> >System.out.println(>'List after removing Australia:'> >+ h);> > >// Display message> >System.out.println(>'Iterating over list:'>);> > >// Iterating over hashSet items> >Iterator i = h.iterator();> > >// Holds true till there is single element remaining> >while> (i.hasNext())> > >// Iterating over elements> >// using next() method> >System.out.println(i.next());> >}> }> |
>
>Ieșire:
[South Africa, Australia, India] List contains India or not:true List after removing Australia:[South Africa, India] Iterating over list: South Africa India>
Metode în HashSet
| METODĂ | DESCRIERE |
|---|---|
| adaugă (și și) | Folosit pentru a adăuga elementul specificat dacă nu este prezent, dacă este prezent atunci returnează false. |
| clar() | Folosit pentru a elimina toate elementele din set. |
| conține (obiectul o) | Folosit pentru a returna true dacă un element este prezent într-o mulțime. |
| elimina (obiectul o) | Folosit pentru a elimina elementul dacă este prezent în set. |
| iterator() | Folosit pentru a returna un iterator peste elementul din set. |
| este gol() | Folosit pentru a verifica dacă setul este gol sau nu. Returnează true pentru gol și false pentru o condiție non-vid pentru set. |
| mărimea() | Folosit pentru a returna dimensiunea setului. |
| clona() | Folosit pentru a crea o copie superficială a setului. |
Efectuarea diferitelor operații pe HashSet
Să vedem cum să efectuați câteva operații utilizate frecvent pe HashSet.
1. Adăugarea de elemente în HashSet
Pentru a adăuga un element la HashSet, putem folosi metoda add() . Cu toate acestea, ordinea de inserare nu este reținută în HashSet. Trebuie să reținem că elementele duplicate nu sunt permise și toate elementele duplicate sunt ignorate.
Exemplu
Java
// Java program to Adding Elements to HashSet> > // Importing required classes> import> java.io.*;> import> java.util.*;> > // Main class> // AddingElementsToHashSet> class> GFG {> > >// Method 1> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an empty HashSet of string entities> >HashSet hs =>new> HashSet();> > >// Adding elements using add() method> >hs.add(>'Geek'>);> >hs.add(>'For'>);> >hs.add(>'Geeks'>);> > >// Printing all string el=ntries inside the Set> >System.out.println(>'HashSet elements : '> + hs);> >}> }> |
>
>Ieșire:
HashSet elements : [Geek, For, Geeks]>
2. Eliminarea elementelor din HashSet
Valorile pot fi eliminate din HashSet folosind metoda remove().
Exemplu
Java
// Java program Illustrating Removal Of Elements of HashSet> > // Importing required classes> import> java.io.*;> import> java.util.*;> > // Main class> // RemoveElementsOfHashSet> class> GFG {> > >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an> >HashSet hs =>new> HashSet();> > >// Adding elements to above Set> >// using add() method> >hs.add(>'Geek'>);> >hs.add(>'For'>);> >hs.add(>'Geeks'>);> >hs.add(>'A'>);> >hs.add(>'B'>);> >hs.add(>'Z'>);> > >// Printing the elements of HashSet elements> >System.out.println(>'Initial HashSet '> + hs);> > >// Removing the element B> >hs.remove(>'B'>);> > >// Printing the updated HashSet elements> >System.out.println(>'After removing element '> + hs);> > >// Returns false if the element is not present> >System.out.println(>'Element AC exists in the Set : '> >+ hs.remove(>'AC'>));> >}> }> |
>
>Ieșire:
Initial HashSet [A, B, Geek, For, Geeks, Z] After removing element [A, Geek, For, Geeks, Z] Element AC exists in the Set : false>
3. Iterarea prin HashSet
Iterați prin elementele HashSet folosind metoda iterator(). De asemenea, cel mai faimos este folosirea îmbunătățit pentru buclă.
Exemplu
Bloc de cod
IeșireA, B, Geek, For, Geeks, Z, A, B, Geek, For, Geeks, Z,>
Complexitatea temporală a operațiunilor HashSet: Structura de date de bază pentru HashSet este hashtable. Deci, amortizați (caz mediu sau obișnuit) complexitatea timpului pentru adăugarea, eliminarea și căutarea (conține metoda) operațiunii HashSet. O(1) timp.
Performanța HashSet
HashSet extinde clasa Abstract Set și implementează A stabilit , Clonabil și Serializabil interfeţe unde E este tipul de elemente menţinute de această mulţime. Subclasa direct cunoscută a HashSet este LinkedHashSet.
Acum, pentru menținerea performanței în timp constant, iterarea peste HashSet necesită timp proporțional cu suma mărimii instanței HashSet (numărul de elemente) plus capacitatea instanței HashMap de rezervă (numărul de găleți). Astfel, este foarte important să nu setați capacitatea inițială prea mare (sau factorul de încărcare prea mic) dacă performanța iterației este importantă.
- Capacitate inițială: Capacitatea inițială înseamnă numărul de găleți atunci când tabelul hash este creat (HashSet utilizează în mod intern structura de date hashtable). Numărul de găleți va crește automat dacă dimensiunea actuală este plină.
- Factor de încărcare: Factorul de încărcare este o măsură a cât de plin poate ajunge HashSet-ului înainte ca capacitatea sa să fie crescută automat. Când numărul de intrări din tabelul hash depășește produsul dintre factorul de încărcare și capacitatea curentă, tabelul hash este rehashed (adică structurile de date interne sunt reconstruite), astfel încât tabelul hash să aibă aproximativ dublul numărului de găleți.
Number of stored elements in the table Load Factor = ----------------------------------------- Size of the hash table>
Exemplu: Dacă capacitatea internă este de 16 și factorul de încărcare este de 0,75, atunci numărul de găleți va crește automat când masa are 12 elemente în el.
Efect asupra performanței:
Factorul de încărcare și capacitatea inițială sunt doi factori principali care afectează performanța operațiunilor HashSet. Un factor de încărcare de 0,75 oferă performanțe foarte eficiente în ceea ce privește complexitatea timpului și spațiului. Dacă creștem valoarea factorului de încărcare mai mult decât atât, atunci supraîncărcarea memoriei va fi redusă (pentru că va scădea operația de reconstrucție internă), dar va afecta operația de adăugare și căutare în tabelul hash. Pentru a reduce operația de rehashing, ar trebui să alegem cu înțelepciune capacitatea inițială. Dacă capacitatea inițială este mai mare decât numărul maxim de intrări împărțit la factorul de încărcare, nu va avea loc nicio operațiune de reluare.
Notă: Implementarea într-un HashSet nu este sincronizată, în sensul că dacă mai multe thread-uri accesează un set hash concomitent, iar cel puțin unul dintre thread-uri modifică setul, acesta trebuie să fie sincronizat extern. Acest lucru se realizează de obicei prin sincronizarea pe un obiect care încapsulează în mod natural setul. Dacă nu există un astfel de obiect, setul ar trebui să fie împachetat folosind metoda Collections.synchronizedSet. Cel mai bine se face acest lucru în momentul creării, pentru a preveni accesul accidental nesincronizat la set, după cum se arată mai jos:
Set s = Collections.synchronizedSet(new HashSet(…));
Metode utilizate cu HashSet
1. Metode moștenite din clasa java.util.AbstractSet
| Metodă | Descriere |
|---|---|
| este egal() | Folosit pentru a verifica egalitatea unui obiect cu un HashSet și pentru a le compara. Lista returnează adevărat numai dacă ambele HashSet conțin aceleași elemente, indiferent de ordine. |
| cod hash() | Returnează valoarea codului hash pentru acest set. |
| removeAll(colecție) | Această metodă este folosită pentru a elimina toate elementele din colecție care sunt prezente în set. Această metodă returnează true dacă acest set se modifică ca urmare a apelului. |
2. Metode moștenite din clasa java.util.AbstractCollection
| METODĂ | DESCRIERE |
|---|---|
| addAll(colecție) | Această metodă este folosită pentru a adăuga toate elementele din colecția menționată la setul existent. Elementele sunt adăugate aleatoriu fără a urma vreo ordine specifică. |
| conţineAll(colecţie) | Această metodă este folosită pentru a verifica dacă setul conține sau nu toate elementele prezente în colecția dată. Această metodă returnează true dacă setul conține toate elementele și returnează false dacă lipsește vreunul dintre elemente. |
| retainAll (colecție) | Această metodă este folosită pentru a reține toate elementele din mulțime care sunt menționate în colecția dată. Această metodă returnează true dacă acest set s-a modificat ca urmare a apelului. |
| toArray() | Această metodă este folosită pentru a forma o matrice din aceleași elemente ca și cea a setului. |
| toString() | Metoda toString() a Java HashSet este folosită pentru a returna o reprezentare în șir a elementelor colecției HashSet. |
3. Metode declarate în interfața java.util.Collection
| METODĂ | DESCRIERE |
|---|---|
| parallelStream() | Returnează un flux posibil paralel cu această colecție ca sursă. |
| removeIf? (filtru de predicate) | Îndepărtează toate elementele acestei colecții care satisfac predicatul dat. |
| curent() | Returnează un flux secvenţial cu această colecţie ca sursă. |
| toArray? (generator de funcții int) | Returnează o matrice care conține toate elementele din această colecție, folosind funcția generator furnizată pentru a aloca matricea returnată. |
4. Metode declarate în interfața java.lang.Iterable
| METODĂ | DESCRIERE |
|---|---|
| pentru fiecare? (acțiunea consumatorului) | Efectuează acțiunea dată pentru fiecare element din Iterable până când toate elementele au fost procesate sau acțiunea aruncă o excepție. |
5. Metode declarate în interfața java.util.Set
| METODĂ | DESCRIERE |
|---|---|
| addAll? (Colecția c) | Adaugă toate elementele din colecția specificată la acest set dacă nu sunt deja prezente (operație opțională). |
| conțineToate? (Colecția c) | Returnează adevărat dacă acest set conține toate elementele colecției specificate. |
| este egal? (Obiect o) | Compară obiectul specificat cu acest set pentru egalitate. |
| hashCode() | Returnează valoarea codului hash pentru acest set. |
| removeAll? (Colecția c) | Îndepărtează din acest set toate elementele sale care sunt conținute în colecția specificată (operație opțională). |
| retainAll? (Colecția c) | Reține doar elementele din acest set care sunt conținute în colecția specificată (operație opțională). |
| toArray() | Returnează o matrice care conține toate elementele din acest set. |
| toArray?(T[] a) | Returnează o matrice care conține toate elementele din acest set; tipul de rulare al matricei returnate este cel al matricei specificate. |
Întrebări frecvente în HashSet în Java
Î1. Ce este HashSet în Java?
Răspuns:
HashSet este un tip de clasă, care extinde AbstractSet și implementează interfețele Set.
Q2. De ce se folosește HashSet?
Răspuns:
tipuri de date de referință în java
HashSet este folosit pentru a evita datele duplicate și pentru a găsi valoare cu metoda rapidă.
Q3. Diferențele dintre HashSet și HashMap.
Răspuns:
| Bază | HashSet | HashMap |
|---|---|---|
| Implementarea | HashSet implementează o interfață Set. | HashMap implementează o interfață storesMap. |
| Duplicate | HashSet nu permite valori duplicate. | HashMap stochează perechile cheie și valoare și nu permite chei duplicate. Dacă cheia este duplicată, vechea cheie este înlocuită cu noua valoare. |
| Numărul de obiecte în timpul depozitării obiectelor | HashSet necesită un singur obiect add(Object o). | HashMap necesită două obiecte puse (key K, V Value) pentru a adăuga un element la obiectul HashMap. |
| Valoare simulată | HashSet utilizează intern HashMap pentru a adăuga elemente. În HashSet, argumentul transmis în metoda add(Object) servește drept cheie K. Java asociază intern o valoare inactivă pentru fiecare valoare transmisă în metoda add(Object). | HashMap nu are niciun concept de valoare inactivă. |
| Stocarea sau adăugarea unui mecanism | HashSet utilizează în mod intern obiectul HashMap pentru a stoca sau adăuga obiectele. | HashMap utilizează intern hashing pentru a stoca sau adăuga obiecte |
| Mai repede | HashSet este mai lent decât HashMap. | HashMap este mai rapid decât HashSet. |
| Inserare | HashSet folosește metoda add() pentru adăugarea sau stocarea datelor. | HashMap folosește metoda put() pentru stocarea datelor. |
| Exemplu | HashSet este un set, de ex. {1, 2, 3, 4, 5, 6, 7}. | HashMap este o hartă cheie -> pereche valoare (cheie la valoare), de ex. {a -> 1, b -> 2, c -> 2, d -> 1}. |
Î4. Diferențele dintre HashSet și TreeSet în Java.
Răspuns:
| Bază | HashSet | TreeSet |
|---|---|---|
| Viteza și internă implementează acțiunea de aruncare | Pentru operațiuni precum căutarea, inserarea și ștergerea. Este nevoie de timp constant pentru aceste operațiuni, în medie. HashSet este mai rapid decât TreeSet. HashSet este implementat folosind un tabel hash. | TreeSet ia O(Log n) pentru căutare, inserare și ștergere, care este mai mare decât HashSet. Dar TreeSet păstrează datele sortate. De asemenea, acceptă operațiuni precum higher() (Afișează elementul cel puțin mai înalt), floor(), plafon(), etc. Aceste operațiuni sunt, de asemenea, O(Log n) în TreeSet și nu sunt acceptate în HashSet. TreeSet este implementat folosind un arbore de căutare binar cu auto-echilibrare (Arbore roșu-negru). TreeSet este susținut de TreeMap în Java. |
| Comanda | Elementele din HashSet nu sunt ordonate. | TreeSet menține obiectele în ordinea sortată, definită fie prin metoda Comparabil, fie prin metoda Comparator în Java. Elementele TreeSet sunt sortate implicit în ordine crescătoare. Oferă mai multe metode de a trata setul ordonat, cum ar fi first(), last(), headSet(), tailSet(), etc. |
| Obiect nul | HashSet permite obiectul nul. | TreeSet nu permite obiectul nul și aruncă NullPointerException, De ce, deoarece TreeSet folosește metoda compareTo() pentru a compara cheile, iar compareTo() va arunca java.lang.NullPointerException. |
| Comparaţie | HashSet folosește metoda equals() pentru a compara două obiecte din set și pentru a detecta duplicatele. | TreeSet folosește metoda compareTo() în același scop. Dacă equals() și compareTo() nu sunt consecvente, adică pentru două obiecte egale equals ar trebui să returneze adevărat în timp ce compareTo() ar trebui să returneze zero, atunci va rupe contractul interfeței Set și va permite duplicate în implementările Set precum TreeSet |