Sprievodca po HashSet v Jave

1. Prehľad

V tomto článku sa do toho ponoríme HashSet. Je to jeden z najpopulárnejších Nastaviť implementácie, ako aj neoddeliteľnú súčasť rámca zbierok Java.

2. Úvod do HashSet

HashSet je jednou zo základných dátových štruktúr v rozhraní Java Collections API.

Pripomeňme si najdôležitejšie aspekty tejto implementácie:

  • Ukladá jedinečné prvky a povoľuje nulové hodnoty
  • Za tým stojí a HashMap
  • Nezachováva objednávku
  • Nie je to bezpečné pre vlákna

Všimnite si, že tento interný HashMap sa inicializuje, keď sa vyskytne inštancia súboru HashSet je vytvorené:

public HashSet () {map = new HashMap (); }

Ak chcete ísť hlbšie do toho, ako HashMap funguje, článok zameraný na to si môžete prečítať tu.

3. API

V tejto časti sa zameriame na najbežnejšie používané metódy a na niekoľko jednoduchých príkladov.

3.1. pridať ()

The pridať () na pridanie prvkov do množiny je možné použiť metódu. Zmluva o metóde uvádza, že prvok bude pridaný, iba ak ešte nie je v množine. Ak bol pridaný prvok, metóda sa vráti pravda, inak - nepravdivé.

Môžeme pridať prvok do a HashSet Páči sa mi to:

@Test public void whenAddingElement_shouldAddElement () {Set hashset = new HashSet (); assertTrue (hashset.add ("Bol pridaný reťazec")); }

Z hľadiska implementácie pridať metóda je mimoriadne dôležitá. Detaily implementácie ilustrujú, ako HashSet pracuje interne a využíva HashMapdať metóda:

public boolean add (E e) {return map.put (e, PRESENT) == null; }

The mapa premenná je odkazom na interný podklad HashMap:

súkromná prechodná mapa HashMap;

Bol by to dobrý nápad oboznámiť sa s hashcode najskôr získať podrobné pochopenie toho, ako sú prvky usporiadané v hašovacích dátových štruktúrach.

Zhrnutie:

  • A HashMap je pole vedierka s predvolenou kapacitou 16 prvkov - každý segment zodpovedá inej hodnote hashcode
  • Ak majú rôzne objekty rovnakú hodnotu hashcode, uložia sa do jedného vedra
  • Ak vyťaženosť je dosiahnuté, vytvorí sa nové pole s dvojnásobnou veľkosťou ako predchádzajúce a všetky prvky sa opätovne umyjú a prerozdelia medzi nové zodpovedajúce segmenty
  • Ak chcete načítať hodnotu, hashujeme kľúč, upravíme ho a potom prejdeme do zodpovedajúceho segmentu a prehľadáme potenciálne prepojený zoznam v prípade, že existuje viac ako jeden objekt

3.2. obsahuje ()

Účelom obsahuje metódou je skontrolovať, či je prvok v danom prvku HashSet. Vracia sa to pravda ak sa prvok nájde, inak nepravdivé.

Môžeme skontrolovať, či sa v prvku nenachádza prvok HashSet:

@Test public void whenCheckingForElement_shouldSearchForElement () {Set hashsetContains = new HashSet (); hashsetContains.add ("Bol pridaný reťazec"); assertTrue (hashsetContains.contains ("Bol pridaný reťazec")); }

Kedykoľvek je objekt odovzdaný tejto metóde, vypočíta sa hodnota hash. Potom sa príslušné umiestnenie segmentu vyrieši a prekoná.

3.3. odstrániť ()

Metóda odstráni zadaný prvok zo súpravy, ak je prítomný. Táto metóda sa vráti pravda ak množina obsahovala uvedený prvok.

Pozrime sa na pracovný príklad:

@Test public void whenRemovingElement_shouldRemoveElement () {Set removeFromHashSet = new HashSet (); removeFromHashSet.add ("Bol pridaný reťazec"); assertTrue (removeFromHashSet.remove ("Bol pridaný reťazec")); }

3.4. jasný()

Túto metódu používame, keď chceme odstrániť všetky položky zo sady. Podkladová implementácia jednoducho vymaže všetky prvky od podkladovej HashMap.

Pozrime sa na to v akcii:

@Test public void whenClearingHashSet_shouldClearHashSet () {Set clearHashSet = new HashSet (); clearHashSet.add ("Bol pridaný reťazec"); clearHashSet.clear (); assertTrue (clearHashSet.isEmpty ()); }

3.5. veľkosť ()

Toto je jedna zo základných metód v API. Je veľmi používaný, pretože pomáha pri identifikácii počtu prvkov prítomných v HashSet. Základná implementácia jednoducho deleguje výpočet na Veľkosť HashMap () metóda.

Pozrime sa na to v akcii:

@Test public void whenCheckingTheSizeOfHashSet_shouldReturnThesize () {Set hashSetSize = new HashSet (); hashSetSize.add ("Bol pridaný reťazec"); assertEquals (1, hashSetSize.size ()); }

3.6. je prázdny()

Túto metódu môžeme použiť na zistenie, či daná inštancia a HashSet je prázdny alebo nie. Táto metóda sa vráti pravda ak sada neobsahuje žiadne prvky:

@Test public void whenCheckingForEmptyHashSet_shouldCheckForEmpty () {Set emptyHashSet = new HashSet (); assertTrue (emptyHashSet.isEmpty ()); }

3.7. iterátor ()

Metóda vracia iterátor nad prvkami v prvku Nastaviť. Prvky sa navštevujú v žiadnom konkrétnom poradí a iterátory sú rýchle.

Poradie náhodných iterácií môžeme sledovať tu:

@Test public void whenIteratingHashSet_shouldIterateHashSet () {Set hashset = new HashSet (); hashset.add ("Prvý"); hashset.add ("druhý"); hashset.add ("tretí"); Iterátor itr = hashset.iterator (); while (itr.hasNext ()) {System.out.println (itr.next ()); }}

Ak je množina upravená kedykoľvek po vytvorení iterátora akýmkoľvek spôsobom, okrem vlastnej metódy odstránenia iterátora, Iterátor hodí a ConcurrentModificationException.

Pozrime sa na to v akcii:

@Test (očakáva sa = ConcurrentModificationException.class) public void whenModifyingHashSetWhileIterating_shouldThrowException () {Set hashset = new HashSet (); hashset.add ("Prvý"); hashset.add ("druhý"); hashset.add ("tretí"); Iterátor itr = hashset.iterator (); while (itr.hasNext ()) {itr.next (); hashset.remove ("Druhý"); }} 

Prípadne, keby sme použili metódu odstránenia iterátora, potom by sme sa nestretli s výnimkou:

@Test public void whenRemovingElementUsingIterator_shouldRemoveElement () {Set hashset = new HashSet (); hashset.add ("Prvý"); hashset.add ("druhý"); hashset.add ("tretí"); Iterátor itr = hashset.iterator (); while (itr.hasNext ()) {Reťazcový prvok = itr.next (); if (element.equals ("Druhý")) itr.remove (); } assertEquals (2, hashset.size ()); }

Zlyhanie rýchleho fungovania iterátora nie je možné zaručiť, pretože nie je možné poskytnúť tvrdé záruky v prípade nesynchronizovanej súbežnej úpravy.

Rýchle zlyhanie iterátorov ConcurrentModificationException na základe maximálneho úsilia. Preto by bolo nesprávne napísať program, ktorý pre svoju správnosť závisel od tejto výnimky.

4. Ako HashSet Zachováva jedinečnosť?

Keď vložíme predmet do a HashSet, používa objekt hashcode hodnota na určenie, či prvok už nie je v množine.

Každá hodnota hash kódu zodpovedá určitému umiestneniu segmentu, ktoré môže obsahovať rôzne prvky, pre ktoré je vypočítaná hodnota hash rovnaká. Ale dva objekty s rovnakými hashCode nemusí byť rovný.

Takže objekty v rovnakom segmente sa budú porovnávať pomocou rovná sa () metóda.

5. Výkonnosť HashSet

Výkon a HashSet je ovplyvnený hlavne dvoma parametrami - jeho Počiatočná kapacita a Vyťaženosť.

Očakávaná časová zložitosť pridania prvku do množiny je O (1) ktoré môžu klesnúť na O (n) v najhoršom prípade (je k dispozícii iba jedno vedro) - preto je nevyhnutné udržiavať správne HashSet kapacita.

Dôležitá poznámka: od JDK 8 je najhoršia časová zložitosť O (log * n).

Faktor zaťaženia popisuje maximálnu úroveň naplnenia, nad ktorou bude potrebné zmeniť veľkosť súpravy.

Môžeme tiež vytvoriť a HashSet s vlastnými hodnotami pre počiatočná kapacita a vyťaženosť:

Nastaviť hashset = nový HashSet (); Nastaviť hashset = nový HashSet (20); Nastaviť hashset = nový HashSet (20, 0,5f); 

V prvom prípade sa použijú predvolené hodnoty - počiatočná kapacita 16 a koeficient zaťaženia 0,75. V druhej prepíšeme predvolenú kapacitu a v tretej prepíšeme obe.

Nízka počiatočná kapacita znižuje priestorovú zložitosť, ale zvyšuje frekvenciu opätovného premývania, čo je nákladný proces.

Na druhej strane, vysoká počiatočná kapacita zvyšuje náklady na iteráciu a počiatočnú spotrebu pamäte.

Ako pravidlo:

  • Vysoká počiatočná kapacita je dobrá pre veľký počet záznamov spojená s malou alebo žiadnou iteráciou
  • Nízka počiatočná kapacita je dobrá pre niekoľko záznamov s veľkou iteráciou

Je preto veľmi dôležité dosiahnuť správnu rovnováhu medzi týmito dvoma zložkami. Predvolená implementácia je zvyčajne optimalizovaná a funguje dobre. Ak cítime potrebu vyladiť tieto parametre tak, aby vyhovovali požiadavkám, musíme to robiť uvážlivo.

6. Záver

V tomto článku sme načrtli užitočnosť a HashSet, jeho účel a základné fungovanie. Videli sme, aká efektívna je z hľadiska použiteľnosti vzhľadom na jej stály výkon v čase a schopnosť vyhnúť sa duplikátom.

Preštudovali sme si niektoré dôležité metódy z API, ako nám ako vývojárom môžu pomôcť pri používaní a HashSet jeho potenciálu.

Útržky kódu ako vždy nájdete na GitHub.


$config[zx-auto] not found$config[zx-overlay] not found