Java源碼重讀之ConcurrentHashMap詳解
如果你沒(méi)有閱讀過(guò) Java 源碼重讀系列之 HashMap 這篇文章的話，建議你先讀一下。以下所有內(nèi)容的前提是你已閱讀過(guò)以上的文章。
另外，凡是涉及到多線程、并發(fā)的東西從來(lái)就沒(méi)有簡(jiǎn)單的，所以這次我們很難講清楚 ConcurrentHashMap 中的所有內(nèi)容，只能聚焦到以下幾個(gè)內(nèi)容
- ConcurrentHashMap 的 get 操作
- ConcurrentHashMap 的 put 操作
- ConcurrentHashMap 的 resize() 操作
- ConcurrentHashMap 是如何保證線程安全的
如果你想要了解的內(nèi)容不在以上范圍內(nèi)，那就不用繼續(xù)閱讀了，以免浪費(fèi)時(shí)間~
0. 第一個(gè)屬性 serialPersistentFields
因?yàn)?ConcurrentHashMap 的邏輯比較復(fù)雜，所以我們直接從 serialPersistentFields 屬性說(shuō)起，它之前的這些屬性等用到的時(shí)候我們?cè)倏淳秃昧?，你只要知?這個(gè)屬性之前還有一堆固定的屬性就好了。
serialPersistentFields 屬性是一個(gè) ObjectStreamField 的數(shù)組，而且默認(rèn)添加了三個(gè)元素。
private static final ObjectStreamField[] serialPersistentFields = {
new ObjectStreamField("segments", Segment[].class),
new ObjectStreamField("segmentMask", Integer.TYPE),
new ObjectStreamField("segmentShift", Integer.TYPE)
};我們點(diǎn)到 ObjectStreamField 類中去，它的類頭有一段這樣的描述：
* A description of a Serializable field from a Serializable class. An array
* of ObjectStreamFields is used to declare the Serializable fields of a class.
簡(jiǎn)單翻譯一下就是，一個(gè)序列化類中可以序列化屬性的描述。ObjectStreamFields 數(shù)組聲明了這個(gè)類的可序列化的字段。
好了，這個(gè)類我們看到這就可以了，而且也知道了 ConcurrentHashMap 中 serialPersistentFields 屬性的作用。就是聲明了一下 ConcurrentHashMap 里有三個(gè) 屬性可以被序列化。這三個(gè)屬性分別是segments、segmentMask、segmentShift 。結(jié)束~
1. spread()
繼續(xù)往下是 Node 類的定義，沒(méi)什么好說(shuō)的，我們遇到了第一個(gè)方法。
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}都是一些位運(yùn)算。解釋一下，這個(gè)方法會(huì)將 h 和 h 右移 16 位的數(shù)值進(jìn)行異或（^）操作，得到的結(jié)果與 HASH_BITS 進(jìn)行與（&）操作。和 HASH_BITS 進(jìn)行與（&）操作，作用就是保證返回的結(jié)果的最高位一定是 0，也就是說(shuō)，返回的結(jié)果一定是正數(shù)。（如果你對(duì)位運(yùn)算沒(méi)有什么概念的話，也可以不用糾結(jié)這個(gè)方法，這個(gè)方法的作用就是，給一個(gè)數(shù)，返回另外一個(gè)數(shù)。）
2. tabAt()、casTabAt()、setTabAt()
@SuppressWarnings("unchecked")
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);
}
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);
}這幾個(gè)是其實(shí)是 ConcurrentHashMap 的核心操作方法。tabAt() 是獲取，casTabAt() 是更新，并且是基于 CAS 方式實(shí)現(xiàn)的更新。setTabAt() 是插入。這些實(shí)現(xiàn)都使用了大名鼎鼎的 sun.misc.Unsafe 類。
如果你對(duì)這個(gè)類不熟悉的話，其實(shí)可以簡(jiǎn)單理解，這個(gè)類里的一些方法都是線程的。因?yàn)檫@個(gè)類提供的是一些硬件級(jí)別的原子操作。簡(jiǎn)單來(lái)說(shuō)，sun.misc.Unsafe 類提供的方法都是線程安全的。理解到這里就可以了，再深入的內(nèi)容，就不再本文范圍內(nèi)了。繼續(xù)往下。
3. counterCells
繼續(xù)往下的話，就看到了 table 和 nextTable，沒(méi)什么說(shuō)的，這個(gè)就是存儲(chǔ)數(shù)據(jù)的數(shù)組了，至于 nextTable，通過(guò)注釋可以看到，這個(gè)變量應(yīng)該是只在擴(kuò)容時(shí)使用到了，等用到的時(shí)候再說(shuō)。
繼續(xù)往下呢就是一些int 類型的值了，通過(guò)名字和注釋也看不出來(lái)什么，直接跳過(guò)。等用到的時(shí)候再說(shuō)。繼續(xù)往下的話我們就看到了一個(gè) CounterCell[] 數(shù)組了，點(diǎn)到這個(gè)類的定義，可以看到以下代碼。
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}好像也沒(méi)有多復(fù)雜，就一個(gè)使用了 volatile 標(biāo)記的 數(shù)值。至于 sun.misc.Contended 注解，主要是解決 CPU 偽緩存 問(wèn)題的，提高性能和效率使用的，可以先不用關(guān)注。
但是，如果你閱讀一下注釋的話，就會(huì)發(fā)現(xiàn)這里面大有文章。涉及到兩個(gè)非常復(fù)雜的東西：LongAdder and Striped64。關(guān)于 LongAdder and Striped64 的內(nèi)容也不在本文范圍內(nèi)，有興趣的話可以搜一下相關(guān)的文章。不了解也沒(méi)有關(guān)系，不影響閱讀。我們繼續(xù)往下看。
4. keySet、values、entrySet
再往下就是幾個(gè) view 變量了。
// views
private transient KeySetView<K,V> keySet;
private transient ValuesView<K,V> values;
private transient EntrySetView<K,V> entrySet;看名字也應(yīng)該能猜出來(lái)，這些變量應(yīng)該是跟 HashMap 的 keySet()、values()、entrySet() 幾個(gè)方法的作用類似。如果你點(diǎn)到它的定義就會(huì)看到，這幾個(gè)類都繼承了 CollectionView 這個(gè)類。
abstract static class CollectionView<K,V,E>
implements Collection<E>, java.io.Serializable {
private static final long serialVersionUID = 7249069246763182397L;
final ConcurrentHashMap<K,V> map;
CollectionView(ConcurrentHashMap<K,V> map) { this.map = map; }
//... ...只看前面幾行就可以了，內(nèi)部有一個(gè) ConcurrentHashMap 類型的變量，而且 CollectionView 只有一個(gè)帶有 ConcurrentHashMap 參數(shù)的構(gòu)造方法。盲猜也能猜到，上面的 xxxView 類內(nèi)部操作的也都是 ConcurrentHashMap 存儲(chǔ)的數(shù)據(jù)。了解這些就可以了，我們繼續(xù)往下看。
5. 構(gòu)造方法
第一個(gè)是個(gè)空構(gòu)造方法沒(méi)有什么好說(shuō)的，先看第二個(gè)。
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}通過(guò)注釋和名稱我們應(yīng)該能夠知道，這個(gè)構(gòu)造方法可以初始化 Map 的容量。有意思的是，計(jì)算 cap 的方法。不知道你還記不記得 HashMap 的初始容量的構(gòu)造方法是怎么計(jì)算容量的。代碼在下面
this.threshold = tableSizeFor(initialCapacity);
而 ConcurrentHashMap 則是將 initialCapacity 加上了 initialCapacity 的一半又加了 1 作為 tableSizeFor 的參數(shù)。其實(shí)就是為了解決 HashMap 存在的可能出現(xiàn)兩次擴(kuò)容的問(wèn)題。
注意，這里使用的是 >>>，不是 >>。>>> 的含義是無(wú)符號(hào)右移。它會(huì)把最高位表示正負(fù)的值也會(huì)右移，然后補(bǔ) 0。 所以 >>> 之后，一定是正數(shù)。如果 >>> 之前是正數(shù)的話，結(jié)果跟 >> 一致。如果是負(fù)數(shù)的話，就會(huì)出現(xiàn)一個(gè)很奇怪的正數(shù)。這是因?yàn)樽罡呶槐硎矩?fù)數(shù)的 1 也跟著右移了。由于代碼里已經(jīng)判斷了小于 0 ，所以我們目前先按照除 2 理解即可。
還有一個(gè)點(diǎn)是，從代碼來(lái)看，ConcurrentHashMap 的最大容量 好像 是用 sizeCtl 表示的。但是，如果僅僅是表示最大容量，為什么會(huì)定義一個(gè)這么奇怪的名字呢？ Ctl 的后綴應(yīng)該是 control 的簡(jiǎn)寫。具體是怎么控制的呢？
繼續(xù)往下，我們先跳過(guò)帶有 Map 參數(shù)的構(gòu)造方法，因?yàn)檫@個(gè)涉及到 putAll() 方法。
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
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è)構(gòu)造方法其實(shí)可以算做一個(gè)，我們直接看下面那個(gè)復(fù)雜的。
先判斷了一下參數(shù)的取值，然后更新了一下 initialCapacity 參數(shù)，然后根據(jù)參數(shù)計(jì)算 size，考慮到 loadFactor 可能小于 1，導(dǎo)致 int 值越界，所以轉(zhuǎn)成了 long 類型。
關(guān)于 concurrencyLevel，給的注釋是：并發(fā)更新線程的預(yù)估數(shù)量。那上面那段判斷更新就不難理解了。假如我預(yù)估會(huì)有 20 個(gè)線程同時(shí)更新這個(gè)初始容量為 15 的 Map，這個(gè)時(shí)候的初始容量會(huì)自動(dòng)的改為 20 。
好像沒(méi)有什么問(wèn)題？有意思的是， loadFactor 這個(gè)參數(shù)竟然沒(méi)有保存??！ 加載因子沒(méi)有保存，那什么時(shí)候觸發(fā)擴(kuò)容呢？我們繼續(xù)往下看。
6. putAll()
回到帶有 Map 參數(shù)的構(gòu)造方法。
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}沒(méi)有什么復(fù)雜的，指定了下默認(rèn)的初始容量（16）就直接 putAll(m); 了。
public void putAll(Map<? extends K, ? extends V> m) {
tryPresize(m.size());
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putVal(e.getKey(), e.getValue(), false);
}好像也不難，先執(zhí)行 tryPresize(m.size()); 應(yīng)該是初始擴(kuò)容， 然后再 for 循環(huán)進(jìn)行 putVal() 操作。
7. tryPresize()
先看下方法名。嘗試并行重置容量。里面的 P 應(yīng)該是 parallel(并行) 的縮寫。
private final void tryPresize(int size) {
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) {
n = (sc > c) ? sc : c;
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 - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == + 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);
}
}
}首先計(jì)算了下變量 c，這個(gè)是保存入?yún)?size 個(gè)元素時(shí)需要的最大容量。
然后是一個(gè) whlie 循環(huán)，因?yàn)槲覀兪峭ㄟ^(guò)構(gòu)造方法進(jìn)來(lái)的，所以 sizeCtl 的值現(xiàn)在是默認(rèn)值 16 ，table 現(xiàn)在是 null。這個(gè)時(shí)候就進(jìn)入到了 if 的代碼里了。
在 if 的條件里是判斷了 compareAndSwapInt() 的結(jié)果。這里需要說(shuō)一下，compareAndSwapInt 方法是 CAS 的一種實(shí)現(xiàn)。這個(gè)方法內(nèi)部做了兩件事情，首先是比較 this 這個(gè)對(duì)象的 SIZECTL 值是否跟 sc 相等，相等的話，把 SIZECTL 的值 改為 -1。而且 Unsafe 類還保證了線程的安全。如果有多個(gè)線程同時(shí)執(zhí)行這個(gè)方法的話，只會(huì)有一個(gè)線程成功。不會(huì)出現(xiàn)兩個(gè)線程都比較通過(guò)了，然后在賦值的時(shí)候產(chǎn)生覆蓋的問(wèn)題。
好像也不難理解，其實(shí)就是把 sizeCtl 值改成了 -1，而且只有一個(gè)線程會(huì)成功。這里的 sizeCtl 更像是一把鎖，哪個(gè)線程改成了 -1 ，哪個(gè)線程就獲取到了鎖，那它就可以執(zhí)行后面的流程了。
繼續(xù)，因?yàn)樯厦嬉呀?jīng)對(duì) tab = table 賦值了，所以下面的判斷也能通過(guò)。然后，就看到了數(shù)組初始化的過(guò)程了。直接 new 了一個(gè)長(zhǎng)度為 n 的 Node[]。并賦值給了 table。如果你往上追一下 n 的賦值，就會(huì)知道，現(xiàn)在的 n 正好是 c。就是方法一開(kāi)始計(jì)算的值。
table 數(shù)組都已經(jīng)初始化了，是不是結(jié)束了？并沒(méi)有。這個(gè)時(shí)候更新了一下 sc。 >>> 2 相當(dāng)于除 4，其實(shí)就是 sc 現(xiàn)在的值是 n 的 3/4 。而且在 finally 塊中，更新了 sizeCtl。這個(gè)時(shí)候 sizeCtl 就不是 -1 了。根據(jù)我們之前的理解，這里更新 sizeCtl，應(yīng)該是在釋放鎖。
然后，第一次 while 循環(huán)就結(jié)束了。再次進(jìn)入 while 循環(huán)，這次 sc 是 n 的 3/4 了，上一次循環(huán)已經(jīng)更新了 sizeCtl。
這次 table 就不等于 null 了。而且根據(jù)我們之前的推斷，現(xiàn)在的 sc 應(yīng)該等于 n 的 3/4 ，而 n 之前又等于 c。所以， c <= sc 這個(gè)條件也不成立。
而且 n >= MAXIMUM_CAPACITY 這個(gè)條件大概率是在擴(kuò)容到最大的時(shí)候才會(huì)成立。所以，就走到了最后一個(gè)條件分支里了。因?yàn)?sc 現(xiàn)在是大于 0 的，所以直接走到了最后一個(gè)分支。
PS: if (sc < 0) 這個(gè)分支好像永遠(yuǎn)不會(huì)執(zhí)行，因?yàn)?while 進(jìn)入的條件要求 sc >= 0，而在判斷sc < 0 之前又沒(méi)有任何地方會(huì)把 sc 更新為負(fù)數(shù)，所以好像一直都不會(huì)執(zhí)行。如果我理解錯(cuò)了，希望有人能解惑一下~
8. resizeStamp()
首先執(zhí)行了一下 resizeStamp() 方法。這個(gè)方法也是一個(gè)位運(yùn)算的方法。你可以直接使用 main() 方法跑一下，會(huì)返回一個(gè)很難理解的正數(shù)。簡(jiǎn)單說(shuō)一下這個(gè)數(shù)是怎么得出來(lái)的。
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}首先， numberOfLeadingZeros() 會(huì)返回 n 的二進(jìn)制串中從最左邊算起連續(xù)的“0”的總個(gè)數(shù)。然后再跟 1 左移 15 位的值按位或（|）操作。 最終得到的就是一個(gè)在二進(jìn)制中，第 16 位為 1 的正數(shù)。
繼續(xù)回到代碼，因?yàn)楝F(xiàn)在已經(jīng)確定 sc 是 n 的 3/4 了(PS：如果這個(gè) 3/4 不理解，那換成 0.75 是不是會(huì)好點(diǎn) ，好像跟 HashMap 的擴(kuò)容因子一樣，其實(shí) sc 的值就是擴(kuò)容閾值，這個(gè)后面會(huì)提到，現(xiàn)在不理解沒(méi)關(guān)系)，所以也是大于 0 的。這里又進(jìn)行了一次 compareAndSwapInt()。這個(gè)時(shí)候賦值的是把 rs 左移了 16 位。 還記得 resizeStamp() 返回的結(jié)果么，第 16 位是 1。所以 rs 右移 16 位之后，最高位就是 1 了，在 int 類型里，二進(jìn)制的最高位表示正負(fù)，1 表示負(fù)數(shù)。
所以，這個(gè)時(shí)候，又把 sizeCtl 更新成負(fù)值了。根據(jù)我們之前的理解，這里應(yīng)該還是獲取鎖的操作。獲取到鎖之后，一般就是需要操作資源了。但是 table 我們不是已經(jīng)初始化好了嗎？這次又要初始什么呢？
記住，現(xiàn)在 sizeCtl 是一個(gè)負(fù)值，并且 sizeCtl = (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2) 后面要用到！
9.transfer()
int n = tab.length, 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) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
//... ...到這里還是比較好理解的。先初始了一下 stride 和 n 這兩個(gè)變量。然后，因?yàn)槲覀兪浅跏蓟M(jìn)來(lái)的，所以 nextTab 一定等于 null。這個(gè)時(shí)候會(huì)初始化 nextTab。在創(chuàng)建數(shù)組的時(shí)候捕獲了一個(gè)異常，這個(gè)異常出現(xiàn)的唯一情況就是內(nèi)存不夠了，分配不了 2 倍的 n 的數(shù)組。這個(gè)時(shí)候，將 sizeCtl 的值改為了 Integer.MAX_VALUE。然后就結(jié)束了。如果沒(méi)有拋異常，會(huì)更新 nextTable 和 transferIndex 的值。
我們需要回頭看下 tryPresize() 方法。如果在拋異常的時(shí)候結(jié)束，會(huì)出現(xiàn)什么情況。根據(jù)代碼，異常結(jié)束后，會(huì)進(jìn)入第三次循環(huán)，這次循環(huán)會(huì)進(jìn)入第二個(gè)分支。因?yàn)?c <= sc 一定會(huì)成立。這里就會(huì)結(jié)束循環(huán)。
到這里，我們已經(jīng)把 tryPresize() 循環(huán)里的三個(gè)分支都走完了，下面繼續(xù)看 transfer() 這個(gè)方法。
nextTab 初始化之后，我們又看到了一個(gè)新的 Node 類:
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
點(diǎn)到這個(gè)類的定義里我們會(huì)發(fā)現(xiàn)，這個(gè)類里面只有一個(gè)屬性 nextTable 和一個(gè) find() 方法。關(guān)于 find() 是在獲取元素時(shí)才能用到，我們先不用關(guān)注。目前來(lái)看 ForwardingNode 其實(shí)就是對(duì) nextTab 的一個(gè)封裝。然后繼續(xù)看 transfer() 。
兩個(gè)boolean 類型的值，默認(rèn)一個(gè) true，一個(gè) false。
下面的代碼是一個(gè) for 循環(huán)，但是這個(gè)循環(huán)有差不多 100 多行的代碼（如果我在項(xiàng)目里遇到這種代碼估計(jì)會(huì)罵人的~）。我們一點(diǎn)點(diǎn)看，首先是一個(gè)while 循環(huán)。
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;
}
}首先 i = 0, bound = 0 ，所以，第一次循環(huán)不會(huì)進(jìn)入第一個(gè)分支。然后，根據(jù)之前 transferIndex = n; 的賦值，也不會(huì)進(jìn)入第二個(gè)分支。
這樣就來(lái)到了第三個(gè)分支。compareAndSwapInt 會(huì)更新 transferIndex 的值，如果 CPU 的個(gè)數(shù)是 1，transferIndex 更新成 0 ，否則更新成 nextIndex - stride 。然后更新 bound、i、advance 的值，循環(huán)就結(jié)束了。
繼續(xù)往下，現(xiàn)在 i 的值是 n - 1，所以不會(huì)命中 if (i < 0 || i >= n || i + n >= nextn) 條件。
然后，因我們是初始化時(shí)進(jìn)入的，素以 tab 里的所有元素都是 null，第二個(gè)條件就通過(guò)了。
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);其實(shí)就是把 tab 的 i 位置 初始化了一個(gè) fwd 元素。 到這里，第一次 for 循環(huán)就結(jié)束了。
第二次循環(huán)其實(shí)也很簡(jiǎn)單，首先 advance = false ，不會(huì)進(jìn)入 while 循環(huán)，然后就會(huì)進(jìn)入下面的判斷
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed首先，獲取了下 tab[i] 的值，因?yàn)樯洗窝h(huán)已經(jīng)賦值過(guò)了，現(xiàn)在 f = fwd。然后，有意思的來(lái)了，先看下 MOVED 的定義
static final int MOVED = -1; // hash for forwarding nodes
沒(méi)錯(cuò)，MOVED = -1，按我們正常的理解，一個(gè)對(duì)象的 hash 值，怎么也不會(huì)等于 -1 吧，我們?cè)倩仡^看下 ForwardingNode 這個(gè)類
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;
}
//... ...
}
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;
}
//... ...
}順便貼了下父類的代碼，主要看構(gòu)造函數(shù)，看到了么? fwd 這個(gè)對(duì)象在初始化的時(shí)候，指定了 hash 值，就是 MOVED。OK，回到之前的循環(huán)。
這次循環(huán)就會(huì)把 advance 改為 true。第二次循環(huán)就結(jié)束了。
經(jīng)過(guò)上面的兩次循環(huán)之后，我們是其實(shí)只是執(zhí)行了一行代碼 tab[n-1] = fwd。現(xiàn)在進(jìn)入第三次循環(huán)，之前 i = n - 1 。現(xiàn)在又執(zhí)行了一次 if (--i >= bound || finishing)，所以現(xiàn)在 i = n - 2 。但是 bound 可能有兩種情況，一種是 bound = n - stride，一種是 bound = 0。我們先假設(shè) bound = n - stride; stride = 16 。所以，第一個(gè)條件是成立的，執(zhí)行 advance = false; ，然后 while 循環(huán)結(jié)束。
然后，第一個(gè) if (i < 0 || i >= n || i + n >= nextn) 條件不會(huì)成立，又執(zhí)行到了賦值操作里。這時(shí) tab[n-2] = fwd。第三次循環(huán)結(jié)束~
然后第四次循環(huán)又會(huì)把 advance 改為 true。
好好回味下~~
其實(shí)，這一頓操作下來(lái)就是在執(zhí)行 tab[i] = fwd 這一行代碼。搞了這么多東西，其實(shí)就是在支持多線程并發(fā)擴(kuò)容，簡(jiǎn)單說(shuō)下過(guò)程。
首先，while 循環(huán)會(huì)確定當(dāng)前線程擴(kuò)容的區(qū)間 [ bound,nextIndex ) 左開(kāi)右閉。然后 while 循環(huán)下面的代碼其實(shí)就是在給 tab 和 nextTab 賦值。設(shè)想下，如果 while 循環(huán)里的 compareAndSwapInt 執(zhí)行失敗，會(huì)是什么情況？沒(méi)錯(cuò)，會(huì)空轉(zhuǎn)！結(jié)束只有兩種情況，一種是 transferIndex = 0。說(shuō)明已經(jīng)有其他線程把所有的區(qū)間都認(rèn)領(lǐng)了，另外一種情況是執(zhí)行 compareAndSwapInt。認(rèn)領(lǐng) [ bound,nextIndex ) 的區(qū)間，進(jìn)行擴(kuò)容。
其實(shí)，你可以直接驗(yàn)證下的，打斷點(diǎn)也好，手寫也罷，假設(shè)n = 1024; NCPU = 4。這時(shí) stride = 32。那么第一個(gè)線程會(huì)先對(duì) tab[1024-32,1024-1]進(jìn)行賦值。如果這時(shí)有其他線程進(jìn)來(lái)，在 while 循環(huán)的時(shí)候，就會(huì)認(rèn)領(lǐng) tab[1024-32-32,1024-32-1] 的區(qū)間進(jìn)行賦值。如果有更多的線程進(jìn)來(lái)的話，就會(huì)加快這個(gè)過(guò)程。這個(gè)就是所謂的 并發(fā)擴(kuò)容 ，也有叫 輔助擴(kuò)容 的。
然后，我們來(lái)看下通過(guò) synchronized 加鎖的這段代碼。能執(zhí)行到這里的話只能是 tab[i].hash != MOVED。那就說(shuō)明這里記錄的是一個(gè)正常的數(shù)據(jù)。
首先判斷了下 if (tabAt(tab, i) == f) 沒(méi)什么說(shuō)的，肯定成立，不成立就結(jié)束了，然后判斷了下 if (fh >= 0)。有點(diǎn)奇怪，正常數(shù)據(jù)的 hash 還能小于 0 ？那我們先看下不成立的情況
else if (f instanceof TreeBin)
明白了吧，當(dāng)發(fā)生 hash 沖突時(shí)，并且鏈表已經(jīng)轉(zhuǎn)成紅黑樹(shù)了，這時(shí) tab[i] = TreeBin，那我們看下 TreeBin 的定義。
static final class TreeBin<K,V> extends Node<K,V> {
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null, null, null);
//... ...
}
}
static final int TREEBIN = -2; // hash for roots of trees真相了，TreeBin 的 hash 值是 -2，就小于 0。后面的代碼我們就不說(shuō)了，其實(shí)跟HashMap是一樣的，如果當(dāng)前節(jié)點(diǎn)是鏈表，那就采用高低位鏈表的形式對(duì) nextTab 賦值，如果是 TreeBin 那就采用紅黑樹(shù)的方式進(jìn)行賦值。而且，我們對(duì) tab[i] 加了 synchronized 鎖，也不會(huì)有線程競(jìng)爭(zhēng)，老老實(shí)實(shí)賦值就好了。
最后，transfer 里的代碼基本上都看完了，就剩下面這段了
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
}
}在 while 循環(huán)里，有這么一行代碼 i = -1; 執(zhí)行了這個(gè)之后，就會(huì)進(jìn)入上面的代碼里。其實(shí)就是 tab 初始化完成之后，即 nextIndex = 0 的時(shí)候，就會(huì)執(zhí)行 i = -1; ，然后就會(huì)進(jìn)入上面的代碼了。我們看下上面的代碼。
首先，finishing 現(xiàn)在應(yīng)該是等于 false 的，直接進(jìn)入第二個(gè) if。這個(gè)也很簡(jiǎn)單，首先 sc = sizeCtl，賦值，然后通過(guò) CAS 將 sizeCtl 的值改為 sc - 1。還記得 sizeCtl 的值是多少么？？ 我直接粘貼一下 sizeCtl = (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2)。是不是跟 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) 這個(gè)判斷邏輯一致？如果不相等，說(shuō)明有其他線程修改了sizeCtl，這同時(shí)說(shuō)明有其他線程還在執(zhí)行擴(kuò)容的動(dòng)作，即還在執(zhí)行 tryPresize() 或者是 transfer() 方法。那么，因?yàn)楫?dāng)前線程已經(jīng)執(zhí)行完了，所以直接 return; 結(jié)束，讓其他線程繼續(xù)執(zhí)行就好了。
如果相等，執(zhí)行 finishing = advance = true; i = n。進(jìn)入下一次 for 循環(huán)。
一頓判斷之后，你會(huì)發(fā)現(xiàn)，還是會(huì)進(jìn)入到上面的代碼，而這時(shí)，finishing == true 了！下面的代碼就不難理解了吧，更新 table ，相當(dāng)于使用了新的數(shù)組了，而 sizeCtl 也更新了一下。都是位運(yùn)算，如果你看不明白，可以用 main 方法跑一下。我們假設(shè) n = 1024，那么 table 現(xiàn)在的大小也就是之前 nextTab 的大小，就是2048，然后，我們用 main 跑一下 sizeCtl 的值，不出意外的話應(yīng)該等于 1536 。如果還看不明白，那么你再計(jì)算下 1536 / 2048。結(jié)果是 0.75 ，這個(gè)數(shù)字熟悉吧？ HashMap 的默認(rèn)加載因子！。沒(méi)錯(cuò)，sizeCtl 其實(shí)就是下次需要擴(kuò)容的閾值。
到這里，我們就把 transfer() 方法看完了。然后，我們重點(diǎn)總結(jié)下 sizeCtl 這個(gè)屬性，不得不承認(rèn)，這個(gè)設(shè)計(jì)非常的巧妙！
首先，通常情況下 sizeCtl 應(yīng)該是等于下次的擴(kuò)容閾值的。但是在擴(kuò)容期間，有兩個(gè)狀態(tài)，一個(gè)是 -1，一個(gè)是非常大的一個(gè)負(fù)值。等于 -1 很好理解，相當(dāng)于是一個(gè)鎖，哪個(gè)線程更新成功，就可以進(jìn)行數(shù)組的初始化動(dòng)作。那么，就剩最后一種情況了。直接用下面的 main() 方法跑一下
public static void main(String[] args) throws IllegalAccessException {
int rs = Integer.numberOfLeadingZeros(1024) | (1 << (16 - 1));
int sizeCtl = (rs << 16) + 2;
System.out.println(sizeCtl);
System.out.println((sizeCtl<<16)>>16);
}會(huì)得到下面的結(jié)果
-2146107390
2
有意思了，(sizeCtl<<16)>>16，這個(gè)操作是先左移 16 位，再右移 16 位，相當(dāng)于把 sizeCtl 的高 16 位都置為 0 了。得到了一個(gè) 2，其實(shí)，這個(gè) 2 就是說(shuō)當(dāng)前有 (2 - 1) 個(gè)線程在進(jìn)行擴(kuò)容操作。（PS： sizeCtl 注釋里有寫~）。具體是為什么，我們繼續(xù)往下看。
transfer() 執(zhí)行完，就回到了 tryPresize()。然后繼續(xù)返回就到了 putAll()。繼續(xù)往下執(zhí)行就是 putVal() 方法了。
10.putVal()
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
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//... ...首先判斷了下 null，然后計(jì)算了下 hash 哈希值。就進(jìn)入 for 循環(huán)了。首先是第一個(gè)分支。其實(shí)就是 tab 還沒(méi)有初始化的時(shí)候會(huì)進(jìn)入這個(gè)分支。
11.initTable()
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}好像也沒(méi)有多少?gòu)?fù)雜的，因?yàn)槲覀冎耙呀?jīng)對(duì) sizeCtl 做了充分的解釋，這里如果 sc < 0 的話，說(shuō)明在擴(kuò)容或者是初始化中，然后當(dāng)前線程直接執(zhí)行了 Thread.yield();，就是放棄 CPU 執(zhí)行權(quán)等待下次分配 CPU 時(shí)間片，如果不小于 0 ，并且 tab = null ，那說(shuō)明現(xiàn)在還沒(méi)有線程執(zhí)行擴(kuò)容，那當(dāng)前線程就會(huì)更新 sizeCtl，然后自己開(kāi)始執(zhí)行初始化動(dòng)作，初始化好后直接返回 tab。
繼續(xù)回到 putVal() 方法，如果執(zhí)行第二個(gè)分支，說(shuō)明 tab[i] == null，這個(gè)位置還沒(méi)有元素，直接通過(guò) casTabAt() 方法進(jìn)行賦值。如果這個(gè)位置有值，并且 (fh = f.hash) == MOVED 說(shuō)明在擴(kuò)容或者是在初始化，這個(gè)時(shí)候當(dāng)前線程會(huì)進(jìn)行 輔助擴(kuò)容。
12.helpTransfer()
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)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}首先在 if 條件里獲取到 nextTab 如果不為 null，就會(huì)進(jìn)入 while 循環(huán)，首先 sc < 0 說(shuō)還在擴(kuò)容或者是初始化中，while 循環(huán)里的第一個(gè)分支是不需要輔助擴(kuò)容或者是已經(jīng)達(dá)到最大的輔助線程數(shù)量，或者是已經(jīng)剩最后一個(gè)線程在擴(kuò)容了，其他的線程都結(jié)束了。所以直接 break; 就可以了。
第二個(gè)分支，首先會(huì)執(zhí)行 sizeCtl + 1 的操作，執(zhí)行成功就會(huì)執(zhí)行 transfer() 方法，這個(gè)方法我們之前已經(jīng)看過(guò)了，就不看了，需要注意的是，我們之前說(shuō)過(guò)，sizeCtl 的低 16 位代表目前正在擴(kuò)容的線程數(shù)減一。因?yàn)檫@里新加入一個(gè)線程參與擴(kuò)容，所以對(duì) sizeCtl 進(jìn)行了加一的操作。如果還有線程進(jìn)來(lái)，那么 sizeCtl 還會(huì)加一。這里就解釋清楚 sizeCtl 的另外的一個(gè)用法了。擴(kuò)容結(jié)束直接 break;。繼續(xù)回到 putVal()。
繼續(xù)下一次 for，如果 tab[i] 還不等于 null，那就說(shuō)明發(fā)生哈希沖突了，并且當(dāng)前已經(jīng)不在擴(kuò)容了。就走到了最后一個(gè)分支，使用 synchronized 加鎖的這一段代碼里，這段代碼其實(shí)并不復(fù)雜，發(fā)生沖突之后無(wú)非就兩種情況，鏈表或者是紅黑樹(shù)。你可以看下 TreeBin 的構(gòu)造方法。它的哈希值是 -2。
static final int TREEBIN = -2; // hash for roots of trees
//... ...
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null, null, null);
//... ...
}所以才有了 if (fh >= 0) 的判斷，如果首節(jié)點(diǎn)的哈希值大于 0 ，那一定是鏈表。
最后還有一段進(jìn)行樹(shù)化的判斷操作。
static final int TREEIFY_THRESHOLD = 8;
//... ...
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}鏈表的節(jié)點(diǎn)數(shù)超過(guò) 8 就會(huì)進(jìn)行樹(shù)化操作。到這里其實(shí) putVal() 的相關(guān)操作基本上已經(jīng)結(jié)束了，就剩最后一個(gè) addCount() 方法了，看名稱也知道這個(gè)是更新計(jì)數(shù)器的，盲猜也能猜到應(yīng)該跟元素?cái)?shù)量有關(guān)系。不過(guò)，好像有點(diǎn)問(wèn)題啊，你有沒(méi)有發(fā)現(xiàn)，在整個(gè) putVal() 方法里面，好像沒(méi)有觸發(fā)擴(kuò)容的邏輯??！
13.addCount()
其實(shí)這個(gè)方法除了操作我們之前見(jiàn)到的 counterCells 屬性外，還會(huì)判斷是否需要進(jìn)行擴(kuò)容。因?yàn)橹挥性谥谰唧w的元素?cái)?shù)量后，才能判斷出是否需要擴(kuò)容。我們先看這個(gè)方法的第一段代碼。
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
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();
}
//... ...首先，我們假設(shè)目前是第一次執(zhí)行這個(gè)方法，那么 counterCells == null，然后就會(huì)使用 CAS 執(zhí)行 baseCount = b + x。失敗之后，就開(kāi)始執(zhí)行 fullAddCount() 方法了，因?yàn)楝F(xiàn)在 as == null 是成立的。
fullAddCount() 方法與 Striped64.longAccumulate() 方法基本上是一模一樣的，因?yàn)橹耙呀?jīng)跳過(guò)了 Striped64，所以這里也不打算去細(xì)看。直接總結(jié)下 counterCells 的作用。其實(shí) counterCells 就是在多個(gè)線程同時(shí)更新 baseCount 失敗時(shí)記錄下新增的元素?cái)?shù)量。
舉個(gè)例子就明白了，假設(shè) ConcurrentHashMap 初始化完成之后，有 2 個(gè)線程，同時(shí)執(zhí)行了 addCount()，那么 baseCount 會(huì)更新成 1，counterCells 會(huì)初始化為一個(gè)大小為 2 的數(shù)組，且一個(gè)元素是 null，另外一個(gè)元素的 counterCells[i].value 值是 1。
如果這個(gè)時(shí)候又來(lái)了一個(gè)線程，會(huì)有 3 種情況，
- CAS 更新
baseCount成功，baseCount = 2。第三個(gè)線程結(jié)束 - CAS 失敗且
counterCells[ThreadLocalRandom.getProbe() & m] == null。繼續(xù)初始化counterCells的另一個(gè)為null的元素，值為 1。 - CAS 失敗且
counterCells[ThreadLocalRandom.getProbe() & m] != null，那么counterCells[i].value值更新成 2。
ThreadLocalRandom.getProbe() 方法其實(shí)就是取了個(gè)隨機(jī)值。就是說(shuō)，如果有多個(gè)線程同時(shí)更新的話，失敗的線程會(huì)隨機(jī)的從 counterCells 取一個(gè)元素，將新增的數(shù)量保存進(jìn)去。
其實(shí)很簡(jiǎn)單，能進(jìn)入到 fullAddCount() 方法的條件只有一種，counterCells == null 并且 CAS 更新 baseCount 失敗，這種情況就是有多個(gè)線程同時(shí)執(zhí)行了 addCount() 方法，比如，有兩線程同時(shí)執(zhí)行 putVal()，那么必然有一個(gè)線程在 CAS 更新 baseCount 時(shí)會(huì)失敗，這個(gè)時(shí)候就進(jìn)入到 fullAddCount() 方法。這個(gè)方法內(nèi)部就是在操作 counterCells 數(shù)組。操作的行為基本上就是下面這幾種
要么是初始化 counterCells 數(shù)組
if (counterCells == as) {
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}要么就是初始化 counterCells 數(shù)組元素
CounterCell r = new CounterCell(x); // Optimistic create
if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
rs[j] = r;
created = true;
}
} finally {
cellsBusy = 0;
}
if (created)
break;
continue; // Slot is now non-empty
}要么就是更新 counterCells 數(shù)組元素的值
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;還有一種操作就是 擴(kuò)容 ，對(duì) counterCells 進(jìn)行擴(kuò)容。
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
}在 fullAddCount() 方法里，每次循環(huán)都會(huì)重新隨機(jī)取元素 h = ThreadLocalRandom.advanceProbe(h);。如果執(zhí)行循環(huán)了多次，都沒(méi)有保存成功，說(shuō)明 counterCells 的容量不夠用了，就會(huì)觸發(fā)擴(kuò)容。從上面的代碼里也能看到，counterCells 的擴(kuò)容非常簡(jiǎn)單，數(shù)組直接翻倍，元素直接賦值到新數(shù)組里，位置都沒(méi)有變。
繼續(xù)回到 addCount() 方法，之后的邏輯就是判斷了下 check 參數(shù)。其實(shí)這里的邏輯是，如果有多個(gè)線程同時(shí)操作，只要沒(méi)有發(fā)生哈希沖突，就不進(jìn)行擴(kuò)容檢查。你往回翻一下就可以看到 check 參數(shù)其實(shí)就是 tab[i] 位置的元素?cái)?shù)量。
如果發(fā)生了哈希沖突，或者說(shuō)沒(méi)有多個(gè)線程同時(shí)操作（這個(gè)時(shí)候就進(jìn)入不了當(dāng)前的分支，更新 baseCount 不會(huì)失?。蜁?huì)執(zhí)行 s = sumCount(); 這個(gè)方法非常簡(jiǎn)單，就是對(duì) baseCount 和 counterCells 里的數(shù)值進(jìn)行了一下求和，然后就開(kāi)始執(zhí)行下面的代碼。
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;
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();
}
}首先 while 循環(huán)判斷了下當(dāng)前的元素?cái)?shù)量是否超過(guò)了 sizeCtl，即便是在擴(kuò)容期間，sizeCtl 小于 0 的時(shí)候，也算成立。然后判斷了下 tab ，基本上也會(huì)成立。直接進(jìn)入循環(huán)內(nèi)部
第一個(gè)分支 if (sc < 0) 說(shuō)明已經(jīng)有線程開(kāi)始執(zhí)行擴(kuò)容動(dòng)作了，這個(gè)時(shí)候更新 sizeCtl 的值加一，當(dāng)前線程參與 輔助擴(kuò)容。
第二個(gè)分支是目前還沒(méi)有線程進(jìn)行擴(kuò)容操作，那么當(dāng)前線程開(kāi)始執(zhí)行擴(kuò)容，(rs << RESIZE_STAMP_SHIFT) + 2) 這個(gè)數(shù)值我們之前已經(jīng)看到過(guò)了，就不再贅述了。
循環(huán)最后重新計(jì)算 s ，擴(kuò)容結(jié)束后 s 就不會(huì)小于 sizeCtl，方法結(jié)束。
好了，到這里我們基本上就把 ConcurrentHashMap 的 put 操作的邏輯看完了。其實(shí)整體上跟 HashMap還是比較類似的，基本上就是把所有對(duì) tab 的操作都使用 Unsafe 包裝了一下，解決多線程操作的問(wèn)題，而發(fā)生哈希沖突時(shí)也是使用了 synchronized 進(jìn)行了加鎖，解決了多線程操作鏈表的覆蓋問(wèn)題。比較難的反而是元素?cái)?shù)量的問(wèn)題。因?yàn)?ConcurrentHashMap 一定要保證元素保存到 tab 成功后，元素?cái)?shù)量一定也要加成功！不能因?yàn)樵財(cái)?shù)量的值更新失敗了，再把保存到 tab 里的元素刪除掉吧。所以呢 ConcurrentHashMap 就使用 counterCells 數(shù)組來(lái)保存那些更新 baseCount 失敗的數(shù)量。
14.get()
下面我們看下 get() 方法
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}好像也不復(fù)雜，第一個(gè)分支是一次就從 tab[i] 位置找到了元素，直接返回。最后一個(gè) while 循環(huán)是 tab[i] 位置發(fā)生了哈希沖突，且當(dāng)前位置是鏈表，通過(guò) while 循環(huán)遍歷尋找。
重點(diǎn)說(shuō)一下第二個(gè)分支吧 else if (eh < 0) 有兩種情況，一種是 tab[i] 位置發(fā)生了哈希沖突，且當(dāng)前位置是紅黑樹(shù)，這時(shí) e 是 TreeBin 類型的，因?yàn)樯婕暗郊t黑樹(shù)，我們直接跳過(guò)，有興趣的可以自己研究下。另外一種情況是在擴(kuò)容期間，當(dāng)前元素已經(jīng)轉(zhuǎn)移到新的 nextTable 上了，這時(shí) e 的類型是 ForwardingNode 類型，我們直接看下 ForwardingNode 類的 find() 代碼
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
outer: for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; int n;
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
for (;;) {
int eh; K ek;
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
if (eh < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
else
return e.find(h, k);
}
if ((e = e.next) == null)
return null;
}
}
}也不復(fù)雜，就是直接在 nextTable 找元素，如果 nextTable[i] 位置為 null 直接返回，否則就進(jìn)入了 for (;;) 循環(huán)里，跟之前類似，第一個(gè)分支里是直接找到了元素，而 if (eh < 0) 也有兩種情況，一個(gè)是擴(kuò)容時(shí)轉(zhuǎn)移到新的 nextTable，一個(gè)就是紅黑樹(shù)。最后就是鏈表了。
好了，到這里基本上所有的內(nèi)容都結(jié)束了，最后還剩一點(diǎn)有意思的東西，就是 Traverser 類，這個(gè)類其實(shí)實(shí)現(xiàn)了在擴(kuò)容期間，也能使 ConcurrentHashMap 可以高效的（不使用鎖）遍歷。代碼不多，有興趣的話可以讀一下~
以下是遺留的一些內(nèi)容，有機(jī)會(huì)再補(bǔ)吧
sun.misc.Unsafe類。LongAdderandStriped64sun.misc.Contended注解TreeBin
以上就是Java源碼重讀之ConcurrentHashMap詳解的詳細(xì)內(nèi)容，更多關(guān)于Java ConcurrentHashMap的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
- Java的ConcurrentHashMap原理深入分析
- Java?ConcurrentHashMap實(shí)現(xiàn)線程安全的代碼示例
- Java面試?？贾瓹oncurrentHashMap多線程擴(kuò)容機(jī)制詳解
- 淺析Java中ConcurrentHashMap的存儲(chǔ)流程
- Java?ConcurrentHashMap的源碼分析詳解
- Java集合ConcurrentHashMap詳解
- java并發(fā)容器ConcurrentHashMap深入分析
- Java HashTable的原理與實(shí)現(xiàn)
- Java中HashMap和Hashtable的區(qū)別小結(jié)
- 一文帶你全面了解Java?Hashtable
- Java中Hashtable集合的常用方法詳解
- 詳解Java中的HashTable
- Java容器HashMap與HashTable詳解
- java HashMap和HashTable的區(qū)別詳解
- java面試題——詳解HashMap和Hashtable 的區(qū)別
- Java中HashMap和Hashtable的區(qū)別淺析
- Java中ConcurrentHashMap和Hashtable的區(qū)別
相關(guān)文章
詳解XML,Object,Json轉(zhuǎn)換與Xstream的使用
這篇文章主要介紹了詳解XML,Object,Json轉(zhuǎn)換與Xstream的使用的相關(guān)資料,需要的朋友可以參考下2017-02-02
這篇文章主要介紹了java多線程之線程同步七種方式代碼示例，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11
關(guān)于SpringBoot靜態(tài)資源路徑管理問(wèn)題
這篇文章主要介紹了SpringBoot靜態(tài)資源路徑管理，主要包括默認(rèn)靜態(tài)資源路徑，增加靜態(tài)資源路徑前綴的相關(guān)操作，本文給大家介紹的非常詳細(xì),需要的朋友可以參考下2022-05-05
這篇文章主要介紹了Java實(shí)現(xiàn)的n階曲線擬合功能,結(jié)合實(shí)例形式分析了Java基于矩陣的多項(xiàng)式曲線擬合相關(guān)操作技巧,需要的朋友可以參考下2018-01-01
這篇文章主要介紹了Java正則表達(dá)式group方法的使用，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-01-01
這篇文章主要給大家介紹了關(guān)于Java中數(shù)組的定義和使用的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-06-06
Jenkins使用Gradle編譯Android項(xiàng)目詳解
這篇文章主要介紹了Jenkins使用Gradle編譯Android項(xiàng)目詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07
這篇文章主要介紹了Mybatis如何一次性插入多條數(shù)據(jù)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11
SpringBoot開(kāi)發(fā)中的組件和容器詳解
這篇文章主要介紹了SpringBoot開(kāi)發(fā)中的組件和容器詳解,SpringBoot 提供了一個(gè)內(nèi)嵌的 Tomcat 容器作為默認(rèn)的 Web 容器,同時(shí)還支持其他 Web 容器和應(yīng)用服務(wù)器,需要的朋友可以參考下2023-09-09
一起來(lái)看看springboot集成redis的使用注解
這篇文章主要為大家詳細(xì)介紹了springboot集成redis的使用注解，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-03-03