Java HashMap detaljno: analiza izvornog koda, princip hash, mehanizam proširenja, faktor opterećenja, nitna nesigurnost

Ovaj članak će temeljno i jasno objasniti Java HashMap, uključujući princip hash metode, mehanizam proširenja HashMap, zašto je faktor opterećenja HashMap 0.75 umesto 0.6 ili 0.8, i zašto HashMap nije bezbedan za niti. U suštini, sva česta pitanja sa intervjua o HashMap biće objašnjena u ovom jednom članku.

HashMap je jedna od najčešće korišćenih struktura podataka u Javi, namenjena za čuvanje parova ključ-vrednost. U HashMap, svaki ključ se mapira na jedinstvenu vrednost, i pomoću ključa se može brzo pristupiti odgovarajućoj vrednosti, pri čemu vremenska složenost algoritma može dostići O(1).

HashMap se ne samo često koristi u svakodnevnom razvoju, već je i ključni predmet provere na intervjuima.

Evo jednostavnog primera dodavanja, brisanja, izmene i pretrage u HashMap:

1) Dodavanje elementa:

Da biste dodali par ključ-vrednost (element) u HashMap, možete koristiti metodu put(). Na primer, dodajte ime i godine kao par ključ-vrednost u HashMap:

HashMap<String, Integer> map = new HashMap<>();
map.put("Chenmo", 20);
map.put("Wang Er", 25);

2) Brisanje elementa:

Da biste obrisali par ključ-vrednost iz HashMap, možete koristiti metodu remove(). Na primer, obrišite par ključ-vrednost čiji je ključ ime "Chenmo":

map.remove("Chenmo");

3) Izmena elementa:

Da biste izmenili par ključ-vrednost u HashMap, možete koristiti metodu put(). Na primer, promenite godine za ime "Chenmo" u 30:

map.put("Chenmo", 30);

Zašto je metoda ista kao za dodavanje elementa? To ćemo objasniti kasnije; ukratko, razlog je što su ključevi u HashMap jedinstveni, pa će ponovno put() prepisati prethodni par ključ-vrednost.

4) Pretraga elementa:

Da biste pronašli vrednost koja odgovara ključu u HashMap, možete koristiti metodu get(). Na primer, pronađite godine za ime "Chenmo":

int age = map.get("Chenmo");

U praksi, HashMap se može koristiti za keširanje, indeksiranje i slične scenarije. Na primer, korisnički ID može biti ključ, a podaci o korisniku vrednost, pri čemu se podaci o korisniku keširaju u HashMap radi brze pretrage. Ili, ključna reč može biti ključ, a lista ID-ova dokumenata vrednost, čime se indeks dokumenata kešira u HashMap radi brze pretrage dokumenata.

Princip implementacije HashMap se zasniva na hash tabeli; njegova osnova je niz, a svaka pozicija u nizu može biti povezana lista ili crveno-crno stablo, ali takođe može biti samo jedan par ključ-vrednost (biće objašnjeno kasnije). Kada se doda par ključ-vrednost, HashMap na osnovu hash vrednosti ključa izračunava indeks (poziciju) u nizu koji odgovara tom ključu, a zatim umeće par ključ-vrednost na odgovarajuću poziciju.

Prilikom traženja vrednosti putem ključa, HashMap takođe izračunava indeks niza na osnovu hash vrednosti ključa i pronalazi odgovarajuću vrednost.

01. Princip hash metode

Nakon kratkog upoznavanja sa HashMap, razmotrimo prvo pitanje: princip hash metode, koji će vam mnogo pomoći da duboko razumete HashMap.

Pogledajmo izvorni kod hash metode (HashMap u JDK 8):

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Zašta zapravo služi ovaj kod?

Za obradu hashCode vrednosti ključa kako bi se dobila konačna hash vrednost.

Kako ovo razumeti? Ne žurite.

Napravimo novi HashMap i dodajmo jedan element preko metode put.

HashMap<String, String> map = new HashMap<>();
map.put("chenmo", "Chenmo");

Pogledajmo izvorni kod metode put.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

Vidite li hash metodu?

Uloga hash metode

Kao što je već rečeno, osnova HashMap se implementira preko niza, a početna veličina je 16 (biće objašnjeno kasnije), zapamtite to za sada.

To znači da HashMap prilikom dodavanja prvog elementa mora pomoću hash koda ključa odrediti poziciju (indeks) u nizu veličine 16. Kako se to određuje?

Da bih vam olakšao intuitivno shvatanje, ovde sam nacrtao sliku sa 16 kvadrata (zamislite ih kao kofe), gde svaki kvadrat ima svoj broj koji odgovara indeksu niza veličine 16.

Sada želimo da smestimo par ključ-vrednost sa ključem "chenmo" i vrednošću "Chenmo" u jedan od tih 16 kvadrata.

Kako odrediti poziciju (indeks)?

Prvo ću vam reći zaključak: preko ove operacije I (n - 1) & hash, gde je promenljiva n dužina niza, a promenljiva hash rezultat dobijen metodom hash().

Koja je pozicija (indeks) ključa "chenmo" nakon izračunavanja?

Odgovor je 8, što znači da će map.put("chenmo", "Chenmo") smestiti par ključ-vrednost sa ključem "chenmo" i vrednošću "Chenmo" na poziciju sa indeksom 8 (odnosno u kofu sa indeksom 8).

Tako ćete steći opšti utisak o tome kako HashMap čuva parove ključ-vrednost (elemente). Jedna važna stvar je da hash metoda ima ključnu ulogu u izračunavanju pozicije para ključ-vrednost.

Vratimo se hash metodi:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Evo nekoliko objašnjenja za ovu metodu:

• Parametar key: ključ za koji treba izračunati hash kod.
• key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16): ovo je ternarni operator; ako je ključ null, hash kod je 0 (što znači da se ključ null čuva na prvoj poziciji); inače se pozivanjem metode hashCode() dobija hash kod ključa i XOR-uje se sa svojom vrednošću pomerenojom udesno za 16 bitova.
• Operator ^: operator ekskluzivne ILI (XOR) je bitni operator u Javi koji upoređuje binarne bitove dva broja — ako su jednaki rezultat je 0, a ako su različiti rezultat je 1.
• h >>> 16: pomeranje hash koda udesno za 16 bitova, što je ekvivalentno tome da se originalni hash kod podeli u dva 16-bitna dela.
• Konačno se vraća hash kod dobijen nakon XOR operacije.

Ova jedna kratka linija koda sadrži mnogo genijalnosti velikana računarstva.

Teorijski, hash vrednost (hash kod) je tip int, u opsegu od -2147483648 do 2147483648.

Zajedno to daje oko 4 milijarde prostora za mapiranje; sve dok se hash vrednosti mapiraju ravnomerno i retko,Hash kolizije se obično ne javljaju (hash konflikti smanjuju efikasnost HashMap).

Ali problem je u tome što niz dužine 4 milijarde ne može stati u memoriju. Početna veličina niza HashMap pre proširenja je samo 16, pa se ta hash vrednost ne može direktno koristiti; pre upotrebe mora se izvršiti I operacija sa dužinom niza (pomenuto (n - 1) & hash, negde se naziva operacija po modulu, negde operacija ostatka), pa se dobijena vrednost koristi za pristup indeksu niza.

Operacija po modulu VS operacija ostatka VS I operacija

Ovde ćemo usput dodati nekoliko ključnih pojmova o operaciji po modulu/ostatku i I operaciji.

Operacija po modulu (Modulo Operation) i operacija ostatka (Remainder Operation) su, strogo gledano, dve različite operacije, i njihova implementacija u računaru je takođe različita.

U Javi se obično koristi operator % za ostatak, dok se Math.floorMod() koristi za modulo.

• Kada su oba operanda pozitivni, rezultat operacije po modulu i operacije ostatka je isti.
• Razlika u rezultatima se javlja samo kada se pojave negativni brojevi među operandima.
• Količnik operacije po modulu teži ka negativnoj beskonačnosti; količnik operacije ostatka teži ka 0. Ovo je osnovni razlog za razliku u rezultatima kada se obrade negativni brojevi.
• Kada je dužina niza 2 na n, ili n-ti stepen, ili ceo broj puta n, operacija po modulu/ostatku se može zameniti bitovnom operacijom, što je efikasnije, jer računar na kraju razume samo binarni zapis.

Pogledajmo jedan konkretan primer.

int a = -7;
int b = 3;

// a ostatak pri deljenju sa b
int remainder = a % b;
// a po modulu b
int modulus = Math.floorMod(a, b);

System.out.println("Brojevi: a = " + a + ", b = " + b);
System.out.println("Ostatak (%): " + remainder);
System.out.println("Modulo (Math.floorMod): " + modulus);

// Promenimo znakove a i b
a = 7;
b = -3;

remainder = a % b;
modulus = Math.floorMod(a, b);

System.out.println("\nBrojevi: a = " + a + ", b = " + b);
System.out.println("Ostatak (%): " + remainder);
System.out.println("Modulo (Math.floorMod): " + modulus);

Rezultat izvršenja je sledeći:

Brojevi: a = -7, b = 3
Ostatak (%): -1
Modulo (Math.floorMod): 2

Brojevi: a = 7, b = -3
Ostatak (%): 1
Modulo (Math.floorMod): -2

Zašto su rezultati ovakvi?

Prvo, razmislimo o običnom deljenju. Kada podelimo jedan broj sa drugim, dobijamo količnik i ostatak.

Na primer, kada 7 podelimo sa 3, dobijamo količnik 2 i ostatak 1, jer je (7 = 3 × 2 + 1).

Preporučeno čitanje: Java modulo i ostatak

01. Ostatak:

Definicija ostatka se zasniva na običnom deljenju, pa je njen znak uvek isti kao znak deljenika. Količnik teži ka 0.

Na primer, za -7 % 3, ostatak je -1. Jer -7 / 3 može dati dva rezultata: količnik -2 i ostatak -1; ili količnik -3 i ostatak 2, zar ne?

Pošto količnik ostatka teži ka 0, a -2 je bliže 0 od -3, rezultat ostatka je -1.

02. Modulo:

I modulo se zasniva na deljenju, ali njen znak je uvek isti kao znak deljenika (délioca). Količnik teži ka negativnoj beskonačnosti.

Na primer, za Math.floorMod(-7, 3), rezultat je 2. Iz istog razloga, -7 / 3 može dati dva rezultata: količnik -2 i ostatak -1; ili količnik -3 i ostatak 2, zar ne?

Pošto količnik modula teži ka negativnoj beskonačnosti, a -3 je bliže negativnoj beskonačnosti od -2, rezultat modula je 2.

Treba napomenuti da, bilo da je modulo ili ostatak u pitanju, delilac ne može biti 0, jer su i modulo i ostatak zasnovani na operaciji deljenja.

03. I operacija:

Kada su i delilac i deljenik pozitivni, rezultat operacije po modulu i operacije ostatka je isti.

Na primer, 7 ostatak pri deljenju sa 3 i 7 po modulu 3 oba daju rezultat 1. Jer su oba zasnovana na deljenju, a 7 / 3 ima količnik 2 i ostatak 1.

Zato ćemo na mnogim mestima videti: ostatak je isto što i modulo, modulo je isto što i ostatak. Ovo je netačan iskaz, koji važi samo pod pretpostavkom da su svi operandi pozitivni.

Za HashMap, on mora da odredi poziciju elementa u nizu preko hash % table.length, što u velikoj meri omogućava ravnomernu raspodelu elemenata u nizu.

Na primer, ako je dužina niza 3, a hash 7, onda je 7 % 3 jednako 1, što znači da se element može smestiti na poziciju sa indeksom 1.

Kada je hash 8, 8 % 3 jednako je 2, pa se element može smestiti na poziciju sa indeksom 2.

Kada je hash 9, 9 % 3 jednako je 0, pa se element može smestiti na poziciju sa indeksom 0.

Zar nije divno? Dužina niza je 3, i sva tri mesta su iskorišćena.

Zašto onda HashMap prilikom izračunavanja indeksa ne koristi direktno operaciju ostatka (ili operaciju po modulu), već koristi bitovnu I operaciju &?

Zato što kada je dužina niza 2 na n, važi hash & (length - 1) = hash % length.

Na primer, 9 % 4 = 1; binarni zapis od 9 je 1001, 4 - 1 = 3, binarni zapis od 3 je 0011, pa je 9 & 3 = 1001 & 0011 = 0001 = 1.

Ili, 10 % 4 = 2; binarni zapis od 10 je 1010, 4 - 1 = 3, binarni zapis od 3 je 0011, pa je 10 & 3 = 1010 & 0011 = 0010 = 2.

Kada dužina niza nije stepen dvojke, rezultati hash % length i hash & (length - 1) se ne poklapaju.

Na primer, 7 % 3 = 1; binarni zapis od 7 je 0111, 3 - 1 = 2, binarni zapis od 2 je 0010, pa je 7 & 2 = 0111 & 0010 = 0010 = 2.

Zašto je to tako?

Jer iz binarnog ugla, hash / length = hash / $2^n$ = hash >> n, odnosno pomeranje hash udesno za n bitova, čime se dobija količnik hash / $2^n$.

Pomeranjem uklonjeni deo je upravo hash % $2^n$, odnosno ostatak.

$2^n$ u binarnom zapisu je 1 praćeno sa nula, pa je binarni zapis od $2^n$ - 1 sastavljen od n jedinica. Na primer, 8 = $2^3$, binarni zapis 1000, 7 = $2^3$ - 1, binarni zapis 0111.

Operacija hash % length nalazi ostatak pri deljenju hash sa $2^n$. U binarnom sistemu, rezultat ove operacije je vrednost najnižih n bitova u binarnom zapisu hash.

Jer u operaciji modula sa $2^n$, sve vrednosti bitova iznad $2^n$ ne doprinose rezultatu; samo deo ispod tog praga određuje ostatak.

Na primer, binarni zapis od 26 je 11010; da bismo izračunali 26 % 8, 8 je $2^3$, pa nas zanimaju najniža 3 bita binarnog zapisa od 26: najniža 3 bita od 11010 su 010.

010 u decimalnom zapisu je 2, pa je rezultat 26 % 8 jednak 2.

Prilikom izvršavanja hash & (length - 1), zapravo se zadržavaju najniža n bita binarnog zapisa hash, dok se sve više pozicije postavljaju na nulu.

I operacija: u oba operanda, bit mora biti 1 da bi rezultat bio 1, inače je 0.

Na primer, neka je hash 14, a n 3, odnosno dužina niza je $2^3$, što je 8.

  1110 (hash = 14)
& 0111 (length - 1 = 7)
  ----
  0110 (rezultat = 6)

Zadržavaju se najniža 3 bita od 14, dok se viši bitovi brišu.

Tako su dve operacije hash % length i hash & (length - 1) dobile savršeno poklapanje. U računaru je brzina bitovne operacije znatno veća od operacije ostatka, jer je računar u suštini binarni.

HashMap ima dva mesta gde se koristi operacija po modulu.

Jedno mesto je prilikom put u HashMap (poziva se privatna metoda putVal):

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // niz
    HashMap.Node<K,V>[] tab;
    // element
    HashMap.Node<K,V> p;

    // n je dužina niza, i je indeks
    int n, i;
    // kada je niz prazan
    if ((tab = table) == null || (n = tab.length) == 0)
        // dužina niza nakon prvog proširenja
        n = (tab = resize()).length;
    // izračunava poziciju umetanja čvora; ako je pozicija prazna, kreira novi čvor i umeće ga
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
}

Gde je (n - 1) & hash operacija po modulu; zašto se ne koristi %, objasnićemo ubrzo.

Drugo mesto je prilikom get iz HashMap (poziva se metoda getNode):

final Node<K,V> getNode(int hash, Object key) {
    // uzima trenutni niz i dužinu, i prvi čvor liste čvorova (nalazi se direktno iz niza prema indeksu)
    Node<K,V>[] tab;
    Node<K,V> first, e;
    int n;
    K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        // ako je prvi čvor upravo onaj koji tražimo, vraća se direktno
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // ako prvi čvor nije traženi, prelazi se na pretragu liste čvorova
        if ((e = first.next) != null) {
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // ako u listi čvorova nije pronađen odgovarajući čvor, vraća se null
    return null;
}

Vidite li? Operacija po modulu (n - 1) & hash se ponovo pojavljuje; jednostavno rečeno, hash kod ključa se izračunava metodom hash(), a zatim se vrši I operacija sa (dužina niza - 1).

Operacija po modulu % i bitovna operacija &

Možda se pitate: zar operacija po modulu ne bi trebalo da koristi %? Zašto koristiti bitovnu operaciju &?

Zato što je & operacija efikasnija od %, a kada je b stepen dvojke, važi sledeća formula.

a % b = a & (b-1)

Zamenimo b sa $2^n$:

a % $2^n$ = a & ($2^n$-1)

Proverimo; neka je a = 14, b = 8, odnosno $2^3$, n=3.

14%8 (ostatak je 6).

Binarni zapis od 14 je 1110, binarni zapis od 8 je 1000, 8-1 = 7, binarni zapis od 7 je 0111, pa je 1110&0111=0110, odnosno 0*$2^0$+1*$2^1$+1*$2^2$+0*$2^3$=0+2+4+0=6, što se poklapa sa 14%8 = 6.

Pa, računar je jednostavno toliko logičan, nema pomoći, 😝

Ovo takođe savršeno objašnjava zašto dužina niza HashMap mora biti stepen dvojke.

Zašto je toliko zgodno?

Jer (dužina niza - 1) deluje kao "maska niskih bitova" — najbolje je da niski bitovi ove maske budu sve jedinice, jer tada I operacija ima smisla; inače bi rezultat sigurno bio 0.

Rezultat a&b je: na odgovarajućoj poziciji, ako su i u a i u b bitovi 1, rezultat je 1, inače je 0. Na primer, 5&3=1; binarni zapis od 5 je 0101, binarni zapis od 3 je 0011, pa je 5&3=0001=1.

Stepen dvojke je paran broj, parni broj minus 1 je neparan, a binarni zapis neparnog broja se završava jedinicom, što osigurava da poslednji bit rezultata hash & (length-1) može biti i 0 i 1 (zavisi od vrednosti hash), odnosno da rezultat & operacije može biti paran ili neparan — čime se osigurava ravnomerna raspodela hash vrednosti.

Drugim rečima, rezultat & operacije postavlja sve visoke bitove hash vrednosti na nulu, zadržavajući samo niske.

Pretpostavimo da je binarni zapis neke hash vrednosti 10100101 11000100 00100101; koristimo ga za & operaciju i pogledajmo rezultat.

Znamo da je početna dužina HashMap 16, 16-1=15, a binarni zapis je 00000000 00000000 00001111 (viši bitovi se popunjavaju nulama):

	 10100101 11000100 00100101
&	 00000000 00000000 00001111
----------------------------------
	 00000000 00000000 00000101

Pošto su svi viši bitovi od 15 jednaki 0, rezultat & operacije na višim pozicijama sigurno je 0, pa preostaju samo 4 niska bita 0101, što je 5 u decimalnom zapisu.

Tako će ključ sa hash vrednošću 10100101 11000100 00100101 biti smešten na peti položaj u nizu.

Naravno, ako ste početnik i vam ovi nizovi 0 i 1 nisu jasni, nije problem. Zapamtite samo da je & operacija namenjena izračunavanju indeksa niza.

• Prilikom put se izračunava indeks, pa se par ključ-vrednost smešta u odgovarajuću kofu.
• Prilikom get se preko indeksa uzima par ključ-vrednost iz odgovarajuće kofe.

Zašto se pre operacije po modulu poziva hash metoda?

Pogledajte sledeću sliku.

Neka je hash vrednost 11111111 11111111 11110000 1110 1010; pomeranjem udesno za 16 bitova (h >>> 16) dobija se tačno 00000000 00000000 11111111 11111111, a zatim se XOR operacijom (h ^ (h >>> 16)) dobija rezultat 11111111 11111111 00001111 00010101.

Operacija ekskluzivne ILI (^) je bitovna operacija zasnovana na binarnom zapisu, označava se simbolom XOR ili ^, i pravilo joj je: ista vrednost daje 0, različita vrednost daje 1.

Pošto su pomešani viši i niži bitovi originalne hash vrednosti, povećana je slučajnost nižih bitova (umešane su neke karakteristike viših bitova, pa su i informacije iz viših bitova sačuvane).

Zatim se sa dužinom niza minus 1 (00000000 00000000 00000000 00001111) vrši operacija po modulu, pa je dobijeni indeks 00000000 00000000 00000000 00000101, odnosno 5.

Sećate li se hash vrednosti 10100101 11000100 00100101 koju smo pretpostavili ranije? Pre poziva hash metode, rezultat & operacije sa 15 je takođe bio 5; pogledajmo sada koliki je rezultat operacije po modulu nakon poziva hash metode.

Hash vrednost 00000000 10100101 11000100 00100101 (popunjeno na 32 bita), pomerena udesno za 16 bitova (h >>> 16), daje 00000000 00000000 00000000 10100101, a zatim se XOR operacijom (h ^ (h >>> 16)) dobija rezultat 00000000 10100101 00111011 10000000.

Zatim se sa dužinom niza minus 1 (00000000 00000000 00000000 00001111) vrši operacija po modulu, pa je dobijeni indeks 00000000 00000000 00000000 00000000, odnosno 0.

Ukratko, hash metoda služi za optimizaciju hash vrednosti: pomeranjem hash vrednosti udesno za 16 bitova, što je tačno polovina njene dužine, a zatim XORovanjem sa originalnom hash vrednošću, mešaju se visoki i niski bitovi originalne hash vrednosti, čime se povećava slučajnost.

Drugim rečima, hash metoda služi da poveća slučajnost, čime se elementi podataka ravnomernije raspoređuju i smanjuje broj kolizija.

Ovde sam napisao test kod: pretpostavimo da je kapacitet HashMap 16 (kao nakon prvog proširenja), ubacio sam pet parova ključ-vrednost i pogledajmo hash vrednosti ključeva (hash kodove izračunate metodom hash()) i indekse (nakon operacije po modulu).

HashMap<String, String> map = new HashMap<>();
map.put("chenmo", "Chenmo");
map.put("wanger", "Wang Er");
map.put("chenqingyang", "Chen Qingyang");
map.put("xiaozhuanling", "Xiao Zhuanling");
map.put("fangxiaowan", "Fang Xiaowan");

// Prolazak kroz HashMap
for (String key : map.keySet()) {
    int h, n = 16;
    int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    int i = (n - 1) & hash;
    // Štampa hash vrednost ključa i indeks i
    System.out.println(key + " hash vrednost : " + hash +" indeks : " + i);
}

Rezultat izvršenja je sledeći:

xiaozhuanling hash vrednost : 14597045 indeks : 5
fangxiaowan hash vrednost : -392727066 indeks : 6
chenmo hash vrednost : -1361556696 indeks : 8
chenqingyang hash vrednost : -613818743 indeks : 9
wanger hash vrednost : -795084437 indeks : 11

To znači da u ovom trenutku još uvek nije došlo do hash kolizije, indeksi su prilično ravnomerno raspoređeni — 5, 6, 8, 9, 11 — a veliki deo zasluge za to pripada hash metodi.

Rezime

Glavna uloga hash metode je da obradi hashCode vrednost ključa i dobije konačnu hash vrednost. Pošto hashCode vrednost ključa nije unapred određena, mogu se javiti hash kolizije, pa je hash vrednost potrebno mapirati odgovarajućim algoritmom na stvarnu poziciju za čuvanje u HashMap.

Princip hash metode je da prvo dobije hashCode vrednost objekta ključa, a zatim izvrši XOR operaciju između njenih viših i nižih bitova, čime se dobija nova hash vrednost. Zašto XOR operacija? Zato što su viši i niži bitovi hashCode prilično ravnomerno raspoređeni; ako bi se samo sabirali ili vršila neka druga bitovna operacija, lako bi došlo do kolizije, dok XOR operacija to izbegava.

Zatim se nova hash vrednost uzima po modulu (mod) kako bi se dobila stvarna pozicija za čuvanje. Svrha ove operacije modula je da mapira hash vrednost na indeks kofe (Bucket); kofa je niz u HashMap, a svaka kofa čuva povezanu listu (ili crveno-crno stablo) koja sadrži parove ključ-vrednost sa istom hash vrednošću (ako nema istih hash vrednosti, čuva se samo jedan par ključ-vrednost).

Ukratko, hash metoda HashMap obrađuje hashCode vrednost objekta ključa, dobija konačnu hash vrednost i zatim je pomoću određenog algoritma mapira na stvarnu poziciju za čuvanje. Ovaj proces određuje efikasnost pretrage parova ključ-vrednost unutar HashMap.

02. Mehanizam proširenja HashMap

Dobro, nakon što smo razumeli hash metodu, pređimo na drugo pitanje: mehanizam proširenja HashMap.

Svi znaju da se veličina niza, jednom kada se inicijalizuje, ne može promeniti, pa je zato nastao ArrayList kao "dinamički niz" koji se automatski može proširiti.

I HashMap za osnovu koristi niz. Kada se u HashMap neprestano dodaju elementi, a niz više ne može da primi nove elemente, potrebno je proširiti niz kako bi se smestilo još elemenata; osim toga, povećanje kapaciteta donekle poboljšava i efikasnost pretrage, jer ima još "kofa (rupa)", pa elementi koji su pre morali da se čuvaju u povezanoj listi (prilikom pretrage je potrebno prolaziti kroz listu) nakon proširenja možda dobiju svoju "rupu" (i mogu se pronaći direktno).

Pogledajmo primer; kapacitet postavimo na 16:

HashMap<String, String> map = new HashMap<>();
map.put("chenmo", "Chenmo");
map.put("wanger", "Wang Er");
map.put("chenqingyang", "Chen Qingyang");
map.put("xiaozhuanling", "Xiao Zhuanling");
map.put("fangxiaowan", "Fang Xiaowan");
map.put("yexin", "Ye Xin");
map.put("liuting","Liu Ting");
map.put("yaoxiaojuan","Yao Xiaojuan");

// Prolazak kroz HashMap
for (String key : map.keySet()) {
    int h, n = 16;
    int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    int i = (n - 1) & hash;
    // Štampa hash vrednost ključa i indeks i
    System.out.println(key + " hash vrednost : " + hash +" indeks : " + i);
}

Pogledajmo rezultat:

liuting hash vrednost : 183821170 indeks : 2
xiaozhuanling hash vrednost : 14597045 indeks : 5
fangxiaowan hash vrednost : -392727066 indeks : 6
yaoxiaojuan hash vrednost : 1231568918 indeks : 6
chenmo hash vrednost : -1361556696 indeks : 8
chenqingyang hash vrednost : -613818743 indeks : 9
yexin hash vrednost : 114873289 indeks : 9
wanger hash vrednost : -795084437 indeks : 11

Vidite li?

• indeksi za fangxiaowan (Fang Xiaowan) i yaoxiaojuan (Yao Xiaojuan) su oba 6;
• indeksi za chenqingyang (Chen Qingyang) i yexin (Ye Xin) su oba 9.

To znači da se mora koristiti metoda razdvajanja (biće objašnjena kasnije) kako bi se smestili u povezane liste pod istim indeksom. Pri pretrazi se ne može direktno doći do njih preko indeksa (vremenska složenost O(1)), već se mora prolaziti kroz listu (vremenska složenost O(n)).

Šta ako se dužina niza proširi sa 16 na 32?

Dovoljno je promeniti n iz prethodnog primera iz 16 u 32 i dobićemo sledeće rezultate:

liuting hash vrednost : 183821170 indeks : 18
xiaozhuanling hash vrednost : 14597045 indeks : 21
fangxiaowan hash vrednost : -392727066 indeks : 6
yaoxiaojuan hash vrednost : 1231568918 indeks : 22
chenmo hash vrednost : -1361556696 indeks : 8
chenqingyang hash vrednost : -613818743 indeks : 9
yexin hash vrednost : 114873289 indeks : 9
wanger hash vrednost : -795084437 indeks : 11

Vidi se da:

• iako su indeksi za chenqingyang (Chen Qingyang) i yexin (Ye Xin) i dalje 9;
• fangxiaowan (Fang Xiaowan) ima indeks 6, dok se indeks za yaoxiaojuan (Yao Xiaojuan) promenio sa 6 na 22 — sada svaki ima svoju rupu.

Naravno, niz ne može sam da se proširi, pa je za proširenje potrebno napraviti novi, veći niz, kopirati elemente iz starog manjeg niza, ponovo izračunati hash vrednosti i preraspodeliti kofe (ponovno raspršivanje). Ovaj proces prilično je vremenski zahtevan.

resize metoda

Proširenje HashMap se ostvaruje preko resize metode; JDK 8 je ugradio crveno-crno stablo (kada dužina liste pređe 8, lista se pretvara u crveno-crno stablo radi povećanja efikasnosti pretrage), što za početnike može biti teško za razumevanje.

Da bismo vam olakšali učenje, koristićemo izvorni kod iz JDK 7; kada razjasnite JDK 7, JDK 8 će biti mnogo lakši.

Pogledajmo izvorni kod resize metode u Java 7, sa mojim komentarima:

// newCapacity je novi kapacitet
void resize(int newCapacity) {
    // mali niz, privremeno za prelazak
    Entry[] oldTable = table;
    // kapacitet pre proširenja
    int oldCapacity = oldTable.length;
    // MAXIMUM_CAPACITY je maksimalni kapacitet, 2 na 30 = 1<<30
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // kapacitet se podešava na maksimalnu vrednost Integer 0x7fffffff (heksadecimalno) = 2 na 31 - 1
        threshold = Integer.MAX_VALUE;
        return;
    }

    // inicijalizuje se novi niz (veliki kapacitet)
    Entry[] newTable = new Entry[newCapacity];
    // elementi malog niza se prebacuju u veliki niz
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // referenca na novi veliki niz
    table = newTable;
    // ponovo se izračunava prag
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

Ova metoda prima novi kapacitet newCapacity, a zatim proširuje kapacitet HashMap na newCapacity.

Prvo, metoda dobija trenutni stari niz oldTable HashMap i stari kapacitet oldCapacity. Ako je stari kapacitet već dostigao maksimalni kapacitet MAXIMUM_CAPACITY koji HashMap podržava (2 na 30), novi prag threshold se podešava na Integer.MAX_VALUE (2 na 31 - 1), jer kapacitet HashMap ne može preći MAXIMUM_CAPACITY.

Jer 2.147.483.647 (Integer.MAX_VALUE) - 1.073.741.824 (MAXIMUM_CAPACITY) = 1.073.741.823, što je tačno polovina (HashMap se pri svakom proširenju udvostručuje).

Zatim metoda kreira novi niz newTable i prebacuje elemente iz starog niza oldTable u novi niz newTable. Proces prebacivanja se ostvaruje pozivom transfer metode. Ta metoda prolazi kroz svaku kofu starog niza, ponovo izračunava hash vrednost parova ključ-vrednost u svakoj kofi i umeće ih u odgovarajuću kofu novog niza.

Nakon završenog prebacivanja, metoda usmerava internu referencu niza table HashMap na novi niz newTable i ponovo izračunava prag threshold. Novi prag je rezultat množenja novog kapaciteta newCapacity sa faktorom opterećenja loadFactor, ali ako rezultat prekoračuje maksimalni kapacitet MAXIMUM_CAPACITY koji HashMap podržava, prag se postavlja na MAXIMUM_CAPACITY + 1, jer broj elemenata HashMap ne može preći MAXIMUM_CAPACITY.

Novi kapacitet newCapacity

Kako se izračunava newCapacity?

int newCapacity = oldCapacity * 2;
if (newCapacity < 0 || newCapacity >= MAXIMUM_CAPACITY) {
    newCapacity = MAXIMUM_CAPACITY;
} else if (newCapacity < DEFAULT_INITIAL_CAPACITY) {
    newCapacity = DEFAULT_INITIAL_CAPACITY;
}

Novi kapacitet newCapacity se inicijalizuje na dvostruku vrednost originalnog kapaciteta oldCapacity. Zatim, ako newCapacity prekoračuje ograničenje MAXIMUM_CAPACITY (2^30), newCapacity se postavlja na MAXIMUM_CAPACITY. Ako je newCapacity manji od podrazumevanog početnog kapaciteta DEFAULT_INITIAL_CAPACITY (16), newCapacity se postavlja na DEFAULT_INITIAL_CAPACITY. Time se izbegava da novi kapacitet bude previše mali ili previše veliki, što bi dovelo do previše kolizija ili rasipanja prostora.

U Java 8 način izračunavanja newCapacity se neznatno promenio.

int newCapacity = oldCapacity << 1;
if (newCapacity >= DEFAULT_INITIAL_CAPACITY && oldCapacity >= DEFAULT_INITIAL_CAPACITY) {
    if (newCapacity > MAXIMUM_CAPACITY)
        newCapacity = MAXIMUM_CAPACITY;
} else {
    if (newCapacity < DEFAULT_INITIAL_CAPACITY)
        newCapacity = DEFAULT_INITIAL_CAPACITY;
}

Obratite pažnju, oldCapacity * 2 je postalo oldCapacity << 1, pojavilo se levo pomeranje (<<); evo kratkog objašnjenja:

a=39
b = a << 2

Decimalni 39 predstavljen binarno sa 8 bitova je 00100111; nakon pomeranja ulevo za dva mesta dobija se 10011100 (niži bitovi se popunjavaju nulama), što u decimalnom zapisu iznosi 156.

Operacija pomeranja se obično može koristiti umesto množenja i deljenja. Na primer, pomeranjem 0010011 (39) ulevo za dva mesta dobija se 10011100 (156), što je tačno četiri puta veća vrednost.

Zapravo, binarni broj pomeranjem ulevo postaje 2, 4, 8 puta veći — zapamtite to.

transfer metoda

Dalje, da kažemo nešto o transfer metodi; ona služi za prebacivanje — kopira elemente starog malog niza u novi veliki niz.

void transfer(Entry[] newTable, boolean rehash) {
    // novi kapacitet
    int newCapacity = newTable.length;
    // prolazak kroz mali niz
    for (Entry<K,V> e : table) {
        while(null != e) {
            // metoda razdvajanja, različite vrednosti za isti ključ
            Entry<K,V> next = e.next;
            // da li je potrebno ponovo izračunati hash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // na osnovu kapaciteta velikog niza i hash vrednosti ključa izračunava se indeks elementa u nizu
            int i = indexFor(e.hash, newCapacity);

            // novi elementi na istoj poziciji se stavljaju na početak liste
            e.next = newTable[i];

            // smeštanje u novi niz
            newTable[i] = e;

            // sledeći element u listi
            e = next;
        }
    }
}

Ova metoda prima novi Entry niz newTable i boolean vrednost rehash kao argumente; newTable predstavlja novu hash tabelu, a rehash označava da li je potrebno ponovo izračunati hash vrednost ključa.

U metodi se prvo dobija dužina nove hash tabele (niza) newCapacity, a zatim se prolazi kroz svaki Entry stare hash tabele. Za svaki Entry se metodom razdvajanja čuvaju različite vrednosti value sa istim key u istoj listi. Ako je rehash true, potrebno je ponovo izračunati hash vrednost ključa i smestiti je u hash svojstvo Entry-ja.

Zatim se, na osnovu dužine nove hash tabele i hash vrednosti ključa, izračunava pozicija i Entry-ja u novom nizu, a zatim se taj Entry dodaje na poziciju i novog niza. Pošto novi element mora biti na početku liste, sledeći element novog elementa se postavlja na trenutni element na toj poziciji niza.

Konačno, nakon prolaska kroz sve elemente stare hash tabele, prebacivanje je završeno i nova hash tabela newTable već sadrži sve elemente stare hash tabele.

Metoda razdvajanja

Obratite pažnju na e.next = newTable[i], što znači da se koristi način umetanja na početak jednostruko povezane liste — novi elementi na istoj poziciji uvek se stavljaju na početak liste; tako elementi koji su pre ubačeni na neki indeks na kraju završavaju na kraju liste, što dovodi do toga da elementi sa iste liste u starom nizu, nakon ponovnog izračunavanja indeksa, mogu završiti na različitim pozicijama novog niza.

Da bi se rešio ovaj problem, Java 8 je uvela veliku optimizaciju (biće objašnjeno u delu o proširenju).

Proširenje u Java 8

Izvorni kod proširenja u JDK 8:

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // uzima originalni niz table
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // uzima dužinu niza oldCap
    int oldThr = threshold; // uzima prag oldThr
    int newCap, newThr = 0;
    if (oldCap > 0) { // ako originalni niz table nije prazan
        if (oldCap >= MAXIMUM_CAPACITY) { // preko maksimuma se više ne proširuje, neka se kolizije dešavaju
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // nije preko maksimuma, proširuje se na dvostruko
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // duplira se prag
    }
    else if (oldThr > 0) // početni kapacitet je befrio smešten u prag
        newCap = oldThr;
    else { // prag od nula znači korišćenje podrazumevanih vrednosti
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // izračunavanje nove gornje granice resize
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // novi prag se dodeljuje članu threshold
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // kreira se novi niz newTab
    table = newTab; // novi niz newTab se dodeljuje članu table
    if (oldTab != null) { // ako stari niz oldTab nije prazan
        for (int j = 0; j < oldCap; ++j) { // prolazi se kroz svaki element starog niza
            Node<K,V> e;
            if ((e = oldTab[j]) != null) { // ako element nije prazan
                oldTab[j] = null; // element na toj poziciji u starom nizu se postavlja na null radi sakupljanja smeća
                if (e.next == null) // ako element nema kolizije
                    newTab[e.hash & (newCap - 1)] = e; // direktno se smešta u novi niz
                else if (e instanceof TreeNode) // ako je element čvor stabla
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // taj čvor stabla se deli u dve liste
                else { // ako je element lista
                    Node<K,V> loHead = null, loTail = null; // glava i rep liste niskih
                    Node<K,V> hiHead = null, hiTail = null; // glava i rep liste visokih
                    Node<K,V> next;
                    do { // prolazi se kroz listu
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { // ako je element u listi niskih
                            if (loTail == null) // ako lista niskih još uvek nema čvorove
                                loHead = e; // element postaje glava liste niskih
                            else
                                loTail.next = e; // ako lista niskih već ima čvorove, element se dodaje na kraj
                            loTail = e; // ažurira se rep liste niskih
                        }
                        else { // ako je element u listi visokih
                            if (hiTail == null) // ako lista visokih još uvek nema čvorove
                                hiHead = e; // element postaje glava liste visokih
                            else
                                hiTail.next = e; // ako lista visokih već ima čvorove, element se dodaje na kraj
                            hiTail = e; // ažurira se rep liste visokih
                        }
                    } while ((e = next) != null); //
                    if (loTail != null) { // ako lista niskih nije prazna
                        loTail.next = null; // rep liste niskih se postavlja na null radi sakupljanja smeća
                        newTab[j] = loHead; // lista niskih postaje element na odgovarajućoj poziciji novog niza
                    }
                    if (hiTail != null) { // ako lista visokih nije prazna
                        hiTail.next = null; // rep liste visokih se postavlja na null radi sakupljanja smeća
                        newTab[j + oldCap] = hiHead; // lista visokih postaje element na odgovarajućoj poziciji novog niza
                    }
                }
            }
        }
    }
    return newTab; // vraća se novi niz
}

1. Dobija se originalni niz table, dužina niza oldCap i prag oldThr.

2. Ako originalni niz table nije prazan, na osnovu pravila proširenja izračunavaju se nova dužina niza newCap i novi prag newThr, a zatim se elementi iz originalnog niza kopiraju u novi niz.

3. Ako je originalni niz table prazan, ali prag oldThr nije nula, to znači da je HashMap kreiran konstruktorom sa parametrima; tada prag postaje nova dužina niza newCap.

4. Ako su i originalni niz table i prag oldThr jednaki nuli, to znači da je HashMap kreiran konstruktorom bez parametara; tada se na osnovu podrazumevanog početnog kapaciteta DEFAULT_INITIAL_CAPACITY (16) i podrazumevanog faktora opterećenja DEFAULT_LOAD_FACTOR (0.75) izračunavaju nova dužina niza newCap i novi prag newThr.

5. Izračunava se novi prag threshold i dodeljuje članu threshold.

6. Kreira se novi niz newTab i dodeljuje članu table.

7. Ako stari niz oldTab nije prazan, prolazi se kroz svaki element starog niza i kopira u novi niz.

8. Vraća se novi niz newTab.

U JDK 7, kod za lociranje pozicije elementa izgleda ovako:

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

To je zapravo ekvivalentno uzimanju hash vrednosti ključa po modulu veličine niza, odnosno hashCode % table.length.

Pretpostavimo sada:

• dužina niza table je 2;
• hash vrednosti ključeva su 3, 7 i 5.

Nakon operacije po modulu, ključevi su došli u koliziju i svi su na table[1]. Pre proširenja situacija izgleda ovako.

Kapacitet niza je 2, elementi sa ključevima 3, 7, 5 nalaze se na table[1], pa je za rešavanje kolizije potrebno koristiti metodu razdvajanja.

Pretpostavimo da je faktor opterećenja loadFactor 1, što znači da se proširenje vrši kada broj elemenata postane veći od dužine table.

Kapacitet niza nakon proširenja je 4.

• ključ 3 po modulu (3%4) daje 3, smešta se na table[3];
• ključ 7 po modulu (7%4) daje 3, smešta se na početak liste na table[3];
• ključ 5 po modulu (5%4) daje 1, smešta se na table[1].

7 je završio ispred 3, jer JDK 7 koristi umetanje na početak.

e.next = newTable[i];

Istovremeno, 5 nakon proširenja završava na poziciji sa indeksom 1.

Najbolji slučaj bi bio da je 7 nakon proširenja iza 3, a 5 iza 7, čime bi se zadržao originalni redosled.

JDK 8 je potpuno promenio ovu situaciju, jer je hash algoritam optimizovan; kada je dužina niza stepen dvojke, veoma elegantno rešava problem iz JDK 7.

Kod proširenja u JDK 8 izgleda ovako:

Node<K,V>[] newTab = new Node[newCapacity];
for (int j = 0; j < oldTab.length; j++) {
    Node<K,V> e = oldTab[j];
    if (e != null) {
        int hash = e.hash;
        int newIndex = hash & (newCapacity - 1); // izračunava poziciju u novom nizu
        // čvor se pomera na odgovarajuću poziciju novog niza
        newTab[newIndex] = e;
    }
}

Način izračunavanja novog indeksa je hash & (newCapacity - 1), što nije bitno drugačije od h & (length-1) iz JDK 7; razlika je uglavnom u hash metodi. JDK 8 je ovakav:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Radi se XORovanje 32-bitne hash vrednosti koju vraća hashCode() ključa sa rezultatom njenog nepredznačenog pomeranja udesno za 16 bitova.

JDK 7 je ovakav:

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Ako primenimo JDK 8 hash algoritam za izračunavanje hash vrednosti, otkrićemo nešto zanimljivo.

Pretpostavimo da je dužina niza pre proširenja 16 (n-1 je binarno 0000 1111, 1X$2^0$+1X$2^1$+1X$2^2$+1X$2^3$=1+2+4+8=15), key1 je 5 (binarno 0000 0101), a key2 je 21 (binarno 0001 0101).

• key1 sa n-1 posle & operacije daje 0000 0101, što je 5;
• key2 sa n-1 posle & operacije daje 0000 0101, što je 5.
• Sada je nastupila kolizija koja se rešava metodom razdvajanja.

Sada se HashMap proširuje; kapacitet je duplo veći, odnosno 32 (n-1 je binarno 0001 1111, 1X$2^0$+1X$2^1$+1X$2^2$+1X$2^3$+1X$2^4$=1+2+4+8+16=31).

• key1 sa n-1 posle & operacije daje 0000 0101, što je 5;
• key2 sa n-1 posle & operacije daje 0001 0101, što je 21=5+16, odnosno pozicija u nizu pre proširenja + dužina originalnog niza.

Zar nije sjajno?

Sanfen E: promena pozicije pri proširenju

To znači da se pod novim hash algoritmom JDK 8, indeks pozicije nakon proširenja niza nalazi ili na originalnoj poziciji, ili na "originalni indeks + originalni kapacitet", po određenom pravilu.

Sanfen E: migracija čvorova pri proširenju

Naravno, ova zasluga pripada i novom hash algoritmu i pretpostavci da je n stepen dvojke; to je rezultat njihove zajedničke saradnje hash & (newCapacity - 1).

Rezime

Kada u HashMap neprestano dodajemo elemente, HashMap automatski vrši proširenje (uslov je da broj elemenata dostigne proizvod faktora opterećenja (load factor) i dužine niza), kako broj sačuvanih elemenata ne bi prešao kapacitet.

Prilikom proširenja HashMap prvo udvostručuje dužinu niza, a zatim prethodne elemente ponovo raspršuje u novi niz.

Pošto se pozicija elementa dobija & operacijom hash ključa i dužine niza, nakon povećanja dužine niza doći će do izvesnih promena u pozicijama elemenata. Jedan deo indeksa ostaje isti, dok drugi deo postaje "originalni indeks + stari kapacitet".

03. Zašto je faktor opterećenja 0.75

Prethodno pitanje je pomenuo faktor opterećenja (ili faktor punjenja); u ovom pitanju ćemo razmotriti zašto je faktor opterećenja 0.75 umesto 0.6 ili 0.8.

Znamo da je HashMap implementiran preko niza + povezane liste/crveno-crnog stabla; kada želimo da dodamo ili uzmemo podatak (element/par ključ-vrednost) iz HashMap, moramo odrediti indeks podataka u nizu.

Prvo se na ključ podataka primenjuje jedan hash:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Zatim se jedna operacija po modulu radi da se odredi indeks:

i = (n - 1) & hash

Ovaj proces lako može dovesti do dva problema:

• ako je kapacitet niza premali, indeksi dobijeni nakon hash izračunavanja livo dolaze u koliziju;
• ako je kapacitet niza prevelik, iskorišćenost prostora je niska.

Faktor opterećenja se koristi da izrazi stepen popunjenosti HashMap podacima:

faktor opterećenja = broj podataka unetih u hash tabelu / dužina hash tabele

To znači da:

• što je faktor opterećenja manji, unetih podataka je manje i verovatnoća kolizije se smanjuje, ali se prostor rasipa, a povećava se i verovatnoća okidanja proširenja;
• što je faktor opterećenja veći, unetih podataka je više, iskorišćenost prostora je veća, ali raste i verovatnoća kolizije.

Baš je teško!!!!

Zato je potrebno napraviti kompromis između "kolizije" i "iskorišćenosti prostora", te održavati ravnotežu koliko god je moguće, tako da jedno ne smeta drugom.

Znamo da HashMap koristi metodu razdvajanja za rešavanje kolizija.

Da bi se smanjila verovatnoća pojave kolizija, kada dužina niza HashMap dostigne kritičnu vrednost, okida se proširenje; nakon proširenja elementi iz starog malog niza se prebacuju u veliki niz, što je prilično vremenski zahtevna operacija.

Čime se određuje ova kritična vrednost?

kritična vrednost = početni kapacitet * faktor opterećenja

Na početku je kapacitet HashMap 16:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

Faktor opterećenja je 0.75:

static final float DEFAULT_LOAD_FACTOR = 0.75f;

To znači da će se pri 16*0.75=12 okinuti mehanizam proširenja.

Zašto se za faktor opterećenja bira 0.75? Zašto ne 0.8 ili 0.6?

To je povezano sa jednim važnim principom iz statistike — Poasonovom raspodelom.

Vreme je za Vikipediju:

Poasonova raspodela je diskretna raspodela verovatnoće koja se često sreće u statistici i teoriji verovatnoće, a koju je 1838. godine postavio francuski matematičar Siméon Denis Poisson. Ona modeluje broj pojavljivanja slučajnih događaja i pogodna je za primene koje uključuju brojanje slučajnih događaja u zadatom vremenskom periodu, rastojanju, površini itd.

Nastavnik Ruan Yifeng je u jednom članku detaljno opisao Poasonovu i eksponencijalnu raspodelu, možete je pročitati.

Veza: https://www.ruanyifeng.com/blog/2015/06/poisson-distribution.html

Konkretno, predstavlja se sledećom formulom.

Sa leve strane znaka jednakosti, P označava verovatnoću, N neku funkcionalnu relaciju, t vreme, a n broj.

U dokumentaciji HashMap se pojavljuje sledeći opis:

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

Da bi vam bilo jasnije, ovde ćemo podsetiti na metodu razdvajanja i strukturu crveno-crnog stabla u HashMap.

Pre Jave 8, HashMap je koristio liste za rešavanje kolizija, odnosno kada se dva ili više ključeva mapiraju u istu kofu, smeštaju se u listu te kofe. Kada čvorova (Node) na listi bude previše, lista postaje dugačka, pa efikasnost pretrage (efikasnost pretrage LinkedList je O(n)) biva pogođena.

U Javi 8, kada broj čvorova u listi pređe prag (8), lista se pretvara u crveno-crno stablo (čvor postaje TreeNode); crveno-crno stablo (biće detaljno objašnjeno u poglavlju o TreeMap) je efikasna struktura balansiranog stabla koja može izvršiti umetanje, brisanje i pretragu u vremenu O(log n). Ova struktura, kada je broj čvorova veliki, poboljšava performanse i skalabilnost HashMap.

Dobro, sada kada imamo tu pozadinu, prevedimo gorenavedenu dokumentaciju:

Pošto je veličina TreeNode-a (čvora crveno-crnog stabla) otprilike duplo veća od običnog čvora (čvora liste Node), crveno-crno stablo se koristi samo kada kofa sadrži dovoljno čvorova (vidi TREEIFY_THRESHOLD — prag, vrednost 8; crveno-crno stablo povećava efikasnost pretrage kada je broj čvorova veći).

Prilikom brisanja elemenata ili promene veličine niza (proširenja) (ponovno raspršivanje), crveno-crno stablo se može pretvoriti u listu (kada je broj čvorova manji od 8); kada je broj čvorova mali, lista je efikasnija od crveno-crnog stabla, jer crveno-crno stablo zahteva više memorijskog prostora za čuvanje čvorova.

U upotrebi sa dobro raspoređenim hashCode-ima, crveno-crno stablo se retko koristi.

U idealnom slučaju, pri slučajnim hashCode-ima, učestalost čvorova u kofama prati Poasonovu raspodelu (https://en.wikipedia.org/wiki/Poisson_distribution), sa prosečnim parametrom oko 0.5 za podrazumevani prag proširenja od 0.75, mada sa velikom varijansom zbog granulacije proširenja. Zanemarujući varijansu, očekivani broj pojavljivanja veličine liste k iznosi (exp(-0.5) * pow(0.5, k) / factorial(k)).

Prvih nekoliko vrednosti je:
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

više: manje od jedan prema deset miliona

Iako suština ovog pasusa više govori o tome zašto se u JDK 8, kada dužina liste pređe 8, vrši konverzija u crveno-crno stablo, pominje se faktor opterećenja 0.75, ali bez pravog objašnjenja zašto.

Da bismo to razjasnili, naišao sam na ovaj članak:

Referentna veza: https://segmentfault.com/a/1190000023308658

U njemu se pominje pojam: binomna raspodela (Binomial Distribution).

Kada radimo nešto, verovatnoća ishoda ima samo dve mogućnosti, kao pri bacanju novčića — ili glava ili pismo.

Ako izvedemo N eksperimenata, onda u svakom ispitivanju postoje samo dva moguća ishoda, svaki eksperiment je nezavisan, različiti eksperimenti međusobno ne utiču jedni na druge, a verovatnoća uspeha u svakom eksperimentu je ista.

Na osnovu ove teorije: ubacujemo podatak u hash tabelu; ako dođe do kolizije to je neuspeh, inače uspeh.

Možemo pretpostaviti da je hash vrednost eksperimenta slučajna, a pošto se ključevi nakon hash izračunavanja mapiraju u adresni prostor hash tabele, i rezultat je slučajan. Zato je svaki put kada radimo put() isto kao da bacamo kockicu sa 16 strana (podrazumevana dužina niza HashMap nakon prvog proširenja je 16); bacanje kockice je svakako međusobno nezavisno. Kolizija se javlja kada se posle n bacanja pojavi ponovljen broj.

Pa, koja je naša svrha?

Kada bacimo kockicu k puta, želimo da verovatnoća da nijedan broj nije isti bude što veća; opšte govoreći, sigurno mora biti veća od 0.5 (ovo je idealna vrednost).

Prema tome, verovatnoća da u n događaja ne bude kolizija data je gornjom formulom:

Ova verovatnoća mora biti veća od 0.5; smatramo da ovakav hashmap može pružiti vrlo nisku stopu kolizija. Dakle:

Podsetnik člana 25. univerzuma

U ovom trenutku, zapravo nas najviše zanima: kada je dužina s, posle koliko n puta treba izvršiti proširenje? Faktor opterećenja je vrednost $n/s$. Izvod je sledeći:

Dakle, dobija se

gde je

Ovo je problem određivanja granice funkcije oblika ∞⋅0. Ovde prvo uzmimo $s=m+1(m\to \mathrm{\infty })$pa se pretvara u

Zatim uzmimo $x=\frac{1}{m}(x\to 0)$ i dobijamo,

Dakle,

S obzirom na to da HashMap ima zahtev prema kapacitetu: on mora biti stepen dvojke. Kada se izabere faktor opterećenja 0.75, može se garantovati da je njegov proizvod sa kapacitetom celi broj.

16*0.75=12
32*0.75=24

Osim 0.75, u opsegu 0.5–1 mogu se izabrati i 0.625 (5/8) i 0.875 (7/8); sa stanovišta medijane, 0.75 je prilično savršen izbor. Osim toga, prema Vikipediji, faktor opterećenja metode razdvajanja (jednog od načina rešavanja kolizija) najbolje je držati ispod 0.7–0.8; preko 0.8, promašaji CPU keša (cache missing) pri pretraživanju tabele rastu eksponencijalno.

Zaključak: 0.75 je prilično savršen izbor.

Rezime

Faktor opterećenja HashMap (load factor, doslovno faktor učitavanja) je odnos broja elemenata popunjenih u hash tabeli i broja kofa; kada broj elemenata dostigne proizvod faktora opterećenja i broja kofa, potrebno je izvršiti proširenje. Ova vrednost se obično bira kao 0.75 jer postiže kompromis između vremenskih i prostornih troškova, čime performanse hash tabele dolaze do boljih rezultata.

Ako je faktor opterećenja prevelik i popunjenost velika, elementi u hash tabeli će sve više težiti da se grupišu u malom broju kofa, što dovodi do povećanja kolizija; te kolizije uzrokuju smanjenje efikasnosti pretrage, umetanja i brisanja. Istovremeno, to dovodi i do sve češćih proširenja, što dodatno smanjuje performanse.

Ako je faktor opterećenja premali, broj kofa će biti veliki; iako se time smanjuje broj kolizija, dolazi do rasipanja prostora, pa se izborom 0.75 nastoji pronaći tačka ravnoteže, odnosno postići dobra ravnoteža između vremenskih i prostornih troškova.

Ukratko, vrednost 0.75 se bira kako bi se postigla dobra ravnoteža između vremenskih i prostornih troškova — koja istovremeno garantuje performanse hash tabele i u potpunosti iskorišćava prostor.

04. Nitna nesigurnost

O ovom pitanju zapravo nema potrebe previše govoriti, ali s obzirom na to da neki intervjueri to pitaju na intervjuu, reći ćemo ukratko.

Razloga je tri:

• Proširenje u višenitnom okruženju može dovesti do beskonačne petlje
• put u višenitnom okruženju može dovesti do gubitka elemenata
• Istovremeni put i get mogu dovesti do toga da get vrati null

1) Proširenje u višenitnom okruženju može dovesti do beskonačne petlje

Kao što je poznato, HashMap koristi metodu razdvajanja za rešavanje kolizija, što znači da se pri koliziji parovi ključ-vrednost sa istom hash vrednošću čuvaju u obliku liste.

U JDK 7 se koristilo umetanje na početak liste, što znači da se sledeći par ključ-vrednost u koliziji smeštao ispred prethodnog (objašnjeno u poglavlju o proširenju). Pri proširenju je moglo doći do pojave kružne liste, što izaziva beskonačnu petlju.

Izvorni kod resize metode:

// newCapacity je novi kapacitet
void resize(int newCapacity) {
    // mali niz, privremeno za prelazak
    Entry[] oldTable = table;
    // kapacitet pre proširenja
    int oldCapacity = oldTable.length;
    // MAXIMUM_CAPACITY je maksimalni kapacitet, 2 na 30 = 1<<30
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // kapacitet se podešava na maksimalnu vrednost Integer 0x7fffffff (heksadecimalno) = 2 na 31 - 1
        threshold = Integer.MAX_VALUE;
        return;
    }

    // inicijalizuje se novi niz (veliki kapacitet)
    Entry[] newTable = new Entry[newCapacity];
    // elementi malog niza se prebacuju u veliki niz
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // referenca na novi veliki niz
    table = newTable;
    // ponovo se izračunava prag
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

transfer metoda služi za prebacivanje — kopira elemente malog niza u novi niz.

void transfer(Entry[] newTable, boolean rehash) {
    // novi kapacitet
    int newCapacity = newTable.length;
    // prolazak kroz mali niz
    for (Entry<K,V> e : table) {
        while(null != e) {
            // metoda razdvajanja, različite vrednosti za isti ključ
            Entry<K,V> next = e.next;
            // da li je potrebno ponovo izračunati hash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // na osnovu kapaciteta velikog niza i hash vrednosti ključa izračunava se indeks elementa u nizu
            int i = indexFor(e.hash, newCapacity);

            // novi elementi na istoj poziciji se stavljaju na početak liste
            e.next = newTable[i];

            // smeštanje u novi niz
            newTable[i] = e;

            // sledeći element u listi
            e = next;
        }
    }
}

Obratite pažnju na linije koda e.next = newTable[i] i newTable[i] = e; one stavljaju novi element na početak liste.

Pretpostavimo da situacija pre proširenja izgleda ovako.

Onda nakon normalnog proširenja izgleda ovako.

Pretpostavimo da sada dve niti istovremeno vrše proširenje; nit A je suspendovana pri izvršavanju e.next = newTable[i], pri čemu u niti A važi: e=3, next=7, e.next=null.

Nit B počinje sa izvršavanjem i završava prenos podataka.

Sada je next od 7 jednako 3, a next od 3 je null.

Zatim nit A dobija CPU vremenski odeljak i nastavlja da izvršava e.next = newTable[i]; newTable[i] = e, čime se 3 smešta na odgovarajuću poziciju u novom nizu; stanje niti A nakon ovog kruga petlje je sledeće:

Izvršava se sledeći krug petlje; sada je e=7. U originalnoj niti A, next od 7 bio je 5, ali pošto je table zajednički za nit A i nit B, a nit B je uspešno završila, next od 7 postao je 3, pa je i u niti A next od 7 sada 3.

Umetanjem na početak, situacija postaje ovakva:

Čini se da nema problema; sada je next = 3, e = 3.

Prelazi se u sledeći krug petlje, ali pošto je nit B postavila next od 3 na null, ovaj krug trebalo bi da bude poslednji.

Zatim, kada se izvrši e.next=newTable[i], odnosno 3.next=7, 3 i 7 se međusobno povezuju; nakon newTable[i]=e, 3 se ponovo umeće na početak liste; rezultat izvršenja je prikazan na slici:

Počinje "ruska lutka", a element 5 postaje napušteno dete — tragično~~~

Ovde ubacujem i analizu člana "Xiao Huifei": "Nit A je suspendovana posle 8. linije, a pre 17. linije".

Xiao Huifei

Međutim, u JDK 8 ovaj problem je ispravljen — pri proširenju se zadržava originalni redosled liste (da, izgleda kao da smo uzalud pričali, haha, tako već jeste sa ovim pitanjem sa intervjua, prilično je plitko, ali neki intervjueri se zaista previše prave važni).

2) put u višenitnom okruženju može dovesti do gubitka elemenata

U normalnim okolnostima, kada dođe do kolizije, HashMap izgleda ovako:

Ali kada više niti istovremeno vrši put, ako im izračunati indeks pozicije bude isti, prethodni ključ će biti prepisan sledećim, što dovodi do gubitka elemenata.

Izvorni kod metode put:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // Korak ①: ako je tab prazan, kreira se
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // Korak ②: izračunava se indeks i postupa se sa null vrednostima
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;

        // Korak ③: ako ključ čvora postoji, direktno se prepisuje value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

        // Korak ④: proverava se da li je lista crveno-crno stablo
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

        // Korak ⑤: u pitanju je lista
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);

                    // kada dužina liste postane veća od 8, vrši se konverzija u crveno-crno stablo
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }

                // ako ključ već postoji, direktno se prepisuje value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // Korak ⑥: direktno prepisivanje
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;

    // Korak ⑦: preko maksimalnog kapaciteta se vrši proširenje
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Problem nastaje u koraku ②:

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

Oba thread-a su izvršila if iskaz; pretpostavimo da je nit A prva izvršila tab[i] = newNode(hash, key, value, null), tabela izgleda ovako:

Zatim nit B izvrši tab[i] = newNode(hash, key, value, null), pa tabela izgleda ovako:

3 je nestao.

3) Istovremeni put i get mogu dovesti do toga da get vrati null

Kada nit 1 vrši put i pošto broj elemenata prekoračuje prag dođe do proširenja, a nit 2 u tom trenutku vrši get, može se pojaviti ovaj problem.

Pošto nit 1 nakon izvršenja table = newTab promeni i ono što nit 2 vidi kao table, pri get-u naravno može dobiti null, jer elementi još uvek nisu prebačeni.

Referentne veze:

• https://blog.csdn.net/lonyw/article/details/80519652
• https://zhuanlan.zhihu.com/p/91636401
• https://www.zhihu.com/question/20733617
• https://zhuanlan.zhihu.com/p/21673805

4) Rezime

HashMap nije bezbedan za niti uglavnom zato što operacije umetanja, brisanja i proširenja mogu dovesti do promene strukture liste, čime se narušava nepromenljivost HashMap. Konkretno, ako jedna nit prelazi kroz listu HashMap, dok druga nit istovremeno modifikuje tu listu (npr. doda čvor), struktura liste će se promeniti, čime se narušava trenutno prelaženje koje izvodi prva nit, što može dovesti do neuspelog prelaženja ili beskonačne petlje.

Da bi se rešio ovaj problem, Java pruža implementaciju HashMap koja je bezbedna za niti — ConcurrentHashMap. ConcurrentHashMap interno koristi segmentne brave (Segment), razdvajajući ceo Map na više malih HashMap; svaki mali HashMap ima svoju bravu, tako da različite niti mogu istovremeno pristupati različitim malim Map-ovima, čime se ostvaruje bezbednost niti. Prilikom operacija umetanja, brisanja i proširenja potrebno je zaključati samo trenutni mali Map, dok se ceo Map ne zaključava, što poboljšava efikasnost konkurentnog pristupa.

05. Rezime

HashMap je jedna od najčešće korišćenih kolekcija u Javi; to je struktura podataka koja čuva parove ključ-vrednost i omogućava brz pristup odgovarajućoj vrednosti preko ključa. Evo kratkog rezimea o HashMap:

• HashMap koristi strukturu čuvanja zasnovanu na nizu + listi/crveno-crnog stabla i može izvršiti dodavanje, brisanje i pretragu elemenata u vremenskoj složenosti O(1).
• HashMap nije bezbedan za niti, pa je u višenitnim okruženjima potrebno koristiti ConcurrentHashMap radi bezbednosti niti.
• Mehanizam proširenja HashMap ostvaruje se povećanjem kapaciteta niza i ponovnim izračunavanjem hash vrednosti; pri proširenju je potrebno ponovo izračunati hash vrednosti svih elemenata, pa proširenje utiče na performanse kada je elemenata mnogo.
• U Javi 8, implementacija HashMap uvodi mehanizme poput metode razdvajanja i transformacije u stablo kako bi se optimizovalo čuvanje velikog broja elemenata, čime se performanse dodatno poboljšavaju.
• Ključevi u HashMap su jedinstveni; ako želite da sačuvate duplikat ključ, kasnija vrednost će prepisati prethodnu.
• Početni kapacitet i faktor opterećenja HashMap se mogu podesiti; početni kapacitet označava početnu veličinu niza, a faktor opterećenja faktor popunjenosti niza. Uobičajeno, početni kapacitet je 16, a faktor opterećenja 0.75.
• HashMap nije uređen pri prelaženju, pa ako je potrebno uređeno prelaženje, može se koristiti TreeMap.

Zaključak: HashMap je efikasna struktura podataka sa mogućnošću brze pretrage i umetanja elemenata, ali treba obratiti pažnju na pitanja bezbednosti niti i performansi.

Ako ste već savladali HashMap, možete rešavati zadatak 001 i 013 na LeetCode-u; oni koriste HashMap, nizove i for petlju. Linkove ka rešenjima sam ostavio:

• Ergeove beleške za LeetCode: 001. Zbir dva broja
• Ergeove beleške za LeetCode: 013. rimske cifre u celi broj

Takođe, zahvaljujem članu "Tage" na ukazivanju na greške u rasporedu teksta; članak je ispravljen, hvala mu na podršci.