1.引言
網(wǎng)上已經(jīng)有很多關(guān)于ConcurrentHashMap1.8源碼的解析，像putval()，get()等方法的源碼也不是很復(fù)雜，在這就不再贅述了。但是很多文章的tryPresize()擴(kuò)容方法講的晦澀難懂，我今天就講講我對(duì)tryPresize()方法的理解
2.源碼解析
首先，tryPresize()方法是在樹(shù)化桶的鏈表時(shí)調(diào)用的，解析見(jiàn)注解
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
//當(dāng)某個(gè)桶個(gè)節(jié)點(diǎn)數(shù)大于，但table[]的長(zhǎng)度小于最小的長(zhǎng)度時(shí)（默認(rèn)64）
// 進(jìn)行擴(kuò)容，調(diào)整某個(gè)桶中結(jié)點(diǎn)數(shù)量過(guò)多的問(wèn)題
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)TREEIFY_THRESHOLD
tryPresize(n << 1);
......省略
}
接下來(lái)看看tryPresize()方法
private final void tryPresize(int size) {
//size在傳入之前就已經(jīng)翻倍了，最終c是一個(gè)大于等于（size * 1.5 + 1）的2的冪次方數(shù)
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
//此時(shí)的sizeCtl是cap * 0.75，擴(kuò)容閾值
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
//如果此時(shí)tab為空，則進(jìn)行初始化，將sizeCtl設(shè)為-1
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
//sc = n * 0.75
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
//tab == table說(shuō)明還沒(méi)開(kāi)始遷移節(jié)點(diǎn)
else if (tab == table) {
int rs = resizeStamp(n);
//開(kāi)始遷移原tab[] 中的數(shù)據(jù)，此時(shí)將sizeCtl設(shè)置為一個(gè)很大的負(fù)值，(rs << RESIZE_STAMP_SHIFT) + 2)必為一個(gè)負(fù)值
if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
//第一個(gè)發(fā)起遷移的線程，傳入nextTable為null
transfer(tab, null);
}
}
}
在說(shuō)明transfer()方法前，先說(shuō)明一下helpTransfer()方法,跟中該方法在源碼中的使用，發(fā)現(xiàn)只有在桶的頭節(jié)點(diǎn)的hash值為Moved時(shí)才會(huì)調(diào)用，功能是幫助遷移節(jié)點(diǎn)
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
//只有f的hash為MOVED，才會(huì)執(zhí)行該方法，說(shuō)明f節(jié)點(diǎn)是ForwardingNode
//如果nextTable為null,則表示遷移完成了，詳見(jiàn)transfer()
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
//每有一個(gè)線程來(lái)幫助遷移，sizeCtl就+1，初始值為(rs << RESIZE_STAMP_SHIFT) + 2)（ps:在tryPresize()設(shè)置），之后再transfer中會(huì)用到
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
弄明白上面幾個(gè)方法邏輯的同學(xué)恭喜你，可以挑戰(zhàn)最晦澀的transfer()方法啦，不多說(shuō)，上code,巨長(zhǎng)，不過(guò)不要被嚇到，我已經(jīng)寫(xiě)明注釋了
//該方法通過(guò)全局的transferIndex來(lái)控制每個(gè)線程的遷移任務(wù)
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
//n為舊tab的長(zhǎng)度，stride為步長(zhǎng)(就是每個(gè)線程遷移的節(jié)點(diǎn)數(shù))
int n = tab.length, stride;
//單核步長(zhǎng)為1，多核為（n>>>3）/ NCPU,最小值為16
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
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為全局屬性
nextTable = nextTab;
//transferIndex也為全局屬性，用于控制遷移位置
transferIndex = n;
}
int nextn = nextTab.length;
//ForwardingNode是正在被遷移的Node，它的key，value，next都為null
//hash為MOVED，其中有個(gè)nextTable屬性指向新tab[]
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
//advance為true，可以繼續(xù)遷移下一個(gè)節(jié)點(diǎn)，false則停止遷移
boolean advance = true;
//是否結(jié)束遷移
boolean finishing = false; // to ensure sweep before committing nextTab
//i是當(dāng)前遷移位置的索引，bound是遷移的邊界，是從后往前的順序
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
//while循環(huán)遷移的--（減減）條件，第一個(gè)條件一直為true，finishing為true則遷移任務(wù)結(jié)束
if (--i >= bound || finishing)
advance = false;
//transferIndex（上一次遷移的邊界）賦值給nextIndex（必執(zhí)行），這里transferIndex一旦小于等于0
//則說(shuō)明原數(shù)組的所有位置的遷移都有相應(yīng)的線程去處理了，該線程可以不用遷移了
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//將nextBound賦值給transferIndex，nextBound = nextIndex - stride（上一個(gè)邊界減去步長(zhǎng)）
//i = nextIndex - 1（上一個(gè)邊界-1變成開(kāi)始遷移的位置）
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
//i < 0說(shuō)明所有遷移任務(wù)完成了
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
//所有遷移完成，將nextTable設(shè)為空，sizeCtl為新tab.length * 0.75
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
//該線程完成遷移，sizeCtl - 1，對(duì)應(yīng)之前helpTransfer()中+1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
//不相等說(shuō)明還有其他線程沒(méi)完成遷移，該線程結(jié)束任務(wù)
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
//如果相等，則說(shuō)明說(shuō)有線程都完成任務(wù)了，設(shè)置finish為true
finishing = advance = true;
i = n; // recheck before commit
}
}
//如果舊tab[i]為null，則放入ForwardingNode
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//如果該節(jié)點(diǎn)為ForwardingNode，則說(shuō)明已經(jīng)被遷移過(guò)了，就可以開(kāi)始遷移下一個(gè)節(jié)點(diǎn)了
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
//遷移開(kāi)始加鎖，這部分和1.8HashMap差不多，將一條鏈表拆分成兩條
//建議去看看1.8HashMap的擴(kuò)容代碼，好懂一點(diǎn)
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
//fh >= 0,說(shuō)明是鏈表結(jié)構(gòu)
//這個(gè)涉及到spread()方法，得到的hash值最高位必為0，則是正數(shù)
if (fh >= 0) {
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);
setTabAt(nextTab, i + n, hn);
//將該位置放入ForwardingNode
setTabAt(tab, i, fwd);
advance = true;
}
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;
}
}
//一分為二后如果節(jié)點(diǎn)數(shù)小于樹(shù)化閾值，則將紅黑樹(shù)轉(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);
//將該位置放入ForwardingNode
setTabAt(tab, i, fwd);
//advance設(shè)置為true，說(shuō)明該位置的遷移已經(jīng)完成了
advance = true;
}
}
}
}
}
}
要是以上注釋都看懂了，那么對(duì)于tryPresize()和transfer()的執(zhí)行邏輯也就大概明白了，要是有錯(cuò)誤或者不明白的地方，歡迎留言討論
