您好,登錄后才能下訂單哦!
ConcurrentHashMap在處理rehash的時(shí)候,并不會(huì)重新計(jì)算每個(gè)key的hash值,而是利用了一種很巧妙的方法。
1、ConcurrentHashMap內(nèi)部的table數(shù)組的大小必須為2的冪次,原因是讓key均勻分布,減少?zèng)_突
2、當(dāng)table數(shù)組的大小為2的冪次時(shí),通過(guò)key.hash & table.length-1這種方式計(jì)算出的索引i,當(dāng)table擴(kuò)容后(2倍),新的索引要么在原來(lái)的位置i,要么是i+n,n為擴(kuò)容之前的容量。
3、這種處理方式非常利于擴(kuò)容時(shí)多個(gè)線程同時(shí)進(jìn)行的數(shù)據(jù)遷移操作,因?yàn)榕ftable的各個(gè)桶中的結(jié)點(diǎn)遷移不會(huì)互相影響,將整個(gè)table數(shù)組劃分為很多部分,每一部分包含一定區(qū)間的桶,每個(gè)數(shù)據(jù)遷移線程處理各自區(qū)間中的結(jié)點(diǎn)
/**
* 鏈表 -> 紅黑樹 的轉(zhuǎn)換.
*/
private final void treeifyBin(Node<K, V>[] tab, int index) {
Node<K, V> b;
int n, sc;
if (tab != null) {
// CASE 1: table的容量 < MIN_TREEIFY_CAPACITY(64)時(shí),直接table擴(kuò)容,不紅黑樹轉(zhuǎn)換
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1); //左移一位,就是*2,擴(kuò)容2倍
// CASE 2: table的容量 ≥ MIN_TREEIFY_CAPACITY(64)時(shí),鏈表 -> 紅黑樹的轉(zhuǎn)換
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K, V> hd = null, tl = null;
// 遍歷鏈表,建立紅黑樹
for (Node<K, V> e = b; e != null; e = e.next) {
TreeNode<K, V> p = new TreeNode<K, V>(e.hash, e.key, e.val, null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
// 封裝TreeBin,并鏈接到table[index]中
setTabAt(tab, index, new TreeBin<K, V>(hd));
}
}
}
}
}
private final void tryPresize(int size) {
//動(dòng)態(tài)調(diào)整擴(kuò)容的大小
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) { //大于等于0代表,初始化或者擴(kuò)容后的(table*負(fù)載因子)的桶數(shù)量
Node<K,V>[] tab = table; int n;
//Case1,table沒(méi)有初始化,先初始化
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
//設(shè)置SIZECTL為-1代表,初始化或者擴(kuò)容進(jìn)行中
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];//生成新的table
table = nt;
sc = n - (n >>> 2); //n-(n/4) = 0.75n,也就是負(fù)載因子
}
} finally {
sizeCtl = sc; //設(shè)置sizeCtl為擴(kuò)容后的桶*負(fù)載因子
}
}
}
//Case2, c<sc說(shuō)明已經(jīng)擴(kuò)容了;n>=MAXIMUM_CAPACITY,說(shuō)明桶超限了。
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
//Case3,開始擴(kuò)容
else if (tab == table) {
int rs = resizeStamp(n);//根據(jù)容量n生成一個(gè)隨機(jī)數(shù),唯一標(biāo)識(shí)本次擴(kuò)容操作
if (sc < 0) { //sc<0,說(shuō)明sizeCtl<0,代表有別的線程正在進(jìn)行擴(kuò)容
Node<K,V>[] nt;
//不能協(xié)助擴(kuò)容,退出
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
//加入擴(kuò)容的隊(duì)伍,同時(shí)sizeCtl+1,此時(shí)sizeCtl代表擴(kuò)容的線程數(shù)量
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
//設(shè)置sizeCtl為負(fù)數(shù),代表自己是第一個(gè)擴(kuò)容的線程,CAS操作保證只有一個(gè)線程安全
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null); //null代表首次擴(kuò)容
}
}
}
/**
* tab, 舊table
* nextTAB 擴(kuò)容后的table
*/
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//每個(gè)線程負(fù)責(zé)遷移table一個(gè)區(qū)間段的桶的個(gè)數(shù),最少是16個(gè)
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
//首次擴(kuò)容
if (nextTab == null) { // initiating
try {
//創(chuàng)建新的table,默認(rèn)n*2
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; //要遷移的桶的個(gè)數(shù)
}
int nextn = nextTab.length;
//創(chuàng)建擴(kuò)容節(jié)點(diǎn),當(dāng)某個(gè)桶遷移完成后,放入table[i],標(biāo)記桶擴(kuò)容完成
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true; //為true,表示當(dāng)前桶遷移完成,可以繼續(xù)處理下一個(gè)桶
boolean finishing = false; // 最后一個(gè)數(shù)據(jù)遷移的線程將該值置為true,進(jìn)行擴(kuò)容的收尾工作
//i桶索引,bound就是線程要處理的另一個(gè)區(qū)間邊界
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
//定位本輪處理區(qū)間【transferIndex-1,transferIndex-stride】
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;
}
}
//Case1,最后一個(gè)遷移線程或者是線程出現(xiàn)了沖突,導(dǎo)致了i<0
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) { //遷移完成
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
//擴(kuò)容線程數(shù)減1,當(dāng)前線程任務(wù)已執(zhí)行完成
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
//判斷是否最后一個(gè)遷移線程,不是則退出
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
//最后一個(gè)線程,還原i值,重新進(jìn)行檢查,是否全部遷移完成,應(yīng)該所有桶都是ForwardingNode
i = n; // recheck before commit
}
}
// CASE2:舊桶本身為null,不用遷移,放一個(gè)ForwardingNode
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//CASE3:該舊桶已經(jīng)遷移完成,直接跳過(guò),hash==moved 代表ForwardingNode
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// CASE4:該舊桶未遷移完成,進(jìn)行數(shù)據(jù)遷移,加鎖
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) { //桶是鏈表,遷移鏈表
/**
* 下面的過(guò)程會(huì)將舊桶中的鏈表分成兩部分:ln鏈和hn鏈
* ln鏈會(huì)插入到新table的槽i中,hn鏈會(huì)插入到新table的槽i+n中
*/
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);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln); // ln鏈表存入新桶的索引i位置
setTabAt(nextTab, i + n, hn); // hn鏈表存入新桶的索引i+n位置
setTabAt(tab, i, fwd); // 設(shè)置ForwardingNode占位
advance = true; // 表示當(dāng)前舊桶的結(jié)點(diǎn)已遷移完畢
}
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;
/**
* 先以鏈表方式遍歷,復(fù)制所有結(jié)點(diǎn),然后根據(jù)高低位組裝成兩個(gè)鏈表;
* 然后看下是否需要進(jìn)行紅黑樹轉(zhuǎn)換,最后放到新table對(duì)應(yīng)的桶中
*/
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;
}
}
// 判斷是否需要進(jìn)行 紅黑樹 <-> 鏈表 的轉(zhuǎn)換
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);// 設(shè)置ForwardingNode占位
advance = true; // 表示當(dāng)前舊桶的結(jié)點(diǎn)已遷移完畢
}
}
}
}
}
}
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。