Java HashMap Pod kapotou

1. Prehľad

V tomto článku sa budeme zaoberať najpopulárnejšou implementáciou Mapa rozhranie z Java Collections Framework podrobnejšie a pokračuje tam, kde náš úvodný článok skončil.

Než začneme s implementáciou, je dôležité zdôrazniť, že je to primárne Zoznam a Nastaviť zbierka rozhraní sa rozširuje Zbierka ale Mapa nie.

Jednoducho povedané HashMap ukladá hodnoty podľa kľúča a poskytuje API na pridávanie, načítanie a manipuláciu s uloženými dátami rôznymi spôsobmi. Implementácia je na základe princípov hashtable, ktorý znie na začiatku trochu zložito, ale je v skutočnosti veľmi ľahko pochopiteľný.

Páry kľúč - hodnota sa ukladajú do takzvaných segmentov, ktoré spolu tvoria takzvanú tabuľku, čo je vlastne interné pole.

Keď poznáme kľúč, pod ktorým je alebo má byť objekt uložený, operácie ukladania a vyhľadávania prebiehajú v konštantnom čase, O (1) na dobre dimenzovanej hašovacej mape.

Aby sme pochopili, ako hash mapy fungujú pod kapotou, je potrebné pochopiť mechanizmus ukladania a načítania, ktorý používa HashMap. Na tieto sa veľa zameriame.

Nakoniec HashMap súvisiace otázky sú pri pohovoroch úplne bežné, takže je to solídny spôsob, ako buď pripraviť pohovor, alebo sa naň pripraviť.

2. The put () API

Na uloženie hodnoty do hashovacej mapy voláme dať API, ktoré má dva parametre; kľúč a zodpovedajúca hodnota:

V put (kľúč K, hodnota V);

Keď na mapu pridáte hodnotu pod kľúčom, znak hashCode () API kľúčového objektu sa volá na získanie tzv. Počiatočnej hodnoty hash.

Aby sme to videli v akcii, vytvorme objekt, ktorý bude slúžiť ako kľúč. Vytvoríme iba jeden atribút, ktorý použijeme ako hash kód na simuláciu prvej fázy hašovania:

public class MyKey {private int id; @Override public int hashCode () {System.out.println ("Volanie hashCode ()"); návratové ID; } // konštruktor, zakladatelia a getri}

Teraz môžeme tento objekt použiť na mapovanie hodnoty v hashovacej mape:

@Test public void whenHashCodeIsCalledOnPut_thenCorrect () {MyKey key = new MyKey (1); Mapová mapa = nová HashMap (); map.put (kľúč, "val"); }

Vo vyššie uvedenom kóde sa veľa nedeje, ale venujte pozornosť výstupu konzoly. Skutočne hashCode metóda je vyvolaná:

Volá sa hashCode ()

Ďalej hash () API hašovacej mapy sa nazýva interne na výpočet konečnej hashovacej hodnoty pomocou počiatočnej hashovacej hodnoty.

Táto konečná hodnota hash sa nakoniec scvrkáva na index v internom poli alebo na to, čo nazývame umiestnenie segmentu.

The hash funkcia HashMap vyzerá takto:

statický konečný int hash (kľúč objektu) {int h; návrat (key == null)? 0: (h = key.hashCode ()) ^ (h >>> 16); }

Tu by sme si mali všimnúť iba použitie hashovacieho kódu z kľúčového objektu na výpočet konečnej hashovacej hodnoty.

Zatiaľ čo vo vnútri dať konečná hodnota hash sa použije takto:

public V put (kľúč K, hodnota V) {return putVal (hash (kľúč), kľúč, hodnota, nepravda, pravda); }

Všimnite si, že interné putVal funkcia sa volá a ako prvý parameter sa jej dá konečná hodnota hash.

Niekto by sa mohol čudovať, prečo sa kláves opäť používa vo vnútri tejto funkcie, pretože sme ho už použili na výpočet hodnoty hash.

Dôvod je ten hash mapy ukladajú kľúč aj hodnotu v umiestnení segmentu ako a Mapa. ​​Vstup objekt.

Ako už bolo spomenuté, rozširujú sa všetky rozhrania rámca zbierok Java Zbierka rozhranie ale Mapa nie. Porovnajte deklaráciu rozhrania Map, ktorú sme videli predtým, s deklaráciou Nastaviť rozhranie:

verejné rozhranie Sada rozširuje zbierku

Dôvod je ten mapy neukladajú presne jednotlivé prvky ako iné kolekcie, ale skôr kolekciu párov kľúč - hodnota.

Takže všeobecné metódy Zbierka rozhranie ako napr pridať, toArray nedávajú zmysel, pokiaľ ide o Mapa.

Koncept, ktorému sme sa venovali v posledných troch odsekoch, predstavuje jeden z týchto textov: najobľúbenejšie otázky týkajúce sa rozhovoru s Java Collection Framework. Takže to stojí za pochopenie.

Jedným špeciálnym atribútom s hash mapou je, že akceptuje nulový hodnoty a nulové kľúče:

@Test public void givenNullKeyAndVal_whenAccepts_thenCorrect () {Mapa mapy = nový HashMap (); map.put (null, null); }

Keď sa počas a. Vyskytne nulový kľúč dať operácii, je mu automaticky priradená konečná hash hodnota 0, čo znamená, že sa stane prvým prvkom základného poľa.

To tiež znamená, že keď je kľúč nulový, nedochádza k hašovaniu a teda k hashCode API kľúča nie je vyvolané, nakoniec sa vyhne výnimke nulového ukazovateľa.

Počas a dať operácia, keď použijeme kľúč, ktorý už bol predtým použitý na uloženie hodnoty, vráti predchádzajúcu hodnotu spojenú s kľúčom:

@Test public void givenExistingKey_whenPutReturnsPrevValue_thenCorrect () {Mapa mapy = nový HashMap (); map.put ("key1", "val1"); Reťazec rtnVal = map.put ("kľúč1", "val2"); assertEquals ("val1", rtnVal); }

inak sa vráti nulový:

@Test public void givenNewKey_whenPutReturnsNull_thenCorrect () {Map map = new HashMap (); Reťazec rtnVal = map.put ("key1", "val1"); assertNull (rtnVal); }

Kedy dať vráti null, mohlo by to tiež znamenať, že predchádzajúca hodnota spojená s kľúčom je null, nie nevyhnutne to, že ide o nové mapovanie kľúč - hodnota:

@Test public void givenNullVal_whenPutReturnsNull_thenCorrect () {Map map = new HashMap (); Reťazec rtnVal = map.put ("key1", null); assertNull (rtnVal); }

The containsKey Na rozlíšenie medzi takýmito scenármi, ktoré uvidíme v nasledujúcej podkapitole, sa dá použiť API.

3. The dostať API

Na získanie objektu už uloženého v hašovacej mape musíme poznať kľúč, pod ktorým bol uložený. Voláme dostať API a odovzdajte mu kľúčový objekt:

@Test public void whenGetWorks_thenCorrect () {Map map = new HashMap (); map.put ("kľúč", "val"); Reťazec val = map.get ("kľúč"); assertEquals ("val", val); }

Interne sa používa rovnaký princíp hashovania. HashCode () API kľúčového objektu sa volá na získanie počiatočnej hodnoty hash:

@Test public void whenHashCodeIsCalledOnGet_thenCorrect () {MyKey key = new MyKey (1); Mapová mapa = nová HashMap (); map.put (kľúč, "val"); map.get (kľúč); }

Tentokrát hashCode API z MyKey sa volá dvakrát; raz pre dať a raz za dostať:

Volanie hashCode () Volanie hashCode ()

Táto hodnota sa potom znova vymyje volaním internej hash () API na získanie konečnej hodnoty hash.

Ako sme videli v predchádzajúcej časti, táto konečná hodnota hash sa nakoniec scvrkáva na umiestnenie segmentu alebo index vnútorného poľa.

Hodnotový objekt uložený na tomto mieste sa potom získa a vráti sa do volajúcej funkcie.

Keď je vrátená hodnota null, mohlo by to znamenať, že kľúčový objekt nie je spojený so žiadnou hodnotou v hash mape:

@Test public void givenUnmappedKey_whenGetReturnsNull_thenCorrect () {Mapa mapy = nový HashMap (); Reťazec rtnVal = map.get ("key1"); assertNull (rtnVal); }

Alebo to môže jednoducho znamenať, že kľúč bol explicitne namapovaný na nulovú inštanciu:

@Test public void givenNullVal_whenRetrieves_thenCorrect () {Mapa mapy = nový HashMap (); map.put ("kľúč", null); Reťazec val = map.get ("kľúč"); assertNull (val); }

Na rozlíšenie týchto dvoch scenárov môžeme použiť containsKey API, do ktorého odovzdáme kľúč a vráti true, len ak bolo pre hašovanú mapu vytvorené mapovanie pre zadaný kľúč:

@Test public void whenContainsDistinguishesNullValues_thenCorrect () {Map map = new HashMap (); Reťazec val1 = map.get ("kľúč"); boolean valPresent = map.containsKey ("kľúč"); assertNull (val1); assertFalse (valPresent); map.put ("kľúč", null); Reťazec val = map.get ("kľúč"); valPresent = map.containsKey ("kľúč"); assertNull (val); assertTrue (valPresent); }

Pre obidva prípady vo vyššie uvedenom teste je návratová hodnota parametra dostať Volanie API je nulové, ale sme schopní rozlíšiť, ktorý z nich je ktorý.

4. Zobrazenia zbierky v HashMap

HashMap ponúka tri pohľady, ktoré nám umožňujú zaobchádzať s jeho kľúčmi a hodnotami ako s ďalšou kolekciou. Môžeme dostať súbor všetkých kľúče mapy:

@Test public void givenHashMap_whenRetrievesKeyset_thenCorrect () {Mapa mapy = nový HashMap (); map.put ("meno", "baeldung"); map.put ("typ", "blog"); Nastaviť klávesy = map.keySet (); assertEquals (2, keys.size ()); assertTrue (keys.contains ("name")); assertTrue (keys.contains ("type")); }

Sada je podložená samotnou mapou. Takže akákoľvek zmena vykonaná v súprave sa prejaví na mape:

@Test public void givenKeySet_whenChangeReflectsInMap_thenCorrect () {Mapa mapy = nový HashMap (); map.put ("meno", "baeldung"); map.put ("typ", "blog"); assertEquals (2, map.size ()); Nastaviť klávesy = map.keySet (); keys.remove ("meno"); assertEquals (1, map.size ()); }

Môžeme tiež získať a pohľad na hodnoty:

@Test public void givenHashMap_whenRetrievesValues_thenCorrect () {Mapa mapy = nový HashMap (); map.put ("meno", "baeldung"); map.put ("typ", "blog"); Hodnoty zbierky = map.values ​​(); assertEquals (2, values.size ()); assertTrue (values.contains ("baeldung")); assertTrue (values.contains ("blog")); }

Rovnako ako sada kľúčov, akákoľvek zmeny vykonané v tejto kolekcii sa prejavia na podkladovej mape.

Nakoniec môžeme získať a nastavenie zobrazenia všetkých záznamov na mape:

@Test public void givenHashMap_whenRetrievesEntries_thenCorrect () {Mapa mapy = nový HashMap (); map.put ("meno", "baeldung"); map.put ("typ", "blog"); Nastaviť entries = map.entrySet (); assertEquals (2, entries.size ()); pre (Záznam e: entries)}

Pamätajte, že hash mapa konkrétne obsahuje neusporiadané prvky, preto pri testovaní kľúčov a hodnôt položiek v kóde predpokladáme akékoľvek poradie pre každý slučka.

Mnohokrát použijete zobrazenia kolekcie v slučke ako v minulom príklade a konkrétnejšie pomocou ich iterátorov.

Len nezabudnite, že iterátory pre všetky vyššie uvedené zobrazenia sú rýchlo zlyhať.

Ak na mape dôjde k akejkoľvek štrukturálnej úprave, po vytvorení iterátora bude vyvolaná výnimka súbežnej úpravy:

@Test (očakáva sa = ConcurrentModificationException.class) public void givenIterator_whenFailsFastOnModification_thenCorrect () {mapa mapy = nový HashMap (); map.put ("meno", "baeldung"); map.put ("typ", "blog"); Nastaviť klávesy = map.keySet (); Iterátor it = keys.iterator (); map.remove ("typ"); while (it.hasNext ()) {Reťazcový kľúč = it.next (); }}

Jediný povolená štrukturálna úprava je a odstrániť operácia vykonaná prostredníctvom samotného iterátora:

public void givenIterator_whenRemoveWorks_thenCorrect () {Map map = new HashMap (); map.put ("meno", "baeldung"); map.put ("typ", "blog"); Nastaviť klávesy = map.keySet (); Iterátor it = keys.iterator (); while (it.hasNext ()) {it.next (); it.remove (); } assertEquals (0, map.size ()); }

Poslednou vecou, ​​ktorú si treba pamätať o týchto zobrazeniach kolekcie, je vykonávanie iterácií. To je miesto, kde hash mapa funguje dosť zle v porovnaní s jej náprotivkami prepojenou hash mapou a stromovou mapou.

V najhoršom prípade dôjde k iterácii nad hash mapou O (n) kde n je súčet jeho kapacity a počtu záznamov.

5. Výkonnosť HashMap

Výkon hashovej mapy ovplyvňujú dva parametre: Počiatočná kapacita a Vyťaženosť. Kapacita je počet segmentov alebo dĺžka podkladového poľa a počiatočná kapacita je jednoducho kapacita počas vytvárania.

Faktor zaťaženia alebo LF je skrátka mierou toho, aká plná by mala byť hash mapa po pridaní niektorých hodnôt pred jej zmenou veľkosti.

Predvolená počiatočná kapacita je 16 a predvolený faktor zaťaženia je 0.75. Môžeme vytvoriť hashovaciu mapu s vlastnými hodnotami počiatočnej kapacity a LF:

Mapa hashMapWithCapacity = nová HashMap (32); Mapa hashMapWithCapacityAndLF = nová HashMap (32, 0,5f);

Predvolené hodnoty nastavené tímom Java sú pre väčšinu prípadov dobre optimalizované. Ak však potrebujete použiť svoje vlastné hodnoty, čo je v poriadku, musíte pochopiť dôsledky na výkon, aby ste vedeli, čo robíte.

Keď počet položiek hash mapy prekročí súčin LF a kapacity, potom omieľanie nastáva t.j. vytvorí sa ďalšie interné pole s dvojnásobnou veľkosťou ako pôvodné pole a všetky položky sa presunú do nových umiestnení segmentu v novom poli.

A nízka počiatočná kapacita znižuje náklady na priestor, ale zvyšuje frekvenciu opätovného umývania. Rehashing je samozrejme veľmi nákladný proces. Spravidla teda platí, že ak očakávate viac vstupov, mali by ste nastaviť značne vysokú počiatočnú kapacitu.

Na druhú stranu, ak nastavíte počiatočnú kapacitu príliš vysokú, zaplatíte náklady v iteračnom čase. Ako sme videli v predchádzajúcej časti.

Takže vysoká počiatočná kapacita je dobrá pre veľký počet záznamov spojená s malou alebo žiadnou iteráciou.

A nízka začiatočná kapacita je dobrá pre niekoľko záznamov s veľkou iteráciou.

6. Zrážky v HashMap

Zrážka alebo presnejšie zrážka hash kódu v a HashMap, je situácia, keď dva alebo viac kľúčových objektov produkuje rovnakú konečnú hodnotu hash a teda smerujú na rovnaké umiestnenie segmentu alebo index poľa.

Tento scenár môže nastať, pretože podľa rovná sa a hashCode zmluva, dva nerovnaké objekty v Jave môžu mať rovnaký hash kód.

Môže sa to stať aj z dôvodu konečnej veľkosti podkladového poľa, to znamená pred zmenou veľkosti. Čím menšie je toto pole, tým vyššia je pravdepodobnosť kolízie.

To znamená, že stojí za zmienku, že Java implementuje techniku ​​riešenia zrážok hash kódu, ktorú uvidíme na príklade.

Majte na pamäti, že je to hodnota hash kľúča, ktorá určuje segment, do ktorého bude objekt uložený. Takže ak dôjde k stretu hašovacích kódov akýchkoľvek dvoch kľúčov, ich záznamy budú stále uložené v rovnakom segmente.

A predvolene implementácia používa prepojený zoznam ako implementáciu segmentu.

Pôvodne konštantný čas O (1)dať a dostať operácie budú prebiehať v lineárnom čase O (n) v prípade kolízie. Je to preto, že po nájdení umiestnenia segmentu s konečnou hodnotou hash bude každý z kľúčov v tomto umiestnení porovnaný s poskytnutým kľúčovým objektom pomocou rovná sa API.

Aby sme simulovali túto techniku ​​riešenia kolízií, poďme trochu upraviť náš starší kľúčový objekt:

public class MyKey {private String name; private int id; public MyKey (int id, String name) {this.id = id; this.name = meno; } // štandardní vyhľadávači a nastavovatelia @Override public int hashCode () {System.out.println ("Volanie hashCode ()"); návratové ID; } // prepísanie toString pre pekné protokolovanie @Override verejné boolean equals (Object obj) {System.out.println ("Volanie equals () pre kľúč:" + obj); // vygenerovaná implementácia}}

Všimnite si, ako jednoducho vraciame id atribút ako hash kód - a tak vynútiť kolíziu.

Upozorňujeme tiež, že sme do nášho záznamu pridali výpisy z denníka rovná sa a hashCode implementácie - aby sme vedeli presne, kedy sa logika volá.

Poďme teraz do ukladania a načítania niektorých objektov, ktoré sa v určitom okamihu zrazia:

@Test public void whenCallsEqualsOnCollision_thenCorrect () {HashMap mapa = nový HashMap (); MyKey k1 = nový MyKey (1, "firstKey"); MyKey k2 = nový MyKey (2, "secondKey"); MyKey k3 = nový MyKey (2, "thirdKey"); System.out.println ("ukladanie hodnoty pre k1"); map.put (k1, "firstValue"); System.out.println ("ukladanie hodnoty pre k2"); map.put (k2, "secondValue"); System.out.println ("ukladanie hodnoty pre k3"); map.put (k3, "tretiahodnota"); System.out.println ("načítanie hodnoty pre k1"); Reťazec v1 = map.get (k1); System.out.println ("načítanie hodnoty pre k2"); Reťazec v2 = map.get (k2); System.out.println ("načítanie hodnoty pre k3"); Reťazec v3 = map.get (k3); assertEquals ("firstValue", v1); assertEquals ("secondValue", v2); assertEquals ("tretiahodnota", v3); }

Vo vyššie uvedenom teste vytvoríme tri rôzne kľúče - jeden má jedinečný id a ďalšie dva majú rovnaké id. Keďže používame id ako počiatočná hodnota hash, určite dôjde ku kolízii počas ukladania aj získavania údajov pomocou týchto kľúčov.

Okrem toho vďaka technike rozlíšenia kolízie, ktorú sme videli predtým, očakávame, že každá z našich uložených hodnôt bude načítaná správne, a teda tvrdenia v posledných troch riadkoch.

Keď spustíme test, mal by prejsť, čo naznačuje, že kolízie boli vyriešené, a pomocou vytvoreného protokolovania potvrdíme, že ku kolíziám skutočne došlo:

uloženie hodnoty pre k1 Volanie hashCode () uloženie hodnoty pre k2 Volanie hashCode () uloženie hodnoty pre k3 Volanie hashCode () Volanie equals () pre kľúč: MyKey [name = secondKey, id = 2] načítanie hodnoty pre k1 Volanie hashCode () načítanie hodnota pre k2 Volanie hashCode () načítanie hodnoty pre k3 Volanie hashCode () Volanie sa rovná () pre kľúč: MyKey [name = secondKey, id = 2]

Všimnite si, že počas operácií skladovania k1 a k2 boli úspešne namapované na ich hodnoty pomocou iba hash kódu.

Skladovanie však k3 nebolo také jednoduché, systém zistil, že jeho umiestnenie segmentu už obsahovalo mapovanie pre k2. Preto rovná sa na ich rozlíšenie sa použilo porovnanie a vytvoril sa prepojený zoznam, ktorý obsahuje obe mapovania.

Akékoľvek ďalšie následné mapovanie, ktorého kľúč sa zahašuje do rovnakého umiestnenia segmentu, bude nasledovať tú istú trasu a nakoniec nahradí jeden z uzlov v prepojenom zozname alebo sa pridá do čela zoznamu, ak rovná sa porovnanie vráti hodnotu false pre všetky existujúce uzly.

Rovnako tak pri vyhľadávaní k3 a k2 boli rovná sa- porovnané na identifikáciu správneho kľúča, ktorého hodnota by sa mala získať.

Na záver treba uviesť, že z Javy 8 sú prepojené zoznamy dynamicky nahradené vyváženými binárnymi vyhľadávacími stromami v rozlíšení kolízií potom, čo počet kolízií v danom umiestnení segmentu prekročí určitú hranicu.

Táto zmena ponúka zvýšenie výkonu, pretože v prípade kolízie dôjde k uloženiu a načítaniu v O (log n).

Táto časť je veľmi časté pri technických pohovoroch, najmä po základných otázkach týkajúcich sa skladovania a vyhľadávania.

7. Záver

V tomto článku sme to preskúmali HashMap implementácia Java Mapa rozhranie.

Celý zdrojový kód všetkých príkladov použitých v tomto článku nájdete v projekte GitHub.


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