知識星球（點選上方公眾號，可快速關註）
來源：JavaDoop ，
javadoop.com/post/hashmap
Java8 ConcurrentHashMap
Java7 中實現的 ConcurrentHashMap 說實話還是比較複雜的，Java8 對 ConcurrentHashMap 進行了比較大的改動。建議讀者可以參考 Java8 中 HashMap 相對於 Java7 HashMap 的改動，對於 ConcurrentHashMap，Java8 也引入了紅黑樹。
說實話，Java8 ConcurrentHashMap 原始碼真心不簡單，最難的在於擴容，資料遷移操作不容易看懂。
我們先用一個示意圖來描述下其結構：
結構上和 Java8 的 HashMap 基本上一樣，不過它要保證執行緒安全性，所以在原始碼上確實要複雜一些。
初始化
// 這建構式裡，什麼都不乾
public ConcurrentHashMap() {
}
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;
}
這個初始化方法有點意思，透過提供初始容量，計算了 sizeCtl，sizeCtl = 【 (1.5 * initialCapacity + 1)，然後向上取最近的 2 的 n 次方】。如 initialCapacity 為 10，那麼得到 sizeCtl 為 16，如果 initialCapacity 為 11，得到 sizeCtl 為 32。
sizeCtl 這個屬性使用的場景很多，不過只要跟著文章的思路來，就不會被它搞暈了。
如果你愛折騰，也可以看下另一個有三個引數的構造方法，這裡我就不說了，大部分時候，我們會使用無參建構式進行實體化，我們也按照這個思路來進行原始碼分析吧。
put 過程分析
仔細地一行一行程式碼看下去：
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();
// 得到 hash 值
int hash = spread(key.hashCode());
// 用於記錄相應連結串列的長度
int binCount = 0;
for (Node
[] tab = table;;) { Node
f; int n, i, fh; // 如果陣列”空”，進行陣列初始化
if (tab == null || (n = tab.length) == 0)
// 初始化陣列，後面會詳細介紹
tab = initTable();
// 找該 hash 值對應的陣列下標，得到第一個節點 f
else if ((f = tabAt(tab, i = (n – 1) & hash)) == null) {
// 如果陣列該位置為空，
// 用一次 CAS 操作將這個新值放入其中即可，這個 put 操作差不多就結束了，可以拉到最後面了
// 如果 CAS 失敗，那就是有併發操作，進到下一個迴圈就好了
if (casTabAt(tab, i, null,
new Node
(hash, key, value, null))) break; // no lock when adding to empty bin
}
// hash 居然可以等於 MOVED，這個需要到後面才能看明白，不過從名字上也能猜到，肯定是因為在擴容
else if ((fh = f.hash) == MOVED)
// 幫助資料遷移，這個等到看完資料遷移部分的介紹後，再理解這個就很簡單了
tab = helpTransfer(tab, f);
else { // 到這裡就是說，f 是該位置的頭結點，而且不為空
V oldVal = null;
// 獲取陣列該位置的頭結點的監視器鎖
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { // 頭結點的 hash 值大於 0，說明是連結串列
// 用於累加，記錄連結串列的長度
binCount = 1;
// 遍歷連結串列
for (Node
e = f;; ++binCount) { K ek;
// 如果發現了”相等”的 key，判斷是否要進行值改寫，然後也就可以 break 了
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
// 到了連結串列的最末端，將這個新值放到連結串列的最後面
Node
pred = e; if ((e = e.next) == null) {
pred.next = new Node
(hash, key, value, null);
break;
}
}
}
else if (f instanceof TreeBin) { // 紅黑樹
Node
p; binCount = 2;
// 呼叫紅黑樹的插值方法插入新節點
if ((p = ((TreeBin
)f).putTreeVal(hash, key, value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// binCount != 0 說明上面在做連結串列操作
if (binCount != 0) {
// 判斷是否要將連結串列轉換為紅黑樹，臨界值和 HashMap 一樣，也是 8
if (binCount >= TREEIFY_THRESHOLD)
// 這個方法和 HashMap 中稍微有一點點不同，那就是它不是一定會進行紅黑樹轉換，
// 如果當前陣列的長度小於 64，那麼會選擇進行陣列擴容，而不是轉換為紅黑樹
// 具體原始碼我們就不看了，擴容部分後面說
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//
addCount(1L, binCount);
return null;
}
put 的主流程看完了，但是至少留下了幾個問題，第一個是初始化，第二個是擴容，第三個是幫助資料遷移，這些我們都會在後面進行一一介紹。
初始化陣列：initTable
這個比較簡單，主要就是初始化一個合適大小的陣列，然後會設定 sizeCtl。
初始化方法中的併發問題是透過對 sizeCtl 進行一個 CAS 操作來控制的。
private final Node
[] initTable() { Node
[] tab; int sc; while ((tab = table) == null || tab.length == 0) {
// 初始化的”功勞”被其他執行緒”搶去”了
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// CAS 一下，將 sizeCtl 設定為 -1，代表搶到了鎖
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// DEFAULT_CAPACITY 預設初始容量是 16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 初始化陣列，長度為 16 或初始化時提供的長度
Node
[] nt = (Node [])new Node,?>[n]; // 將這個陣列賦值給 table，table 是 volatile 的
table = tab = nt;
// 如果 n 為 16 的話，那麼這裡 sc = 12
// 其實就是 0.75 * n
sc = n – (n >>> 2);
}
} finally {
// 設定 sizeCtl 為 sc，我們就當是 12 吧
sizeCtl = sc;
}
break;
}
}
return tab;
}
連結串列轉紅黑樹: treeifyBin
前面我們在 put 原始碼分析也說過，treeifyBin 不一定就會進行紅黑樹轉換，也可能是僅僅做陣列擴容。我們還是進行原始碼分析吧。
private final void treeifyBin(Node
[] tab, int index) { Node
b; int n, sc; if (tab != null) {
// MIN_TREEIFY_CAPACITY 為 64
// 所以，如果陣列長度小於 64 的時候，其實也就是 32 或者 16 或者更小的時候，會進行陣列擴容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// 後面我們再詳細分析這個方法
tryPresize(n << 1);
// b 是頭結點
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
// 加鎖
synchronized (b) {
if (tabAt(tab, index) == b) {
// 下麵就是遍歷連結串列，建立一顆紅黑樹
TreeNode
hd = null, tl = null; for (Node
e = b; e != null; e = e.next) { TreeNode
p = new TreeNode
(e.hash, e.key, e.val, null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
// 將紅黑樹設定到陣列相應位置中
setTabAt(tab, index, new TreeBin
(hd)); }
}
}
}
}
擴容：tryPresize
如果說 Java8 ConcurrentHashMap 的原始碼不簡單，那麼說的就是擴容操作和遷移操作。
這個方法要完完全全看懂還需要看之後的 transfer 方法，讀者應該提前知道這點。
這裡的擴容也是做翻倍擴容的，擴容後陣列容量為原來的 2 倍。
// 首先要說明的是，方法引數 size 傳進來的時候就已經翻了倍了
private final void tryPresize(int size) {
// c：size 的 1.5 倍，再加 1，再往上取最近的 2 的 n 次方。
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node
[] tab = table; int n;
// 這個 if 分支和之前說的初始化陣列的程式碼基本上是一樣的，在這裡，我們可以不用管這塊程式碼
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
[] nt = (Node [])new Node,?>[n]; table = nt;
sc = n – (n >>> 2); // 0.75 * n
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
// 我沒看懂 rs 的真正含義是什麼，不過也關係不大
int rs = resizeStamp(n);
if (sc < 0) {
Node
[] nt; if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 2. 用 CAS 將 sizeCtl 加 1，然後執行 transfer 方法
// 此時 nextTab 不為 null
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// 1. 將 sizeCtl 設定為 (rs << RESIZE_STAMP_SHIFT) + 2)
// 我是沒看懂這個值真正的意義是什麼？不過可以計算出來的是，結果是一個比較大的負數
// 呼叫 transfer 方法，此時 nextTab 引數為 null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
這個方法的核心在於 sizeCtl 值的操作，首先將其設定為一個負數，然後執行 transfer(tab, null)，再下一個迴圈將 sizeCtl 加 1，並執行 transfer(tab, nt)，之後可能是繼續 sizeCtl 加 1，並執行 transfer(tab, nt)。
所以，可能的操作就是執行 1 次 transfer(tab, null) + 多次 transfer(tab, nt)，這裡怎麼結束迴圈的需要看完 transfer 原始碼才清楚。
資料遷移：transfer
下麵這個方法很點長，將原來的 tab 陣列的元素遷移到新的 nextTab 陣列中。
雖然我們之前說的 tryPresize 方法中多次呼叫 transfer 不涉及多執行緒，但是這個 transfer 方法可以在其他地方被呼叫，典型地，我們之前在說 put 方法的時候就說過了，請往上看 put 方法，是不是有個地方呼叫了 helpTransfer 方法，helpTransfer 方法會呼叫 transfer 方法的。
此方法支援多執行緒執行，外圍呼叫此方法的時候，會保證第一個發起資料遷移的執行緒，nextTab 引數為 null，之後再呼叫此方法的時候，nextTab 不會為 null。
閱讀原始碼之前，先要理解併發操作的機制。原陣列長度為 n，所以我們有 n 個遷移任務，讓每個執行緒每次負責一個小任務是最簡單的，每做完一個任務再檢測是否有其他沒做完的任務，幫助遷移就可以了，而 Doug Lea 使用了一個 stride，簡單理解就是步長，每個執行緒每次負責遷移其中的一部分，如每次遷移 16 個小任務。所以，我們就需要一個全域性的排程者來安排哪個執行緒執行哪幾個任務，這個就是屬性 transferIndex 的作用。
第一個發起資料遷移的執行緒會將 transferIndex 指向原陣列最後的位置，然後從後往前的 stride 個任務屬於第一個執行緒，然後將 transferIndex 指向新的位置，再往前的 stride 個任務屬於第二個執行緒，依此類推。當然，這裡說的第二個執行緒不是真的一定指代了第二個執行緒，也可以是同一個執行緒，這個讀者應該能理解吧。其實就是將一個大的遷移任務分為了一個個任務包。
private final void transfer(Node
[] tab, Node [] nextTab) { int n = tab.length, stride;
// stride 在單核下直接等於 n，多核樣式下為 (n>>>3)/NCPU，最小值是 16
// stride 可以理解為”步長“，有 n 個位置是需要進行遷移的，
// 將這 n 個任務分為多個任務包，每個任務包有 stride 個任務
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 如果 nextTab 為 null，先進行一次初始化
// 前面我們說了，外圍會保證第一個發起遷移的執行緒呼叫此方法時，引數 nextTab 為 null
// 之後參與遷移的執行緒呼叫此方法時，nextTab 不會為 null
if (nextTab == null) {
try {
// 容量翻倍
Node
[] nt = (Node [])new Node,?>[n << 1]; nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
// nextTable 是 ConcurrentHashMap 中的屬性
nextTable = nextTab;
// transferIndex 也是 ConcurrentHashMap 的屬性，用於控制遷移的位置
transferIndex = n;
}
int nextn = nextTab.length;
// ForwardingNode 翻譯過來就是正在被遷移的 Node
// 這個構造方法會生成一個Node，key、value 和 next 都為 null，關鍵是 hash 為 MOVED
// 後面我們會看到，原陣列中位置 i 處的節點完成遷移工作後，
// 就會將位置 i 處設定為這個 ForwardingNode，用來告訴其他執行緒該位置已經處理過了
// 所以它其實相當於是一個標誌。
ForwardingNode
fwd = new ForwardingNode (nextTab);
// advance 指的是做完了一個位置的遷移工作，可以準備做下一個位置的了
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
/*
* 下麵這個 for 迴圈，最難理解的在前面，而要看懂它們，應該先看懂後面的，然後再倒回來看
*
*/
// i 是位置索引，bound 是邊界，註意是從後往前
for (int i = 0, bound = 0;;) {
Node
f; int fh;
// 下麵這個 while 真的是不好理解
// advance 為 true 表示可以進行下一個位置的遷移了
// 簡單理解結局：i 指向了 transferIndex，bound 指向了 transferIndex-stride
while (advance) {
int nextIndex, nextBound;
if (–i >= bound || finishing)
advance = false;
// 將 transferIndex 值賦給 nextIndex
// 這裡 transferIndex 一旦小於等於 0，說明原陣列的所有位置都有相應的執行緒去處理了
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex – stride : 0))) {
// 看括號中的程式碼，nextBound 是這次遷移任務的邊界，註意，是從後往前
bound = nextBound;
i = nextIndex – 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
// 所有的遷移操作已經完成
nextTable = null;
// 將新的 nextTab 賦值給 table 屬性，完成遷移
table = nextTab;
// 重新計算 sizeCtl：n 是原陣列長度，所以 sizeCtl 得出的值將是新陣列長度的 0.75 倍
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 之前我們說過，sizeCtl 在遷移前會設定為 (rs << RESIZE_STAMP_SHIFT) + 2
// 然後，每有一個執行緒參與遷移就會將 sizeCtl 加 1，
// 這裡使用 CAS 操作對 sizeCtl 進行減 1，代表做完了屬於自己的任務
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc – 1)) {
// 任務結束，方法退出
if ((sc – 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// 到這裡，說明 (sc – 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT，
// 也就是說，所有的遷移任務都做完了，也就會進入到上面的 if(finishing){} 分支了
finishing = advance = true;
i = n; // recheck before commit
}
}
// 如果位置 i 處是空的，沒有任何節點，那麼放入剛剛初始化的 ForwardingNode ”空節點“
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 該位置處是一個 ForwardingNode，代表該位置已經遷移過了
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// 對陣列該位置處的結點加鎖，開始處理陣列該位置處的遷移工作
synchronized (f) {
if (tabAt(tab, i) == f) {
Node
ln, hn; // 頭結點的 hash 大於 0，說明是連結串列的 Node 節點
if (fh >= 0) {
// 下麵這一塊和 Java7 中的 ConcurrentHashMap 遷移是差不多的，
// 需要將連結串列一分為二，
// 找到原連結串列中的 lastRun，然後 lastRun 及其之後的節點是一起進行遷移的
// lastRun 之前的節點需要進行克隆，然後分到兩個連結串列中
int runBit = fh & n;
Node
lastRun = f; for (Node
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
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
(ph, pk, pv, ln); else
hn = new Node
(ph, pk, pv, hn); }
// 其中的一個連結串列放在新陣列的位置 i
setTabAt(nextTab, i, ln);
// 另一個連結串列放在新陣列的位置 i+n
setTabAt(nextTab, i + n, hn);
// 將原陣列該位置處設定為 fwd，代表該位置已經處理完畢，
// 其他執行緒一旦看到該位置的 hash 值為 MOVED，就不會進行遷移了
setTabAt(tab, i, fwd);
// advance 設定為 true，代表該位置已經遷移完畢
advance = true;
}
else if (f instanceof TreeBin) {
// 紅黑樹的遷移
TreeBin
t = (TreeBin )f; TreeNode
lo = null, loTail = null; TreeNode
hi = null, hiTail = null; int lc = 0, hc = 0;
for (Node
e = t.first; e != null; e = e.next) { int h = e.hash;
TreeNode
p = new TreeNode (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;
}
}
// 如果一分為二後，節點數少於 8，那麼將紅黑樹轉換回連結串列
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin
(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin
(hi) : t;
// 將 ln 放置在新陣列的位置 i
setTabAt(nextTab, i, ln);
// 將 hn 放置在新陣列的位置 i+n
setTabAt(nextTab, i + n, hn);
// 將原陣列該位置處設定為 fwd，代表該位置已經處理完畢，
// 其他執行緒一旦看到該位置的 hash 值為 MOVED，就不會進行遷移了
setTabAt(tab, i, fwd);
// advance 設定為 true，代表該位置已經遷移完畢
advance = true;
}
}
}
}
}
}
說到底，transfer 這個方法並沒有實現所有的遷移任務，每次呼叫這個方法只實現了 transferIndex 往前 stride 個位置的遷移工作，其他的需要由外圍來控制。
這個時候，再回去仔細看 tryPresize 方法可能就會更加清晰一些了。
get 過程分析
get 方法從來都是最簡單的，這裡也不例外：
-
計算 hash 值
-
根據 hash 值找到陣列對應位置: (n – 1) & h
-
根據該位置處結點性質進行相應查詢
-
如果該位置為 null，那麼直接傳回 null 就可以了
-
如果該位置處的節點剛好就是我們需要的，傳回該節點的值即可
-
如果該位置節點的 hash 值小於 0，說明正在擴容，或者是紅黑樹，後面我們再介紹 find 方法
-
如果以上 3 條都不滿足，那就是連結串列，進行遍歷比對即可
public V get(Object key) {
Node
[] tab; Node 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;
}
// 如果頭結點的 hash 小於 0，說明 正在擴容，或者該位置是紅黑樹
else if (eh < 0)
// 參考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k)
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;
}
簡單說一句，此方法的大部分內容都很簡單，只有正好碰到擴容的情況，ForwardingNode.find(int h, Object k) 稍微複雜一些，不過在瞭解了資料遷移的過程後，這個也就不難了，所以限於篇幅這裡也不展開說了。
總結
其實也不是很難嘛，雖然沒有像之前的 AQS 和執行緒池一樣一行一行原始碼進行分析，但還是把所有初學者可能會糊塗的地方都進行了深入的介紹，只要是稍微有點基礎的讀者，應該是很容易就能看懂 HashMap 和 ConcurrentHashMap 原始碼了。
看原始碼不算是目的吧，深入地瞭解 Doug Lea 的設計思路，我覺得還挺有趣的，大師就是大師，程式碼寫得真的是好啊。
我發現很多人都以為我寫部落格主要是原始碼分析，說真的，我對於原始碼分析沒有那麼大熱情，主要都是為了用原始碼說事罷了，可能之後的文章還是會有比較多的原始碼分析成分，大家該怎麼看就怎麼看吧。
不要臉地自以為本文的質量還是挺高的，資訊量比較大，如果你覺得有寫得不好的地方，或者說看完本文你還是沒看懂它們，那麼請提出來~~~
看完本文有收穫？請轉發分享給更多人
關註「ImportNew」，提升Java技能
