13 izabranih Java HashMap intervju pitanja👍

Chenmo Wang Er1834 reči6 minuta

Za Java kandidate koji traže posao, HashMap je apsolutno najvažnija tema i obavezan deo svakog intervjua. Međutim, HashMap ima mnogo tačaka znanja, pa je za ponavljanje potrebno mnogo truda.

01. Koja je osnovna struktura podataka HashMap-e?

U JDK 7, HashMap se sastoji od „niza + povezane liste"; niz je glavni deo HashMap-e, dok povezana lista prvenstveno služi za rešavanje heš konflikata.

U JDK 8, HashMap se sastoji od „niza + povezane liste + crveno-crnog stabla". Preduga povezana lista ozbiljno utiče na performanse HashMap-e, dok je vremenska složenost pretrage crveno-crnog stabla O(logn), za razliku od loše O(n) složenosti povezane liste. Stoga je JDK 8 dodatno optimizovao strukturu podataka uvođenjem crveno-crnog stabla; povezana lista i crveno-crno stablo se konvertuju pod određenim uslovima:

Kada povezana lista pređe 8, a ukupna količina podataka pređe 64, pretvara se u crveno-crno stablo.
Pre konverzije povezane liste u crveno-crno stablo, proverava se: ako je dužina trenutnog niza manja od 64, tada će se prvo izabrati proširenje niza (resize), umesto konverzije u crveno-crno stablo, radi smanjenja vremena pretrage.

Dužina povezane liste veća od 8 ogleda se u ovom delu koda u metodi putVal:

// ako je dužina povezane liste veća od 8, konvertuje se u crveno-crno stablo
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

Dužina table 64 ogleda se u ovom delu koda u metodi treeifyBin:

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
}

Vrednost MIN_TREEIFY_CAPACITY je tačno 64.

static final int MIN_TREEIFY_CAPACITY = 64;

Šema strukture HashMap-e u JDK 8:

02. Zašto je prag za konverziju povezane liste u crveno-crno stablo baš 8?

Zbog Poasonove distribucije; pogledajte komentar autora u izvornom kodu:

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) pow(0.5, k) / factorial(k)). The first values are: 0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million

U prevodu, grubo rečeno: u idealnom slučaju, pri korišćenju nasumičnih heš kodova, raspodela čvorova po heš baketu prati Poasonovu distribuciju; na osnovu formule Poasonove distribucije izračunata je tabela odnosa između broja elemenata u baketu i verovatnoće — može se videti da je verovatnoća da povezana lista ima 8 elemenata veoma mala, a za više od toga još manja. Zato je originalni autor za broj elemenata povezane liste izabrao 8, na osnovu statistike verovatnoće.

03. Koje metode postoje za rešavanje heš konflikata? Koju koristi HashMap?

Metode za rešavanje heš konflikata su:

Metoda otvorenog adresiranja: naziva se i re-heširanje; osnovna ideja je da ako p=H(key) dođe do konflikta, onda se uz p kao osnova ponovo hešira, p1=H(p); ako p1 ponovo dođe do konflikta, uzima se p1 kao osnova i tako dalje, dok se ne pronađe heš adresa bez konflikta pi. Zato metoda otvorenog adresiranja zahteva da dužina heš tabele bude veća ili jednaka broju elemenata koje treba uskladištiti; a pošto postoji re-heširanje, na obrisanim čvorovima se samo stavlja oznaka i ne mogu se stvarno obrisati.
Metoda ponovnog heširanja: dvostruko heširanje, višestruko heširanje; pruža više različitih heš funkcija; kada R1=H1(key1) dođe do konflikta, ponovo se izračunava R2=H2(key1), i tako sve dok nema konflikta. Iako se na ovaj način ređe stvaraju gomile, povećava se vreme računanja.
Metoda lančanih adresa (separate chaining): povezana lista; elementi sa istom heš vrednošću čine jednu povezanu listu sinonima, a pokazivač na početak te povezane liste čuva se u i-toj jedinici heš tabele; pretraga, umetanje i brisanje se uglavnom odvijaju unutar liste sinonima. Metoda povezane liste je pogodna za slučajeve kada se čsto umeće i briše.
Uvođenje zajedničkog preliva (overflow area): heš tabela se deli na osnovnu i prelivnu; kada dođe do preliv a, svi prelivni podaci se smeštaju u zonu preliva.

HashMap koristi metodu lančanih adresa.

04. Zašto se pri rešavanju heš konflikata ne koristi odmah crveno-crno stablo? Zašto se prvo bira povezana lista, pa tek onda konverzija u crveno-crno stablo?

Zato što crveno-crno stablo mora da izvodi levo i desno rotiranje i promenu boja kako bi održalo balans, dok to nije potrebno kod jednostruko povezane liste.

Kada je broj elemenata manji od 8, za operaciju upita struktura povezane liste već može da garantuje performanse upita. Kada je broj elemenata veći od 8, složenost pretrage crveno-crnog stabla je O(logn), dok je povezana lista O(n); tada je potrebno crveno-crno stablo da ubrza pretragu, ali je efikasnost dodavanja novih čvorova sporija.

Prema tome, ako bi se odmah krenulo sa crveno-crnim stablom, sa malim brojem elemenata i sporijim dodavanjem, to bi sigurno bilo rasipanje performansi.

05. Koja je podrazumevana vrednost faktora opterećenja u HashMap-i? Zašto je 0.75, a ne 0.6 ili 0.8?

Kao opšte pravilo, podrazumevani faktor opterećenja (0.75) pruža dobar kompromis između troškova vremena i prostora.

Detalje pogledajte ovde

06. Kako se u HashMap-i izračunava indeks za čuvanje ključa (key)?

Prvo se na osnovu vrednosti ključa izračuna vrednost hashcode-a, zatim se na osnovu hashcode-a izračuna hash vrednost, i konačno se operacijom hash & (length-1) dobija pozicija za čuvanje.

Detalje pogledajte ovde

07. Zašto JDK 8 radi XOR hashcode-a sa vrednošću pomeranja udesno za šesnaest bitova?

Pošto se u JDK 7 heširanje ponavljalo 4 puta, performanse izračunavanja hash vrednosti bile su nešto slabije.

Sa aspekta brzine, efikasnosti i kvaliteta, JDK 8 je optimizovao algoritam za operacije nad višim bitovima, putem XOR-a gornjih 16 bitova hashCode() sa donjih 16 bitova: (h = k.hashCode()) ^ (h >>> 16).

Na taj način, čak i kada je dužina niza table relativno mala, može se garantovati da i viši i niži bitovi učestvuju u izračunavanju heša, bez prevelikog dodatnog troška.

08. Zašto se hash vrednost AND-uje sa length-1?

Modulo operacija hash vrednosti po dužini niza je skupa; modulo operacija je znatno sporija od operacije nad bitovima.
Kada je length uvek stepen dvojke, operacija h & (length-1) je ekvivalentna modulo operaciji po length, odnosno h%length, ali & ima veću efikasnost nego %.

09. Zašto dužina niza HashMap-e mora biti stepen dvojke?

Stepen dvojke pomaže u smanjenju verovatnoće kolizije. Ako je length stepen dvojke, tada length-1 u binarnom obliku nužno ima oblik 11111..., što operaciju AND sa binarnim oblikom h čini veoma brzom i pritom neće rasipati prostor. Navedimo primer, pogledajte sliku:

Kada je length=15, rezultat za 6 i 7 je isti, što znači da je njihova pozicija u table ista — dakle dolazi do kolizije; 6 i 7 će na istoj poziciji formirati povezanu listu; rezultat za 4 i 5 je takođe isti, što dovodi do smanjenja brzine upita.

Ako detaljnije analiziramo, otkrićemo i ogromno rasipanje prostora: sa length=15, na pozicijama 1, 3, 5, 7, 9, 11, 13, 15 neće biti podataka. Jer kada se hash vrednost AND-uje sa 14 (odnosno 1110), rezultat u poslednjem bitu uvek iznosi 0, što znači da na pozicijama 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111 nije moguće čuvati podatke.

Još jedna mala tajna u izračunavanju kapaciteta niza.

Konstruktor HashMap-e dozvoljava korisniku da prosledi kapacitet koji nije stepen dvojke, jer ga automatski može pretvoriti u stepen dvojke. Kao početni kapacitet niza table uzima se najbliži stepen dvojke koji je veći ili jednak toj vrednosti, pomoću metode tableSizeFor(int). Na primer, tableSizeFor(10) = 16 (2 na 4.), tableSizeFor(20) = 32 (2 na 5.), što znači da je dužina niza table uvek stepen dvojke. JDK 8 izvorni kod:

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

Svrha oduzimanja 1 od cap i dodeljivanja n je da ciljna vrednost bude veća ili jednaka originalnoj. Na primer, binarni oblik 1000 predstavlja decimalni broj 8. Ako se ne oduzme 1 i odmah se primeni operacija, dobićemo rezultat 10000, odnosno 16. Očigledno, to nije pravi rezultat. Posle oduzimanja 1, binarni oblik je 111, a nakon operacija ćemo dobiti originalnu vrednost 1000, odnosno 8.

10. Tok metode put u HashMap-i?

Uzevši JDK 8 kao primer, kratak tok je sledeći:

Prvo se na osnovu vrednosti ključa izračuna hash vrednost i pronađe indeks u nizu na kojem se taj element čuva;
Ako je niz prazan, poziva se resize radi inicijalizacije;
Ako nema heš konflikta, stavlja se direktno na odgovarajući indeks u nizu;
Ako postoji konflikt i ključ već postoji, value se prepisuje;
Ako nakon konflikta ispadne da je taj čvor crveno-crno stablo, ovaj čvor se kači na stablo;
Ako nakon konflikta ispadne da je u pitanju povezana lista, proverava se da li je lista duža od 8; ako jeste, a kapacitet niza je manji od 64, radi se resize; ako lista ima više od 8 čvorova, a kapacitet niza je veći od 64, ova struktura se konvertuje u crveno-crno stablo; inače, par ključ-vrednost se umeće u listu, a ako ključ postoji, prepisuje se value.

11. Kako se vrši resize (proširenje) HashMap-e?

Kada HashMap pređe kapacitet definisan faktorom opterećenja, vrši proširenje.

Detalje pogledajte ovde

12. Šta se obično koristi kao ključ (key) HashMap-e?

Obično se kao ključ HashMap-e koriste immutable klase poput Integer i String, pri čemu je String najčešći.

Pošto su stringovi nepromenljivi, njihov hashcode se kešira već pri kreiranju i ne mora ponovo da se izračunava.
Pošto se pri dohvatanju objekta koriste metode equals() i hashCode(), veoma je važno da ključni objekat pravilno redefiniše ove dve metode. Integer, String i slične klase su već standardno korektno redefinisale hashCode() i equals() metode.

13. Zašto HashMap nije bezbedna za niti (thread-safe)?

U JDK 7, resize pod više niti mogao je da izazove beskonačnu petlju.
Operacija put pod više niti može dovesti do gubitka elemenata.
Pri istovremenom put i get, get može vratiti null.

Detalje pogledajte ovde

Referentni link:https://zhuanlan.zhihu.com/p/362214327