streamalism.org

1. Pregled

U ovom ćemo članku istražiti najpopularniju implementaciju Karta sučelje iz Okvira Java Collections detaljnije, nastavljajući tamo gdje je naš uvodni članak stao.

Prije nego što započnemo s provedbom, važno je istaknuti da je primarni Popis i Postavi sučelja za prikupljanje se proširuju Kolekcija ali Karta ne.

Jednostavno rečeno, HashMap pohranjuje vrijednosti po ključu i pruža API-je za dodavanje, dohvaćanje i manipulaciju pohranjenim podacima na razne načine. Provedba je zasnovan na načelima hashtablea, što u početku zvuči malo složeno, ali je zapravo vrlo lako razumljivo.

Parovi ključ / vrijednost pohranjeni su u onome što je poznato kao segmenti koji zajedno čine ono što se naziva tablicom, koja je zapravo unutarnji niz.

Jednom kada saznamo ključ pod kojim se objekt čuva ili ga treba pohraniti, operacije skladištenja i pronalaženja događaju se u stalnom vremenu, O (1) u dobro dimenzioniranoj hash mapi.

Da bismo razumjeli kako hash karte rade ispod haube, treba razumjeti mehanizam za pohranu i pronalaženje koji koristi HashMap. Usredotočit ćemo se puno na ovo.

Konačno, HashMap srodna pitanja su prilično česta u intervjuima, tako da je ovo solidan način ili pripremiti intervju ili se pripremiti za njega.

2. The staviti() API

Da bismo pohranili vrijednost u hash kartu, nazivamo staviti API koji uzima dva parametra; ključ i odgovarajuća vrijednost:

V put (ključ K, vrijednost V);

Kada se na ključ doda vrijednost na ključ, hashCode () API ključnog objekta poziva se za dohvaćanje onoga što je poznato kao početna hash vrijednost.

Da bismo to vidjeli na djelu, stvorimo objekt koji će djelovati kao ključ. Stvorit ćemo samo jedan atribut koji ćemo koristiti kao hash kod za simulaciju prve faze raspršivanja:

javna klasa MyKey {private int id; @Override public int hashCode () {System.out.println ("Pozivanje hashCode ()"); return id; } // konstruktor, postavljači i dobivači}

Sada možemo koristiti ovaj objekt za mapiranje vrijednosti na hash mapi:

@Test public void whenHashCodeIsCalledOnPut_thenCorrect () {MyKey key = new MyKey (1); Karta karte = novi HashMap (); map.put (ključ, "val"); }

U gornjem kodu se ništa posebno ne događa, ali obratite pažnju na izlaz konzole. Doista hashCode metoda se poziva:

Pozivanje hashCode ()

Dalje, hash () API hash mape poziva se interno za izračunavanje konačne hash vrijednosti pomoću početne hash vrijednosti.

Ova se konačna vrijednost raspršivanja na kraju svodi na indeks u unutarnjem nizu ili na ono što nazivamo mjestom.

The hash funkcija HashMap izgleda ovako:

statički završni int hash (Object key) {int h; vratiti (ključ == null)? 0: (h = key.hashCode ()) ^ (h >>> 16); }

Ovdje bismo trebali primijetiti samo upotrebu hash koda iz ključnog objekta za izračunavanje konačne hash vrijednosti.

Dok je unutar staviti funkcija, konačna hash vrijednost koristi se ovako:

javni V put (K ključ, V vrijednost) {return putVal (hash (ključ), ključ, vrijednost, false, true); }

Primijetite da interni putVal funkcija se poziva i daje joj se konačna vrijednost raspršivanja kao prvi parametar.

Može se zapitati zašto se ključ ponovno koristi unutar ove funkcije, jer smo ga već koristili za izračunavanje hash vrijednosti.

Razlog je taj hash karte pohranjuju i ključ i vrijednost na mjesto segmenta kao Karta.Ulaz objekt.

Kao što je već spomenuto, sva sučelja okvira Java zbirki se proširuju Kolekcija sučelje ali Karta ne. Usporedite izjavu sučelja Map koju smo ranije vidjeli s izjavom Postavi sučelje:

javno sučelje Set proširuje Zbirku

Razlog je taj mape ne pohranjuju točno pojedinačne elemente kao ostale zbirke, već zbirku parova ključ / vrijednost.

Dakle, generičke metode Kolekcija sučelje poput dodati, toArray nemaju smisla kad je riječ o Karta.

Koncept koji smo obradili u posljednja tri odlomka čini jedan od najpopularnija pitanja o intervjuu za Java Collections Framework. Dakle, vrijedi razumjeti.

Poseban atribut hash mape je da prihvaća null vrijednosti i null ključevi:

@Test javna praznina givenNullKeyAndVal_whenAccepts_thenCorrect () {Map map = new HashMap (); map.put (null, null); }

Kada se tijekom a. Naiđe na null ključ staviti operaciji, automatski joj se dodjeljuje konačna hash vrijednost od 0, što znači da postaje prvi element temeljnog niza.

To također znači da kada je ključ null, nema operacije raspršivanja i stoga, hashCode API ključa se ne poziva, u konačnici izbjegavajući null iznimku pokazivača.

Tijekom a staviti operacija, kada koristimo ključ koji je već korišten za pohranu vrijednosti, vraća prethodnu vrijednost povezanu s ključem:

@Test javna praznina givenExistingKey_whenPutReturnsPrevValue_thenCorrect () {Map map = new HashMap (); map.put ("key1", "val1"); Niz rtnVal = map.put ("key1", "val2"); assertEquals ("val1", rtnVal); }

u suprotnom, vraća se null:

@Test javna praznina givenNewKey_whenPutReturnsNull_thenCorrect () {Map map = new HashMap (); Niz rtnVal = map.put ("key1", "val1"); assertNull (rtnVal); }

Kada staviti vraća nulu, to bi također moglo značiti da je prethodna vrijednost povezana s ključem null, ne nužno da je to novo mapiranje ključ / vrijednost:

@Test javna praznina givenNullVal_whenPutReturnsNull_thenCorrect () {Map map = new HashMap (); Niz rtnVal = map.put ("key1", null); assertNull (rtnVal); }

The sadržiKljuč API se može koristiti za razlikovanje takvih scenarija kao što ćemo vidjeti u sljedećem pododjeljku.

3. The dobiti API

Da bismo dohvatili objekt koji je već pohranjen na hash mapi, moramo znati ključ pod kojim je pohranjen. Mi zovemo dobiti API i proslijedite mu ključni objekt:

@Test public void whenGetWorks_thenCorrect () {Map map = new HashMap (); map.put ("ključ", "val"); Niz val = map.get ("ključ"); assertEquals ("val", val); }

Interno se koristi isti princip raspršivanja. HashCode () API ključnog objekta poziva se za dobivanje početne hash vrijednosti:

@Test public void whenHashCodeIsCalledOnGet_thenCorrect () {MyKey key = novi MyKey (1); Karta karte = novi HashMap (); map.put (ključ, "val"); map.get (ključ); }

Ovaj put, hashCode API od MyKey zove se dva puta; jednom za staviti i jednom za dobiti:

Pozivanje hashCode () Pozivanje hashCode ()

Ta se vrijednost zatim preispituje pozivanjem internog hash () API za dobivanje konačne hash vrijednosti.

Kao što smo vidjeli u prethodnom odjeljku, ova se konačna vrijednost raspršivanja na kraju svodi na mjesto segmenta ili indeks unutarnjeg niza.

Vrijednosni objekt pohranjen na tom mjestu tada se dohvaća i vraća funkciji pozivanja.

Kada je vraćena vrijednost null, to bi moglo značiti da objekt ključa nije povezan s bilo kojom vrijednošću na hash mapi:

@Test javna praznina givenUnmappedKey_whenGetReturnsNull_thenCorrect () {Map map = new HashMap (); Niz rtnVal = map.get ("key1"); assertNull (rtnVal); }

Ili to može jednostavno značiti da je ključ izričito mapiran na null instancu:

@Test javna praznina givenNullVal_whenRetrieves_thenCorrect () {Map map = new HashMap (); map.put ("ključ", null); Niz val = map.get ("ključ"); assertNull (val); }

Da bismo razlikovali dva scenarija, možemo koristiti sadržiKljuč API, kojem prosljeđujemo ključ i on vraća vrijednost true ako i samo ako je za navedeni ključ u hash mapi stvoreno mapiranje:

@Test public void whenContainsDistinguishesNullValues_thenCorrect () {Map map = new HashMap (); Niz val1 = map.get ("ključ"); boolean valPresent = map.containsKey ("ključ"); assertNull (val1); assertFalse (valPresent); map.put ("ključ", null); Niz val = map.get ("ključ"); valPresent = map.containsKey ("ključ"); assertNull (val); assertTrue (valPresent); }

Za oba slučaja u gornjem testu, povratna vrijednost dobiti API poziv nije valjan, ali možemo razlikovati koji je koji.

4. Pogledi zbirke u HashMap

HashMap nudi tri pogleda koji nam omogućuju da se prema njegovim ključevima i vrijednostima odnosimo kao prema drugoj zbirci. Možemo dobiti set svih tipke karte:

@Test javna praznina givenHashMap_whenRetrievesKeyset_thenCorrect () {Map map = new HashMap (); map.put ("ime", "baeldung"); map.put ("vrsta", "blog"); Postavi tipke = map.keySet (); assertEquals (2, keys.size ()); assertTrue (keys.contens ("name")); assertTrue (keys.contens ("type")); }

Uz set stoji i sama karta. Tako svaka promjena u skupu odražava se na karti:

@Test javna praznina givenKeySet_whenChangeReflectsInMap_thenCorrect () {Map map = new HashMap (); map.put ("ime", "baeldung"); map.put ("vrsta", "blog"); assertEquals (2, map.size ()); Postavi tipke = map.keySet (); keys.remove ("ime"); assertEquals (1, map.size ()); }

Također možemo dobiti i zbirni prikaz vrijednosti:

@Test javna praznina givenHashMap_whenRetrievesValues_thenCorrect () {Map map = new HashMap (); map.put ("ime", "baeldung"); map.put ("vrsta", "blog"); Vrijednosti zbirke = map.values ​​(); assertEquals (2, values.size ()); assertTrue (values.contens ("baeldung")); assertTrue (values.contens ("blog")); }

Baš kao i set ključeva, bilo koji promjene napravljene u ovoj zbirci odrazit će se na osnovnoj karti.

Napokon, možemo dobiti a postavljeni prikaz svih unosa na karti:

@Test javna praznina givenHashMap_whenRetrievesEntries_thenCorrect () {Map map = new HashMap (); map.put ("ime", "baeldung"); map.put ("vrsta", "blog"); Postavi unosi = map.entrySet (); assertEquals (2, entries.size ()); za (Unos e: unosi)}

Imajte na umu da hash karta posebno sadrži neuređene elemente, stoga pretpostavljamo bilo koji redoslijed prilikom testiranja ključeva i vrijednosti unosa u za svakoga petlja.

Mnogo ćete puta upotrijebiti prikaze kolekcije u petlji kao u prošlom primjeru, točnije koristeći njihove iteratore.

Sjetite se samo da iteratori za sve gore navedene poglede su neuspješan.

Ako se na karti izvrši bilo kakva strukturna izmjena, nakon stvaranja iteratora izbacit će se istodobna iznimka izmjene:

@Test (očekuje se = ConcurrentModificationException.class) javna praznina givenIterator_whenFailsFastOnModification_thenCorrect () {Map map = new HashMap (); map.put ("ime", "baeldung"); map.put ("vrsta", "blog"); Postavi tipke = map.keySet (); Iterator it = keys.iterator (); map.remove ("vrsta"); while (it.hasNext ()) {String key = it.next (); }}

Jedini dopuštena strukturna preinaka je a ukloniti operacija izvedena kroz sam iterator:

javna praznina givenIterator_whenRemoveWorks_thenCorrect () {Map map = new HashMap (); map.put ("ime", "baeldung"); map.put ("vrsta", "blog"); Postavi tipke = map.keySet (); Iterator it = keys.iterator (); while (it.hasNext ()) {it.next (); it.remove (); } assertEquals (0, map.size ()); }

Konačno što treba zapamtiti kod ovih prikaza zbirke je izvođenje iteracija. Ovdje se hash karta prilično loše izvodi u usporedbi s povezanom hash mapom i mapom stabla.

Iteracija nad hash mapom događa se u najgorem slučaju Na) gdje je n zbroj njegovog kapaciteta i broja ulazaka.

5. Izvedba HashMap-a

Na izvedbu hash mape utječu dva parametra: Početni kapacitet i Faktor opterećenja. Kapacitet je broj kašika ili duljina temeljnog polja, a početni kapacitet je jednostavno kapacitet tijekom stvaranja.

Faktor opterećenja ili LF, ukratko, mjera je koliko puna mora biti hash karta nakon dodavanja nekih vrijednosti prije nego što se promijeni.

Zadani početni kapacitet je 16 a zadani faktor opterećenja je 0.75. Možemo stvoriti hash kartu s prilagođenim vrijednostima za početni kapacitet i LF:

Karta hashMapWithCapacity = nova HashMap (32); Karta hashMapWithCapacityAndLF = nova HashMap (32, 0.5f);

Zadane vrijednosti koje je postavio Java tim dobro su optimizirane za većinu slučajeva. Međutim, ako trebate koristiti vlastite vrijednosti, što je vrlo u redu, morate razumjeti implikacije izvedbe kako biste znali što radite.

Kada broj unosa hash mape premaši umnožak LF i kapaciteta, tada rehashing javlja se tj. kreira se drugi unutarnji niz dvostruko veće veličine od početnog i svi se unosi premještaju na nova mjesta segmenta u novom polju.

A nizak početni kapacitet smanjuje troškove prostora ali povećava učestalost ponavljanja. Preispitivanje je očito vrlo skup postupak. Dakle, u pravilu, ako predviđate mnogo unosa, trebali biste postaviti znatno visoki početni kapacitet.

S druge strane, ako početni kapacitet postavite previsoko, platit ćete trošak u vremenu ponavljanja. Kao što smo vidjeli u prethodnom odjeljku.

Tako visoki početni kapacitet dobar je za velik broj unosa zajedno s malo ili nimalo ponavljanja.

A nizak početni kapacitet dobar je za nekoliko unosa s puno ponavljanja.

6. Sudari u HashMap

Sudar, ili preciznije, kolizija hash koda u a HashMap, je situacija u kojoj dva ili više ključnih objekata daju istu konačnu hash vrijednost i stoga upućuju na isto mjesto segmenta ili indeks niza.

Ovaj se scenarij može dogoditi jer prema jednako i hashCode ugovor, dva nejednaka objekta u Javi mogu imati isti hash kôd.

To se može dogoditi i zbog konačne veličine osnovnog niza, odnosno prije promjene veličine. Što je ovaj niz manji, to su veće šanse za sudar.

Međutim, vrijedi spomenuti da Java implementira tehniku ​​razrješenja sudara hash koda što ćemo vidjeti na primjeru.

Imajte na umu da je hash vrijednost ključa ta koja određuje segment u kojem će objekt biti pohranjen. Dakle, ako se hashi kodovi bilo koje dvije tipke sudare, njihovi će unosi i dalje biti pohranjeni u istom segmentu.

I prema zadanim postavkama, implementacija koristi povezani popis kao segmentnu implementaciju.

U početku konstantno vrijeme O (1)staviti i dobiti operacije će se događati u linearnom vremenu Na) u slučaju sudara. To je zato što će se nakon pronalaska mjesta segmenta s konačnom vrijednošću raspršivanja svaki od ključeva na ovom mjestu usporediti s navedenim objektom ključa pomoću jednako API.

Da bismo simulirali ovu tehniku ​​rješavanja sudara, izmijenimo malo naš raniji ključni objekt:

javna klasa MyKey {naziv privatnog niza; privatni int id; javni MyKey (int id, naziv niza) {this.id = id; this.name = ime; } // standardni getteri i postavljači @Override public int hashCode () {System.out.println ("Pozivanje hashCode ()"); return id; } // nadjačavanje toString za prilično bilježenje @Override javno logičko jednako (Objekt obj) {System.out.println ("Pozivanje jednako () za ključ:" + obj); // generirana implementacija}}

Primijetite kako jednostavno vraćamo iskaznica atribut kao hash kôd - i tako prisiliti na sudar.

Također, imajte na umu da smo u naš dodali izjave dnevnika jednako i hashCode implementacije - kako bismo točno znali kada se poziva logika.

Ajmo sada pohraniti i dohvatiti neke predmete koji se u nekom trenutku sudare:

@Test public void whenCallsEqualsOnCollision_thenCorrect () {HashMap map = new HashMap (); MyKey k1 = novi MyKey (1, "firstKey"); MyKey k2 = novi MyKey (2, "secondKey"); MyKey k3 = novi MyKey (2, "thirdKey"); System.out.println ("pohrana vrijednosti za k1"); map.put (k1, "firstValue"); System.out.println ("pohrana vrijednosti za k2"); map.put (k2, "secondValue"); System.out.println ("pohrana vrijednosti za k3"); map.put (k3, "thirdValue"); System.out.println ("dohvaćanje vrijednosti za k1"); Niz v1 = map.get (k1); System.out.println ("dohvaćanje vrijednosti za k2"); Niz v2 = map.get (k2); System.out.println ("dohvaćanje vrijednosti za k3"); Niz v3 = map.get (k3); assertEquals ("firstValue", v1); assertEquals ("secondValue", v2); assertEquals ("thirdValue", v3); }

U gore navedenom testu kreiramo tri različita ključa - jedan ima jedinstveni iskaznica a ostale dvije imaju isto iskaznica. Budući da koristimo iskaznica kao početna hash vrijednost, sigurno će doći do sudara tijekom pohrane i pretraživanja podataka s ovim ključevima.

Uz to, zahvaljujući tehnici razrješenja sudara koju smo ranije vidjeli, očekujemo da će svaka naša pohranjena vrijednost biti ispravno dohvaćena, otud i tvrdnje u posljednja tri retka.

Kada pokrenemo test, trebao bi proći, pokazujući da su sudari riješeni, a upotrijebljenom evidencijom ćemo potvrditi da su se sudari zaista dogodili:

spremanje vrijednosti za k1 Pozivanje hashCode () spremanje vrijednosti za k2 Pozivanje hashCode () spremanje vrijednosti za k3 Pozivanje hashCode () Pozivanje jednako () za ključ: MyKey [name = secondKey, id = 2] dohvaćanje vrijednosti za k1 Pozivanje hashCode () dohvaćanje vrijednost za k2 Pozivanje hashCode () dohvaćanje vrijednosti za k3 Pozivanje hashCode () Pozivanje jednako () za ključ: MyKey [name = secondKey, id = 2]

Primijetite da tijekom pohrane, k1 i k2 su uspješno mapirani na njihove vrijednosti koristeći samo hash kôd.

Međutim, pohrana k3 nije bilo tako jednostavno, sustav je otkrio da njegovo mjesto u segmentu već sadrži mapiranje za k2. Stoga, jednako za njihovo razlikovanje korištena je usporedba i stvoren je povezani popis koji sadrži oba preslikavanja.

Svako drugo naknadno mapiranje čiji se ključ raspršuje na isto mjesto segmenta slijedit će istu rutu i na kraju će zamijeniti jedan od čvorova na povezanom popisu ili će biti dodano u glavu popisa ako jednako usporedba vraća false za sve postojeće čvorove.

Isto tako, tijekom pronalaska, k3 i k2 bili jednako-u usporedbi s identificiranjem ispravnog ključa čija bi vrijednost trebala biti dohvaćena.

Na kraju, iz Java 8, povezani se popisi dinamički zamjenjuju uravnoteženim binarnim stablima pretraživanja u razlučivosti sudara nakon što broj sudara na danom mjestu segmenta prijeđe određeni prag.

Ova promjena nudi poboljšanje performansi, jer se u slučaju sudara, pohrana i pronalaženje događaju u O (log n).

Ovaj odjeljak je vrlo često u tehničkim intervjuima, posebno nakon osnovnih pitanja o pohrani i pronalaženju.

7. Zaključak

U ovom smo članku istražili HashMap implementacija Jave Karta sučelje.

Potpuni izvorni kod za sve primjere korištene u ovom članku možete pronaći u projektu GitHub.