streamalism.org

1. Áttekintés

Ebben a cikkben elmélyülünk HashSet. Ez az egyik legnépszerűbb Készlet implementációk, valamint a Java Collections Framework szerves része.

2. Bevezetés HashSet

HashSet a Java Collections API egyik alapvető adatstruktúrája.

Emlékezzünk a megvalósítás legfontosabb szempontjaira:

• Egyedi elemeket tárol és megengedi a nullákat
• Ezt a HashMap
• Nem tartja fenn a beszúrási sorrendet
• Ez nem szálkás

Vegye figyelembe, hogy ez a belső HashMap inicializálódik, amikor a HashSet létrehozva:

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

Ha mélyebbre akarsz menni, hogyan HashMap működik, a rá összpontosító cikket itt olvashatja el.

3. Az API

Ebben a szakaszban áttekintjük a leggyakrabban alkalmazott módszereket, és megnézünk néhány egyszerű példát.

3.1. add ()

A add () metódus használható elemek hozzáadásához egy halmazhoz. A metódusszerződés kimondja, hogy egy elem csak akkor kerül hozzáadásra, ha még nincs meg egy készletben. Ha elemet adtak hozzá, a metódus visszatér igaz, másképp - hamis.

Hozzáadhatunk egy elemet az a-hoz HashSet mint:

@Test public void whenAddingElement_shouldAddElement () {Set hashset = new HashSet (); assertTrue (hashset.add ("String hozzáadva")); }

A megvalósítás szempontjából az hozzá módszer rendkívül fontos. A megvalósítás részletei szemléltetik, hogy a HashSet belül működik és kihasználja a HashMap'stedd módszer:

nyilvános logikai add (E e) {return map.put (e, PRESENT) == null; }

A térkép változó utalás a belső, háttérre HashMap:

saját átmeneti HashMap térkép;

Jó ötlet lenne megismerkedni a hash kód először annak részletes megértése, hogy az elemek hogyan épülnek fel hash-alapú adatstruktúrákban.

Összegezve:

• A HashMap tömbje vödrök alapértelmezett kapacitása 16 elem - mindegyik csoport más és más hashcode értéknek felel meg
• Ha a különböző objektumok hashcode értéke megegyezik, egyetlen vödörben tárolódnak
• Ha a terhelési tényező elérve, egy új tömb jön létre az előzőnél kétszer nagyobb méretben, és az összes elem újraszerkesztésre kerül, és újraelosztásra kerül az új megfelelő vödrök között
• Egy érték lekéréséhez kivonatolunk egy kulcsot, módosítjuk, majd elmegyünk egy megfelelő vödörbe, és átkutatjuk a potenciálisan összekapcsolt listát, ha egynél több objektum van

3.2. tartalmaz ()

A tartalmazza A módszer az, hogy ellenőrizzük, van-e egy adott elem egy adott elemben HashSet. Visszatér igaz ha az elem megtalálható, különben hamis.

Ellenőrizhetünk egy elemet a HashSet:

@Test public void whenCheckingForElement_shouldSearchForElement () {Set hashsetContains = new HashSet (); hashsetContains.add ("String hozzáadva"); assertTrue (hashsetContains.contains ("String hozzáadva")); }

Amikor egy objektumot átadunk ennek a módszernek, a kivonatolási érték kiszámításra kerül. Ezután a megfelelő vödör helyét megoldják és bejárják.

3.3. eltávolítás ()

A módszer eltávolítja a megadott elemet a halmazból, ha van ilyen. Ez a módszer visszatér igaz ha egy halmaz tartalmazta a megadott elemet.

Lássunk egy működő példát:

@Test public void whenRemovingElement_shouldRemoveElement () {Set removeFromHashSet = new HashSet (); removeFromHashSet.add ("Karakterlánc hozzáadva"); assertTrue (removeFromHashSet.remove ("String hozzáadva")); }

3.4. egyértelmű()

Akkor használjuk ezt a módszert, amikor az összes elemet el akarjuk távolítani egy készletből. Az alapul szolgáló megvalósítás egyszerűen kitisztítja az összes elemet az mögöttesről HashMap.

Lássuk ezt működés közben:

@Test public void whenClearingHashSet_shouldClearHashSet () {Set clearHashSet = new HashSet (); clearHashSet.add ("String hozzáadva"); clearHashSet.clear (); assertTrue (clearHashSet.isEmpty ()); }

3.5. méret()

Ez az API egyik alapvető módszere. Erősen használják, mivel segít azonosítani az elemben található elemek számát HashSet. Az alapul szolgáló megvalósítás egyszerűen átruházza a számítást a HashMap mérete () módszer.

Lássuk ezt működés közben:

@Test public void whenCheckingTheSizeOfHashSet_shouldReturnThesize () {Set hashSetSize = new HashSet (); hashSetSize.add ("String hozzáadva"); assertEquals (1, hashSetSize.size ()); }

3.6. üres()

Használhatjuk ezt a módszert arra, hogy kitaláljuk, ha a HashSet üres vagy sem. Ez a módszer visszatér igaz ha a készlet nem tartalmaz elemeket:

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

3.7. iterátor ()

A metódus egy iterátort ad vissza a Készlet. Az elemeket nem külön sorrendben keressük fel, és az iterátorok hibamentesek.

A véletlenszerű iterációs sorrendet itt figyelhetjük meg:

@Test public void whenIteratingHashSet_shouldIterateHashSet () {Set hashset = new HashSet (); hashset.add ("Első"); hashset.add ("Második"); hashset.add ("Harmadik"); Iterátor itr = hashset.iterator (); while (itr.hasNext ()) {System.out.println (itr.next ()); }}

Ha a halmaz bármikor módosul az iterátor létrehozása után, kivéve az iterátor saját eltávolítási módszerét, a Iterátor dob egy ConcurrentModificationException.

Lássuk ezt működés közben:

@Test (várható = ConcurrentModificationException.class) public void whenModifyingHashSetWhileIterating_shouldThrowException () {Set hashset = new HashSet (); hashset.add ("Első"); hashset.add ("Második"); hashset.add ("Harmadik"); Iterátor itr = hashset.iterator (); while (itr.hasNext ()) {itr.next (); hashset.remove ("Második"); }} 

Alternatív megoldásként, ha az iterátor eltávolítási módszerét használtuk volna, akkor nem találkoztunk volna a kivétellel:

@Test public void whenRemovingElementUsingIterator_shouldRemoveElement () {Set hashset = new HashSet (); hashset.add ("Első"); hashset.add ("Második"); hashset.add ("Harmadik"); Iterátor itr = hashset.iterator (); while (itr.hasNext ()) {String elem = itr.next (); if (elem.egyenlő ("Második")) itr.remove (); } assertEquals (2, hashset.size ()); }

Az iterátor hibamentes viselkedése nem garantálható, mivel szinkronizálatlan párhuzamos módosítás esetén lehetetlen szigorú garanciákat nyújtani.

Kudarcsebességű iterátorok dobnak ConcurrentModificationException legjobb erőfeszítés alapján. Ezért téves lenne olyan programot írni, amely helyessége ettől a kivételtől függ.

4. Hogyan HashSet Fenntartja az egyediséget?

Amikor egy tárgyat a HashSet, az objektumét használja hash kód érték annak meghatározásához, hogy egy elem nincs-e már a halmazban.

Mindegyik kivonatkódérték egy bizonyos csoportos helynek felel meg, amely különféle elemeket tartalmazhat, amelyeknél a számított kivonatolási érték megegyezik. De két tárgy azonos hash kód lehet, hogy nem egyenlő.

Tehát az ugyanazon vödörben lévő objektumokat a egyenlő () módszer.

5. Teljesítése HashSet

Az előadás a HashSet főleg két paraméter befolyásolja - annak Kezdeti kapacitás és a Terhelési tényező.

Az elem hozzáadása a halmazhoz várható időbeli összetettsége O (1) ami leeshet Tovább) a legrosszabb esetben (csak egy vödör van jelen) - ezért elengedhetetlen a jog fenntartása HashSet kapacitás.

Fontos megjegyzés: a JDK 8 óta a legrosszabb esetben az idő összetettsége O (log * n).

A terhelési tényező leírja, hogy mi a maximális kitöltési szint, amely felett egy készletet át kell méretezni.

Hozhatunk létre a HashSet egyéni értékeivel kezdeti kapacitás és terhelési tényező:

Set hashset = new HashSet (); Set hashset = új HashSet (20); Set hashset = új HashSet (20, 0,5f); 

Az első esetben az alapértelmezett értékeket használják - a kezdeti kapacitás 16 és a terhelési tényező 0,75. A másodikban felülírjuk az alapértelmezett kapacitást, a harmadikban pedig mindkettőt.

Az alacsony kezdeti kapacitás csökkenti a tér bonyolultságát, de megnöveli az újragyártás gyakoriságát, ami drága folyamat.

Másrészről, a magas kezdeti kapacitás megnöveli az iteráció költségét és a kezdeti memóriafelhasználást.

Mint egy ökölszabály:

• A magas kezdeti kapacitás sok bejegyzéshez jó, kevés vagy egyáltalán nem iterálva
• Az alacsony kezdeti kapacitás kevés bejegyzéshez jó, sok iterációval

Ezért nagyon fontos megtalálni a helyes egyensúlyt a kettő között. Általában az alapértelmezett megvalósítás optimalizálódik, és remekül működik, ha úgy érezzük, hogy ezeket a paramétereket a követelményeknek megfelelően kell hangolnunk, akkor megfontoltan kell tennünk.

6. Következtetés

Ebben a cikkben felvázoltuk a HashSet, célja és mögöttes működése. Láttuk, hogy mennyire hatékony a használhatóság szempontjából, tekintettel az állandó időbeli teljesítményre és az ismétlődések elkerülésére.

Tanulmányoztunk néhány fontos módszert az API-ból, hogyan segíthetnek nekünk fejlesztőként az a használatában HashSet annak lehetőségeihez.

Mint mindig, a kódrészletek is megtalálhatók a GitHubon.