Kako oduševiti Java ispitivača: ConcurrentHashMap (hash tabela bezbedna za niti)
ConcurrentHashMap je implementacija hash tabela bezbedna za niti u Java paketu za konkurentnost (java.util.concurrent).
HashMap se pri proširenju u višenitnom okruženju može suočiti sa situacijom da se CPU približi 100%, jer HashMap nije bezbedan za niti. Možemo preko metode Map<K,V> synchronizedMap(Map<K,V> m) iz Collections da umotamo HashMap u mapu bezbednu za niti.
Na primer, izvorni kod put metode SynchronzedMap-a je zaključan:
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}Način rada synchronized sinhronizovanih blokova smo već ranije obradili, sigurno se još sećate.
Međutim, to nije najelegantniji način. Majstor Doug Lea se nije štedeo da bi nam stvorio neke konkurentne kontejnere bezbedne za niti, čineći svakog Java programera veoma srećnim. U poređenju sa HashMap, ConcurrentHashMap je mapa bezbedna za niti, u kojoj je idejom segmentnih brava znatno povećana efikasnost konkurentnosti.
Kada smo predstavljali konkurentne kontejnere, takođe smo pomenuli ConcurrentHashMap. On je počevši od JDK 1.8 doživeo velike promene — samo količina koda se znatno povećala.
Verzija 1.8 je odbacila segment i koristi veliku količinu synchronized i CAS operacija bez brava kako bi se garantovala bezbednost niti u ConcurrentHashMap-u.
Zašto se koristi ReentrantLock umesto synchronized?
Zapravo, synchronized je prošao mnogo optimizacija, o čemu smo već govorili, uključujući biasovanu bravu, laku bravu i tešku bravu, pri čemu se stanje brave može postepeno unapređivati. Zbog toga su performanse synchronized-a u odnosu na ReentrantLock zapravo slične, a u nekim situacijama čak i bolje.
Promene u ConcurrentHashMap-u
ConcurrentHashMap ima razlike između JDK 1.7 i JDK 1.8. Ovde ćemo ih posebno predstaviti.
JDK 1.7
U JDK 1.7, ConcurrentHashMap pruža finiji mehanizam zaključavanja koji se zove segmentna brava „Lock Striping". Cela hash tabela je podeljena na više segmenata, od kojih svaki ima sopstvenu bravu. Operacije čitanja ne zahtevaju bravu, a operacije pisanja zaključavaju samo relevantni segment. To smanjuje verovatnoću sukoba oko brave i tako povećava konkurentne performanse.
Prednost ovog mehanizma: u konkurentnom okruženju postiže se veća propusnost, dok se u jednonitnom okruženju gubi samo veoma mali deo performansi.
Segmentnu bravu možemo ovako razumeti: podaci se podele na segmente, i svakom segmentu se dodeli jedna brava. Kada jedna nit drži bravu i pristupa jednom segmentu podataka, podacima u ostalim segmentima mogu da pristupaju i druge niti.
Neke metode zahtevaju rad preko segmenata, kao što su size(), isEmpty(), containsValue() — one možda moraju da zaključaju celu tabelu, a ne samo jedan segment. To zahteva uzastopno zaključavanje svih segmenata, a nakon operacije — uzastopno otključavanje svih segmenata. Pogledajte sliku:
ConcurrentHashMap se sastoji od niza Segment i niza HashEntry. Segment je reentrantna brava ReentrantLock, dok se HashEntry koristi za čuvanje podataka u obliku parova ključ-vrednost.
Jedan ConcurrentHashMap sadrži niz Segment; struktura Segment-a je slična HashMap-i, to je struktura niza i povezane liste. Jedan Segment sadrži niz HashEntry; svaki HashEntry je element strukture povezane liste. Svaki Segment štiti elemente u svom nizu HashEntry. Kada se menjaju podaci u nizu HashEntry, prvo mora da se pribavi odgovarajuća brava Segment-a.
Struktura jednog Segment-a je prikazana ispod:
Koliko ovakvih Segment objekata ima u kolekciji ConcurrentHashMap? Ima ih stepena dvojke (2 na N), i svi se čuvaju u nizu koji se zove segments. Dakle, cela struktura ConcurrentHashMap-a je:
Može se reći da je ConcurrentHashMap hash tabela drugog nivoa. Ispod jedne opšte hash tabela nalazi se nekoliko pod-hash-tabela.
Slučaj 1: istovremeno pisanje u različite Segment-e (može se izvršavati konkurentno)
Slučaj 2: jedno pisanje i jedno čitanje u istom Segment-u (može se izvršavati konkurentno)
Slučaj 3: istovremeno pisanje u isti Segment
Pisanje u Segment zahteva bravu, pa će istovremeno pisanje u isti Segment biti blokirano.
Odatle se vidi da u ConcurrentHashMap-u svaki Segment drži sopstvenu bravu. Uz garantovanje bezbednosti niti, smanjuje se granulacija brave, što čini konkurentne operacije efikasnijim.
Proces čitanja i pisanja u ConcurrentHashMap-u je sledeći:
get metoda
- Vrši Hash operaciju nad ulaznim ključem i dobija hash vrednost.
- Pomoću hash vrednosti pronalazi odgovarajući Segment objekat.
- Ponovo pomoću hash vrednosti pronalazi konkretan položaj u nizu unutar Segment-a.
put metoda
- Vrši Hash operaciju nad ulaznim ključem i dobija hash vrednost.
- Pomoću hash vrednosti pronalazi odgovarajući Segment objekat.
- Pribavlja reentrantnu bravu.
- Ponovo pomoću hash vrednosti pronalazi konkretan položaj u nizu unutar Segment-a.
- Umeće ili prepisuje HashEntry objekat.
- Otključava bravu.
JDK 1.8
U JDK 1.8, ConcurrentHashMap je uradio dve glavne optimizacije:
- Kao i HashMap, povezana lista će se kada dužina dostigne 8 pretvoriti u crveno-crno stablo, što poboljšava efikasnost pretrage pri velikom broju kolizija.
- Kao brava se koristi glavni čvor na nekoj poziciji (glava povezane liste ili koren crveno-crnog stabla), uz kombinaciju spinning-a + CAS kako bi se izbegli nepotrebni troškovi brave i dodatno poboljšale konkurentne performanse.
U poređenju sa ConcurrentHashMap-om u JDK 1.7, ConcurrentHashMap u JDK 1.8 je odbacio segmentne brave Segment i koristi CAS + synchronized da bi garantovao konkurentnu bezbednost. Ceo kontejner je podeljen na samo jedan Segment, odnosno niz table.
U ConcurrentHashMap-u JDK 1.8, deljene promenljive u klasi čvora Node koriste ključnu reč volatile, kao i u JDK 1.7, čime se garantuje vidljivost promenljivih pri radu više niti!
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
......
}Polja ConcurrentHashMap-a
- table,
volatile Node<K,V>[] table:
Niz koji sadrži Node-e, kao osnovni kontejner ConcurrentHashMap-a. Koristi lenjo učitavanje — inicijalizacija se obavlja tek pri prvom umetanju podataka. Veličina niza je uvek stepen dvojke, kao što smo obradili pri priči o HashMap-i.
- nextTable,
volatile Node<K,V>[] nextTable
Koristi se pri proširenju; inače je null, a ne-null je samo tokom proširenja.
- sizeCtl,
volatile int sizeCtl
Ovo polje kontroliše veličinu niza table. U zavisnosti od toga da li je inicijalizovan i da li je u toku proširenje, ima nekoliko situacija:
- Kada je vrednost negativna: ako je -1, znači da je u toku inicijalizacija; ako je -N, znači da trenutno N-1 niti vrše operaciju proširenja.
- Kada je vrednost pozitivna: ako je trenutni niz null, znači da je table u procesu inicijalizacije i sizeCtl predstavlja dužinu niza koji treba napraviti; ako je već inicijalizovan, predstavlja dostupni kapacitet trenutnog podatkovnog kontejnera (niza table), što se može shvatiti i kao granična vrednost (kada broj umetnutih čvorova pređe tu graničnu vrednost potrebno je proširenje) — konkretno, dužina niza n puta faktor opterećenja loadFactor.
- Kada je vrednost 0, dužina niza je podrazumevana početna vrednost.
sun.misc.Unsafe U
U implementaciji ConcurrentHashMap-a se vidi da se koristi veliki broj U.compareAndSwapXXXX metoda za izmenu pojedinih svojstava ConcurrentHashMap-a.
Ove metode zapravo koriste CAS algoritam da bi garantovale bezbednost niti — to je optimistička strategija: pretpostavlja se da svaka operacija neće stvoriti sukob, a pokušava se ponovo samo kada sukob nastane.
Već smo o tome govorili: CAS operacije se oslanjaju na skup instrukcija modernih procesora i implementirane su preko niskonivoiske instrukcije CMPXCHG. Osnovna ideja CAS(V,O,N) je: ako je stvarna trenutna vrednost promenljive V jednaka očekivanoj staroj vrednosti O, to znači da promenljivu nije modifikovala nijedna druga nit, pa je bezbedno dodeliti novu vrednost N toj promenljivoj; ako stvarna trenutna vrednost V nije jednaka očekivanoj staroj vrednosti O, to znači da je promenljivu već obradila neka druga nit, pa je u tom slučaju dodeljivanje nove vrednosti N nebezbedno i treba pokušati ponovo.
U konkurentnim kontejnerima, CAS se implementira preko klase sun.misc.Unsafe, koja pruža neke niskonivoiske operacije kojima se može direktno upravljati memorijom i nitima — može se shvatiti kao „pokazivač" u Javi. Ova članska promenljiva se pribavlja u statičkom bloku:
static {
try {
U = sun.misc.Unsafe.getUnsafe();
.......
} catch (Exception e) {
throw new Error(e);
}
}Unutrašnje klase ConcurrentHashMap-a
1. Node
Klasa Node implementira interfejs Map.Entry, uglavnom čuva parove ključ-vrednost i ima next polje.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
......
}Takođe se vidi da su mnoga svojstva modifikovana ključnom reči volatile, takođe radi garantovanja memorijske vidljivosti.
2. TreeNode
Čvor stabla, nasleđuje klasu Node koja nosi podatke. Operacije crveno-crnog stabla se odnose na klasu TreeBin. Iz komentara te klase se takođe vidi da je TreeBin ponovo umotanje TreeNode-a, o čemu će biti reči ispod.
**
* Nodes for use in TreeBins
*/
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
......
}3. TreeBin
Ova klasa ne čuva korisničke informacije o ključu i vrednosti, već umotava više TreeNode čvorova. U stvarnom „nizu" ConcurrentHashMap-a nalaze se TreeBin objekti, a ne TreeNode objekti.
static final class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root;
volatile TreeNode<K,V> first;
volatile Thread waiter;
volatile int lockState;
// values for lockState
static final int WRITER = 1; // set while holding write lock
static final int WAITER = 2; // set when waiting for write lock
static final int READER = 4; // increment value for setting read lock
......
}4. ForwardingNode
Specijalni čvor koji se javlja tokom proširenja; njegov ključ, vrednost i hash su svi null. Ima referencu nextTable na novi niz table.
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
.....
}CAS u ConcurrentHashMap-u
ConcurrentHashMap u velikoj meri koristi CAS za izmenu svojih svojstava i izvođenje nekih operacija. Zato, pre nego što razumemo metode ConcurrentHashMap-a, moramo da upoznamo nekoliko uobičajenih operacija koje koriste CAS algoritam za garantovanje bezbednosti niti.
1. tabAt
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}Ova metoda se koristi za dobijanje Node elementa sa indeksom i u nizu table.
2. casTabAt
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}Pomoću CAS operacije se postavlja element sa indeksom i u nizu table.
3. setTabAt
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}Ova metoda se koristi za postavljanje elementa sa indeksom i u nizu table.
Metode ConcurrentHashMap-a
Konstruktor
ConcurrentHashMap pruža ukupno sledećih 5 konstruktora:
// 1. Konstruiše praznu mapu, odnosno niz table još nije inicijalizovan; inicijalizacija se vrši pri prvom umetanju podataka; podrazumevana veličina je 16
ConcurrentHashMap()
// 2. Zadana veličina mape
ConcurrentHashMap(int initialCapacity)
// 3. Zadana mapa
ConcurrentHashMap(Map<? extends K, ? extends V> m)
// 4. Zadana veličina mape i faktor opterećenja
ConcurrentHashMap(int initialCapacity, float loadFactor)
// 5. Zadana veličina mape, faktor opterećenja i nivo konkurentnosti (očekivani broj niti koje istovremeno pristupaju podacima)
ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel)Razlike pogledajte u komentarima. Pogledajmo drugi konstruktor, čiji je izvorni kod ispod:
public ConcurrentHashMap(int initialCapacity) {
//1. Manje od 0 odmah baca izuzetak
if (initialCapacity < 0)
throw new IllegalArgumentException();
//2. Proverava da li je premašena dozvoljena maksimalna vrednost; ako jeste uzima maksimalnu, inače dalje obrađuje tu vrednost
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
//3. Dodeljuje se sizeCtl-u
this.sizeCtl = cap;
}Logiku ovog koda pogledajte u komentarima, lako je razumljiva: ako je manje od 0 odmah baca izuzetak; ako je navedena vrednost veća od dozvoljene maksimalne uzima maksimalnu, inače dalje obrađuje navedenu vrednost. Na kraju se cap dodeljuje sizeCtl-u.
Nakon poziva konstruktora, veličina sizeCtl-a predstavlja veličinu ConcurrentHashMap-a, odnosno dužinu niza table.
Šta radi tableSizeFor? Izvorni kod je ispod:
/**
* Returns a power of two table size for the given desired capacity.
* See Hackers Delight, sec 3.2
*/
private static final int tableSizeFor(int c) {
int n = c - 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;
}Komentar jasno kaže: ova metoda pretvara veličinu zadatu konstruktorom u stepen dvojke, odnosno veličina ConcurrentHashMap-a je uvek stepen dvojke. Na primer, kada je zadata veličina 18, da bi se zadovoljila osobina stepena dvojke, veličina ConcurrentHashMap-a je zapravo 2 na 5 (32).
Takođe treba napomenuti: poziv konstruktora još uvek ne inicijalizuje niz table, već samo izračunava dužinu niza table. Prava inicijalizacija i kreiranje niza table obavlja se tek pri prvom umetanju podataka u ConcurrentHashMap.
initTable metoda
Evo i izvornog koda:
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
// 1. Garantuje da samo jedna nit vrši inicijalizaciju
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// 2. Izračunava veličinu niza
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
// 3. Ovde se niz zaista inicijalizuje
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// 4. Izračunava dostupnu veličinu niza: stvarna veličina n*0.75 (faktor opterećenja)
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}Logiku koda pogledajte u komentarima.
Može postojati situacija da više niti istovremeno uđe u ovu metodu. Da bi se garantovala ispravna inicijalizacija, u koraku 1 se prvo proverava preko if: ako već jedna nit vrši inicijalizaciju, druge niti će pozvati Thread.yield() i prepustiti CPU vremenski isečak.
Nit koja vrši inicijalizaciju će pozvati U.compareAndSwapInt i promeniti sizeCtl u -1, odnosno u stanje inicijalizacije.
Takođe treba napomenuti da se u četvrtom koraku dalje izračunava dostupna veličina niza, odnosno stvarna veličina niza n puta faktor opterećenja 0.75. 0.75 je tri četvrtine, i ovde n - (n >>> 2) je tačno n-(1/4)n=(3/4)n — zanimljivo, zar ne?
Ako se izabere konstruktor bez argumenata, ovde će se pri kreiranju niza Node koristiti podrazumevana veličina DEFAULT_CAPACITY (16), a zatim pomnožiti faktorom opterećenja 0.75, što daje 12 — dakle dostupna veličina niza je 12.
put metoda
Pri pozivu put metode poziva se metoda putVal, čiji je izvorni kod ispod:
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//1. Izračunava hash vrednost ključa
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//2. Ako table još nije inicijalizovan, prvo poziva initTable da inicijalizuje tab
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//3. Ako je element na poziciji i u tab null, direktno se koristi CAS za umetanje vrednosti
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//4. Trenutno je u toku proširenje
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
//5. Trenutno je povezana lista; u nju se umeće novi par ključ-vrednost
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 6. Trenutno je crveno-crno stablo; novi par ključ-vrednost se umeće u crveno-crno stablo
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 7. Nakon umetanja para ključ-vrednost ponovo se proverava na osnovu stvarne veličine da li je potrebna konverzija u crveno-crno stablo
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//8. Proverava se trenutna veličina kapaciteta; ako je premašena granična vrednost (stvarna veličina*faktor opterećenja) potrebno je proširenje
addCount(1L, binCount);
return null;
}ConcurrentHashMap je niz hash bucket-a; kada nema hash kolizije, svaki element je ravnomerno raspoređen u nizu hash bucket-a. Kada dođe do hash kolizije, koristi se rešenje metode lance (separate chaining) — čvorovi sa istom hash vrednošću se pretvaraju u oblik povezane liste. Pored toga, u verziji JDK 1.8, da bi se sprečilo predugo lancanje, kada dužina povezane liste pređe 8, ona se pretvara u crveno-crno stablo.
Nakon određivanja indeksa niza i, može se pozvati metoda tabAt() da se dobije element na toj poziciji. Ako je trenutni Node null, može se direktno koristiti casTabAt metoda za umetanje nove vrednosti.
Znanje o metodi lance i određivanju indeksa i smo obradili pri učenju HashMap-a, sigurno ga niste zaboravili.
Ako trenutni čvor nije null i taj čvor je specijalni čvor (ForwardingNode), to znači da se nad trenutnim ConcurrentHashMap-om obavlja operacija proširenja. Kako se utvrđuje da je ovaj Node specijalni čvor?
Proverom da li je hash vrednost tog čvora jednaka -1 (MOVED):
static final int MOVED = -1; // hash for forwarding nodesKada table[i] nije null i nije ForwardingNode, a hash vrednost trenutnog Node-a je veća od 0 (fh >= 0), to znači da je trenutni čvor glava povezane liste. Umetanje nove vrednosti u ConcurrentHashMap tada je umetanje nove vrednosti u tu povezanu listu. Zaključavanjem putem synchronized (f) se ostvaruje bezbednost niti.
Deo koda za umetanje čvora u povezanu listu je ispod:
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// Pronađe ključ sa istom hash vrednošću i prepiše staru vrednost
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
//Ako se do kraja liste ne pronađe, umetni novu vrednost na kraj liste
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}Ovaj deo koda se lako razume, postoje samo dve situacije:
- Ako se u povezanoj listi pronađe čvor sa istim ključem kao ključ koji se umeće, direktno se prepisuje.
- Ako se do kraja povezane liste ne pronađe, par ključ-vrednost koji se umeće se dodaje na kraj liste.
Kada dužina povezane liste pređe 8 (podrazumevana vrednost), povezana lista se pretvara u crveno-crno stablo. Korišćenjem osobina crveno-crnog stabla za brzo dodavanje, brisanje i izmenu može se poboljšati performansa ConcurrentHashMap-a:
if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}Ovaj kod je vrlo jednostavan: poziva se metoda putTreeVal za umetanje novog čvora u crveno-crno stablo. Istom logikom, ako u crveno-crnom stablu postoji čvor sa istim ključem (jednake hash vrednosti i equals metoda vraća true), stara vrednost se prepisuje, inače se dodaje novi čvor u crveno-crno stablo.
Nakon umetanja novog čvora podataka, vrši se dodatno podešavanje veličine trenutne povezane liste:
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}Time je analiza put metode završena. Hajde da sumiramo:
- Za svaku umetnutu vrednost, prvo se metodom spread izračunava hash code ključa čime se određuje pozicija te vrednosti u nizu table.
- Ako niz table još nije inicijalizovan, vrši se inicijalizacija.
- Ako je ta pozicija null, koristi se CAS operacija za direktno umetanje.
- Ako na toj poziciji postoji čvor, znači da je došlo do hash kolizije; prvo se proverava tip tog čvora — ako je čvor
==MOVED, znači da je u toku proširenje. - Ako je u pitanju čvor povezane liste (
fh>0), prvo se uzima glavni čvor, a zatim se uzastopno prelazi unapred kako bi se odredila pozicija novog čvora. Ako se naiđe na čvor sa istim ključem, direktno se prepisuje; u suprotnom se umeće na kraj liste. - Ako je tip tog čvora TreeBin, direktno se poziva metoda za umetanje crveno-crnog stabla da se umetne novi čvor.
- Nakon umetanja čvora ponovo se proverava dužina povezane liste; ako je dužina veća od 8, ta povezana lista se pretvara u crveno-crno stablo.
- Proverava se trenutna veličina kapaciteta; ako je premašena granična vrednost (stvarna veličina*faktor opterećenja) potrebno je proširenje.
get metoda
Izvorni kod get metode je ispod:
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 1. Ponovni hash
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 2. Ključ bucket čvora table[i] je isti kao traženi ključ, pa se direktno vraća
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 3. Hash trenutnog čvora manji od 0 znači da je u pitanju čvor stabla; pretraga se vrši u crveno-crnom stablu
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
//4. Pretraga u povezanoj listi; ako se pronađe vraća se vrednost tog čvora, inače null
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}- Hash: raspršuje se hash vrednost prosleđenog ključa, što pomaže u smanjenju verovatnoće hash kolizije. Metoda spread garantuje da će različiti ključevi biti ravnomernije raspoređeni u nizu bucket-a.
- Direktna pretraga: prvi korak pretrage je provera da li se hash vrednost ključa nalazi na pravoj poziciji u tabeli. Ako se ključ pronađe u prvom elementu tog bucket-a, odmah se vraća vrednost tog elementa. Ovde se koristi operator == i metoda equals za poređenje ključeva, što pomaže u obradi mogućih null vrednosti i osiguravanju ispravnog poređenja jednakosti.
- Pretraga crveno-crnog stabla: ako je hash vrednost prvog čvora manja od 0, struktura podataka tog bucket-a je crveno-crno stablo (Java 8 je uvela strukturu stabla da bi poboljšala performanse povezane liste pri hash koliziji). U tom slučaju se koristi metoda find za pretragu ključa u crveno-crnoma stablu.
- Pretraga povezane liste: ako nijedan od prethodna dva uslova nije ispunjen, kod prelazi povezanu listu u tom bucket-u. Ako se u povezanoj listi pronađe element sa istom hash vrednošću i ključem, vraća se njegova vrednost. Ako se pređe cela povezana lista i ništa se ne pronađe, vraća se null.
transfer metoda
Kada ConcurrentHashMap-u ponestane kapaciteta, potrebno je proširiti niz table. Osnovna ideja ove metode je vrlo slična HashMap-i, ali pošto podržava konkurentno proširenje, nešto je složenija. Izvorni kod transfer metode je ispod:
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
//1. Pravi se novi Node niz kapaciteta duplo većeg od prethodnog
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
//2. Pravi se ForwardingNode referenca koja će kasnije biti korišćena
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// 3. Određuje se indeks i tokom prolaska
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
//4. Elementi iz originalnog niza se kopiraju u novi niz
//4.5 Izlazak iz for petlje, proširenje završeno, izmena sizeCtl svojstva
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
//4.1 Ako je i-ti element u trenutnom nizu null, postavlja se CAS-om na specijalni čvor ForwardingNode (može se shvatiti kao mesto-rezervacija)
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//4.2 Ako se naiđe na ForwardingNode čvor, to znači da je ta tačka već obrađena — preskače se. Ovo je jezgro kontrole konkurentnog proširenja.
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) {
//4.3 Obrada slučaja gde je trenutni čvor glava povezane liste. Na osnovu toga da li je najviši bit 1 ili 0 (najviši bit se odnosi na bit dužine niza), originalna povezana lista se deli u dve liste koje se smeštaju na pozicije i i i+n u novom nizu. Ovde se, kroz domišljatu obradu, deo originalne liste može direktno preneti u novu listu (odnosno lastRun i čvorovi koji ga prate), dok preostali deo mora da se klonira putem new metode i premesti u novu listu (metodom umetanja na početak).
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln); // vidi se da se novi čvorovi umeću obrnutim redosledom (na početak)
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
//Na poziciju i u nextTable umeće se jedna lista
setTabAt(nextTab, i, ln);
//Na poziciju i+n u nextTable umeće se druga lista
setTabAt(nextTab, i + n, hn);
//Na poziciju i u table umeće se ForwardingNode čvor — označava da je taj čvor obrađen
setTabAt(tab, i, fwd);
//Postavlja se advance na true i vraća u while petlju gore, pa se može izvršiti operacija i--
advance = true;
}
//4.4 Obrada slučaja gde je trenutni čvor TreeBin; operacija je slična gore navedenoj
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}Logiku koda pogledajte u komentarima. Cela operacija proširenja se deli u dva dela:
Prvi deo je izgradnja nextTable-a čiji je kapacitet duplo veći; ovu operaciju obavlja jedna nit.
Drugi deo je kopiranje elemenata iz originalnog table u nextTable, uglavnom proces prolaska i kopiranja. Dobija se pozicija i u nizu koja se trenutno obilazi, a zatim se metodom tabAt dobija element na poziciji i:
- Ako je ta pozicija prazna, u originalni table na poziciju i stavlja se ForwardingNode čvor — to je i okidač za konkurentno proširenje.
- Ako je na toj poziciji Node čvor (
fh>=0) i glava je povezane liste, ta povezana lista se deli u dve i stavljaju se na pozicije i i i+n u nextTable-u. - Ako je na toj poziciji TreeBin čvor (
fh<0), takođe se radi obrada obrnutim redosledom i proverava se da li je potrebno untreeify; rezultati obrade se stavljaju na pozicije i i i+n u nextTable-u. - Kada se obiđu svi čvorovi, kopiranje je završeno. Tada nextTable postaje novi table i sizeCtl se ažurira na 0,75 puta novi kapacitet — proširenje je završeno.
Metode vezane za size
Za ConcurrentHashMap, koliko je tačno stvari u ovom table-u je nesigurno, jer je nemoguće pri pozivu metode size() „stop the world" i zaustaviti sve ostale niti da bi se izvršila statistika. Za ovu nesigurnu vrednost size, ConcurrentHashMap je ipak uložio mnogo truda.
Da bi se izbrojao broj elemenata, ConcurrentHashMap definiše neke promenljive i jednu unutrašnju klasu.
/**
* A padded cell for distributing counts. Adapted from LongAdder
* and Striped64. See their internal docs for explanation.
*/
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
/******************************************/
/**
* U stvari čuva broj elemenata u HashMap-i. Ažurira se CAS bravom,
ali ne vraća trenutni broj elemenata u HashMap-i.
*/
private transient volatile long baseCount;
/**
* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
*/
private transient volatile int cellsBusy;
/**
* Table of counter cells. When non-null, size is a power of 2.
*/
private transient volatile CounterCell[] counterCells;Pogledajmo sada i izvorni kod brojanja:
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
/**
* Returns the number of mappings. This method should be used
* instead of {@link #size} because a ConcurrentHashMap may
* contain more mappings than can be represented as an int. The
* value returned is an estimate; the actual count may differ if
* there are concurrent insertions or removals.
*
* @return the number of mappings
* @since 1.8
*/
public long mappingCount() {
long n = sumCount();
return (n < 0L) ? 0L : n; // ignore transient negative values
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;//suma vrednosti svih brojača
}
}
return sum;
}Metoda size vraća broj elemenata u mapi, ali je rezultat ograničen na Integer.MAX_VALUE. Ako izračunata veličina pređe tu vrednost, vraća se Integer.MAX_VALUE. Ako je izračunata veličina manja od 0, vraća se 0.
Metoda mappingCount takođe vraća broj elemenata u mapi, ali dozvoljava vraćanje long vrednosti, pa može da predstavi količine veće od Integer.MAX_VALUE. Slično metodi size(), i ova metoda zanemaruje negativne vrednosti i vraća 0.
Metoda sumCount izračunava stvarnu veličinu mape. ConcurrentHashMap koristi osnovni brojač baseCount i niz CounterCell counterCells da prati veličinu. Ova struktura pomaže u smanjenju sukoba u višenitnom okruženju, jer različite niti mogu ažurirati različite CounterCell-e.
Prilikom izračunavanja zbira, metoda sumCount() sabira baseCount sa vrednostima svih ne-null ćelija u nizu counterCells.
Na kraju put metode se poziva metoda addCount koja povećava broj elemenata trenutnog ConcurrentHashMap-a za 1. Ova metoda radi dve stvari: ažurira vrednost baseCount i proverava da li je potrebno proširenje.
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
//CAS metodom se ažurira vrednost baseCount
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
//Ako je vrednost check veća ili jednaka 0 potrebno je proveriti da li je potrebno proširenje
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
//
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
//Ako već druge niti vrše operaciju proširenja
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
//Trenutna nit je jedina ili prva koja pokreće proširenje; tada je nextTable=null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}Primer ConcurrentHashMap-a
Pretpostavimo da želimo da izgradimo funkciju bezbednu za niti koja sa visokom konkurentnošću broji korisničke posete. Ovde je ConcurrentHashMap odličan izbor jer pruža visoke konkurentne performanse.
import java.util.concurrent.ConcurrentHashMap;
public class UserVisitCounter {
private final ConcurrentHashMap<String, Integer> visitCountMap;
public UserVisitCounter() {
this.visitCountMap = new ConcurrentHashMap<>();
}
// Metoda koja se poziva pri korisničkoj poseti
public void userVisited(String userId) {
visitCountMap.compute(userId, (key, value) -> value == null ? 1 : value + 1);
}
// Dobijanje broja poseta korisnika
public int getVisitCount(String userId) {
return visitCountMap.getOrDefault(userId, 0);
}
public static void main(String[] args) {
UserVisitCounter counter = new UserVisitCounter();
// Simulacija korisničkih poseta
counter.userVisited("user1");
counter.userVisited("user1");
counter.userVisited("user2");
System.out.println("User1 visit count: " + counter.getVisitCount("user1")); // Izlaz: User1 visit count: 2
System.out.println("User2 visit count: " + counter.getVisitCount("user2")); // Izlaz: User2 visit count: 1
}
}U gore navedenom primeru:
- Koristili smo ConcurrentHashMap za čuvanje broja korisničkih poseta.
- Kada korisnik poseti, ažuriramo broj poseta preko metode userVisited.
- Korišćenjem compute metode ConcurrentHashMap-a može se osigurati atomično ažuriranje broja korisničkih poseta.
- Broj poseta bilo kog korisnika može se dobiti preko metode getVisitCount.
ConcurrentHashMap nam omogućava da izgradimo ovakav efikasan statistički sistem bez brige o pitanjima konkurentnosti.
Rezime
ConcurrentHashMap je bezbedan za niti, podržava potpuno konkurentno čitanje i omogućava mnogim nitima da istovremeno pišu. U ranijim verzijama (npr. JDK 1.7), ConcurrentHashMap je koristio tehniku segmentnih brava. Cela hash tabela je podeljena na segmente (Segment), od kojih je svaki nezavisno zaključan. Tako se operacije na različitim segmentima mogu obavljati konkurentno. Počevši od JDK 1.8, interna implementacija ConcurrentHashMap-a se znatno promenila. Napustio je tehniku segmentnih brava i usvojio naprednije strategije kontrole konkurentnosti, kao što su CAS operacije i crveno-crna stabla, čime je dodatno poboljšana konkurentna performansa.
Zbog svoje konkurentne prirode, izračunavanje veličine ConcurrentHashMap-a možda nije precizno, ali je obično dovoljno blizu stvarne vrednosti.
Urednik: Chenmo Wang Er. Deo sadržaja potiče iz GitHub repozitorijuma CL0610 https://github.com/CL0610/Java-concurrency, a deo iz ovog članka Concurrent landfill prvih misli, slike su nacrtane posebno lepo.