目錄
1、addCount
2、tryPresize / helpTransfer
3、transfer
4、remove / replace / replaceAll / clear
5、get / getOrDefault
6、compute
7、merge
8、Traverser / keys / elements
9、總結
本篇部落格繼續上一篇《Java8 ConcurrentHashMap（一） 源碼解析》講解ConcurrentHashMap的擴容，元素替換和查找等方法的實作。
1、addCount
addCount用于增加鍵值對個數，如果check大于1，則檢查目前是否需要擴容，如果需要則擴容。
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null || 如果counterCells不為null，該屬性預設為null
//如果counterCells為null，則将baseCount原子加x，baseCount預設是0，如果修改失敗進入if分支
!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 || //如果as未初始化
(a = as[ThreadLocalRandom.getProbe() & m]) == null || //目前線程對應的CounterCell未初始化
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { //設定對應CounterCell的value失敗
//初始化counterCells或者目前線程對應的CounterCell，修改對應CounterCell的value
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return; //不需要檢查負載率，則直接傳回
s = sumCount(); //計算目前的鍵值對個數
}
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;
//sc+1表示有一個新的線程進來了，退出時會減1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
//幫助轉移擴容前數組元素中的節點到擴容後的數組元素中
transfer(tab, nt);
}
//rs << RESIZE_STAMP_SHIFT) + 2算出來的是一個負值，表示準備執行擴容
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2)) //cas修改成功，由目前線程負責擴容
//執行擴容
transfer(tab, null);
s = sumCount();
}
}
}
//修改目前線程對應的CounterCell的value，加上x
//如果目前線程的probe未初始化，則初始化，
//如果counterCells未初始化或者目前線程對應的CounterCell未初始化則初始化
//如果counterCells數組的長度小于CPU個數則擴容
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
if ((h = ThreadLocalRandom.getProbe()) == 0) {
//目前線程的probe未初始化，則強制初始化probe
ThreadLocalRandom.localInit();
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
if ((as = counterCells) != null && (n = as.length) > 0) {
//counterCells已初始化
if ((a = as[(n - 1) & h]) == null) {
//目前線程對應的CounterCell未初始化
if (cellsBusy == 0) { // 如果未加鎖
CounterCell r = new CounterCell(x); // Optimistic create
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { //擷取鎖，cas加鎖，隻有一個線程操作成功
boolean created = false;
try { //成功加鎖後，再次檢查目前線程對應的CounterCell是否為null
CounterCell[] rs; int m, j;
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
//如果為nul，則指派
rs[j] = r;
created = true;
}
} finally {
cellsBusy = 0; //釋放鎖，該變量是volatile，可保證對其他CPU立即可見
}
if (created)
break; //建立了一個CounterCell則終止循環
continue; //再次檢查時，對應的CounterCell不為null，則繼續下一次循環
}//如果搶占鎖失敗，繼續下一次for循環
}//如果鎖被占用了
collide = false;
}
//目前線程對應的CounterCell已初始化
else if (!wasUncontended) //如果是wasUncontended，将其置為true，然後通過advanceProbe重新hash
wasUncontended = true;
//wasUncontended為true
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) //修改value成功，終止循環
break;
else if (counterCells != as || n >= NCPU) //counterCells擴容了，發生變更
collide = false; // At max size or stale
else if (!collide) //collide為false後，置為true，通過advanceProbe重新hash
collide = true;
//如果counterCells沒變，n小于NCPU，則進入此分支擴容
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { //加鎖成功
try {
if (counterCells == as) {//再次校驗counterCells沒有變更
CounterCell[] rs = new CounterCell[n << 1]; //擴容一倍
for (int i = 0; i < n; ++i) //将原來的CounterCell複制到新的數組中
rs[i] = as[i];
counterCells = rs;
}
} finally {
cellsBusy = 0; //釋放鎖
}
collide = false;
continue; // Retry with expanded table
}
h = ThreadLocalRandom.advanceProbe(h);
} //外層if結束
//counterCells未初始化
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { //未加鎖，嘗試加鎖成功
boolean init = false;
try { // Initialize table
if (counterCells == as) { //再次檢查counterCells未初始化
//初始化
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x); //指派
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0;
}
if (init)
break; //已完成初始化，則終止循環
}
//上述else分支嘗試加鎖失敗，則原子修改baseCount
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
} //for循環結束
}
//擷取目前總的鍵值對個數
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
//将baseCount同各CounterCell的value累加
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
static final int resizeStamp(int n) {
//RESIZE_STAMP_BITS的值是16
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
2、tryPresize / helpTransfer
tryPresize會判斷table是否初始化，如果未初始化則完成初始化，接着判斷容量是否充足，如果不足則執行擴容，擴容的邏輯跟上面的addCount一緻。helpTransfer方法會判斷目前Map是否正在擴容，如果在擴容且有未配置設定的轉移任務，則會調用transfer方法幫忙轉移老數組中的節點到擴容後的新數組中。
private final void tryPresize(int size) {
//根據size計算對應的容量，如果找過MAXIMUM_CAPACITY的一半，則為MAXIMUM_CAPACITY
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
//如果未擴容
Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {
//如果數組未初始化，此時sc記錄了初始容量，取sc和c的最大值
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //原子的修改為-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，鍵值對個數超過此值則擴容
sizeCtl = sc;
}
}
}
//如果table已初始化，如果目前Map容量足夠或者達到最大容量了，終止循環
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) { //容量不夠，可以繼續擴容，校驗table是否變更
//resizeStamp和下面的RESIZE_STAMP_SHIFT配合使用，計算出一個負值
int rs = resizeStamp(n);
if (sc < 0) {
//如果正在擴容
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
//上述條件成立表示轉移的任務已配置設定完了或者已擴容完成
break;
//sc+1表示有一個新的線程進來了，退出時會減1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
//幫助轉移老數組中的元素到擴容後的新數組中
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2)) //sc成功cas成負值
//由目前線程負責擴容
transfer(tab, null);
}
}
}
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
//如果f是有效的ForwardingNode
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; //所有轉移任務已配置設定
//sc+1，表示目前線程會幫助轉移老數組元素中的節點
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
//如果擴容已完成
return nextTab;
}
return table;
}
3、transfer
transfer方法就是執行擴容的核心了，擴容時會将原來的數組切分成多個段，每個調用transfer方法的線程會配置設定其中的一段，然後周遊其中的數組元素，如果數組元素為null，則将其初始化成ForwardingNode表示該數組元素正在遷移的過程中，不能往裡面插入新節點；如果數組元素的hash值是MOVED表示已經處理過了；如果是hash值大于0，表示一個連結清單；否則就是一顆紅黑樹。無論是連結清單還是紅黑樹，都需要将節點的hash值與原來的容量重新計算，因為原來的容量都是2的整數次幂，是以計算結果是0或者1，就将計算結果是0和是1的節點分開，構成一個新的連結清單或者一顆新的紅黑樹，計算結果是0的則放在原來的位置不變，計算結果是1的則放在目前數組元素的索引加上原來容量對應的索引處。當某個線程處理完配置設定該線程的所有數組元素時就會重新申請一個新的段，如果都配置設定完了，則退出；最後一個退出的線程會負責将擴容後的新數組指派給table并重新計算下一次擴容的門檻值。注意當某個數組元素中的節點都被轉移後會将其置為ForwardingNode。注意在轉移某個數組元素中的節點時，老數組中的節點和連結清單關系都未發生變更，都是利用原來節點的屬性重新建立了一個新節點，新節點構成了一個新連結清單或者新紅黑樹，等所有節點都轉移完成才會将老數組元素置為ForwardingNode，該元素原來的連結清單或者紅黑樹還是沒變，即擴容期間是允許其他線程并行的查找的。如果查找時發現數組數組是ForwardingNode，則會在擴容的新數組中查找。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//如果是多核的，stride等于n/(8*NCPU),如果結果低于MIN_TRANSFER_STRIDE，則為MIN_TRANSFER_STRIDE
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) {
//因為記憶體不足導緻數組配置設定失敗，此時并沒有抛出異常終止程序，而是捕獲了
//将觸發擴容的門檻值設定為int的最大值，避免再次觸發擴容
sizeCtl = Integer.MAX_VALUE;
return;
}
//新數組配置設定成功，儲存新數組和原數組的長度
nextTable = nextTab;
transferIndex = n;
}
//如果nextTab不為null則直接進入下面的邏輯
int nextn = nextTab.length;
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;
//通過while循環計算i和bound
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing) //i減一後大于等于bound則繼續處理i對應的數組元素，不用重新配置設定一個stride範圍的數組元素
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1; //所有的轉移任務都配置設定完了
advance = false;
}
else if (U.compareAndSwapInt //cas修改transferIndex
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
//計算bound和i，将advance置為false，退出while循環
//下一次for循環時就進入上面的if分支，直到i減1小于bound後又會重新進入此else if分支
//這裡實際是将i到bound之間的數組元素配置設定給目前線程，由目前線程負責轉移這些數組元素中包含的節點
//如果有其他線程進來，因為transferIndex已經cas修改過了就會配置設定另外一個stride範圍的數組元素
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
} //while結束
//i小于0
if (i < 0 || i >= n || i + n >= nextn) {
//所有任務已配置設定或者目前線程配置設定的任務已執行完成
int sc;
if (finishing) {
//如果已經完成擴容
nextTable = null;
table = nextTab;
//n*2-n/2，結果就是2n的四分之三
sizeCtl = (n << 1) - (n >>> 1);
return;
}
//有一個新的線程來并行執行transfer時會将sc加1，此時減1表示目前線程的任務執行完成
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
//還有其他線程未完成任務，直接退出，最後一個退出的線程負責将finishing置為true
return;
//如果上面的if條件不成立，即sc - 2與後面的值相等，說明其他并行執行transfer的線程已經退出
//整個擴容已完成，則将finishing = advance置為true
finishing = advance = true;
i = n; //重新for循環，下一次for循環時就進入是上面的if分支，修改table和sizeCtl
}
}
//i大于0且i小于n的，即i是擴容前的數組的某個索引
else if ((f = tabAt(tab, i)) == null) //如果對應的數組元素為null，将初始化成fwd
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED) //如果對應的數組元素不為null且狀态是MOVED
advance = true; // already processed
else {
//如果對應的數組元素狀态正常
synchronized (f) {
//加鎖成功
if (tabAt(tab, i) == f) { //再次檢查數組元素是否變更
Node<K,V> ln, hn;
if (fh >= 0) { //如果是正常的連結清單
//n是2的整數倍，計算出來的結果要麼是0，要麼是1
//擴容一倍後計算hash，計算結果是0的依然還是在原來的位置，計算結果是1的在原來的索引的基礎上加上原來的容量
int runBit = fh & n;
Node<K,V> lastRun = f;
//周遊f後面的節點，找到最後一個重新hash後不等于runBit的節點
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) { //如果b不等于runBit，更新runBit
runBit = b;
lastRun = p;
}
}
//ln就是 fh & n為0的節點構成的連結清單的頭元素，hn就是fh & n為1的節點構成的連結清單的頭元素
if (runBit == 0) {
ln = lastRun; //此時lastRun及其後面的多個節點fh & n都為0
hn = null;
}
else {
hn = lastRun; //此時lastRun及其後面的多個節點，fh & n都為1
ln = null;
}
//從f開始往後周遊直到lastRun，lastRun之後的多個節點其計算結果是一緻的，要麼是0，要麼是1，不用再次周遊
//注意此處數組元素中連結清單的節點和連結清單關系都未發生變更，即擴容時老數組還是可以支援查找的
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); //新節點插入到ln的前面
else
hn = new Node<K,V>(ph, pk, pv, hn); //新節點插入到hn的前面
}
//将ln對應的連結清單放到i
setTabAt(nextTab, i, ln);
//将hn對應的連結清單放到i+n
setTabAt(nextTab, i + n, hn);
//原數組索引為i的位置放上fwd
setTabAt(tab, i, fwd);
//重新計算i，處理原數組中下一個元素
advance = true;
}
else if (f instanceof TreeBin) { //如果是紅黑樹
TreeBin<K,V> t = (TreeBin<K,V>)f;
//lo是loTail連結清單的第一個節點
TreeNode<K,V> lo = null, loTail = null;
//ho是hiTail連結清單中的第一個節點
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
//從first開始往後周遊，first是最近才插入紅黑樹的節點
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
//建立一個新的TreeNode，此時next節點和父節點都是null
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
//插入到loTail的後面
if ((p.prev = loTail) == null)//loTail為空
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
//h& n等于1
//插入到hiTail的後面
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
//如果節點數量低于UNTREEIFY_THRESHOLD，則轉換成連結清單，否則轉換成紅黑樹
//untreeify通過lo或者hi的next屬性周遊
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t; //如果hc等于0，說明所有節點都在lo中，即不需要移動節點了，原來的紅黑樹可以不變
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
//将ln儲存到索引為i處
setTabAt(nextTab, i, ln);
//将hn儲存到索引為i+n處
setTabAt(nextTab, i + n, hn);
//原來的數組i處設定成fwd
setTabAt(tab, i, fwd);
//重新計算i，處理原數組中下一個元素
advance = true;
}
}
}//釋放鎖
}//else結束
} //for循環結束
}
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);
}
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
4、remove / replace / replaceAll / clear
//移除指定的key對應的鍵值對，傳回原來的value
public V remove(Object key) {
return replaceNode(key, null, null);
}
//移除key和value都相等的鍵值對，傳回true表示移除成功
public boolean remove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
return value != null && replaceNode(key, null, value) != null;
}
//将指定的key對應的鍵值對的value改成指定值，相當于put，傳回原來的值
public V replace(K key, V value) {
if (key == null || value == null)
throw new NullPointerException();
return replaceNode(key, value, null);
}
//将key和value都比對的鍵值對的value替換成newValue，傳回true表示替換成功
public boolean replace(K key, V oldValue, V newValue) {
if (key == null || oldValue == null || newValue == null)
throw new NullPointerException();
return replaceNode(key, newValue, oldValue) != null;
}
//用于替換所有的節點，替換過程中如果value發生變更會重試
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
if (function == null) throw new NullPointerException();
Node<K,V>[] t;
if ((t = table) != null) {
//建立一個周遊器
Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
//advance方法傳回下一個節點
for (Node<K,V> p; (p = it.advance()) != null; ) {
V oldValue = p.val;
for (K key = p.key;;) {
//計算新值
V newValue = function.apply(key, oldValue);
if (newValue == null)
throw new NullPointerException();
if (replaceNode(key, newValue, oldValue) != null ||
(oldValue = get(key)) == null)
//如果替換成功或者該key對應的值為null則終止内層for循環
//注意執行replaceNode時，該key對應的value可能發生變更，此replaceNode傳回null，get(key)不為null
//然後借助get(key)讀取了最新的value，通過内層for循環重試
break;
}
}
}
}
public void clear() {
long delta = 0L; // negative number of deletions
int i = 0;
Node<K,V>[] tab = table;
while (tab != null && i < tab.length) {
int fh;
Node<K,V> f = tabAt(tab, i);
if (f == null) //數組元素為空，處理下一個
++i;
else if ((fh = f.hash) == MOVED) { //正在擴容的過程中
tab = helpTransfer(tab, f);
i = 0; //擴容完成，從0開始重新清理
}
else {
synchronized (f) { //加鎖
if (tabAt(tab, i) == f) { //f未發生變更
//如果f是連結清單則p等于f，如果f是紅黑樹，則p等于first節點，紅黑樹内部維護的連結清單
Node<K,V> p = (fh >= 0 ? f :
(f instanceof TreeBin) ?
((TreeBin<K,V>)f).first : null);
//周遊連結清單，統計總的節點數
while (p != null) {
--delta;
p = p.next;
}
//數組元素置為null，連結清單中的節點沒有了數組元素的引用，會自動被GC回收掉
setTabAt(tab, i++, null);
}
}
}
}
if (delta != 0L)
//元素個數減少
addCount(delta, -1);
}
final V replaceNode(Object key, V value, Object cv) {
//計算key的hash值
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0 || //table未初始化，Map為空
(f = tabAt(tab, i = (n - 1) & hash)) == null) //對應的數組為null
break; //上述兩種情形下肯定沒有比對的元素，終止循環，傳回null
else if ((fh = f.hash) == MOVED)
//如果正在擴容中，幫助完成擴容，擴容未完成期間會一直進入此分支，不斷for循環，直到擴容完成
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
synchronized (f) { //加鎖
if (tabAt(tab, i) == f) { //檢查數組元素是否變更
if (fh >= 0) { //如果是連結清單
validated = true;
//從f開始往後周遊
for (Node<K,V> e = f, pred = null;;) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) { //hash值和key值相等，找到比對節點
V ev = e.val;
if (cv == null || cv == ev || //如果沒有指定cv或者ev等于cv
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
e.val = value; //替換成新值，不用移除
//value為null，移除該節點
else if (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break; //終止循環
}
pred = e;
//周遊下一個節點，如果為null則終止循環
if ((e = e.next) == null)
break;
}
}
else if (f instanceof TreeBin) { //如果是紅黑樹
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) { //通過根節點查找比對的節點
V pv = p.val;
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) { //如果cv為null或者cv等于pv
oldVal = pv;
if (value != null)
p.val = value; //重置val
//value為null，将該節點移除，該方法傳回true時是說明樹中節點數較少，需要将其轉換成連結清單
else if (t.removeTreeNode(p))
//将其轉成連結清單
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) { //如果查找過
if (oldVal != null) { //如果找到了目标節點
if (value == null)
addCount(-1L, -1); //如果是移除，則将計數減1
return oldVal; //傳回原來的值
}
break;
}
}
}//循環終止
return null;
}
5、get / getOrDefault
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//計算hash值
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//table已初始化且對應的數組元素非空，否則傳回null
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val; //hash值和key值相等，傳回目标節點的value
}
else if (eh < 0)
//如果是ForwardingNode，會在擴容後的新數組中查找
//如果是TreeBin，會在紅黑樹中查找
//如果是ReservationNode，則傳回null
return (p = e.find(h, key)) != null ? p.val : null;
//eh大于0的情形，周遊連結清單查找
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
//如果查找失敗傳回預設值，否則傳回比對key的value
public V getOrDefault(Object key, V defaultValue) {
V v;
return (v = get(key)) == null ? defaultValue : v;
}
6、compute
compute類有三個方法，compute，computeIfAbsent和computeIfPresent，compute包含後面兩者的邏輯，computeIfAbsent是跟指定key比對的鍵值對不存在時才調用remappingFunction，傳入的參數為null，如果存在則傳回原來的value；computeIfPresent是跟指定key比對的鍵值對存在時才調用remappingFunction，傳入的參數是原來的value，如果不存在則傳回null；compute是先查找比對的鍵值對，如果比對會使用原來的value調用remappingFunction，如果沒有比對的，會有null調用remappingFunction。調用remappingFunction後，傳回值不是null時，如果該節點已存在則需要更新value，如果不存在則插入新節點；如果傳回值是null，如果該節點已存在則删除該節點，最後都傳回remappingFunction的計算結果。
//如果找到了跟key比對的節點，則使用原來的value調用remappingFunction，否則使用null調用remappingFunction
//remappingFunction傳回null表示這個鍵值對需要被删除，傳回非null，表示這個鍵值對的value需要被更新，如果沒有該節點則put一個新節點
//最終傳回remappingFunction計算的結果
public V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (key == null || remappingFunction == null)
throw new NullPointerException();
//計算hash值
int h = spread(key.hashCode());
V val = null;
int delta = 0;
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0) //table未初始化，則初始化talbe
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { //對應的數組元素未初始化
Node<K,V> r = new ReservationNode<K,V>();
synchronized (r) {
if (casTabAt(tab, i, null, r)) { //數組元素置為ReservationNode
binCount = 1;
Node<K,V> node = null;
try {
if ((val = remappingFunction.apply(key, null)) != null) { //計算value
delta = 1;
node = new Node<K,V>(h, key, val, null); //建立一個新節點
}
} finally {
//更新數組元素
setTabAt(tab, i, node);
}
}
}
if (binCount != 0) //如果上面casTabAt成功，則終止循環，傳回val
break;
}
else if ((fh = f.hash) == MOVED) //正在擴容，幫忙完成擴容
tab = helpTransfer(tab, f);
else {
synchronized (f) { //加鎖
if (tabAt(tab, i) == f) { //校驗數組元素沒有變更，如果變更了，下一次for循環重新讀取
if (fh >= 0) { //如果是連結清單
binCount = 1;
for (Node<K,V> e = f, pred = null;; ++binCount) {
K ek;
if (e.hash == h &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
//找到比對的節點
val = remappingFunction.apply(key, e.val);
if (val != null)
e.val = val; //更新val
else {
//計算的val為空，則移除該節點
delta = -1;
Node<K,V> en = e.next;
if (pred != null)
pred.next = en;
else
setTabAt(tab, i, en);
}
break;
}
pred = e;
//周遊下一個節點，如果周遊到最後一個節點
if ((e = e.next) == null) {
val = remappingFunction.apply(key, null);
if (val != null) {
delta = 1;
//插入一個新節點
pred.next =
new Node<K,V>(h, key, val, null);
}
break;
}
}
}
else if (f instanceof TreeBin) { //如果是紅黑樹
binCount = 1;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
//找到目标節點
if ((r = t.root) != null)
p = r.findTreeNode(h, key, null);
else
p = null;
V pv = (p == null) ? null : p.val;
val = remappingFunction.apply(key, pv);
if (val != null) {
if (p != null)
p.val = val; //更新val
else {
//插入新節點
delta = 1;
t.putTreeVal(h, key, val);
}
}
//val為空且該節點存在
else if (p != null) {
delta = -1;
if (t.removeTreeNode(p)) //移除該節點，如果元素個數較少，則轉換成連結清單
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
if (binCount != 0) {
//如果是連結清單，binCount記錄了周遊的節點數，如果是紅黑樹binCount為1
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i); //超過門檻值，連結清單轉換成紅黑樹
break;
}
}
}//for循環結束
if (delta != 0) //要麼插入一個新節點，要麼删除原來的節點，更新總的鍵值對個數
addCount((long)delta, binCount);
return val;
}
//邏輯大體相同，不過隻有跟key比對的鍵值不存在才會調用mappingFunction，使用null來計算，如果傳回值不是null則插入一個新節點，最終傳回mappingFunction的計算結果
//如果找到了比對的鍵值對，則直接傳回原來的value
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
if (key == null || mappingFunction == null)
throw new NullPointerException();
int h = spread(key.hashCode());
V val = null;
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0) //初始化數組
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { //初始化數組元素
Node<K,V> r = new ReservationNode<K,V>();
synchronized (r) {
if (casTabAt(tab, i, null, r)) {
binCount = 1;
Node<K,V> node = null;
try {
if ((val = mappingFunction.apply(key)) != null)
node = new Node<K,V>(h, key, val, null);
} finally {
setTabAt(tab, i, node);
}
}
}
if (binCount != 0)
break;
}
else if ((fh = f.hash) == MOVED) //幫助擴容
tab = helpTransfer(tab, f);
else {
boolean added = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { //連結清單
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek; V ev;
if (e.hash == h &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
val = e.val;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
//周遊完了，沒有找到比對節點才會調用mappingFunction
if ((val = mappingFunction.apply(key)) != null) {
added = true;
pred.next = new Node<K,V>(h, key, val, null);
}
break;
}
}
}
else if (f instanceof TreeBin) { //紅黑樹
binCount = 2;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(h, key, null)) != null)
val = p.val;
else if ((val = mappingFunction.apply(key)) != null) {
added = true;
t.putTreeVal(h, key, val);
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (!added) //找到了比對的節點，不需要增加總的鍵值對個數
return val;
break;
}
}
}
if (val != null) //沒有找到比對的節點，新增了一個節點，鍵值對個數加1
addCount(1L, binCount);
return val;
}
//隻有存在比對key的鍵值對才調用remappingFunction計算，使用原來的value計算，結果為非null則修改value，為null則移除該節點，最終傳回計算結果
//如果沒有比對的鍵值對，則傳回null
public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (key == null || remappingFunction == null)
throw new NullPointerException();
int h = spread(key.hashCode());
V val = null;
int delta = 0;
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0) //初始化數組
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) //對應數組元素為null，直接傳回null
break;
else if ((fh = f.hash) == MOVED) //幫助擴容
tab = helpTransfer(tab, f);
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { //連結清單
binCount = 1;
for (Node<K,V> e = f, pred = null;; ++binCount) {
K ek;
if (e.hash == h &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
//隻有找到比對節點才計算
val = remappingFunction.apply(key, e.val);
if (val != null)
e.val = val;
else {
delta = -1;
Node<K,V> en = e.next;
if (pred != null)
pred.next = en;
else
setTabAt(tab, i, en);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
else if (f instanceof TreeBin) { //紅黑樹
binCount = 2;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(h, key, null)) != null) {
//比對到目标節點
val = remappingFunction.apply(key, p.val);
if (val != null)
p.val = val;
else {
delta = -1;
if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (binCount != 0)
break;
}
}
if (delta != 0)
addCount((long)delta, binCount);
return val;
}
7、merge
merge的邏輯跟compute基本一緻，差別在于如果沒有跟key的鍵值對，會直接使用value插入一個新的鍵值對，而compute會使用null算一次，如果結果不為null才插入一個新的鍵值對。另外如果比對時，會把比對的鍵值對的val和參數中的value都傳給remappingFunction計算，計算結果為null則删除節點，不為null則更新val。
public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
if (key == null || value == null || remappingFunction == null)
throw new NullPointerException();
int h = spread(key.hashCode());
V val = null;
int delta = 0;
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0) //初始化數組
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) { //初始化數組元素，如果cas失敗則通過下一次for循環修改
delta = 1;
val = value;
break;
}
}
else if ((fh = f.hash) == MOVED) //幫助擴容
tab = helpTransfer(tab, f);
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { //連結清單
binCount = 1;
for (Node<K,V> e = f, pred = null;; ++binCount) {
K ek;
if (e.hash == h &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
val = remappingFunction.apply(e.val, value);
if (val != null)
e.val = val; //更新val
else {
//val為空，删除鍵值對
delta = -1;
Node<K,V> en = e.next;
if (pred != null)
pred.next = en;
else
setTabAt(tab, i, en);
}
break;
}
pred = e;
if ((e = e.next) == null) {
//沒有找到比對鍵值對，插入一個新節點
delta = 1;
val = value;
pred.next =
new Node<K,V>(h, key, val, null);
break;
}
}
}
else if (f instanceof TreeBin) { //紅黑樹
binCount = 2;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r = t.root;
TreeNode<K,V> p = (r == null) ? null :
r.findTreeNode(h, key, null);
//沒有比對的節點，val等于value
val = (p == null) ? value :
remappingFunction.apply(p.val, value);
if (val != null) {
if (p != null)
p.val = val; //更新value
else {
//插入新節點
delta = 1;
t.putTreeVal(h, key, val);
}
}
else if (p != null) {
delta = -1;
if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
break;
}
}
}
if (delta != 0)
addCount((long)delta, binCount);
return val;
}
8、Traverser / keys / elements
Traverser是周遊器的基類，其類繼承關系如下：
其中KeyIterator和ValueIterator就是上述兩個周遊方法的底層實作了，如下：
public Enumeration<K> keys() {
Node<K,V>[] t;
int f = (t = table) == null ? 0 : t.length;
return new KeyIterator<K,V>(t, f, 0, f, this);
}
public Enumeration<V> elements() {
Node<K,V>[] t;
int f = (t = table) == null ? 0 : t.length;
return new ValueIterator<K,V>(t, f, 0, f, this);
}
EntryIterator比較特殊是内部類EntrySetView傳回的周遊器，我們for循環周遊entrySet方法傳回的視圖時，底層調用的實際就是EntryIterator的方法，如下：
這幾個類的實作如下：
static class Traverser<K,V> {
Node<K,V>[] tab; //儲存鍵值對的數組
Node<K,V> next; //下一次next方法傳回的節點
TableStack<K,V> stack, spare; //spare表示空閑的TableStack連結清單，stack表示正在使用中的
int index; // 下一次周遊的數組索引
int baseIndex; // 初始值跟index一樣，會跟index一起改變
int baseLimit; // 儲存初始化時傳入的limit
final int baseSize; //儲存構造方法傳入的size
//通常index傳0，size和limit傳入數組的長度
Traverser(Node<K,V>[] tab, int size, int index, int limit) {
this.tab = tab;
this.baseSize = size;
this.baseIndex = this.index = index;
this.baseLimit = limit;
this.next = null;
}
final Node<K,V> advance() {
Node<K,V> e;
if ((e = next) != null)
e = e.next; //擷取下一個節點
for (;;) {
Node<K,V>[] t; int i, n; // must use locals in checks
if (e != null)
return next = e; //傳回next
//e的下一個節點為null了，需要周遊其他數組元素中的節點
if (baseIndex >= baseLimit || (t = tab) == null ||
(n = t.length) <= (i = index) || i < 0) //數組元素都周遊完了，傳回null
return next = null;
//i等于index，n是數組長度
if ((e = tabAt(t, i)) != null && e.hash < 0) {
//如果數組元素不為null，且hash值小于0
if (e instanceof ForwardingNode) { //如果正在擴容
tab = ((ForwardingNode<K,V>)e).nextTable; //更新tab
e = null;
//t是原來tab，i是目前周遊的數組索引，n是原tab的長度
pushState(t, i, n);
continue; //下一次for循環就周遊擴容後新數組中的節點了
}
else if (e instanceof TreeBin) //如果是紅黑樹則使用first節點周遊
e = ((TreeBin<K,V>)e).first;
else
e = null;
}
//如果正在擴容
if (stack != null)
//此時n是擴容後的數組的長度，第一次調用時會将index加上原數組的長度，下一次擷取周遊的數組元素時就會擷取該索引處的數組元素
//如果該處的數組元素周遊完成則再将index加上原數組的長度，就會進入while循環中，将index和table恢複成原來的，繼續周遊原數組中的下一個元素
//即遇到發生擴容的節點，就周遊擴容的後的新數組的index處，再周遊新數組的index+原數組長度處，然後接着周遊老數組中下一個元素
recoverState(n);
else if ((index = i + baseSize) >= n) //沒有擴容的情形下會進入此分支，因為baseSize初始時等于n，是以i+baseSize必然大于n
index = ++baseIndex; //baseIndex的初始值和index是一樣的，将baseIndex加1，周遊下一個元素
}
}
//如果spare始終為null，則建立新的節點并插入到stack連結清單的前面
//若幹spare不為null，則取出spare連結清單頭的節點初始化，然後插入到stack連結清單的前面
private void pushState(Node<K,V>[] t, int i, int n) {
TableStack<K,V> s = spare; // reuse if possible
if (s != null)
spare = s.next;
else
//spare為null，則建立一個新的TableStack
s = new TableStack<K,V>();
s.tab = t;
s.length = n;
s.index = i;
s.next = stack;
stack = s;
}
private void recoverState(int n) {
TableStack<K,V> s; int len;
//index表示已周遊的元素個數，stack的length表示擴容前的數組長度，n表示擴容後的數組長度
//第一次調用時index加原數組的長度，然後傳回，第二次調用時還是加上原數組的長度就滿足了while條件
while ((s = stack) != null && (index += (len = s.length)) >= n) {
n = len;
//恢複index和tab
index = s.index;
tab = s.tab;
//将s的tab置為null，将其插入到spare連結清單的前面
s.tab = null;
TableStack<K,V> next = s.next;
s.next = spare; // save for reuse
stack = next;//繼續周遊stack連結清單的下一個節點，正常stack隻有一個節點，因為出現ForwardingNode後就會周遊新數組了
spare = s;
}//while循環結束
//stack為null，退出循環後n等于原數組的長度，此時因為baseSize就等于n，是以if條件成立
if (s == null && (index += baseSize) >= n)
index = ++baseIndex; //index加1，周遊下一個數組元素
}
}
static class BaseIterator<K,V> extends Traverser<K,V> {
final ConcurrentHashMap<K,V> map; //關聯的Map
Node<K,V> lastReturned; //上一次傳回的節點
BaseIterator(Node<K,V>[] tab, int size, int index, int limit,
ConcurrentHashMap<K,V> map) {
super(tab, size, index, limit);
this.map = map;
advance(); //擷取下一個節點
}
public final boolean hasNext() { return next != null; }
public final boolean hasMoreElements() { return next != null; }
public final void remove() {
Node<K,V> p;
if ((p = lastReturned) == null)
throw new IllegalStateException();
lastReturned = null;
//通過replaceNode移除節點
map.replaceNode(p.key, null, null);
}
}
static final class KeyIterator<K,V> extends BaseIterator<K,V>
implements Iterator<K>, Enumeration<K> {
//注意子類的構造方法的入參的順序和父類不一緻，index和size的順序反了
KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
ConcurrentHashMap<K,V> map) {
//此處的index實際對應BaseIterator的size，size對應BaseIterator的index
super(tab, index, size, limit, map);
}
public final K next() {
Node<K,V> p;
if ((p = next) == null)
throw new NoSuchElementException();
K k = p.key; //傳回下一個節點的key
lastReturned = p;
advance(); //重新擷取下一個節點
return k;
}
public final K nextElement() { return next(); }
}
static final class ValueIterator<K,V> extends BaseIterator<K,V>
implements Iterator<V>, Enumeration<V> {
ValueIterator(Node<K,V>[] tab, int index, int size, int limit,
ConcurrentHashMap<K,V> map) {
super(tab, index, size, limit, map);
}
public final V next() {
Node<K,V> p;
if ((p = next) == null)
throw new NoSuchElementException();
V v = p.val; //傳回下一個節點的val
lastReturned = p;
advance(); //重新擷取下一個節點
return v;
}
public final V nextElement() { return next(); }
}
static final class EntryIterator<K,V> extends BaseIterator<K,V>
implements Iterator<Map.Entry<K,V>> {
EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
ConcurrentHashMap<K,V> map) {
super(tab, index, size, limit, map);
}
public final Map.Entry<K,V> next() {
Node<K,V> p;
if ((p = next) == null)
throw new NoSuchElementException();
K k = p.key;
V v = p.val;
lastReturned = p;
advance(); //擷取下一個節點
return new MapEntry<K,V>(k, v, map); //利用next節點的key和val傳回一個新的MapEntry
}
}
//MapEntry是一個簡單的資料結構
static final class MapEntry<K,V> implements Map.Entry<K,V> {
final K key; // non-null
V val; // non-null
final ConcurrentHashMap<K,V> map;
MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
this.key = key;
this.val = val;
this.map = map;
}
public K getKey() { return key; }
public V getValue() { return val; }
public int hashCode() { return key.hashCode() ^ val.hashCode(); }
public String toString() { return key + "=" + val; }
public boolean equals(Object o) {
Object k, v; Map.Entry<?,?> e;
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == val || v.equals(val)));
}
public V setValue(V value) {
if (value == null) throw new NullPointerException();
V v = val;
val = value;
map.put(key, value);
return v;
}
}
static final class TableStack<K,V> {
int length;
int index;
Node<K,V>[] tab;
TableStack<K,V> next;
}
9、總結
除上述常用的方法外，ConcurrentHashMap還提供了多個并行執行某個操作的方法，這些方法不是ConcurrentMap的接口方法，如下圖：
這些方法底層是通過ConcurrentHashMap定義的内部類來實作的，如下：
這些内部類都繼承CountedCompleter，該類繼承自ForkJoinTask，通過ForkJoinPool來并行執行，後面講解ForkJoin相關類的使用說明時會再來探讨這些方法的實作細節。現總結下 ConcurrentHashMap實作線程安全的要點：
- 無論是插入一個新的節點還是移除舊的節點或者修改一個已有節點的val，都會對該節點所屬的數組元素，即對應的連結清單頭或者TreeBin節點加鎖，直到修改結束才釋放鎖，一旦加鎖其他想要修改屬于同一個數組元素的節點的線程就必須等待前面的修改完成。如果修改的是紅黑樹，為了避免查找的結果不準确，還需要對紅黑樹加寫鎖，此時如果正在查找紅黑樹中的某個節點，會等待所有執行查找的線程釋放紅黑樹的讀鎖，會通過park将目前線程休眠或者自旋等待。
- 查找某個key值時不需要對數組元素加鎖，但是如果數組元素對應的是一顆紅黑樹，需要對紅黑樹加讀鎖，避免其他線程對紅黑樹的修改，這是因為修改後，紅黑樹為了保持平衡會移動節點的位置，有可能導緻某個已經存在的key查找不出來，讀鎖可以被多個線程同時擷取，必須等所有讀鎖都釋放了才能加寫鎖，才能修改紅黑樹中的節點。
- 在Map擴容時，ConcurrentHashMap會将原來的數組按照長度切割成多個段，每個線程占用其中的一個段，負責将其中的數組元素包含的節點轉移到擴容後的新數組中，當修改Map時如果發現對應的數組元素的hash值是MOVED，就認為目前正在擴容，會嘗試去申請一個段，如果所有的段都配置設定了，則自旋等待擴容完成，數組元素的hash值變成非MOVED，最後一個完成轉移任務的線程會負責将擴容後已經完成節點轉移的臨時數組設定成Map的有效數組。注意原數組中的數組元素及其節點關系都未發生變更，即此時其他線程可以繼續在原數組中周遊，直到感覺到了臨時數組被設定成新數組了。如果沒有線程通路原數組，原數組因為沒有根節點引用，就會整體被垃圾回收掉。
- 為了避免并行修改Map的鍵值對個數時出現誤差，同時保證性能，ConcurrentHashMap采用了類似于LongAdder的實作機制，将對鍵值對個數的修改壓力分散到多個CounterCell中，并行修改時通常一個線程命中一個CounterCell，最後将所有CounterCell的值累加起來即是實際的鍵值對總數。