重要的一些變量
//數(shù)組最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
//數(shù)組默認容量
private static final int DEFAULT_CAPACITY = 16;
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//轉換因子，一般是求閾值的時候用數(shù)組長度*轉換因子
private static final float LOAD_FACTOR = 0.75f;
//鏈表轉換紅黑樹的閾值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹轉換鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
//最小紅黑樹容量
static final int MIN_TREEIFY_CAPACITY = 64;
private static final int MIN_TRANSFER_STRIDE = 16;
private static int RESIZE_STAMP_BITS = 16;
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
//標識該節(jié)點正在遷移
static final int MOVED = -1;
//標識該節(jié)點是樹節(jié)點
static final int TREEBIN = -2;
static final int RESERVED = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
//獲取系統(tǒng)的CPU核數(shù)
static final int NCPU = Runtime.getRuntime().availableProcessors();
put方法分析
我們先看下流程圖：
OK，看了流程圖，腦海大概有個映象蟆沫，大概有以下幾點：
- 數(shù)組不存在的時候初始化數(shù)組。
- 數(shù)組下標位置節(jié)點不存在温治，則直接創(chuàng)建一個新的節(jié)點放進數(shù)組就可以饭庞。
- 數(shù)組下標位置存在節(jié)點，并且該節(jié)點正在進行節(jié)點的遷移熬荆，則當前線程就先幫助節(jié)點進行遷移舟山，再進行相應的新增節(jié)點操作。
- 數(shù)組下標位置存在節(jié)點且當前線程獲得當前節(jié)點的所有權卤恳，如果該節(jié)點是鏈表形式則直接插到鏈表尾累盗，如果是樹節(jié)點，則跟鏈表一樣若债。
- 如果一個數(shù)組下標位置處的鏈表節(jié)點超過8個，但是數(shù)組的長度小于最小數(shù)組長度64則對數(shù)組容量擴容拆融，一般是擴容為原來的2的n次方倍；如果節(jié)點處鏈表節(jié)點超過8個并且數(shù)組的長度大于等于最小數(shù)組長度64趟脂，則進行紅黑樹化泰讽，將新的樹設置到數(shù)組對應下標處。
大概總結了下，現(xiàn)在我們對put的源碼進行分析：
//往map加入數(shù)據(jù)
public V put(K key, V value) {
//onlyIfAbsent=true菇绵，只有在不存在該key時才會進行put操作
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
//key和value都不能為空
if (key == null || value == null) throw new NullPointerException();
//求hash
int hash = spread(key.hashCode());
//存儲鏈表元素個數(shù)
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//如果數(shù)組還沒有被創(chuàng)建
if (tab == null || (n = tab.length) == 0)
//初始化數(shù)組
tab = initTable();
//以volatile的形式獲取，數(shù)組的最后一個位置沒節(jié)點的話镇眷，直接創(chuàng)建node放進去
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
//如果是MOVED,說明正在擴容咬最，去幫助遷移
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 到這里就是說，f 是該位置的頭結點欠动，而且不為空
else {
V oldVal = null;
//鎖定當前節(jié)點永乌，防止并發(fā)
synchronized (f) {
//讀取i位置下的節(jié)點是不是當前鎖定節(jié)點f
if (tabAt(tab, i) == f) {
//說明是鏈表形式
if (fh >= 0) {
//記錄鏈表節(jié)點格式
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
//鏈表中已經(jīng)存在相同key
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
//onlyIfAbsent=true，只有在不存在該key時才會進行put操作
if (!onlyIfAbsent)
e.val = value;
//結束
break;
}
Node<K,V> pred = e;
//下一個節(jié)點已經(jīng)不存在
if ((e = e.next) == null) {
//直接放到下一個節(jié)點位置處
pred.next = new Node<K,V>(hash, key,
value, null);
//結束
break;
}
}
}
//樹形態(tài)的插入這里就不細講了
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;
}
}
}
}
//當前節(jié)點的鏈表節(jié)點個數(shù)不是0具伍，也就是是條鏈表或樹形式翅雏，而不是只是單個節(jié)點在數(shù)組
if (binCount != 0) {
//鏈表超過8個接點就轉換成樹節(jié)點
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
//要插入的key與鏈表的key一樣的舊值不為空，就返回舊值
if (oldVal != null)
return oldVal;
//結束
break;
}
}
}
addCount(1L, binCount);
return null;
}
其實整套ConcurrentHashMap難點就在擴容人芽，數(shù)據(jù)的轉移方面望几，所以我將單獨拉出來講：
- helpTransfer
如果當前線程添加節(jié)點的時候，發(fā)現(xiàn)數(shù)組正在擴容萤厅，那么當前線程就會幫助遷移橄抹，當然，幫助遷移調(diào)用的也是遷移節(jié)點的代碼惕味，代碼注釋很詳細了楼誓，這里也就不廢話了：
//關于 sizeCtl 變量：
//-1 :代表table正在初始化,其他線程應該交出CPU時間片
//-N: 表示正有N-1個線程執(zhí)行擴容操作（高 16 位是 length 生成的標識符，低 16 位是擴容的線程數(shù)）
//大于 0: 如果table已經(jīng)初始化,代表table容量,默認為table大小的0.75,如果還未初始化,代表需要初始化的大小
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
//ForwardingNode 翻譯過來就是正在被遷移的 Node
//關鍵是 hash 為 MOVED
// 后面我們會看到名挥，原數(shù)組中位置 i 處的節(jié)點完成遷移工作后疟羹，
//就會將位置 i 處設置為這個 ForwardingNode，用來告訴其他線程該位置已經(jīng)處理過了
//所以它其實相當于是一個標志禀倔。
//只有f的hash為MOVED榄融，才會執(zhí)行該方法，說明f節(jié)點是ForwardingNode
//如果nextTable為null,則表示遷移完成了蹋艺，詳見transfer()
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
// 根據(jù) length 得到一個標識符號
int rs = resizeStamp(tab.length);
// 如果 nextTab 沒有被并發(fā)修改 且 tab 也沒有被并發(fā)修改
// sizeCtl < 0 （說明還在擴容）
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
// 如果 sizeCtl 無符號右移 16 不等于 rs （ sc前 16 位如果不等于標識符剃袍，則標識符變化了）
// 或者 sizeCtl == rs + 1 （擴容結束了，不再有線程進行擴容）（默認第一個線程設置 sc ==rs 左移 16 位 + 2捎谨，
// 當?shù)谝粋€線程結束擴容了民效，就會將 sc 減一。這個時候涛救，sc 就等于 rs + 1）
// 或者 sizeCtl == rs + 65535 （如果達到最大幫助線程的數(shù)量畏邢，即 65535）
// 或者轉移下標正在調(diào)整 （擴容結束）
// 結束循環(huán)，返回 table
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
// 如果以上都不是, 將 sizeCtl + 1, （表示增加了一個線程幫助其擴容）
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
//進行擴容轉移
transfer(tab, nextTab);
//擴容完退出循環(huán)
break;
}
}
//返回遷移的節(jié)點
return nextTab;
}
return table;
}
- transfer
舊的節(jié)點遷移到新的數(shù)組中检吆，流程圖如下：
節(jié)點遷移的代碼比較難理解舒萎，以我的理解大概概括成以下幾點：
- 根據(jù)系統(tǒng)的cpu核數(shù)，計算出每個線程的步數(shù)蹭沛，也就是各自負責遷移數(shù)組長度臂寝，默認最小步長是16章鲤。
- 如果還沒有創(chuàng)建新數(shù)組，則創(chuàng)建新的數(shù)組咆贬，容量是舊數(shù)組的2倍败徊。
- 遷移節(jié)點的時候如果碰到舊數(shù)組的對應節(jié)點不存在，則直接放一個ForwardingNode（表示正在節(jié)點遷移）掏缎，無需進行節(jié)點遷移皱蹦。
- 如果舊數(shù)組的節(jié)點還未遷移完成，當前節(jié)點存在且當前線程獲得當前節(jié)點的操作權眷蜈，判斷該節(jié)點是什么類型的節(jié)點沪哺，假如是鏈表形式，轉移的時候會維護兩條鏈表酌儒，其中一條是放置新數(shù)組的位置和舊數(shù)組一樣辜妓，另一條則是舊數(shù)組位置下標加上舊數(shù)組的長度。而它是runBit屬性區(qū)分要把哪個節(jié)點放置哪條鏈表的今豆，runBit取值只有0和1嫌拣。
- 將鏈表從頭遍歷到尾，記錄最后一次與其它節(jié)點的runBit不一樣的節(jié)點呆躲，并且記錄這個節(jié)點异逐，當然這樣的好處在后面遍歷創(chuàng)建節(jié)點的時候就不用再遍歷記錄的這個節(jié)點以及它的那些后驅節(jié)點。
- 遍歷j舊的鏈表完畢后形成新的兩條鏈表插掂，將兩條鏈表設置到新數(shù)組相應位置灰瞻。
- 當然樹的遷移跟鏈表差不多，值得一說的是辅甥，當變成兩課樹節(jié)點后酝润，分別對兩棵樹判斷樹節(jié)點個數(shù)是不是小于8個，小于8個則會轉換成鏈表璃弄，這里就不多說要销，源碼中我都做了詳細的注釋。
//數(shù)據(jù)轉移和擴容
//每個調(diào)用tranfer的線程會對當前舊table中[transferIndex-stride, transferIndex-1]位置的結點進行遷移
//@param tab 舊table數(shù)組
//@param nextTab 新table數(shù)組
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
//stride代表步長夏块，從后往前數(shù)
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;
//nextTab表示為新的表
// 如果 nextTab 為 null政己，先進行一次初始化
//外圍會保證第一個發(fā)起遷移的線程調(diào)用此方法時酌壕，參數(shù) nextTab 為 null
//之后參與遷移的線程調(diào)用此方法時，nextTab 不會為 null
if (nextTab == null) {
try {
//創(chuàng)建新的Node數(shù)組的容量翻倍，并作為nextTab
@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-stride, transferIndex-1]表示當前線程要進行數(shù)據(jù)遷移的桶區(qū)間
//記錄當前轉移的位置
transferIndex = n;
}
int nextn = nextTab.length;
// ForwardingNode結點卵牍，當舊table的某個桶中的所有結點都遷移完后果港，用該結點占據(jù)這個桶
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// 標識一個桶的遷移工作是否完成，advance == true 表示可以進行下一個位置的遷移
boolean advance = true;
// 最后一個數(shù)據(jù)遷移的線程將該值置為true糊昙，并進行本輪擴容的收尾工作
boolean finishing = false;
// i標識桶索引, bound標識邊界
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// 每一次自旋前的預處理京腥，主要是定位本輪處理的桶區(qū)間
// 正常情況下，預處理完成后：i == transferIndex-1溅蛉，bound == transferIndex-stride
while (advance) {
int nextIndex, nextBound;
//判斷達到了bound值，或者最后一個數(shù)據(jù)搬完他宛，advance標注false船侧，準備退出循環(huán)
if (--i >= bound || finishing)
advance = false;
//這里 transferIndex 一旦小于等于 0，說明原數(shù)組的所有位置都有相應的線程去處理了
//標注false準備退出
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//cas計算下一個任務索引位置
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
//當前是處理最后一個需要tranfer任務的線程或出現(xiàn)擴容沖突
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
//是否遷移完成厅各，遷移完成用nextTab替換table
if (finishing) {
nextTable = null;
table = nextTab;
//sizeCtl閾值為原來的1.5倍
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
}
}
//舊桶本身為null，不用遷移焰情，直接嘗試放一個ForwardingNode
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 該位置處是一個 ForwardingNode陌凳，代表該位置已經(jīng)遷移過了
//這里是控制并發(fā)擴容的核心
//該舊桶已經(jīng)遷移完成，直接跳過
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
//該舊桶未遷移完成内舟，進行數(shù)據(jù)遷移
else {
// 對數(shù)組該位置處的結點加鎖合敦，開始處理數(shù)組該位置處的遷移工作
synchronized (f) {
//對應的下表拿到的節(jié)點是否與當前加鎖的f節(jié)點是同一個節(jié)點
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// 頭結點的 hash 值大于 0，說明是鏈表
if (fh >= 0) {
/**
* 下面的過程會將舊桶中的鏈表分成兩部分：ln鏈和hn鏈
* ln鏈會插入到新table的槽i中验游，hn鏈會插入到新table的槽i+n中
*/
//簡單說就是區(qū)分舊的節(jié)點要放在新數(shù)組什么位置充岛，0-與舊的數(shù)組一樣的位置，1-舊數(shù)組位置+n的位置
int runBit = fh & n; // 由于n是2的冪次批狱，所以runBit要么是0裸准，要么高位是1
Node<K,V> lastRun = f; // lastRun指向最后一個相鄰runBit不同的結點
//將f節(jié)點后面的節(jié)點進行遍歷
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
//如果下一個節(jié)點不是處于相同鏈表的節(jié)點
if (b != runBit) {
//runBit重新賦值，也結束runBit變?yōu)榕c剛才不同的值
//比如一開始0赔硫，現(xiàn)在變?yōu)?
runBit = b;
//記住這次不一樣的節(jié)點炒俱，然后繼續(xù)循環(huán)，直到?jīng)]值了，記錄最后一個不一樣RunBit的節(jié)點
lastRun = p;
}
}
//ln鏈表是放新鏈表位置與舊鏈表的位置相同
if (runBit == 0) {
ln = lastRun;
hn = null;
}
//hn鏈表是放新鏈表位置=舊鏈表的位置+n(舊數(shù)組長度)
else {
hn = lastRun;
ln = null;
}
//因為lastRun和它后面的節(jié)點已經(jīng)賦值給ln或hn权悟，則這里就不用遍歷了
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);
}
// 其中的一個鏈表放在新數(shù)組的位置 i
setTabAt(nextTab, i, ln);
// 另一個鏈表放在新數(shù)組的位置 i+n
setTabAt(nextTab, i + n, hn);
// 將原數(shù)組該位置處設置為 fwd砸王，代表該位置已經(jīng)處理完畢，
// 其他線程一旦看到該位置的 hash 值為 MOVED峦阁，就不會進行遷移了
setTabAt(tab, i, fwd);
// advance 設置為 true谦铃，代表該位置已經(jīng)遷移完畢
advance = true;
}
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
//也是維護了兩棵樹lo,hi
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
//遍歷樹節(jié)點
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);
//runBit==0則節(jié)點放lo
if ((h & n) == 0) {
//當前節(jié)點的前驅節(jié)點，也就是loTail記錄的尾結點
if ((p.prev = loTail) == null)
//放在低位鏈表
lo = p;
//尾結點有值榔昔，就將尾結點的next指針指向當前節(jié)點
else
loTail.next = p;
//更新尾結點
loTail = p;
//低位節(jié)點統(tǒng)計
++lc;
}
//runBit==1則節(jié)點放hi
else {
////當前節(jié)點的前驅節(jié)點驹闰，也就是hiTail記錄的尾結點
if ((p.prev = hiTail) == null)
//放在高位鏈表
hi = p;
//尾結點有值，就將尾結點的next指針指向當前節(jié)點
else
hiTail.next = p;
//更新尾結點
hiTail = p;
//高位節(jié)點統(tǒng)計
++hc;
}
}
// 如果一分為二后撒会，節(jié)點數(shù)少于 8嘹朗，那么將紅黑樹轉換回鏈表
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
// 如果一分為二后，節(jié)點數(shù)少于 8诵肛，那么將紅黑樹轉換回鏈表
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
// 將 ln 放置在新數(shù)組的位置 i
setTabAt(nextTab, i, ln);
// 將 hn 放置在新數(shù)組的位置 i+n
setTabAt(nextTab, i + n, hn);
// 將原數(shù)組該位置處設置為 fwd屹培，代表該位置已經(jīng)處理完畢，
// 其他線程一旦看到該位置的 hash 值為 MOVED怔檩，就不會進行遷移了
setTabAt(tab, i, fwd);
// advance 設置為 true褪秀，代表該位置已經(jīng)遷移完畢
advance = true;
}
}
}
}
}
}
- treeifyBin
我們還是先看下流程圖：
由鏈表轉成紅黑樹結構大概概括以下幾點：
- 如果數(shù)組的長度小于最小數(shù)組長度64的話則進行擴容，而不進行紅黑樹化薛训，擴容為原來長度的2的n次方倍媒吗。
- 如果是鏈表結構并且個數(shù)超過8，則進行紅黑樹化乙埃，詳細看我源代碼注釋蝴猪。
//當數(shù)組長度小于64的時候，擴張數(shù)組長度一倍膊爪，否則的話把鏈表轉為樹
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
//數(shù)組不為空
if (tab != null) {
//數(shù)組的長度小于64的話自阱，這是約束
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
//嘗試調(diào)整表的大小以適應給定的元素數(shù)量,擴容為原來的2的n次方倍
tryPresize(n << 1);
//找到下角標為index的節(jié)點，不為空米酬，并且hash大于0沛豌，說明是鏈表形式的，下面變成樹
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
//雙重確認赃额，再次確認index節(jié)點下的節(jié)點是不是跟剛取出來的b是同個節(jié)點加派，防止并發(fā)
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
//遍歷鏈表
for (Node<K,V> e = b; e != null; e = e.next) {
//創(chuàng)建樹節(jié)點
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
//如果當前樹節(jié)點沒有前驅節(jié)點，將當前節(jié)點給hd頭結點跳芳，也就是p自己成為頭結點
if ((p.prev = tl) == null)
hd = p;
//如果當前樹節(jié)點有前驅節(jié)點芍锦，并且是tl尾結點,則將tl的next指針指向p，讓p成為tl后驅節(jié)點
else
tl.next = p;
tl = p;
}
//整棵樹設置進數(shù)組的index處飞盆，完成鏈表到樹的轉換
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
- tryPresize
//將數(shù)組擴容為原來的2的n次方倍娄琉，size參數(shù)傳進來的時候是n << 1次乓，也就是已經(jīng)變成原來的兩倍
public final void tryPresize(int size) {
//size在傳入之前就已經(jīng)翻倍了，最終c是一個大于等于（size * 1.5 + 1）的2的冪次方數(shù)
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
//此時的sizeCtl是cap * 0.75孽水，擴容閾值
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
//如果數(shù)組還沒被初始化票腰，則嘗試進行數(shù)組的初始化
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;
//n默認16，將sc也就是后面要給sizeCtl閾值變?yōu)?2女气，也就是原來大小的0.75
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
//一直擴容到的c小于等于sizeCtl或者數(shù)組長度大于最大長度的時候杏慰，則退出
//所以在一次擴容之后，不是原來長度的兩倍炼鞠，而是2的n次方倍
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
//table不為空缘滥，且在此期間其他線程未修改table
else if (tab == table) {
int rs = resizeStamp(n);
//數(shù)組正在擴容，因為sc<0
if (sc < 0) {
Node<K,V>[] nt;
// 如果 sizeCtl 無符號右移 16 不等于 rs （ sc前 16 位如果不等于標識符谒主，則標識符變化了）完域，數(shù)組數(shù)據(jù)遷移還沒結束
// 或者 sizeCtl == rs + 1 （擴容結束了，不再有線程進行擴容）（默認第一個線程設置 sc ==rs 左移 16 位 + 2瘩将，
// 當?shù)谝粋€線程結束擴容了，就會將 sc 減一凹耙。這個時候姿现，sc 就等于 rs + 1）
// 或者 sizeCtl == rs + 65535 （如果達到最大幫助線程的數(shù)量，即 65535）
// 或者轉移下標正在調(diào)整 （擴容結束）
// 結束循環(huán)肖抱，返回 table
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
//cas比較嘗試將sc加一备典，代表當前線程幫助數(shù)組擴容
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
//遷移數(shù)據(jù)
transfer(tab, nt);
}
//到這里說明沒有線程在擴容，沒有線程在遷移數(shù)據(jù)意述，所以cas設置比較sc的值
//默認第一個線程設置 sc ==rs 左移 16 位 + 2提佣，
//當?shù)谝粋€線程結束擴容了，就會將 sc 減一荤崇。這個時候拌屏，sc 就等于 rs + 1
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
//遷移數(shù)據(jù)
transfer(tab, null);
}
}
}
get方法分析
以下是流程圖：
看了上面的put方法解析，看get會容易很多术荤，因為難點都在put,簡單概括幾點：
- 數(shù)組存在且找到相應的節(jié)點與要找的key一樣倚喂，則直接返回該節(jié)點的值。
- 如果找到節(jié)點正在遷移或者是樹節(jié)點瓣戚，則用ForwardingNode的查找方法對新數(shù)組進行查找或者用TreeNode的查找方法進行查找端圈。
- 如果是鏈表節(jié)點則遍歷查找即可。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
//找到數(shù)組相應位置的節(jié)點子库，并且節(jié)點的key和當前key想的 則直接返回
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;
}
//數(shù)組正在擴容,調(diào)用ForwardingNode的find去查找舱权，當搬一個舊的節(jié)點到新數(shù)組的時候，就會在
//舊的數(shù)組該節(jié)點出設置為ForwardingNode
//這里有可能調(diào)用TreeNode的find方法仑嗅，TreeNode=-2宴倍，F(xiàn)orwardingNode=-1
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
//到這里 節(jié)點是鏈表形式的张症，開始遍歷比對key返回
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方法
static final class ForwardingNode<K,V> extends Node<K,V> {
//新的數(shù)組
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
Node<K,V> find(int h, Object k) {
//tab是搬遷后的新數(shù)組
outer: for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; int n;
//新數(shù)組為空或者在新數(shù)組中沒有找到
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
//到這塊就是在新數(shù)組里已經(jīng)定位到
//自旋比對key，找到對應的key
for (;;) {
int eh; K ek;
//如果key相同就返回相應節(jié)點啊楚，結束
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
//如果該節(jié)點正在搬遷,或者是樹節(jié)點吠冤，-1是ForwardingNode，-2是TreeNode
if (eh < 0) {
//如果是正在搬遷的節(jié)點恭理，將它維護的數(shù)組重新對tab賦值拯辙，回到for循環(huán)，也就是更新tab,
//因為正在搬遷颜价，所以新數(shù)組里面的節(jié)點都是處于不斷更新的狀態(tài)
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
//該節(jié)點是樹節(jié)點涯保，則調(diào)用TreeNode的查找方法，按樹的格式查找節(jié)點
else
return e.find(h, k);
}
//查找下一個節(jié)點
if ((e = e.next) == null)
return null;
}
}
}
}
remove方法分析
簡單地做一下概括：
- 要刪除的節(jié)點不存在則不進行任何操作周伦，直接返回空夕春。
- 如果要刪除的節(jié)點正在遷移，則當前線程先去幫助遷移专挪，后續(xù)再進行相應的刪除操作及志。
- 不管是樹節(jié)點還是鏈表刪除都是對其進行遍歷，然后將指針的引用
public V remove(Object key) {
return replaceNode(key, null, null);
}
- replaceNode
final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
//自旋
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//數(shù)組為空或者數(shù)組下標對應的節(jié)點不存在寨腔，就直接跳出自旋速侈，返回空
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
//如果該節(jié)點正在遷移數(shù)據(jù)，當前線程幫助遷移
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//存在節(jié)點迫卢，且節(jié)點沒有處于搬遷狀態(tài)
else {
V oldVal = null;
//校驗標識倚搬，只要獲得鎖，進入鏈表節(jié)點或者樹節(jié)點乾蛤，都會更改為true
boolean validated = false;
//鎖定頭結點
synchronized (f) {
//再次確認數(shù)組當前索引下的節(jié)點是否變更每界，沒變更則開始進行相應的操作
if (tabAt(tab, i) == f) {
//鏈表形式
if (fh >= 0) {
//校驗標識設為true
validated = true;
//這個過程是遍歷當前頭結點下的所有節(jié)點，直到找到與我們當前要刪除的key一樣的key,
//然后修改相應頭尾指針和設置數(shù)組新的頭結點等等
for (Node<K,V> e = f, pred = null;;) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
V ev = e.val;
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
e.val = value;
else if (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
//該節(jié)點是紅黑樹節(jié)點家卖，跟鏈表差不多眨层，這里就不做過多解釋
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))) {
oldVal = pv;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
//刪除了節(jié)點
if (validated) {
if (oldVal != null) {
//value是參數(shù)，它必為空上荡，則進行
//增加計數(shù)谐岁，如果表太小且尚未調(diào)整大小，則開始數(shù)據(jù)遷移榛臼。
//如果已經(jīng)調(diào)整大小伊佃，則在工作可用時幫助執(zhí)行轉移。
//轉移后重新檢查占用率沛善，以查看是否已經(jīng)需要其他調(diào)整大小航揉，因為調(diào)整大小是滯后的。
if (value == null)
addCount(-1L, -1);
//返回刪除后的節(jié)點值
return oldVal;
}
break;
}
}
}
return null;
}
