streamalism.org

1. Áttekintés

Hashtable a hash tábla adatstruktúrájának legrégebbi megvalósítása a Java-ban. A HashMap a második megvalósítás, amelyet a JDK 1.2-ben vezettek be.

Mindkét osztály hasonló funkcionalitást kínál, de vannak kisebb eltérések is, amelyeket ebben az oktatóanyagban fogunk megvizsgálni.

2. Mikor kell használni Hashtable

Tegyük fel, hogy van egy szótárunk, ahol minden szónak megvan a meghatározása. Ezenkívül gyorsan meg kell szereznünk, beillesztenünk és eltávolítanunk a szavakat a szótárból.

Ennélfogva, Hashtable (vagy HashMap) van értelme. A szavak lesznek a kulcsok a Hashtable, mivel állítólag egyediek. A definíciók viszont az értékek lesznek.

3. Példa a felhasználásra

Folytassuk a szótár példával. Mi modellezünk Szó kulcsként:

public class Word {private String name; public Word (karakterlánc neve) {this.name = név; } // ...}

Mondjuk az értékek Húrok. Most létrehozhatunk egy Hashtable:

Hashtable táblázat = új Hashtable ();

Először adjunk hozzá egy bejegyzést:

Szó szó = új Szó ("macska"); table.put (szó, "állat");

A bejegyzés megszerzéséhez:

Karaktersorozat meghatározása = tábla.get (szó);

Végül távolítsunk el egy bejegyzést:

meghatározás = tábla.eltávolítás (szó);

Sokkal több módszer létezik az osztályban, és néhányukat később leírjuk.

De először beszéljünk a kulcsobjektum néhány követelményéről.

4. A fontossága hash kód()

Kulcsként használható a Hashtable, az objektum nem sértheti a hash kód() szerződés. Röviden, az egyenlő objektumoknak ugyanazt a kódot kell visszaadniuk. Hogy megértsük, miért nézzük meg, hogyan van felépítve a hash tábla.

Hashtable tömböt használ. A tömb minden pozíciója egy „vödör”, amely lehet null, vagy tartalmazhat egy vagy több kulcs-érték párot. Minden pár indexét kiszámítják.

De miért ne tárolhatnánk elemeket egymás után, új elemeket adva a tömb végéhez?

A lényeg az, hogy egy elem index alapján történő megkeresése sokkal gyorsabb, mint az elemek egymás utáni iterálása az összehasonlítással. Ezért szükségünk van egy olyan funkcióra, amely a kulcsokat indexekhez társítja.

4.1. Közvetlen címtábla

Az ilyen leképezés legegyszerűbb példája a közvetlen cím tábla. Itt a kulcsokat használják indexként:

index (k) = k, ahol k egy kulcs

A kulcsok egyediek, vagyis mindegyik csoport egy-érték párot tartalmaz. Ez a technika egész számkulcsok esetén jól működik, ha ezek lehetséges tartománya meglehetősen kicsi.

De két problémánk van itt:

• Először is, a kulcsaink nem egész számok, hanem Szó tárgyakat
• Másodszor, ha egész számok lennének, senki sem garantálná, hogy kicsik. Képzelje el, hogy a kulcsok 1, 2 és 1000000. Nagy 1000000 méretű tömbünk lesz, csak három elemmel, a többi pedig elpazarolt hely lesz

hash kód() módszer megoldja az első problémát.

Az adatkezelés logikája a Hashtable megoldja a második problémát.

Beszéljük meg ezt alaposan.

4.2. hash kód() Módszer

Bármely Java objektum örökli a hash kód() metódus, amely egy int érték. Ez az érték az objektum belső memória címéből kerül kiszámításra. Alapértelmezés szerint hash kód() különböző egész számokat ad vissza különálló objektumokhoz.

Így bármely kulcsobjektum konvertálható egész számra a hash kód(). De ez az egész nagy lehet.

4.3. A hatótávolság csökkentése

kap(), put () és eltávolítás () A metódusok tartalmazzák azt a kódot, amely megoldja a második problémát - csökkentve a lehetséges egész számok tartományát.

A képlet kiszámítja a kulcs indexét:

int index = (hash & 0x7FFFFFFF)% fül.hossz;

Hol fül.hossz a tömb mérete, és hash a kulcs által visszaadott szám hash kód() módszer.

Ahogy látjuk index emlékezteti a megosztást hash a tömb méretével. Vegye figyelembe, hogy az azonos hash kódok ugyanazt az indexet hozzák létre.

4.4. Ütközések

Továbbá még a különböző hash kódok ugyanazt az indexet hozhatják létre. Ezt ütközésnek nevezzük. Az ütközések megoldására Hashtable üzletek a LinkedList kulcs-érték párokból.

Az ilyen adatszerkezetet hash-táblának hívják láncolással.

4.5. Terhelési tényező

Könnyű kitalálni, hogy az ütközések lelassítják az elemekkel végzett műveleteket. A bejegyzés megszerzéséhez nem elég az indexének ismerete, de át kell mennünk a listán, és össze kell hasonlítanunk az egyes elemeket.

Ezért fontos az ütközések számának csökkentése. Minél nagyobb egy tömb, annál kisebb az ütközés esélye. A terhelési tényező meghatározza a tömb mérete és a teljesítmény közötti egyensúlyt. Alapértelmezés szerint ez 0,75, ami azt jelenti, hogy a tömb mérete megduplázódik, ha a vödrök 75% -a nem üres. Ezt a műveletet a felmelegít() módszer.

De térjünk vissza a kulcsokhoz.

4.6. Az egyenlő () és a hashCode () felülírása

Amikor bejegyzést teszünk a Hashtable és kihozzuk belőle, azt várjuk, hogy az érték nemcsak a kulcs példányával, hanem egy egyenlő kulccsal is megszerezhető:

Szó szó = új Szó ("macska"); table.put (szó, "állat"); Karaktersorozat kivonva = table.get (új Szó ("macska"));

Az egyenlőség szabályainak megállapításához felülírjuk a kulcsot egyenlő () módszer:

nyilvános logikai egyenlő (o objektum) {if (o == this) return true; ha (! (a Word példánya)) hamis értéket ad vissza; Szó szó = (Szó) o; return word.getName (). egyenlő (ez.név); }

De ha nem írjuk felül hash kód() amikor felülbírálja egyenlő () akkor két egyenlő kulcs kerülhet a különböző vödrökbe, mert Hashtable kiszámítja a kulcs indexét hash-kódja segítségével.

Vizsgáljuk meg alaposan a fenti példát. Mi történik, ha nem írjuk felül hash kód()?

• Két példa Szó részt vesznek itt - az első a bejegyzés feltöltése, a második pedig a bejegyzés megszerzése. Bár ezek az esetek egyenlőek, azok hash kód() metódus különböző számokat ad vissza
• Az egyes kulcsok indexét a 4.3 szakasz képlete számítja ki. E képlet szerint a különböző hash-kódok különböző indexeket hozhatnak létre
• Ez azt jelenti, hogy a bejegyzést egy vödörbe tesszük, majd megpróbáljuk kihozni a másik vödörből. Ilyen logika szakad meg Hashtable

Az egyenlő kulcsoknak egyenlő hash kódokat kell visszaadniuk, ezért felülírjuk a hash kód() módszer:

public int hashCode () {return name.hashCode (); }

Vegye figyelembe, hogy azt is javasoljuk, hogy a nem egyenlő kulcsok különböző hash kódokat adjanak vissza, különben ugyanabba a vödörbe kerülnek. Ez eléri a teljesítményt, így elveszíti a Hashtable.

Vegye figyelembe azt is, hogy nem érdekelnek a kulcsok Húr, Egész szám, Hosszú vagy más burkolótípus. Mindkét egyenlő() és hash kód() a burkoló osztályokban már felülírják a módszereket.

5. Iteráló Hashtables

Van néhány módja az iterációnak Hashtables. Ebben a részben beszéljen róluk, és magyarázza el néhány következményét.

5.1. Gyors kudarc: Ismétlés

A sikertelen iteráció azt jelenti, hogy ha a Hashtable után módosul Iterátor létrejön, akkor a ConcurrentModificationException dobni fogják. Bemutassuk ezt.

Először létrehozunk egy Hashtable és adjon hozzá bejegyzéseket:

Hashtable táblázat = új Hashtable (); table.put (új Szó ("macska"), "állat"); table.put (új Szó ("kutya"), "másik állat");

Másodszor létrehozunk egy Iterátor:

Iterátor it = table.keySet (). Iterator ();

Harmadszor pedig módosítjuk a táblázatot:

table.remove (új Szó ("kutya"));

Most, ha megpróbálunk iterálni az asztalon, akkor kapunk egy ConcurrentModificationException:

while (it.hasNext ()) {Word kulcs = it.next (); }

java.util.ConcurrentModificationException itt: java.util.Hashtable $ Enumerator.next (Hashtable.java:1378)

ConcurrentModificationException segít megtalálni a hibákat és így elkerülni a kiszámíthatatlan viselkedést, amikor például az egyik szál végig iterál a táblán, és egy másik egyszerre próbálja módosítani.

5.2. Nem bukik meg gyorsan: Felsorolás

Felsorolás a Hashtable nem kudarc. Nézzünk meg egy példát.

Először hozzunk létre egy Hashtable és adjon hozzá bejegyzéseket:

Hashtable táblázat = új Hashtable (); table.put (new Word ("1"), "one"); table.put (új Szó ("2"), "kettő");

Másodszor hozzunk létre egy Felsorolás:

Számlálás enumKey = table.keys ();

Harmadszor, módosítsuk a táblázatot:

table.remove (új Szó ("1"));

Most, ha iterálunk az asztalon, nem vet ki kivételt:

while (enumKey.hasMoreElements ()) {Word kulcs = enumKey.nextElement (); }

5.3. Kiszámíthatatlan iterációs sorrend

Vegye figyelembe azt is, hogy az iterációs sorrend a Hashtable kiszámíthatatlan és nem egyezik a bejegyzések hozzáadásának sorrendjével.

Ez érthető, mivel minden indexet kiszámít a kulcs kivonatával. Sőt, az újragyakorlás időről időre megtörténik, átrendezi az adatstruktúra sorrendjét.

Ezért adjunk hozzá néhány bejegyzést, és ellenőrizzük a kimenetet:

Hashtable táblázat = új Hashtable (); table.put (új Szó ("1"), "egy"); table.put (új Szó ("2"), "kettő"); // ... table.put (új Word ("8"), "nyolc"); Iterátor it = table.entrySet (). iterator (); while (it.hasNext ()) {Map.Entry entry = it.next (); // ...}}

öt négy három kettő nyolc hét

6. Hashtable vs. HashMap

Hashtable és HashMap nagyon hasonló funkcionalitást nyújtanak.

Mindkettő biztosítja:

• Hibaelhárító iteráció
• Megjósolhatatlan iterációs sorrend

De van néhány különbség is:

• HashMap nem nyújt semmit Felsorolás, míg Hashtable nem gyors Felsorolás
• Hashtable nem engedi nulla gombok és nulla értékek, míg HashMap engedjen meg egyet nulla kulcs és tetszőleges számú nulla értékek
• HashtableA módszerek szinkronizálva vannak HashMaps’S módszerei nem

7. Hashtable API Java 8-ban

A Java 8 új módszereket vezetett be, amelyek elősegítik a kód tisztábbá tételét. Különösen megszabadulhatunk néhányaktól ha blokkok. Bemutassuk ezt.

7.1. getOrDefault ()

Tegyük fel, hogy meg kell kapnunk a „kutya” és rendelje hozzá a változóhoz, ha az asztalon van. Ellenkező esetben a „not found” értéket rendelje hozzá a változóhoz.

Java 8 előtt:

Szó kulcs = új Szó ("kutya"); Húr meghatározása; if (tábla.tartjaKulcs (kulcs)) {meghatározás = tábla.get (kulcs); } else {meghatározás = "nem található"; }

Java 8 után:

meghatározás = tábla.getOrDefault (kulcs, "nem található");

7.2. putIfAbsent ()

Tegyük fel, hogy ki kell tennünk egy szót: „macska“ csak ha még nincs a szótárban.

Java 8 előtt:

if (! table.containsKey (new Word ("cat")))) {table.put (new Word ("cat"), meghatározás); }

Java 8 után:

table.putIfAbsent (új Szó ("macska"), meghatározás);

7.3. logikai eltávolítás ()

Tegyük fel, hogy el kell távolítanunk a „macska” szót, de csak akkor, ha meghatározása „állat”.

Java 8 előtt:

if (tábla.get (új Szó ("macska")). egyenlő ("állat")) {tábla.eltávolítás (új Szó ("macska")); }

Java 8 után:

logikai eredmény = table.remove (új Szó ("macska"), "állat");

Végül, míg öreg eltávolítás () metódus adja vissza az értéket, az új metódus visszatér logikai.

7.4. cserélje ()

Tegyük fel, hogy ki kell cserélnünk a „macska” definícióját, de csak akkor, ha régi meghatározása „egy kis háziasított húsevő emlős”.

Java 8 előtt:

if (table.containsKey (új szó ("macska")) && table.get (új szó ("macska")). egyenlő ("egy kis háziasított húsevő emlős")) {table.put (új szó ("macska") ), meghatározása); }

Java 8 után:

table.replace (új Szó ("macska"), "kis háziasított húsevő emlős", meghatározás);

7.5. computeIfAbsent ()

Ez a módszer hasonló a putIfabsent (). De putIfabsent () közvetlenül veszi az értéket, és computeIfAbsent () leképezési funkciót vesz fel. Az értéket csak a kulcs ellenőrzése után számítja ki, és ez hatékonyabb, különösen, ha az értéket nehéz megszerezni.

table.computeIfAbsent (új Szó ("macska"), kulcs -> "állat");

Ezért a fenti sor ekvivalens:

if (! table.containsKey (cat)) {String definíció = "állat"; // vegye figyelembe, hogy a számítások az if block block.put belsejében zajlanak (new Word ("cat"), definíció); }

7.6. computeIfPresent ()

Ez a módszer hasonló a cserélje () módszer. De megint: cserélje () közvetlenül veszi az értéket, és computeIfPresent () leképezési funkciót vesz fel. Kiszámítja a ha blokk, ezért hatékonyabb.

Tegyük fel, hogy meg kell változtatnunk a definíciót:

table.computeIfPresent (macska, (kulcs, érték) -> key.getName () + "-" + érték);

Ezért a fenti sor ekvivalens:

if (tábla.tartjaKulcs (macska)) {Karakterlánc összefűzése = macska.címNév () + "-" + tábla.get (macska); table.put (macska, összefogás); }

7.7. kiszámít()

Most megoldunk egy újabb feladatot. Tegyük fel, hogy van egy tömbünk Húr, ahol az elemek nem egyediek. Számítsuk ki azt is, hogy egy String hány előfordulását kaphatunk a tömbben. Itt van a tömb:

Húr [] állatok = {"macska", "kutya", "kutya", "macska", "madár", "egér", "egér"};

Ezenkívül szeretnénk létrehozni egy Hashtable amely kulcsként egy állatot és értékként tartalmazza az előfordulások számát.

Itt van egy megoldás:

Hashtable táblázat = új Hashtable (); for (String animal: animals) {table.compute (animal, (kulcs, érték) -> (érték == null? 1: érték + 1)); }

Végül győződjünk meg arról, hogy az asztal két macskát, két kutyát, egy madarat és két egeret tartalmaz:

assertThat (tábla.értékek (), hasItems (2, 2, 2, 1));

7.8. összeolvad()

Van egy másik módja a fenti feladat megoldásának:

for (String animal: animals) {table.merge (animal, 1, (oldValue, value) -> (oldValue + value)); }

A második érv, 1, az az érték, amely a kulcshoz van hozzárendelve, ha a kulcs még nincs az asztalon. Ha a kulcs már szerepel a táblázatban, akkor a következőképpen számoljuk ki oldValue + 1.

7.9. az egyes()

Ez egy új módszer a bejegyzések iterációjára. Nyomtassuk ki az összes bejegyzést:

table.forEach ((k, v) -> System.out.println (k.getName () + "-" + v)

7.10. csereAll ()

Ezenkívül az összes értéket iteráció nélkül helyettesíthetjük:

table.replaceAll ((k, v) -> k.getName () + "-" + v);

8. Következtetés

Ebben a cikkben leírtuk a hash tábla struktúrájának célját, és megmutattuk, hogyan bonyolíthatjuk a közvetlen című tábla struktúráját annak megszerzéséhez.

Ezenkívül kitértünk az ütközésekre és a terhelési tényezőkre a Hashtable. Megtanultuk, miért kell felülbírálni egyenlő () és hash kód() kulcsobjektumokhoz.

Végül megbeszéltük HashtableTulajdonságait és a Java 8 specifikus API-t.

Szokás szerint a teljes forráskód elérhető a Githubon.