免費(fèi)AI編程助手
ConcurrentHashMap 是 HashMap 的一個(gè)線程安全，支持高效并發(fā)的一個(gè)版本。下面，我們就通過 Java 中源代碼，來詳細(xì)地解析一下 ConcurrentHashMap 的內(nèi)容。
一、容器初始化
1、源碼分析
在jdk8的ConcurrentHashMap中一共有5個(gè)構(gòu)造方法，這四個(gè)構(gòu)造方法中都沒有對內(nèi)部的數(shù)組做初始化， 只是對一些變量的初始值做了處理
jdk8的ConcurrentHashMap的數(shù)組初始化是在第一次添加元素時(shí)完成
// 沒有維護(hù)任何變量的操作，如果調(diào)用該方法，數(shù)組長度默認(rèn)是16
public ConcurrentHashMap() {
}// 傳遞進(jìn)來一個(gè)初始容量，ConcurrentHashMap會基于這個(gè)值計(jì)算一個(gè)比這個(gè)值大的2的冪次方數(shù)作為初始容量
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));// 此處的初始容量計(jì)算結(jié)果為傳入的容量 + 傳入的容量的一半 + 1
this.sizeCtl = cap;
}注意，調(diào)用這個(gè)方法，得到的初始容量和HashMap以及jdk7的ConcurrentHashMap不同，即使你傳遞的是一個(gè)2的冪次方數(shù)，該方法計(jì)算出來的初始容量依然是比這個(gè)值大的2的冪次方數(shù)
// 調(diào)用四個(gè)參數(shù)的構(gòu)造
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}// 計(jì)算一個(gè)大于或者等于給定的容量值，該值是2的冪次方數(shù)作為初始容量
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}// 基于一個(gè)Map集合，構(gòu)建一個(gè)ConcurrentHashMap
// 初始容量為16
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}2、sizeCtl含義解釋
注意：以上這些構(gòu)造方法中，都涉及到一個(gè)變量
sizeCtl，這個(gè)變量是一個(gè)非常重要的變量，而且具有非常豐富的含義，它的值不同，對應(yīng)的含義也不一樣，這里我們先對這個(gè)變量不同的值的含義做一下說明，后續(xù)源碼分析過程中，進(jìn)一步解釋
sizeCtl為0，代表數(shù)組未初始化， 且數(shù)組的初始容量為16
sizeCtl為正數(shù)，如果數(shù)組未初始化，那么其記錄的是數(shù)組的初始容量，如果數(shù)組已經(jīng)初始化，那么其記錄的是數(shù)組的擴(kuò)容閾值
sizeCtl為-1，表示數(shù)組正在進(jìn)行初始化
sizeCtl小于0，并且不是-1，表示數(shù)組正在擴(kuò)容， -(1+n)，表示此時(shí)有n個(gè)線程正在共同完成數(shù)組的擴(kuò)容操作
3、其他屬性含義
代表整個(gè)哈希表
transient volatile Node<K,V>[] table;用于哈希表擴(kuò)容，擴(kuò)容完成后會被重置為null。
private transient volatile Node<K,V>[] nextTable;baseCount和counterCells一起保存著整個(gè)哈希表中存儲的所有的結(jié)點(diǎn)的個(gè)數(shù)總和。
private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;二、添加安全
1、源碼分析
1.1、添加元素put/putVal方法
public V put(K key, V value) {
return putVal(key, value, false);
}final V putVal(K key, V value, boolean onlyIfAbsent) {
// 如果有空值或者空鍵，直接拋異常
if (key == null || value == null) throw new NullPointerException();
// 基于key計(jì)算hash值，并進(jìn)行一定的擾動,這里計(jì)算的hash一定是正數(shù)，因?yàn)榕c7FFFFFFF進(jìn)行了位與運(yùn)算，負(fù)數(shù)的hash值另有他用
int hash = spread(key.hashCode());
// 記錄某個(gè)桶上元素的個(gè)數(shù)，如果超過8個(gè)(并且table長度>=64)，會轉(zhuǎn)成紅黑樹
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果數(shù)組還未初始化，先對數(shù)組進(jìn)行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 如果hash計(jì)算得到的桶位置沒有元素，利用cas將元素添加
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// cas+自旋（和外側(cè)的for構(gòu)成自旋循環(huán)），保證元素添加安全
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 如果hash計(jì)算得到的桶位置元素的hash值為MOVED(-1)，證明正在擴(kuò)容，那么協(xié)助擴(kuò)容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
// hash計(jì)算的桶位置元素不為空，且當(dāng)前沒有處于擴(kuò)容操作，進(jìn)行元素添加
V oldVal = null;
// 對當(dāng)前數(shù)組的第一個(gè)結(jié)點(diǎn)進(jìn)行加鎖，執(zhí)行添加操作，這里不僅保證了線程安全而且使得鎖的粒度相對較小
synchronized (f) {
if (tabAt(tab, i) == f) {
// 普通鏈表節(jié)點(diǎn)
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 鏈表的遍歷找到最后一個(gè)結(jié)點(diǎn)進(jìn)行尾插法(如果找到相同的key則會覆蓋)
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;
// 找到了最后一個(gè)結(jié)點(diǎn)，尾插法插入新結(jié)點(diǎn)在最后
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 樹節(jié)點(diǎn)，將元素添加到紅黑樹中
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;
}
}
}
}
if (binCount != 0) {
// 鏈表長度>=8，將鏈表轉(zhuǎn)成紅黑樹
if (binCount >= TREEIFY_THRESHOLD)
// (在該方法中會對table也就是數(shù)組長度進(jìn)行判斷，>=64時(shí)才會進(jìn)行轉(zhuǎn)樹，否則為數(shù)組擴(kuò)容)
treeifyBin(tab, i);
// 如果是重復(fù)鍵，直接將舊值返回
if (oldVal != null)
return oldVal;
break;
}
}
}
// 添加的是新元素，維護(hù)集合長度，并判斷是否要進(jìn)行擴(kuò)容操作
addCount(1L, binCount);
return null;
}通過以上源碼，我們可以看到，當(dāng)需要添加元素時(shí)，會針對當(dāng)前元素所對應(yīng)的桶位進(jìn)行加鎖操作，這樣一方面保證元素添加時(shí)，多線程的安全，同時(shí)對某個(gè)桶位加鎖不會影響其他桶位的操作，進(jìn)一步提升多線程的并發(fā)效率
1.2、數(shù)組初始化，initTable方法
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// cas+自旋，保證線程安全，對數(shù)組進(jìn)行初始化操作
while ((tab = table) == null || tab.length == 0) {
// 如果sizeCtl的值（-1）小于0，說明此時(shí)正在初始化， 讓出cpu
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// cas修改sizeCtl的值為-1，修改成功，進(jìn)行數(shù)組初始化，失敗，繼續(xù)自旋
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// double checking，防止重復(fù)初始化
if ((tab = table) == null || tab.length == 0) {
// sizeCtl為0，取默認(rèn)長度16，否則去sizeCtl的值
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
// 基于初始長度，構(gòu)建數(shù)組對象
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// 計(jì)算擴(kuò)容閾值，并賦值給sc
// n就是當(dāng)前數(shù)組的長度，當(dāng)初始化完成后，sc記錄的是下次需要擴(kuò)容的閾值
// n >>> 2 就相當(dāng)于 n / 4
// 所以 n - (n >>> 2) 就相當(dāng)于 n - n / 4 = n * 0.75，而0.75就是默認(rèn)的加載因子
sc = n - (n >>> 2);
}
} finally {
//將擴(kuò)容閾值，賦值給sizeCtl
sizeCtl = sc;
}
break;
}
}
return tab;
}2、圖解
2.1、put加鎖圖解
三、擴(kuò)容安全
1、源碼分析
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 如果是多cpu，那么每個(gè)線程劃分任務(wù)，最小任務(wù)量是16個(gè)桶位的遷移
// 如果是單cpu，則沒必要?jiǎng)澐? if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 如果是擴(kuò)容線程，此時(shí)新數(shù)組為null
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
// 兩倍擴(kuò)容創(chuàng)建新數(shù)組
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;
}
// 記錄新數(shù)組的末尾
int nextn = nextTab.length;
// 已經(jīng)遷移的桶位，會用這個(gè)節(jié)點(diǎn)占位（這個(gè)節(jié)點(diǎn)的hash值為-1——MOVED）
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 (advance) {
int nextIndex, nextBound;
// i記錄當(dāng)前正在遷移桶位的索引值
// bound記錄下一次任務(wù)遷移的開始桶位
// --i >= bound 成立表示當(dāng)前線程分配的遷移任務(wù)還沒有完成
if (--i >= bound || finishing)
advance = false;
// 沒有元素需要遷移 -- 后續(xù)會去將擴(kuò)容線程數(shù)減1，并判斷擴(kuò)容是否完成
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// 計(jì)算下一次任務(wù)遷移的開始桶位，并將這個(gè)值賦值給transferIndex
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
// 如果沒有更多的需要遷移的桶位，就進(jìn)入該if
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
//擴(kuò)容結(jié)束后，保存新數(shù)組，并重新計(jì)算擴(kuò)容閾值，賦值給sizeCtl
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 擴(kuò)容任務(wù)線程數(shù)減1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 判斷當(dāng)前所有擴(kuò)容任務(wù)線程是否都執(zhí)行完成
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// 所有擴(kuò)容線程都執(zhí)行完，標(biāo)識結(jié)束
finishing = advance = true;
i = n; // recheck before commit
}
}
// 當(dāng)前遷移的桶位沒有元素，直接在該位置添加一個(gè)fwd節(jié)點(diǎn)
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 當(dāng)前節(jié)點(diǎn)已經(jīng)被遷移
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// 當(dāng)前節(jié)點(diǎn)需要遷移，加鎖遷移，保證多線程安全
// 此處的遷移與hashmap類似
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
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);
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;
}
}
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;
}
}
}
}
}
}2、圖解
四、多線程擴(kuò)容效率改進(jìn)(協(xié)助擴(kuò)容)
多線程協(xié)助擴(kuò)容的操作會在兩個(gè)地方被觸發(fā)：
① 當(dāng)添加元素時(shí)，發(fā)現(xiàn)添加的元素對用的桶位為fwd節(jié)點(diǎn)，就會先去協(xié)助擴(kuò)容，然后再添加元素
② 當(dāng)添加完元素后，判斷當(dāng)前元素個(gè)數(shù)達(dá)到了擴(kuò)容閾值，此時(shí)發(fā)現(xiàn)sizeCtl的值小于0，并且新數(shù)組不為空，這個(gè)時(shí)候，會去協(xié)助擴(kuò)容
每當(dāng)有一個(gè)線程幫助擴(kuò)容時(shí)，sc就會+1，有一個(gè)線程擴(kuò)容結(jié)束時(shí)，sc就會-1，當(dāng)sc重新回到(rs << RESIZE_STAMP_SHIFT) + 2這個(gè)值時(shí)，代表當(dāng)前線程是最后一個(gè)擴(kuò)容的線程，則擴(kuò)容結(jié)束。
1、源碼分析
1.1、元素未添加，先協(xié)助擴(kuò)容，擴(kuò)容完后再添加元素
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
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) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 發(fā)現(xiàn)此處為fwd節(jié)點(diǎn)，協(xié)助擴(kuò)容，擴(kuò)容結(jié)束后，再循環(huán)回來添加元素
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 省略代碼final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
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;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
// 擴(kuò)容，傳遞一個(gè)不是null的nextTab
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}1.2、先添加元素，再協(xié)助擴(kuò)容
private final void addCount(long x, int check) {
// 省略代碼
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// 元素個(gè)數(shù)達(dá)到擴(kuò)容閾值
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
// sizeCtl小于0，說明正在執(zhí)行擴(kuò)容，那么協(xié)助擴(kuò)容
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}注意：擴(kuò)容的代碼都在transfer方法中，這里不再贅述
2、圖解
五、集合長度的累計(jì)方式
1、源碼分析
1.1、addCount方法
① CounterCell數(shù)組不為空，優(yōu)先利用數(shù)組中的CounterCell記錄數(shù)量
② 如果數(shù)組為空，嘗試對baseCount進(jìn)行累加，失敗后，會執(zhí)行fullAddCount邏輯
③ 如果是添加元素操作，會繼續(xù)判斷是否需要擴(kuò)容
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// 當(dāng)CounterCell數(shù)組不為空，則優(yōu)先利用數(shù)組中的CounterCell記錄數(shù)量
// 或者當(dāng)baseCount的累加操作失敗，會利用數(shù)組中的CounterCell記錄數(shù)量
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
// 標(biāo)識是否有多線程競爭
boolean uncontended = true;
// 當(dāng)as數(shù)組為空
// 或者當(dāng)as長度為0
// 或者當(dāng)前線程對應(yīng)的as數(shù)組桶位的元素為空
// 或者當(dāng)前線程對應(yīng)的as數(shù)組桶位不為空，但是累加失敗
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
// 以上任何一種情況成立，都會進(jìn)入該方法，傳入的uncontended是false
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
// 計(jì)算元素個(gè)數(shù)
s = sumCount();
}
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// 當(dāng)元素個(gè)數(shù)達(dá)到擴(kuò)容閾值
// 并且數(shù)組不為空
// 并且數(shù)組長度小于限定的最大值
// 滿足以上所有條件，執(zhí)行擴(kuò)容
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
// 這個(gè)是一個(gè)很大的正數(shù)
int rs = resizeStamp(n);
// sc小于0，說明有線程正在擴(kuò)容，那么會協(xié)助擴(kuò)容
if (sc < 0) {
// 擴(kuò)容結(jié)束或者擴(kuò)容線程數(shù)達(dá)到最大值或者擴(kuò)容后的數(shù)組為null或者沒有更多的桶位需要轉(zhuǎn)移，結(jié)束操作
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 擴(kuò)容線程加1，成功后，進(jìn)行協(xié)助擴(kuò)容操作
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// 協(xié)助擴(kuò)容，newTable不為null
transfer(tab, nt);
}
// 沒有其他線程在進(jìn)行擴(kuò)容，達(dá)到擴(kuò)容閾值后，給sizeCtl賦了一個(gè)很大的負(fù)數(shù)
// 1+1=2 --》 代表此時(shí)有一個(gè)線程在擴(kuò)容
// rs << RESIZE_STAMP_SHIFT)是一個(gè)很大的負(fù)數(shù)
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// 擴(kuò)容，newTable為null
transfer(tab, null);
s = sumCount();
}
}
}1.2、fullAddCount方法
① 當(dāng)CounterCell數(shù)組不為空，優(yōu)先對CounterCell數(shù)組中的CounterCell的value累加
② 當(dāng)CounterCell數(shù)組為空，會去創(chuàng)建CounterCell數(shù)組，默認(rèn)長度為2，并對數(shù)組中的CounterCell的value累加
③ 當(dāng)數(shù)組為空，并且此時(shí)有別的線程正在創(chuàng)建數(shù)組，那么嘗試對baseCount做累加，成功即返回，否則自旋
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
// 獲取當(dāng)前線程的hash值
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
// 標(biāo)識是否有沖突，如果最后一個(gè)桶不是null，那么為true
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
// 數(shù)組不為空，優(yōu)先對數(shù)組中CouterCell的value累加
if ((as = counterCells) != null && (n = as.length) > 0) {
// 線程對應(yīng)的桶位為null
if ((a = as[(n - 1) & h]) == null) {
if (cellsBusy == 0) { // Try to attach new Cell
// 創(chuàng)建CounterCell對象
CounterCell r = new CounterCell(x); // Optimistic create
// 利用CAS修改cellBusy狀態(tài)為1，成功則將剛才創(chuàng)建的CounterCell對象放入數(shù)組中
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
// 桶位為空， 將CounterCell對象放入數(shù)組
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
rs[j] = r;
// 表示放入成功
created = true;
}
} finally {
cellsBusy = 0;
}
if (created) //成功退出循環(huán)
break;
// 桶位已經(jīng)被別的線程放置了已給CounterCell對象，繼續(xù)循環(huán)
continue; // Slot is now non-empty
}
}
collide = false;
}
// 桶位不為空，重新計(jì)算線程hash值，然后繼續(xù)循環(huán)
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
// 重新計(jì)算了hash值后，對應(yīng)的桶位依然不為空，對value累加
// 成功則結(jié)束循環(huán)
// 失敗則繼續(xù)下面判斷
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;
// 數(shù)組被別的線程改變了，或者數(shù)組長度超過了可用cpu大小，重新計(jì)算線程hash值，否則繼續(xù)下一個(gè)判斷
else if (counterCells != as || n >= NCPU)
collide = false; // At max size or stale
// 當(dāng)沒有沖突，修改為有沖突，并重新計(jì)算線程hash，繼續(xù)循環(huán)
else if (!collide)
collide = true;
// 如果CounterCell的數(shù)組長度沒有超過cpu核數(shù)，對數(shù)組進(jìn)行兩倍擴(kuò)容
// 并繼續(xù)循環(huán)
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
if (counterCells == as) {// Expand table unless stale
CounterCell[] rs = new CounterCell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
counterCells = rs;
}
} finally {
cellsBusy = 0;
}
collide = false;
continue; // Retry with expanded table
}
h = ThreadLocalRandom.advanceProbe(h);
}
// CounterCell數(shù)組為空，并且沒有線程在創(chuàng)建數(shù)組，修改標(biāo)記，并創(chuàng)建數(shù)組
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0;
}
if (init)
break;
}
// 數(shù)組為空，并且有別的線程在創(chuàng)建數(shù)組，那么嘗試對baseCount做累加，成功就退出循環(huán)，失敗就繼續(xù)循環(huán)
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}2、圖解
fullAddCount方法中，當(dāng)as數(shù)組不為空的邏輯圖解
六、集合長度獲取
1、源碼分析
1.1、size方法
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}1.2、sumCount方法
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
// 獲取baseCount的值
long sum = baseCount;
if (as != null) {
// 遍歷CounterCell數(shù)組，累加每一個(gè)CounterCell的value值
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}注意：這個(gè)方法并不是線程安全的
七、get方法
這個(gè)就很簡單了，獲得hash值，然后判斷存在與否，遍歷鏈表即可，注意get沒有任何鎖操作！
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 計(jì)算key的hash值
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) { // 表不為空并且表的長度大于0并且key所在的桶不為空
if ((eh = e.hash) h) { // 表中的元素的hash值與key的hash值相等
if ((ek = e.key) key || (ek != null && key.equals(ek))) // 鍵相等
// 返回值
return e.val;
}
else if (eh < 0) // 是個(gè)TreeBin hash = -2
// 在紅黑樹中查找,因?yàn)榧t黑樹中也保存這一個(gè)鏈表順序
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) { // 對于結(jié)點(diǎn)hash值大于0的情況鏈表
if (e.hash h &&
((ek = e.key) key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}到此這篇關(guān)于 Java 8 中的ConcurrentHashMap源碼分析的文章就介紹到這了,想要了解更多相關(guān) Java 8 的內(nèi)容請搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，也希望大家以后多多支持！
