streamalism.org

1. Prehľad

V tomto článku uvidíme, ako sa používa HashMap v Jave a my sa pozrieme na to, ako to funguje interne.

Trieda veľmi podobná HashMap je Hashtable. Prečítajte si niekoľko ďalších článkov, kde sa dozviete viac o java.util.Hashtable trieda samotná a rozdiely medzi HashMap a Hashtable.

2. Základné použitie

Najprv sa pozrime, čo to znamená HashMap je mapa. Mapa je mapovanie kľúč - hodnota, čo znamená, že každý kľúč je namapovaný na presne jednu hodnotu a že pomocou neho môžeme získať príslušnú hodnotu z mapy.

Možno si položiť otázku, prečo jednoducho nepridať hodnotu do zoznamu. Prečo potrebujeme HashMap? Jednoduchým dôvodom je výkon. Ak chceme nájsť konkrétny prvok v zozname, je časová zložitosť O (n) a ak je zoznam zoradený, bude O (log n) napríklad pomocou binárneho vyhľadávania.

Výhodou a HashMap je to, že časová zložitosť na vloženie a získanie hodnoty je O (1) v priemere. Neskôr sa pozrieme na to, ako sa to dá dosiahnuť. Najprv sa pozrime na to, ako sa používa HashMap.

2.1. Nastaviť

Vytvorme jednoduchú triedu, ktorú použijeme v tomto článku:

public class Produkt {private String name; popis súkromného reťazca; súkromné ​​zoznamové značky; // štandardné getre / settery / konštruktory public Produkt addTagsOfOtherProdcut (produktový produkt) {this.tags.addAll (product.getTags ()); vráťte to; }}

2.2. Daj

Teraz môžeme vytvoriť HashMap s kľúčom typu String a prvky typu Výrobok:

Map productsByName = new HashMap (); 

A pridávať výrobky do našej HashMap:

Produkt eBike = nový produkt („E-Bike“, „Bicykel s batériou“); Produkt roadBike = nový produkt („Cestný bicykel“, „Bicykel pre súťaž“); productsByName.put (eBike.getName (), eBike); productsByName.put (roadBike.getName (), roadBike); 

2.3. Získajte

Hodnotu z mapy môžeme načítať podľa jej kľúča:

Produkt nextPurchase = productsByName.get ("E-Bike"); assertEquals ("Bicykel s batériou", nextPurchase.getDescription ());

Ak sa pokúsime nájsť hodnotu pre kľúč, ktorý na mape neexistuje, dostaneme a nulový hodnota:

Produkt nextPurchase = productsByName.get ("Auto"); assertNull (nextPurchase);

A ak vložíme druhú hodnotu s rovnakým kľúčom, dostaneme iba poslednú vloženú hodnotu pre tento kľúč:

Produkt newEBike = nový produkt („E-Bike“, „Bicykel s lepšou batériou“); productsByName.put (newEBike.getName (), newEBike); assertEquals ("Bicykel s lepšou batériou", productsByName.get ("E-Bike"). getDescription ());

2.4. Null ako kľúč

HashMap tiež nám umožňuje mať nulový ako kľúč:

Produkt defaultProduct = nový Produkt („Čokoláda“, „Aspoň kúpiť čokoládu“); productsByName.put (null, defaultProduct); Produkt nextPurchase = productsByName.get (null); assertEquals ("Aspoň kúpiť čokoládu", nextPurchase.getDescription ());

2.5. Hodnoty s rovnakým kľúčom

Ďalej môžeme vložiť ten istý objekt dvakrát s iným kľúčom:

productsByName.put (defaultProduct.getName (), defaultProduct); assertSame (productsByName.get (null), productsByName.get ("Chocolate"));

2.6. Odstrániť hodnotu

Mapovanie párov kľúč - hodnota môžeme odstrániť z HashMap:

productsByName.remove ("E-Bike"); assertNull (productsByName.get ("E-Bike"));

2.7. Skontrolujte, či na mape existuje kľúč alebo hodnota

Na kontrolu, či sa na mape nachádza kľúč, môžeme použiť containsKey () metóda:

productsByName.containsKey ("E-Bike");

Alebo na kontrolu, či je na mape hodnota, môžeme použiť containsValue () metóda:

productsByName.containsValue (eBike);

Vrátia sa obe volania metód pravda v našom príklade. Aj keď vyzerajú veľmi podobne, medzi týmito dvoma volaniami metód je dôležitý rozdiel vo výkonnosti. Zložitosť kontroly, či kľúč existuje, je O (1), zatiaľ čo zložitosť kontroly prvku je O (n), pretože je potrebné vytvoriť slučku cez všetky prvky na mape.

2.8. Iterácia cez a HashMap

Existujú tri základné spôsoby iterácie cez všetky páry kľúč - hodnota v a HashMap.

Môžeme iterovať cez množinu všetkých kľúčov:

for (String key: productsByName.keySet ()) {Product product = productsByName.get (key); }

Alebo môžeme iterovať cez množinu všetkých záznamov:

pre (položka Map.Entry: productsByName.entrySet ()) {Product product = entry.getValue (); Reťazcový kľúč = entry.getKey (); // urob niečo s kľúčom a hodnotou}

Nakoniec môžeme iterovať nad všetkými hodnotami:

Zoznam produktov = nový ArrayList (productsByName.values ​​());

3. Kľúč

Ako kľúč v našom programe môžeme použiť ktorúkoľvek triedu HashMap. Aby však mapa fungovala správne, je potrebné zabezpečiť jej implementáciu rovná sa () a hashCode ().Povedzme, že chceme mať mapu s produktom ako kľúčom a cenou ako hodnotou:

HashMap priceByProduct = nový HashMap (); priceByProduct.put (eBike, 900);

Poďme implementovať rovná sa () a hashCode () metódy:

@Override public boolean equals (Object o) {if (this == o) {return true; } if (o == null || getClass ()! = o.getClass ()) {return false; } Produkt produktu = (Produkt) o; vrátiť Objects.equals (názov, produkt.názov) && Objects.equals (popis, produkt.description); } @Override public int hashCode () {return Objects.hash (meno, popis); }

Poznač si to hashCode () a rovná sa () je potrebné prepísať iba pre triedy, ktoré chceme použiť ako kľúče mapy, nie pre triedy, ktoré sa používajú iba ako hodnoty v mape. Uvidíme, prečo je to potrebné, v časti 5 tohto článku.

4. Ďalšie metódy od Javy 8

Java 8 pridala do metódy niekoľko metód funkčného štýlu HashMap. V tejto časti sa pozrieme na niektoré z týchto metód.

Pre každú metódu sa pozrieme na dva príklady. Prvý príklad ukazuje, ako používať novú metódu, a druhý príklad ukazuje, ako dosiahnuť to isté v starších verziách Java.

Pretože tieto metódy sú celkom priame, nebudeme sa pozerať na podrobnejšie príklady.

4.1. pre každý()

The pre každý metóda je spôsob funkčného štýlu na iteráciu všetkých prvkov na mape:

productsByName.forEach ((key, product) -> {System.out.println ("Key:" + key + "Product:" + product.getDescription ()); // urobte niečo s kľúčom a hodnotou}); 

Pred Java 8:

pre (položka Map.Entry: productsByName.entrySet ()) {Product product = entry.getValue (); Reťazec key = entry.getKey (); // urob niečo s kľúčom a hodnotou}

Náš článok Sprievodca Java 8 pre každý pokrýva pre každý slučka podrobnejšie.

4.2. getOrDefault ()

Pomocou getOrDefault () metódou môžeme získať hodnotu z mapy alebo vrátiť predvolený prvok v prípade, že pre daný kľúč neexistuje mapovanie:

Produktová čokoláda = nový produkt („čokoláda“, „niečo sladké“); Produkt defaultProduct = productsByName.getOrDefault ("konský povoz", čokoláda); Produkt bike = productsByName.getOrDefault ("E-Bike", čokoláda);

Pred Java 8:

Produkt bike2 = productsByName.containsKey ("E-Bike")? productsByName.get ("E-Bike"): čokoláda; Produkt defaultProduct2 = productsByName.containsKey ("konský povoz")? productsByName.get ("horse carriage"): čokoláda; 

4.3. putIfAbsent ()

Pomocou tejto metódy môžeme pridať nové mapovanie, ale iba ak ešte neexistuje mapovanie pre daný kľúč:

productsByName.putIfAbsent ("E-Bike", čokoláda); 

Pred Java 8:

if (productsByName.containsKey ("E-Bike")) {productsByName.put ("E-Bike", čokoláda); }

Náš článok Zlúčenie dvoch máp s Java 8 sa tejto metóde podrobnejšie venuje.

4.4. zlúčiť()

A s zlúčiť(), môžeme upraviť hodnotu pre daný kľúč, ak existuje mapovanie, alebo pridať novú hodnotu inak:

Produkt eBike2 = nový produkt („E-Bike“, „Bicykel s batériou“); eBike2.getTags (). add ("šport"); productsByName.merge ("E-Bike", eBike2, Product :: addTagsOfOtherProdcut);

Pred Java 8:

if (productsByName.containsKey ("E-Bike")) {productsByName.get ("E-Bike"). addTagsOfOtherProdcut (eBike2); } else {productsByName.put ("E-Bike", eBike2); } 

4.5. vypočítať ()

Vďaka vypočítať () metódou môžeme vypočítať hodnotu pre daný kľúč:

productsByName.compute ("E-Bike", (k, v) -> {if (v! = null) {return v.addTagsOfOtherProdcut (eBike2);} else {return eBike2;}});

Pred Java 8:

if (productsByName.containsKey ("E-Bike")) {productsByName.get ("E-Bike"). addTagsOfOtherProdcut (eBike2); } else {productsByName.put ("E-Bike", eBike2); } 

Stojí za zmienku, že metódy zlúčiť() a vypočítať () sú si dosť podobné. The metóda výpočtu () prijíma dva argumenty: kľúč a a BiFunkcia na premapovanie. A zlúčiť() akceptuje tri parametre: kľúč, a predvolená hodnota pridať na mapu, ak kľúč ešte neexistuje, a a BiFunkcia na premapovanie.

5. HashMap Interní

V tejto časti sa pozrieme na to, ako na to HashMap funguje interne a aké sú výhody používania HashMap napríklad namiesto jednoduchého zoznamu.

Ako sme videli, môžeme načítať prvok z a HashMap jeho kľúčom. Jedným z prístupov by bolo použitie zoznamu, opakovanie všetkých prvkov a návrat, keď nájdeme prvok, pre ktorý sa kľúč zhoduje. Časová aj priestorová zložitosť tohto prístupu by bola O (n).

S HashMap, môžeme dosiahnuť priemernú časovú zložitosť vo výške O (1) pre dať a dostať prevádzky a priestorová zložitosť systému O (n). Pozrime sa, ako to funguje.

5.1. Hašovací kód a rovnaké

Namiesto opakovania všetkých svojich prvkov HashMap sa pokúsi vypočítať polohu hodnoty na základe jej kľúča.

Naivným prístupom by bolo mať zoznam, ktorý môže obsahovať toľko prvkov, koľko klávesov je možné. Ako príklad povedzme, že naším kľúčom je znak malých písmen. Potom stačí mať zoznam veľkosti 26 a ak chceme k prvku pristúpiť pomocou klávesu „c“, vedeli by sme, že je to ten na pozícii 3, a môžeme ho načítať priamo.

Tento prístup by však nebol veľmi efektívny, keby sme mali oveľa väčší priestor kľúčov. Povedzme napríklad, že náš kľúč bolo celé číslo. V takom prípade by veľkosť zoznamu musela byť 2 147 483 647. Vo väčšine prípadov by sme mali aj oveľa menej prvkov, takže veľká časť pridelenej pamäte by zostala nevyužitá.

HashMap ukladá prvky do takzvaných segmentov a volá sa počet segmentov kapacita.

Keď dáme do mapy hodnotu, kľúč hashCode () metóda sa používa na určenie segmentu, v ktorom bude hodnota uložená.

Ak chcete načítať hodnotu, HashMap počíta vedro rovnakým spôsobom - pomocou hashCode (). Potom iteruje cez objekty nájdené v danom segmente a používa kľúče rovná sa () metóda na nájdenie presnej zhody.

5.2. Kľúčová nezmeniteľnosť

Vo väčšine prípadov by sme mali používať nemenné klávesy. Prinajmenšom si musíme uvedomiť dôsledky používania premenlivých kľúčov.

Pozrime sa, čo sa stane, keď sa náš kľúč zmení, keď sme ho použili na uloženie hodnoty do mapy.

Pre tento príklad vytvoríme MutableKey:

public class MutableKey {private String name; // štandardný konštruktor, getter a setter @Override public boolean equals (Object o) {if (this == o) {return true; } if (o == null || getClass ()! = o.getClass ()) {return false; } MutableKey that = (MutableKey) o; vrátiť Objects.equals (meno, to.názov); } @Override public int hashCode () {return Objects.hash (meno); }}

A tu je test:

Kľúč MutableKey = nový MutableKey ("počiatočný"); Položky na mape = nová HashMap (); items.put (kľúč, „úspech“); key.setName ("zmenene"); assertNull (items.get (kľúč));

Ako vidíme, po zmene kľúča už nie sme schopní získať zodpovedajúcu hodnotu, nulový sa vracia. To je preto, že HashMap hľadá v nesprávnom segmente.

Vyššie uvedený testovací prípad môže byť prekvapivý, ak dobre nerozumieme tomu, ako HashMap pracuje interne.

5.3. Zrážky

Aby to správne fungovalo, musia mať rovnaké kľúče rovnaký hash, rôzne kľúče však môžu mať rovnaký hash. Ak majú dva rôzne kľúče rovnaký hash, dve hodnoty, ktoré im patria, sa uložia do toho istého segmentu. Vo vnútri vedra sú hodnoty uložené v zozname a načítané opakovaním cez všetky prvky. Náklady na to sú O (n).

Od Javy 8 (pozri JEP 180) sa dátová štruktúra, v ktorej sú uložené hodnoty v jednom segmente, zmení zo zoznamu na vyvážený strom, ak segment obsahuje 8 alebo viac hodnôt, a zmení sa späť na zoznam, ak na v určitom okamihu v koši zostane iba 6 hodnôt. To zlepšuje výkon, ktorý má byť O (log n).

5.4. Kapacita a koeficient zaťaženia

Ak sa chcete vyhnúť tomu, aby ste mali veľa segmentov s viacerými hodnotami, kapacita sa zdvojnásobí, ak 75% (koeficient zaťaženia) segmentov zostane prázdnych. Predvolená hodnota pre faktor zaťaženia je 75% a predvolená počiatočná kapacita je 16. Obidve je možné nastaviť v konštruktore.

5.5. Zhrnutie dať a dostať Operácie

Poďme si zhrnúť, ako dať a dostať prevádzkové práce.

Keď pridáme prvok na mapu,HashMap počíta vedro. Ak segment už obsahuje hodnotu, hodnota sa pridá do zoznamu (alebo stromu) patriaceho k tomuto segmentu. Ak sa faktor zaťaženia stane väčším ako maximálny faktor zaťaženia mapy, kapacita sa zdvojnásobí.

Keď chceme získať hodnotu z mapy,HashMap vypočítava segment a získa hodnotu rovnakým kľúčom zo zoznamu (alebo stromu).

6. Záver

V tomto článku sme videli, ako používať a HashMap a ako to funguje interne. Spolu s ArrayList, HashMap je jednou z najčastejšie používaných dátových štruktúr v Jave, takže je veľmi užitočné mať dobré vedomosti o tom, ako ju používať a ako funguje pod kapotou. Náš článok Java HashMap Under the Hood pokrýva vnútorné priestory HashMap podrobnejšie.

Celý zdrojový kód je ako obvykle k dispozícii na serveri Github.