Java HashSet trieda implementuje rozhranie Set, podporované hash tabuľkou, ktorá je v skutočnosti inštanciou HashMap. Nie je zaručené poradie iterácií množín hash, čo znamená, že trieda nezaručuje konštantné poradie prvkov v priebehu času. Táto trieda povoľuje nulový prvok. Trieda tiež ponúka konštantný časový výkon pre základné operácie, ako je pridanie, odstránenie, obsah a veľkosť za predpokladu, že hašovacia funkcia správne rozptýli prvky medzi vedrá, čo uvidíme ďalej v článku.
Funkcie Java HashSet
Nižšie je uvedených niekoľko dôležitých funkcií HashSet:
- Implementuje Nastaviť rozhranie .
- Základná dátová štruktúra pre HashSet je Hashtable .
- Keďže implementuje rozhranie Set Interface, duplicitné hodnoty nie sú povolené.
- Nie je zaručené, že objekty, ktoré vložíte do HashSet, budú vložené v rovnakom poradí. Objekty sa vkladajú na základe ich hash kódu.
- Prvky NULL sú v HashSet povolené.
- HashSet tiež implementuje Serializovateľné a Klonovateľné rozhrania.
Vyhlásenie HashSet
public class HashSet extends AbstractSet implements Set, Cloneable, Serializable>
kde A je typ prvkov uložených v HashSet.
Príklad HashSet Java
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());> >}> }> |
viacriadkový komentár powershell
>
>Výkon:
1>
Pred uložením objektu HashSet skontroluje, či existuje existujúci záznam pomocou metód hashCode() a equals(). Vo vyššie uvedenom príklade sa dva zoznamy považujú za rovnocenné, ak majú rovnaké prvky v rovnakom poradí. Keď vyvoláte hashCode() metódy na dvoch zoznamoch, obidva by dali rovnaký hash, pretože sú rovnaké.
Poznámka: HashSet áno neukladať duplicitné položky , ak dáte dva objekty, ktoré sú rovnaké, uloží sa iba prvý, tu je zoznam1.
Hierarchia HashSet je nasledovná:
Interné fungovanie HashSet
Všetky triedy rozhrania Set sú interne zálohované službou Map. HashSet používa HashMap na interné ukladanie svojho objektu. Určite vás zaujíma, že na zadanie hodnoty do HashMap potrebujeme pár kľúč – hodnota, ale v HashSet odovzdávame iba jednu hodnotu.
Ukladanie v HashMap: V skutočnosti hodnota, ktorú vložíme do HashSet, funguje ako kľúč k objektu mapy a pre svoju hodnotu používa java konštantnú premennú. Takže v páre kľúč – hodnota budú všetky hodnoty rovnaké.
Implementácia HashSet v Jave 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();> Ak sa pozrieme na pridať () metóda triedy HashSet:
public boolean add(E e) { return map.put(e, PRESENT) == null; }> Môžeme si všimnúť, že metóda add() triedy HashSet interne volá dať () metóda zálohovania objektu HashMap odovzdaním prvku, ktorý ste zadali ako kľúč, a konštanty PRESENT ako jeho hodnoty. odstrániť () metóda tiež funguje rovnakým spôsobom. Interne volá metódu odstránenia rozhrania mapy.
public boolean remove(Object o) { return map.remove(o) == PRESENT; }> HashSet ukladá nielen jedinečné objekty, ale aj jedinečnú zbierku objektov Páči sa mi to ArrayList , LinkedList , Vector ,..atď.
Konštruktory triedy HashSet
Na vytvorenie HashSet musíme vytvoriť objekt triedy HashSet. Trieda HashSet pozostáva z rôznych konštruktorov, ktoré umožňujú možné vytvorenie HashSet. Nasledujú konštruktory dostupné v tejto triede.
1. HashSet()
Tento konštruktor sa používa na vytvorenie prázdneho objektu HashSet, v ktorom je predvolená počiatočná kapacita 16 a predvolený faktor zaťaženia je 0,75. Ak chceme vytvoriť prázdny HashSet s názvom hs, môžeme ho vytvoriť ako:
HashSet hs = new HashSet();>
2. HashSet (int initialCapacity)
Tento konštruktor sa používa na vytvorenie prázdneho objektu HashSet, v ktorom je počiatočná kapacita špecifikovaná v čase vytvárania objektu. Tu zostáva predvolený faktor zaťaženia 0,75.
HashSet hs = new HashSet(int initialCapacity);>
3. HashSet (int initialCapacity, float loadFactor)
Tento konštruktor sa používa na vytvorenie prázdneho objektu HashSet, v ktorom sú v čase vytvárania objektu špecifikované počiatočná kapacita a faktor zaťaženia.
HashSet hs = new HashSet(int initialCapacity, float loadFactor);>
4. HashSet (kolekcia)
Tento konštruktor slúži na zostavenie objektu HashSet obsahujúceho všetky prvky z danej kolekcie. Stručne povedané, tento konštruktor sa používa, keď je potrebná akákoľvek konverzia z akéhokoľvek objektu Collection na objekt HashSet. Ak chceme vytvoriť HashSet s názvom hs, môžeme ho vytvoriť ako:
HashSet hs = new HashSet(Collection C);>
Nižšie je uvedená implementácia vyššie uvedených tém:
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());> >}> }> |
>
>Výkon:
[South Africa, Australia, India] List contains India or not:true List after removing Australia:[South Africa, India] Iterating over list: South Africa India>
Metódy v HashSet
| METÓDA | POPIS |
|---|---|
| pridať (a a) | Používa sa na pridanie špecifikovaného prvku, ak nie je prítomný, ak je prítomný, vráti hodnotu false. |
| jasný() | Používa sa na odstránenie všetkých prvkov zo sady. |
| obsahuje (Objekt o) | Používa sa na vrátenie true, ak je prvok prítomný v množine. |
| odstrániť (Objekt o) | Používa sa na odstránenie prvku, ak je prítomný v súprave. |
| iterátor() | Používa sa na vrátenie iterátora nad prvkom v množine. |
| je prázdny() | Používa sa na kontrolu, či je súprava prázdna alebo nie. Vráti hodnotu true pre prázdnu a false pre neprázdnu podmienku pre množinu. |
| veľkosť () | Slúži na vrátenie veľkosti súpravy. |
| klon() | Používa sa na vytvorenie plytkej kópie súpravy. |
Vykonávanie rôznych operácií na HashSet
Pozrime sa, ako vykonať niekoľko často používaných operácií na HashSet.
1. Pridávanie prvkov do HashSet
Na pridanie prvku do HashSet môžeme použiť metódu add() . Objednávka vloženia sa však nezachová v HashSet. Musíme si uvedomiť, že duplicitné prvky nie sú povolené a všetky duplicitné prvky sú ignorované.
Príklad
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);> >}> }> |
>
>Výkon:
HashSet elements : [Geek, For, Geeks]>
2. Odstránenie prvkov v HashSet
Hodnoty je možné z HashSet odstrániť pomocou metódy remove().
Príklad
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'>));> >}> }> |
>
>Výkon:
Initial HashSet [A, B, Geek, For, Geeks, Z] After removing element [A, Geek, For, Geeks, Z] Element AC exists in the Set : false>
3. Iterácia cez HashSet
Iterujte cez prvky HashSet pomocou metódy iterator(). Najznámejším z nich je tiež použitie vylepšená slučka for.
Príklad
Blok kódu
VýkonA, B, Geek, For, Geeks, Z, A, B, Geek, For, Geeks, Z,>
Časová zložitosť operácií HashSet: Základná dátová štruktúra pre HashSet je hašovateľná. Takže amortizujte (priemerný alebo zvyčajný prípad) časovú zložitosť pridania, odstránenia a vyhľadávania (obsahuje metódu) operácie HashSet O(1) čas.
Výkon HashSet
HashSet rozširuje triedu Abstract Set a implementuje Set , klonovateľné a Serializovateľné rozhrania, kde E je typ prvkov udržiavaných touto množinou. Priamo známa podtrieda HashSet je LinkedHashSet .
Teraz, aby sa zachoval konštantný časový výkon, iterovanie cez HashSet vyžaduje čas úmerný súčtu veľkosti inštancie HashSet (počet prvkov) plus kapacita záložnej inštancie HashMap (počet segmentov). Preto je veľmi dôležité nenastaviť počiatočnú kapacitu príliš vysoko (alebo príliš nízky faktor zaťaženia), ak je dôležitý výkon iterácie.
- Počiatočná kapacita: Počiatočná kapacita znamená počet bucketov pri vytváraní hashtable (HashSet interne používa štruktúru hashtable dát). Počet segmentov sa automaticky zvýši, ak sa aktuálna veľkosť zaplní.
- Vyťaženosť: Faktor zaťaženia je mierou toho, ako sa môže HashSet naplniť predtým, ako sa automaticky zvýši jeho kapacita. Keď počet záznamov v hašovacej tabuľke presiahne súčin záťažového faktora a aktuálnej kapacity, hašovacia tabuľka sa znovu hašuje (to znamená, že interné dátové štruktúry sú prestavané), takže hašovacia tabuľka má približne dvojnásobný počet bucketov.
Number of stored elements in the table Load Factor = ----------------------------------------- Size of the hash table>
Príklad: Ak je vnútorná kapacita 16 a faktor zaťaženia je 0,75, potom sa počet vedier automaticky zvýši, keď stôl obsahuje 12 prvkov.
Vplyv na výkon:
Faktor zaťaženia a počiatočná kapacita sú dva hlavné faktory, ktoré ovplyvňujú výkon operácií HashSet. Faktor zaťaženia 0,75 poskytuje veľmi efektívny výkon s ohľadom na časovú a priestorovú zložitosť. Ak zvýšime hodnotu faktora zaťaženia viac, potom sa réžia pamäte zníži (pretože sa zníži operácia interného prebudovania), ale ovplyvní to operáciu pridávania a vyhľadávania v hašovacej tabuľke. Aby sme zredukovali operáciu premývania, mali by sme počiatočnú kapacitu zvoliť múdro. Ak je počiatočná kapacita väčšia ako maximálny počet záznamov vydelený faktorom zaťaženia, nikdy nedôjde k žiadnej aktualizácii.
Poznámka: Implementácia v HashSet nie je synchronizovaná v tom zmysle, že ak viaceré vlákna pristupujú k hash setu súčasne a aspoň jedno z vlákien upravuje sadu, musí byť synchronizovaná externe. To sa zvyčajne dosiahne synchronizáciou na nejakom objekte, ktorý prirodzene zapuzdruje sadu. Ak takýto objekt neexistuje, množina by mala byť zabalená pomocou metódy Collections.synchronizedSet. Najlepšie je to urobiť pri vytváraní, aby ste predišli náhodnému nesynchronizovanému prístupu k súprave, ako je uvedené nižšie:
Set s = Collections.synchronizedSet(new HashSet(…));
Metódy používané s HashSet
1. Metódy zdedené z triedy java.util.AbstractSet
| Metóda | Popis |
|---|---|
| rovná sa() | Používa sa na overenie rovnosti objektu s HashSet a ich porovnanie. Zoznam vráti hodnotu true iba vtedy, ak obe sady HashSet obsahujú rovnaké prvky, bez ohľadu na poradie. |
| hashcode() | Vráti hodnotu hash kódu pre túto množinu. |
| odstrániť všetko (kolekcia) | Táto metóda sa používa na odstránenie všetkých prvkov z kolekcie, ktoré sa nachádzajú v množine. Táto metóda vráti hodnotu true, ak sa táto množina zmení v dôsledku volania. |
2. Metódy zdedené z triedy java.util.AbstractCollection
| METÓDA | POPIS |
|---|---|
| addAll(kolekcia) | Táto metóda sa používa na pripojenie všetkých prvkov z uvedenej kolekcie k existujúcej množine. Prvky sa pridávajú náhodne bez toho, aby sa dodržali konkrétne poradie. |
| obsahuje všetko (kolekcia) | Táto metóda sa používa na kontrolu, či sada obsahuje všetky prvky prítomné v danej kolekcii alebo nie. Táto metóda vráti hodnotu true, ak množina obsahuje všetky prvky, a vráti hodnotu false, ak niektorý z prvkov chýba. |
| ponechať všetko (kolekcia) | Táto metóda sa používa na zachovanie všetkých prvkov zo sady, ktoré sú uvedené v danej kolekcii. Táto metóda vráti hodnotu true, ak sa táto množina zmenila v dôsledku volania. |
| toArray() | Táto metóda sa používa na vytvorenie poľa rovnakých prvkov, aké má sada. |
| natiahnuť() | Metóda toString() Java HashSet sa používa na vrátenie reťazcovej reprezentácie prvkov kolekcie HashSet. |
3. Metódy deklarované v rozhraní java.util.Collection
| METÓDA | POPIS misia nemožné všetky filmy |
|---|---|
| parallelStream() | Vráti možný paralelný stream s touto kolekciou ako zdrojom. |
| removeIf? (Filter predikátov) | Odstráni všetky prvky tejto kolekcie, ktoré spĺňajú daný predikát. |
| Prúd() | Vráti sekvenčný stream s touto kolekciou ako zdrojom. |
| toArray? (generátor IntFunction) | Vráti pole obsahujúce všetky prvky v tejto kolekcii pomocou poskytnutej funkcie generátora na pridelenie vráteného poľa. |
4. Metódy deklarované v rozhraní java.lang.Iterable
| METÓDA | POPIS |
|---|---|
| pre každého? (spotrebiteľská akcia) | Vykoná danú akciu pre každý prvok Iterable, kým nie sú spracované všetky prvky alebo kým akcia nevyvolá výnimku. |
5. Metódy deklarované v rozhraní java.util.Set
| METÓDA | POPIS |
|---|---|
| addAll? (Kolekcia c) | Pridá všetky prvky v zadanej kolekcii do tejto množiny, ak ešte nie sú prítomné (voliteľná operácia). |
| obsahuje všetko? (Kolekcia c) | Vráti hodnotu true, ak táto množina obsahuje všetky prvky zadanej kolekcie. |
| rovná sa? (Objekt o) | Porovná zadaný objekt s touto množinou z hľadiska rovnosti. |
| hashCode() | Vráti hodnotu hash kódu pre túto množinu. |
| odstrániť všetko? (Kolekcia c) | Odstráni z tejto množiny všetky jej prvky, ktoré sú obsiahnuté v zadanej kolekcii (voliteľná operácia). |
| keepAll? (Kolekcia c) | Zachová iba prvky v tejto množine, ktoré sú obsiahnuté v zadanej kolekcii (voliteľná operácia). |
| toArray() | Vráti pole obsahujúce všetky prvky v tejto množine. |
| toArray?(T[] a) | Vráti pole obsahujúce všetky prvky v tejto množine; typ runtime vráteného poľa je typ zadaného poľa. |
Časté otázky v HashSet v jazyku Java
Q1. Čo je HashSet v jazyku Java?
odpoveď:
HashSet je typ triedy, ktorý rozširuje AbstractSet a implementuje rozhrania Set.
Q2. Prečo sa používa HashSet?
odpoveď:
HashSet sa používa na zabránenie duplicitným údajom a na nájdenie hodnoty pomocou rýchlej metódy.
Q3. Rozdiely medzi HashSet a HashMap.
odpoveď:
| Základ | HashSet | HashMap |
|---|---|---|
| Implementácia | HashSet implementuje rozhranie Set. | HashMap implementuje rozhranie storeMap. |
| Duplikáty | HashSet nepovoľuje duplicitné hodnoty. | HashMap ukladá páry kľúčov a hodnôt a neumožňuje duplicitné kľúče. Ak je kľúč duplicitný, starý kľúč sa nahradí novou hodnotou. |
| Počet predmetov pri ukladaní predmetov | HashSet vyžaduje iba jeden objekt pridať (Object o). | HashMap vyžaduje dva objekty put (kľúč K, hodnota V) na pridanie prvku do objektu HashMap. |
| Falošná hodnota | HashSet interne používa HashMap na pridávanie prvkov. V HashSet argument odovzdaný v metóde add(Object) slúži ako kľúč K. Java interne priraďuje fiktívnu hodnotu pre každú hodnotu odovzdanú v metóde add(Object). | HashMap nemá žiadny koncept fiktívnej hodnoty. |
| Uloženie alebo pridanie mechanizmu | HashSet interne používa objekt HashMap na ukladanie alebo pridávanie objektov. | HashMap interne používa hashovanie na ukladanie alebo pridávanie objektov |
| Rýchlejšie | HashSet je pomalší ako HashMap. | HashMap je rýchlejší ako HashSet. |
| Vkladanie | HashSet používa metódu add() na pridávanie alebo ukladanie údajov. | HashMap používa na ukladanie údajov metódu put(). |
| Príklad | HashSet je súbor, napr. {1, 2, 3, 4, 5, 6, 7}. | HashMap je mapa kľúč -> pár hodnôt (kľúč k hodnote), napr. {a -> 1, b -> 2, c -> 2, d -> 1}. |
Q4. Rozdiely medzi HashSet a TreeSet v Jave.
odpoveď:
| Základ | HashSet | TreeSet |
|---|---|---|
| Rýchlosť a vnútorná implementácia, hádzanie akcie | Pre operácie ako vyhľadávanie, vkladanie a mazanie. Tieto operácie si vyžadujú v priemere konštantný čas. HashSet je rýchlejší ako TreeSet. HashSet sa implementuje pomocou hašovacej tabuľky. | TreeSet má O(Log n) na vyhľadávanie, vkladanie a mazanie, ktoré je vyššie ako HashSet. Ale TreeSet uchováva zoradené dáta. Tiež podporuje operácie ako vyššia () (Vráti najmenej vyšší prvok), podlaha (), strop () atď. Tieto operácie sú tiež O (Log n) v TreeSet a nie sú podporované v HashSet. TreeSet je implementovaný pomocou samovyvažujúceho binárneho vyhľadávacieho stromu (červeno-čierny strom). TreeSet je podporovaný TreeMap v Jave. |
| Objednávanie | Prvky v HashSet nie sú usporiadané. | TreeSet udržiava objekty v triedenom poradí definovanom buď metódou Comparable alebo Comparator v jazyku Java. Prvky TreeSet sú štandardne zoradené vo vzostupnom poradí. Ponúka niekoľko metód, ako sa vysporiadať s usporiadanou množinou, ako napríklad first(), last(), headSet(), tailSet() atď. |
| Objekt Null | HashSet umožňuje nulový objekt. | TreeSet nepovoľuje null Object a vyvoláva výnimku NullPointerException, Why, pretože TreeSet používa metódu CompareTo() na porovnanie kľúčov a CompareTo() vyvolá java.lang.NullPointerException. |
| Porovnanie | HashSet používa metódu equals() na porovnanie dvoch objektov v množine a na detekciu duplikátov. | TreeSet používa metódu CompareTo() na rovnaký účel. Ak equals() a CompareTo() nie sú konzistentné, t. j. pre dva rovnaké objekty by sa rovná mala vrátiť ako true, zatiaľ čo CompareTo() by mala vrátiť nulu, potom to poruší zmluvu rozhrania Set a umožní duplikáty v implementáciách Set, ako je TreeSet |