Úvod do triedy Java.util.Hashtable
1. Prehľad
Hashtable je najstaršia implementácia dátovej štruktúry hash tabuľky v Jave. The HashMap je druhá implementácia, ktorá bola zavedená v JDK 1.2.
Obe triedy poskytujú podobnú funkcionalitu, ale existujú aj malé rozdiely, ktoré preskúmame v tomto tutoriále.
2. Kedy použiť Hashtable
Povedzme, že máme slovník, kde každé slovo má svoju definíciu. Musíme tiež rýchlo získať, vložiť a odstrániť slová zo slovníka.
Teda Hashtable (alebo HashMap) dáva zmysel. Slová budú kľúčmi v Hashtable, pretože majú byť jedinečné. Na druhej strane budú definíciami hodnoty.
3. Príklad použitia
Pokračujme príkladom zo slovníka. Budeme modelovať Slovo ako kľúč:
public class Word {private String name; verejné slovo (názov reťazca) {this.name = meno; } // ...}Povedzme, že hodnoty sú Struny. Teraz môžeme vytvoriť Hashtable:
Hashtable tabuľka = nová Hashtable ();Najskôr pridajme záznam:
Slovo slovo = nové slovo ("mačka"); table.put (slovo, "zviera");Pre získanie záznamu:
Definícia reťazca = table.get (slovo);Nakoniec odstráňte záznam:
definícia = tabuľka.odstrániť (slovo);V triede je oveľa viac metód a niektoré z nich si popíšeme neskôr.
Najprv si však povieme niečo o niektorých požiadavkách na kľúčový objekt.
4. Dôležitosť hashCode ()
Používa sa ako kľúč v a Hashtable, objekt nesmie porušovať hashCode () zmluva. Stručne povedané, rovnaké objekty musia vrátiť rovnaký kód. Aby sme pochopili, prečo sa pozrime na to, ako je usporiadaná tabuľka hash.
Hashtable používa pole. Každá pozícia v poli je „segment“, ktorý môže mať nulovú hodnotu alebo môže obsahovať jeden alebo viac párov kľúč - hodnota. Vypočíta sa index každého páru.
Prečo ale neukladať prvky postupne a na koniec poľa pridávať nové prvky?
Jedná sa o to, že hľadanie prvku podľa indexu je oveľa rýchlejšie ako postupné iterácia cez prvky s porovnaním. Preto potrebujeme funkciu, ktorá mapuje kľúče na indexy.
4.1. Tabuľka priamych adries
Najjednoduchším príkladom takéhoto mapovania je tabuľka priamych adries. Tu sa kľúče používajú ako indexy:
index (k) = k, kde k je kľúčKľúče sú jedinečné, to znamená, že každý segment obsahuje jeden pár kľúč - hodnota. Táto technika funguje dobre pre celé čísla, keď je ich možný rozsah primerane malý.
Máme tu však dva problémy:
- Po prvé, naše kľúče nie sú celé čísla, ale Slovo predmety
- Po druhé, keby to boli celé čísla, nikto by nezaručil, že sú malé. Predstavte si, že kľúče sú 1, 2 a 10 000 000. Budeme mať veľké pole veľkosti 10 000 000 s iba tromi prvkami a zvyšok bude zbytočným priestorom.
hashCode () metóda rieši prvý problém.
Logika manipulácie s údajmi v Hashtable rieši druhý problém.
Poďme o tom diskutovať do hĺbky.
4.2. hashCode () Metóda
Akýkoľvek objekt Java zdedí hashCode () metóda, ktorá vracia int hodnotu. Táto hodnota sa počíta z adresy vnútornej pamäte objektu. Predvolene hashCode () vráti odlišné celé čísla pre odlišné objekty.
Teda akýkoľvek kľúčový objekt je možné previesť na celé číslo pomocou hashCode (). Ale toto celé číslo môže byť veľké.
4.3. Zníženie rozsahu
dostať (), put () a odstrániť () metódy obsahujú kód, ktorý rieši druhý problém - zmenšenie rozsahu možných celých čísel.
Vzorec počíta index pre kľúč:
int index = (hash & 0x7FFFFFFF)% tab.length;Kde dĺžka tab je veľkosť poľa a hash je číslo vrátené kľúčom hashCode () metóda.
Ako vidíme index je pripomienkou rozdelenia hash podľa veľkosti poľa. Upozorňujeme, že rovnaké kódy hash produkujú rovnaký index.
4.4. Zrážky
Ďalej rovnomerne rôzne hash kódy môžu produkovať rovnaký index. Hovoríme o tom ako o kolízii. Riešiť kolízie Hashtable obchody a LinkedList párov kľúč - hodnota.
Takáto dátová štruktúra sa nazýva hašovacia tabuľka s reťazením.
4.5. Vyťaženosť
Je ľahké uhádnuť, že kolízie spomaľujú operácie s prvkami. Na získanie záznamu nestačí poznať jeho index, ale musíme prejsť zoznamom a vykonať porovnanie s každou položkou.
Preto je dôležité znížiť počet kolízií. Čím väčšie je pole, tým menšia je pravdepodobnosť kolízie. Faktor zaťaženia určuje rovnováhu medzi veľkosťou poľa a výkonom. Predvolene je to 0,75, čo znamená, že veľkosť poľa sa zdvojnásobí, keď 75% segmentov nebude prázdnych. Túto operáciu vykonáva rehash () metóda.
Vráťme sa však ku kľúčom.
4.6. Prepísanie equals () a hashCode ()
Keď vložíme záznam do a Hashtable a dostaneme to z toho, očakávame, že hodnotu je možné získať nielen pomocou rovnakej inštancie kľúča, ale aj pomocou rovnakého kľúča:
Slovo slovo = nové slovo ("mačka"); table.put (slovo, "zviera"); Reťazec extrahovaný = table.get (nové slovo ("mačka"));Aby sme stanovili pravidlá rovnosti, prepíšeme kľúčové rovná sa () metóda:
public boolean equals (Object o) {if (o == this) return true; if (! (o instanceof Word)) return false; Slovo slovo = (Slovo) o; návrat word.getName (). equals (this.name); }Ale ak neprepíšeme hashCode () pri prevahe rovná sa () potom dva rovnaké kľúče môžu skončiť v rôznych segmentoch, pretože Hashtable vypočítava index kľúča pomocou jeho hash kódu.
Pozrime sa podrobne na vyššie uvedený príklad. Čo sa stane, ak neprepíšeme hashCode ()?
- Dva prípady Slovo sú tu zapojené - prvá slúži na vloženie záznamu a druhá na získanie záznamu. Aj keď sú tieto prípady rovnaké, ich hashCode () metóda vráti rôzne čísla
- Index pre každý kľúč sa vypočíta podľa vzorca z časti 4.3. Podľa tohto vzorca môžu rôzne hašovacie kódy vytvárať rôzne indexy
- To znamená, že sme vložili vstup do jedného vedra a potom sa ho pokúsili dostať von z druhého vedra. Takéto logické zlomy Hashtable
Rovnaké kľúče musia vracať rovnaké hašovacie kódy, preto prepíšeme hashCode () metóda:
public int hashCode () {return name.hashCode (); }Poznač si to tiež sa odporúča, aby nerovnaké kľúče vracali rôzne hash kódy, inak skončia v rovnakom vedre. To zasiahne výkon, a tým stratí niektoré z výhod a Hashtable.
Upozorňujeme tiež, že sa nestaráme o kľúče od String, Celé číslo, Dlhé alebo iného typu obalu. Oboje rovnaké () a hashCode () metódy sú už prepísané v obálkových triedach.
5. Iterácia Hashtables
Existuje niekoľko spôsobov, ako iterovať Hashtables. V tejto časti o nich dobre hovorte a vysvetlite niektoré z nich.
5.1. Rýchle zlyhanie: Iterácia
Fail-fast iterácia znamená, že ak a Hashtable je upravený po Iterátor potom sa vytvorí ConcurrentModificationException bude vyhodený. Poďme si to demonštrovať.
Najskôr vytvoríme a Hashtable a pridajte do nej záznamy:
Hashtable tabuľka = nová Hashtable (); table.put (nové slovo ("mačka"), "zviera"); table.put (nové slovo ("pes"), "iné zviera");Po druhé, vytvoríme Iterátor:
Iterátor it = table.keySet (). Iterator ();A do tretice upravíme tabuľku:
table.remove (nové slovo ("pes"));Teraz, keď sa pokúsime iterovať tabuľkou, dostaneme a ConcurrentModificationException:
while (it.hasNext ()) {kľúč Word = it.next (); }java.util.ConcurrentModificationException na java.util.Hashtable $ Enumerator.next (Hashtable.java:1378)ConcurrentModificationException pomáha nájsť chyby a vyhnúť sa tak nepredvídateľnému správaniu, keď napríklad jedno vlákno iteruje tabuľkou a iné sa ho snaží súčasne upravovať.
5.2. Nezlyhá rýchlo: Vymenovanie
Vymenovanie v Hashtable nie je rýchly. Pozrime sa na príklad.
Najskôr vytvorme a Hashtable a pridajte do nej záznamy:
Hashtable tabuľka = nová Hashtable (); table.put (nové slovo ("1"), "jeden"); table.put (nové slovo ("2"), "dva");Po druhé, vytvorme Vymenovanie:
Výpočet enumKey = table.keys ();Po tretie, poďme upraviť tabuľku:
table.remove (nové slovo ("1"));Teraz, keď prechádzame tabuľkou, nebude to spôsobovať výnimku:
while (enumKey.hasMoreElements ()) {Word key = enumKey.nextElement (); }5.3. Nepredvídateľný príkaz na iteráciu
Upozorňujeme tiež, že poradie iterácií v a Hashtable je nepredvídateľný a nezhoduje sa s poradím, v ktorom boli záznamy pridané.
Je to pochopiteľné, pretože každý index sa počíta pomocou hashovacieho kódu kľúča. Okrem toho sa čas od času uskutoční opätovné premiešanie, ktoré zmení poradie dátovej štruktúry.
Preto poďme pridať nejaké položky a skontrolovať výstup:
Hashtable tabuľka = nová Hashtable (); table.put (nové slovo ("1"), "jeden"); table.put (nové slovo ("2"), "dva"); // ... table.put (nové slovo ("8"), "osem"); Iterátor it = table.entrySet (). iterator (); while (it.hasNext ()) {Map.Entry entry = it.next (); // ...}} päť štyri tri dva jeden osem sedem6. Hashtable vs. HashMap
Hashtable a HashMap poskytujú veľmi podobnú funkčnosť.
Obaja poskytujú:
- Rýchla iterácia zlyhania
- Nepredvídateľné poradie iterácie
Existujú však aj niektoré rozdiely:
- HashMap neposkytuje žiadne Počet, zatiaľ čo Hashtable poskytuje rýchle zlyhanie Vymenovanie
- Hashtable neumožňuje nulový kľúče a nulový hodnoty, zatiaľ čo HashMap povoliť jeden nulový kľúč a ľubovoľný počet nulový hodnoty
- HashtableMetódy sú synchronizované, zatiaľ čo HashMapsMetódy nie sú
7. Hashtable API v Jave 8
Java 8 predstavila nové metódy, ktoré pomáhajú vylepšiť náš kód. Najmä sa niektorých môžeme zbaviť ak blokov. Poďme si to demonštrovať.
7.1. getOrDefault ()
Povedzme, že musíme získať definíciu slova „pes” a priraďte ju k premennej, ak je na stole. V opačnom prípade priraďte premennej slovo „nenájdené“.
Pred jazykom Java 8:
Kľúč slova = nové slovo („pes“); Definícia reťazca; if (table.containsKey (kľúč)) {definícia = table.get (kľúč); } else {definition = "nenájdené"; }Po prostredí Java 8:
definition = table.getOrDefault (kľúč, "nenájdený");7.2. putIfAbsent ()
Povedzme, že musíme dať slovo „mačka“ iba ak to ešte nie je v slovníku.
Pred jazykom Java 8:
if (! table.containsKey (new Word ("cat"))) {table.put (new Word ("cat"), definition); }Po prostredí Java 8:
table.putIfAbsent (nové slovo ("mačka"), definícia);7.3. boolean remove ()
Povedzme, že musíme odstrániť slovo „mačka“, ale iba ak je to definícia pojmu „zviera“.
Pred jazykom Java 8:
if (table.get (new Word ("cat")). equals ("an animal")) {table.remove (new Word ("cat")); }Po prostredí Java 8:
boolean result = table.remove (nové slovo ("mačka"), "zviera");Nakoniec, kým je starý odstrániť () metóda vráti hodnotu, vráti sa nová metóda boolovský.
7.4. nahradiť ()
Povedzme, že musíme nahradiť definíciu „mačky“, ale iba ak je jej stará definícia „malý domestikovaný mäsožravý cicavec“.
Pred jazykom Java 8:
if (table.containsKey (nové slovo ("mačka")) && table.get (nové slovo ("mačka")). rovná sa ("malý domestikovaný mäsožravý cicavec")) {table.put (nové slovo ("mačka") ), definícia); }Po prostredí Java 8:
table.replace (nové slovo („mačka“), „malý domestikovaný mäsožravý cicavec“, definícia);7.5. computeIfAbsent ()
Táto metóda je podobná ako v putIfabsent (). ale putIfabsent () preberá hodnotu priamo a computeIfAbsent () má funkciu mapovania. Hodnotu vypočítava až po kontrole kľúča, čo je efektívnejšie, najmä ak je ťažké ju získať.
table.computeIfAbsent (nové slovo ("mačka"), klávesa -> "zviera");Preto je vyššie uvedený riadok ekvivalentný:
if (! table.containsKey (cat)) {Definícia reťazca = "zviera"; // všimnite si, že výpočty prebiehajú vo vnútri if block table.put (nový Word ("mačka"), definícia); }7.6. computeIfPresent ()
Táto metóda je podobná ako v prípade nahradiť () metóda. Ale opäť nahradiť () preberá hodnotu priamo a computeIfPresent () má funkciu mapovania. Vypočíta hodnotu vo vnútri súboru ak blok, preto je to efektívnejšie.
Povedzme, že musíme zmeniť definíciu:
table.computeIfPresent (mačka, (kľúč, hodnota) -> key.getName () + "-" + hodnota);Preto je vyššie uvedený riadok ekvivalentný:
if (table.containsKey (cat)) {reťazec concatination = cat.getName () + "-" + table.get (cat); table.put (mačka, konkatinácia); }7.7. vypočítať ()
Teraz vyriešime ďalšiu úlohu. Povedzme, že máme pole String, kde prvky nie sú jedinečné. Poďme tiež vypočítať, koľko výskytov reťazca môžeme v poli získať. Tu je pole:
Reťazec [] zvieratá = {"mačka", "pes", "pes", "mačka", "vták", "myš", "myš"};Tiež chceme vytvoriť a Hashtable ktorá obsahuje zviera ako kľúč a počet jeho výskytov ako hodnotu.
Tu je riešenie:
Hashtable tabuľka = nová Hashtable (); pre (String animal: animals) {table.compute (animal, (key, value) -> (value == null? 1: value + 1)); }Na záver sa uistite, že tabuľka obsahuje dve mačky, dva psy, jedného vtáka a dve myši:
assertThat (table.values (), hasItems (2, 2, 2, 1));7.8. zlúčiť()
Vyššie uvedenú úlohu je možné vyriešiť ďalším spôsobom:
pre (String animal: animals) {table.merge (animal, 1, (oldValue, value) -> (oldValue + value)); }Druhý argument, 1, je hodnota, ktorá je namapovaná na kľúč, ak kľúč ešte nie je na stole. Ak je kľúč už v tabuľke, vypočítame ho ako oldValue + 1.
7.9. pre každý()
Toto je nový spôsob opakovania položiek. Vytlačme všetky záznamy:
table.forEach ((k, v) -> System.out.println (k.getName () + "-" + v)7.10. nahradiť všetko()
Ďalej môžeme nahradiť všetky hodnoty bez iterácie:
table.replaceAll ((k, v) -> k.getName () + "-" + v);8. Záver
V tomto článku sme opísali účel štruktúry tabuľky hash a ukázali sme, ako ju získať, aby sa skomplikovala štruktúra tabuľky priamych adries.
Ďalej sme sa venovali tomu, čo sú kolízie a aký je faktor zaťaženia v a Hashtable. Tiež sme sa naučili, prečo prepísať rovná sa () a hashCode () pre kľúčové objekty.
Nakoniec sme hovorili o HashtableVlastnosti a API špecifické pre Java 8.
Kompletný zdrojový kód je ako obvykle dostupný na stránkach Github.
