大家推薦個靠譜的公衆号程式員探索之路,大家一起加油,這個公衆号已經接入圖靈
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注意與HasMap不一樣 &的是HASH_BITS 目的是散列更均勻 具體自查
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();
//得到hash值對應的數組下标,擷取第一個節點f
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果數組該位置為空,
// 用一次 CAS 操作将這個新值放入其中即可
// 如果 CAS 失敗,進到下一個循環就好了
if (casTabAt(tab, i, null,
new Node<K,V>(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 {
V oldVal = null;
// 此時 f是該位置的第一個節點 synchronized鎖住目前的位置的連結清單或者紅黑樹
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { // 判斷是否是連結清單
binCount = 1;
// 周遊連結清單
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 如果是相等的 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;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
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 其實 裡面還有一層判斷
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
put 的主流程看完了,但是至少留下了幾個問題,第一個是初始化,第二個是擴容,第三個是幫助資料遷移,這些我們都會在後面進行一一介紹。
初始化數組:initTable
這個比較簡單,主要就是初始化一個合适大小的數組,然後會設定 sizeCtl。
初始化方法中的并發問題是通過對 sizeCtl 進行一個 CAS 操作來控制的。
//這個初始化方法 使用的是cas算法 可以看看大師是如何巧妙地使用cas 來達到先判斷後執行也能實作同步
/**
整體思路是這樣的 如果目前線程搶占到時間片來執行初始化map 那麼會将 sizeCtl設定為-1 因為是單個原子變量執行cas是以隻有一個會成功,
那麼别的線程看到 sizeCtl < 0 就會明白有線程正在執行初始化,就不需要自己操心了,放棄目前時間片讓别的線程執行,然後進入下一次
循環大家會發現U.compareAndSwapInt(this, SIZECTL, sc, -1) 操作的是SIZECTL,點進去會發現是
SIZECTL = U.objectFieldOffset(k.getDeclaredField("sizeCtl"));隻是原子的域更新器,如有需要自查(我也解釋不清楚)
大家就認為更新的是sizeCtl就行了 這樣就能保證隻有一個線程能執行 初始化操作
*/
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
// sizeCtl 設定為 -1,代表該線程要執行初始化
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
//預設初始容量是 16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 初始化數組,長度為 16
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
// 将這個數組指派給 table,table 是 volatile 的
table = tab = nt;
// 如果 n 為 16 的話,那麼這裡 sc = 12
// 其實就是 0.75 * n
sc = n - (n >>> 2);
}
} finally {
// 設定 sizeCtl 為 sc 那麼他将大于0
sizeCtl = sc;
}
break;
}
}
return tab;
}
擴容和轉成紅黑樹來自:
https://javadoop.com/post/hashmap
連結清單轉紅黑樹: treeifyBin
前面我們在 put 源碼分析也說過,treeifyBin 不一定就會進行紅黑樹轉換,也可能是僅僅做數組擴容。我們還是進行源碼分析吧。
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> 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<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(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<K,V>(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<K,V>[] 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<K,V>[] nt = (Node<K,V>[])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<K,V>[] 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<K,V>[] tab, Node<K,V>[] 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<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 是 ConcurrentHashMap 中的屬性
nextTable = nextTab;
// transferIndex 也是 ConcurrentHashMap 的屬性,用于控制遷移的位置
transferIndex = n;
}
int nextn = nextTab.length;
// ForwardingNode 翻譯過來就是正在被遷移的 Node
// 這個構造方法會生成一個Node,key、value 和 next 都為 null,關鍵是 hash 為 MOVED
// 後面我們會看到,原數組中位置 i 處的節點完成遷移工作後,
// 就會将位置 i 處設定為這個 ForwardingNode,用來告訴其他線程該位置已經處理過了
// 是以它其實相當于是一個标志。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// advance 指的是做完了一個位置的遷移工作,可以準備做下一個位置的了
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
/*
* 下面這個 for 循環,最難了解的在前面,而要看懂它們,應該先看懂後面的,然後再倒回來看
*
*/
// i 是位置索引,bound 是邊界,注意是從後往前
for (int i = 0, bound = 0;;) {
Node<K,V> 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<K,V> ln, hn;
// 頭結點的 hash 大于 0,說明是連結清單的 Node 節點
if (fh >= 0) {
// 下面這一塊和 Java7 中的 ConcurrentHashMap 遷移是差不多的,
// 需要将連結清單一分為二,
// 找到原連結清單中的 lastRun,然後 lastRun 及其之後的節點是一起進行遷移的
// lastRun 之前的節點需要進行克隆,然後分到兩個連結清單中
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);
}
// 其中的一個連結清單放在新數組的位置 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<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;
}
}
// 如果一分為二後,節點數少于 8,那麼将紅黑樹轉換回連結清單
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;
// 将 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<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;
}
// 如果頭結點的 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;
}