1.JDK1.7
數(shù)據(jù)結(jié)構(gòu)：
- 分為兩級數(shù)組，外面有一個Segment數(shù)組，大小與并發(fā)級別有關(guān)
- 每個Segment管理一個HashEntry數(shù)組
Segment鎖機制：
- 比如put，在Segment里面put時，先要加鎖tryLock()
- Segment繼承了ReentrantLock
- tryLock()失敗后，進入while(!tryLock)循環(huán)，創(chuàng)建HashEntry，自旋達到閾值后（64/1），直接lock()阻塞
哈希尋址：
- 第一步用來定位Segment位置，這里取的是高位
- 第二步用來定位Segment里面小數(shù)組的位置
擴容rehash()：
- 是Segment里面的數(shù)組進行擴容
- lastRun機制
末尾放到同一個位置的連續(xù)鏈表；
直接插入到新數(shù)組位置；
移動：只用移動鏈表頭到lastRun的元素。
get()：
- 首先定位Segment
- 其次定位HashEntry
- 最后遍歷鏈表
size()：
- 第一次不加鎖
- 第二次也不加鎖，如果與第一次相等，則返回統(tǒng)計數(shù)值
- 第三次加鎖統(tǒng)計（對所有segment都加鎖）
2.JDK1.8
2.1 數(shù)據(jù)結(jié)構(gòu)
基本數(shù)據(jù)結(jié)構(gòu)是數(shù)組，發(fā)送哈希沖突時采用鏈表解決，如果數(shù)組大小達到64并且鏈表長度達到8，則轉(zhuǎn)換為紅黑樹。
通過節(jié)點的hash值區(qū)分不同節(jié)點：
- ForwardingNode，擴容時被轉(zhuǎn)移的節(jié)點，hash值是-1
- TreeBin，紅黑樹，hash值是-2
- 正常鏈表Node節(jié)點，會通過spread()后的，會跟0x7fffffff相與，是個大于0的數(shù)
2.1.1 數(shù)組大小
數(shù)組的大小為2的冪次方：返回>=c的最小的2的次方數(shù)
private static final int tableSizeFor(int c) {
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
2.1.2 sizeCtl
- sizeCtl < 0
1） -1 表示當前table正在初始化（有線程在創(chuàng)建table數(shù)組），當前線程需要自旋等待..
2）表示當前table數(shù)組正在進行擴容 ,高16位表示：擴容的標識戳 低16位表示：（1 + nThread） 當前參與并發(fā)擴容的線程數(shù)量 - sizeCtl = 0，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
- sizeCtl > 0
1）如果table未初始化，表示初始化大小
2）如果table已經(jīng)初始化，表示下次擴容時的 觸發(fā)條件（閾值）
/**
* sizeCtl < 0
* 1. -1 表示當前table正在初始化（有線程在創(chuàng)建table數(shù)組），當前線程需要自旋等待..
* 2.表示當前table數(shù)組正在進行擴容 ,高16位表示：擴容的標識戳 低16位表示：（1 + nThread） 當前參與并發(fā)擴容的線程數(shù)量
*
* sizeCtl = 0，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
*
* sizeCtl > 0
*
* 1. 如果table未初始化，表示初始化大小
* 2. 如果table已經(jīng)初始化，表示下次擴容時的 觸發(fā)條件（閾值）
*/
private transient volatile int sizeCtl;
2.1.3 數(shù)組初始化
在put()中進行延遲初始化
/**
* Initializes table, using the size recorded in sizeCtl.
* * sizeCtl < 0
* * 1. -1 表示當前table正在初始化（有線程在創(chuàng)建table數(shù)組），當前線程需要自旋等待..
* * 2.表示當前table數(shù)組正在進行擴容 ,高16位表示：擴容的標識戳 低16位表示：（1 + nThread） 當前參與并發(fā)擴容的線程數(shù)量
* *
* * sizeCtl = 0，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
* *
* * sizeCtl > 0
* *
* * 1. 如果table未初始化，表示初始化大小
* * 2. 如果table已經(jīng)初始化，表示下次擴容時的 觸發(fā)條件（閾值）
*/
private final Node<K,V>[] initTable() {
//tab 引用map.table
//sc sizeCtl的臨時值
Node<K,V>[] tab; int sc;
//自旋 條件：map.table 尚未初始化
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
//大概率就是-1，表示其它線程正在進行創(chuàng)建table的過程，當前線程沒有競爭到初始化table的鎖。
Thread.yield(); // lost initialization race; just spin
//1.sizeCtl = 0，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
//2.如果table未初始化，表示初始化大小
//3.如果table已經(jīng)初始化，表示下次擴容時的 觸發(fā)條件（閾值）
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//這里為什么又要判斷呢？ 防止其它線程已經(jīng)初始化完畢了，然后當前線程再次初始化..導致丟失數(shù)據(jù)。
//條件成立，說明其它線程都沒有進入過這個if塊，當前線程就是具備初始化table權(quán)利了。
if ((tab = table) == null || tab.length == 0) {
//sc大于0 創(chuàng)建table時 使用 sc為指定大小，否則使用 16 默認值.
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
//最終賦值給 map.table
table = tab = nt;
//n >>> 2 => 等于 1/4 n n - (1/4)n = 3/4 n => 0.75 * n
//sc 0.75 n 表示下一次擴容時的觸發(fā)條件。
sc = n - (n >>> 2);
}
} finally {
//1.如果當前線程是第一次創(chuàng)建map.table的線程話，sc表示的是 下一次擴容的閾值
//2.表示當前線程 并不是第一次創(chuàng)建map.table的線程，當前線程進入到else if 塊 時，將
//sizeCtl 設(shè)置為了-1 ，那么這時需要將其修改為 進入時的值。
sizeCtl = sc;
}
break;
}
}
return tab;
}
2.1.4 TreeBin鎖狀態(tài)
1.寫鎖狀態(tài) 寫是獨占狀態(tài)，以散列表來看，真正進入到TreeBin中的寫線程 同一時刻 只有一個線程。 1
2.讀鎖狀態(tài) 讀鎖是共享，同一時刻可以有多個線程 同時進入到 TreeBin對象中獲取數(shù)據(jù)。 每一個線程 都會給 lockStat + 4
3.等待者狀態(tài)（寫線程在等待），當TreeBin中有讀線程目前正在讀取數(shù)據(jù)時，寫線程無法修改數(shù)據(jù)，那么就將lockState的最低2位 設(shè)置為 0b 10
/**
* 1.寫鎖狀態(tài) 寫是獨占狀態(tài)，以散列表來看，真正進入到TreeBin中的寫線程 同一時刻 只有一個線程。 1
* 2.讀鎖狀態(tài) 讀鎖是共享，同一時刻可以有多個線程 同時進入到 TreeBin對象中獲取數(shù)據(jù)。 每一個線程 都會給 lockStat + 4
* 3.等待者狀態(tài)（寫線程在等待），當TreeBin中有讀線程目前正在讀取數(shù)據(jù)時，寫線程無法修改數(shù)據(jù)，那么就將lockState的最低2位 設(shè)置為 0b 10
*/
volatile int lockState;
2.2 get()
public V get(Object key) {
//tab 引用map.table
//e 當前元素
//p 目標節(jié)點
//n table數(shù)組長度
//eh 當前元素hash
//ek 當前元素key
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//擾動運算后得到 更散列的hash值
int h = spread(key.hashCode());
//條件一：(tab = table) != null
//true->表示已經(jīng)put過數(shù)據(jù)，并且map內(nèi)部的table也已經(jīng)初始化完畢
//false->表示創(chuàng)建完map后，并沒有put過數(shù)據(jù)，map內(nèi)部的table是延遲初始化的，只有第一次寫數(shù)據(jù)時會觸發(fā)創(chuàng)建邏輯。
//條件二：(n = tab.length) > 0 true->表示table已經(jīng)初始化
//條件三：(e = tabAt(tab, (n - 1) & h)) != null
//true->當前key尋址的桶位 有值
//false->當前key尋址的桶位中是null，是null直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//前置條件：當前桶位有數(shù)據(jù)
//對比頭結(jié)點hash與查詢key的hash是否一致
//條件成立：說明頭結(jié)點與查詢Key的hash值 完全一致
if ((eh = e.hash) == h) {
//完全比對 查詢key 和 頭結(jié)點的key
//條件成立：說明頭結(jié)點就是查詢數(shù)據(jù)
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//條件成立：
//1.-1 fwd 說明當前table正在擴容，且當前查詢的這個桶位的數(shù)據(jù) 已經(jīng)被遷移走了
//2.-2 TreeBin節(jié)點，需要使用TreeBin 提供的find 方法查詢。
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
//當前桶位已經(jīng)形成鏈表的這種情況
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
這里對hash值進行了處理，使高位向低位融合，是為了得到更散列的hash值。
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
上面eh < 0，有兩種情況：
- ForwardingNode，此時回去nextTable里面查找
- TreeBin，此時獲取紅黑樹查找（這里嘗試加讀鎖進行樹查找，如果沒加成功，則進行鏈表查找）
ForwardingNode#find
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
//tab 一定不為空
Node<K,V>[] tab = nextTable;
outer: for (;;) {
//n 表示為擴容而創(chuàng)建的 新表的長度
//e 表示在擴容而創(chuàng)建新表使用 尋址算法 得到的 桶位頭結(jié)點
Node<K,V> e; int n;
//條件一：永遠不成立
//條件二：永遠不成立
//條件三：永遠不成立
//條件四：在新擴容表中 重新定位 hash 對應(yīng)的頭結(jié)點
//true -> 1.在oldTable中 對應(yīng)的桶位在遷移之前就是null
// 2.擴容完成后，有其它寫線程，將此桶位設(shè)置為了null
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
//前置條件：擴容后的表 對應(yīng)hash的桶位一定不是null，e為此桶位的頭結(jié)點
//e可能為哪些node類型？
//1.node 類型
//2.TreeBin 類型
//3.FWD 類型
for (;;) {
//eh 新擴容后表指定桶位的當前節(jié)點的hash
//ek 新擴容后表指定桶位的當前節(jié)點的key
int eh; K ek;
//條件成立：說明新擴容 后的表，當前命中桶位中的數(shù)據(jù)，即為 查詢想要數(shù)據(jù)。
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
//eh<0
//1.TreeBin 類型 2.FWD類型（新擴容的表，在并發(fā)很大的情況下，可能在此方法 再次拿到FWD類型..）
if (eh < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
else
//說明此桶位 為 TreeBin 節(jié)點，使用TreeBin.find 查找紅黑樹中相應(yīng)節(jié)點。
return e.find(h, k);
}
//前置條件：當前桶位頭結(jié)點 并沒有命中查詢，說明此桶位是 鏈表
//1.將當前元素 指向鏈表的下一個元素
//2.判斷當前元素的下一個位置 是否為空
// true->說明迭代到鏈表末尾，未找到對應(yīng)的數(shù)據(jù)，返回Null
if ((e = e.next) == null)
return null;
}
}
}
}
/**
* Returns matching node or null if none. Tries to search
* using tree comparisons from root, but continues linear
* search when lock not available.
*/
final Node<K,V> find(int h, Object k) {
if (k != null) {
//e 表示循環(huán)迭代的當前節(jié)點 迭代的是first引用的鏈表
for (Node<K,V> e = first; e != null; ) {
//s 保存的是lock臨時狀態(tài)
//ek 鏈表當前節(jié)點 的key
int s; K ek;
//(WAITER|WRITER) => 0010 | 0001 => 0011
//lockState & 0011 != 0 條件成立：說明當前TreeBin 有等待者線程 或者 目前有寫操作線程正在加鎖
if (((s = lockState) & (WAITER|WRITER)) != 0) {
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
e = e.next;
}
//前置條件：當前TreeBin中 等待者線程 或者 寫線程 都沒有
//條件成立：說明添加讀鎖成功
else if (U.compareAndSwapInt(this, LOCKSTATE, s,
s + READER)) {
TreeNode<K,V> r, p;
try {
//查詢操作
p = ((r = root) == null ? null :
r.findTreeNode(h, k, null));
} finally {
//w 表示等待者線程
Thread w;
//U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER)
//1.當前線程查詢紅黑樹結(jié)束，釋放當前線程的讀鎖 就是讓 lockstate 值 - 4
//(READER|WAITER) = 0110 => 表示當前只有一個線程在讀，且“有一個線程在等待”
//當前讀線程為 TreeBin中的最后一個讀線程。
//2.(w = waiter) != null 說明有一個寫線程在等待讀操作全部結(jié)束。
if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
(READER|WAITER) && (w = waiter) != null)
//使用unpark 讓 寫線程 恢復運行狀態(tài)。
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}
2.3 put()
binCount的含義：
- binCount表示當前k-v 封裝成node后插入到指定桶位后，在桶位中的所屬鏈表的下標位置（兩種情況：1.當前插入key與鏈表當中所有元素的key都不一致時，當前的插入操作是追加到鏈表的末尾，binCount表示鏈表長度；2.當前插入key與鏈表當中的某個元素的key一致時，當前插入操作可能就是替換了。binCount表示沖突位置（binCount - 1））
- 0表示當前桶位為null，node可以直接放著
- 2表示當前桶位已經(jīng)可能是紅黑樹
總體來說分為幾種情況：
- CASE1：當前map中的table尚未初始化
- CASE2：定位的桶位（槽位）為null。i 表示key使用路由尋址算法得到 key對應(yīng) table數(shù)組的下標位置，tabAt 獲取指定桶位的頭結(jié)點 f
- CASE3：前置條件，桶位的頭結(jié)點一定不是null。當前桶位的頭結(jié)點 為 FWD結(jié)點，表示目前map正處于擴容過程中..
- CASE4：當前桶位 可能是 鏈表 也可能是 紅黑樹代理結(jié)點TreeBin
final V putVal(K key, V value, boolean onlyIfAbsent) {
//控制k 和 v 不能為null
if (key == null || value == null) throw new NullPointerException();
//通過spread方法，可以讓高位也能參與進尋址運算。
int hash = spread(key.hashCode());
//binCount表示當前k-v 封裝成node后插入到指定桶位后，在桶位中的所屬鏈表的下標位置
//0 表示當前桶位為null，node可以直接放著
//2 表示當前桶位已經(jīng)可能是紅黑樹
int binCount = 0;
//tab 引用map對象的table
//自旋
for (Node<K,V>[] tab = table;;) {
//f 表示桶位的頭結(jié)點
//n 表示散列表數(shù)組的長度
//i 表示key通過尋址計算后，得到的桶位下標
//fh 表示桶位頭結(jié)點的hash值
Node<K,V> f; int n, i, fh;
//CASE1：成立，表示當前map中的table尚未初始化..
if (tab == null || (n = tab.length) == 0)
//最終當前線程都會獲取到最新的map.table引用。
tab = initTable();
//CASE2：i 表示key使用路由尋址算法得到 key對應(yīng) table數(shù)組的下標位置，tabAt 獲取指定桶位的頭結(jié)點 f
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//進入到CASE2代碼塊 前置條件 當前table數(shù)組i桶位是Null時。
//使用CAS方式 設(shè)置 指定數(shù)組i桶位 為 new Node<K,V>(hash, key, value, null),并且期望值是null
//cas操作成功 表示ok，直接break for循環(huán)即可
//cas操作失敗，表示在當前線程之前，有其它線程先你一步向指定i桶位設(shè)置值了。
//當前線程只能再次自旋，去走其它邏輯。
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//CASE3：前置條件，桶位的頭結(jié)點一定不是null。
//條件成立表示當前桶位的頭結(jié)點 為 FWD結(jié)點，表示目前map正處于擴容過程中..
else if ((fh = f.hash) == MOVED)
//看到fwd節(jié)點后，當前節(jié)點有義務(wù)幫助當前map對象完成遷移數(shù)據(jù)的工作
//學完擴容后再來看。
tab = helpTransfer(tab, f);
//CASE4：當前桶位 可能是 鏈表 也可能是 紅黑樹代理結(jié)點TreeBin
else {
//當插入key存在時，會將舊值賦值給oldVal，返回給put方法調(diào)用處..
V oldVal = null;
//使用sync 加鎖“頭節(jié)點”，理論上是“頭結(jié)點”
synchronized (f) {
//為什么又要對比一下，看看當前桶位的頭節(jié)點 是否為 之前獲取的頭結(jié)點？
//為了避免其它線程將該桶位的頭結(jié)點修改掉，導致當前線程從sync 加鎖 就有問題了。之后所有操作都不用在做了。
if (tabAt(tab, i) == f) {//條件成立，說明咱們 加鎖 的對象沒有問題，可以進來造了！
//條件成立，說明當前桶位就是普通鏈表桶位。
if (fh >= 0) {
//1.當前插入key與鏈表當中所有元素的key都不一致時，當前的插入操作是追加到鏈表的末尾，binCount表示鏈表長度
//2.當前插入key與鏈表當中的某個元素的key一致時，當前插入操作可能就是替換了。binCount表示沖突位置（binCount - 1）
binCount = 1;
//迭代循環(huán)當前桶位的鏈表，e是每次循環(huán)處理節(jié)點。
for (Node<K,V> e = f;; ++binCount) {
//當前循環(huán)節(jié)點 key
K ek;
//條件一：e.hash == hash 成立 表示循環(huán)的當前元素的hash值與插入節(jié)點的hash值一致，需要進一步判斷
//條件二：((ek = e.key) == key ||(ek != null && key.equals(ek)))
// 成立：說明循環(huán)的當前節(jié)點與插入節(jié)點的key一致，發(fā)生沖突了
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
//將當前循環(huán)的元素的 值 賦值給oldVal
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
//當前元素 與 插入元素的key不一致 時，會走下面程序。
//1.更新循環(huán)處理節(jié)點為 當前節(jié)點的下一個節(jié)點
//2.判斷下一個節(jié)點是否為null，如果是null，說明當前節(jié)點已經(jīng)是隊尾了，插入數(shù)據(jù)需要追加到隊尾節(jié)點的后面。
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//前置條件，該桶位一定不是鏈表
//條件成立，表示當前桶位是 紅黑樹代理結(jié)點TreeBin
else if (f instanceof TreeBin) {
//p 表示紅黑樹中如果與你插入節(jié)點的key 有沖突節(jié)點的話 ，則putTreeVal 方法 會返回沖突節(jié)點的引用。
Node<K,V> p;
//強制設(shè)置binCount為2，因為binCount <= 1 時有其它含義，所以這里設(shè)置為了2 回頭講 addCount。
binCount = 2;
//條件一：成立，說明當前插入節(jié)點的key與紅黑樹中的某個節(jié)點的key一致，沖突了
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
//將沖突節(jié)點的值 賦值給 oldVal
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
//說明當前桶位不為null，可能是紅黑樹 也可能是鏈表
if (binCount != 0) {
//如果binCount>=8 表示處理的桶位一定是鏈表
if (binCount >= TREEIFY_THRESHOLD)
//調(diào)用轉(zhuǎn)化鏈表為紅黑樹的方法
treeifyBin(tab, i);
//說明當前線程插入的數(shù)據(jù)key，與原有k-v發(fā)生沖突，需要將原數(shù)據(jù)v返回給調(diào)用者。
if (oldVal != null)
return oldVal;
break;
}
}
}
//1.統(tǒng)計當前table一共有多少數(shù)據(jù)
//2.判斷是否達到擴容閾值標準，觸發(fā)擴容。
addCount(1L, binCount);
return null;
}
2.4 addCount()
這里的核心是sizeCtl：表示當前table數(shù)組正在進行擴容 ,高16位表示：擴容的標識戳 低16位表示：（1 + nThread） 當前參與并發(fā)擴容的線程數(shù)量
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
上面這個條件代碼有一個bug：
- 條件二： JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達的是 = sc == (rs << 16 ) + 1
true-> 表示擴容完畢，當前線程不需要再參與進來了
false->擴容還在進行中，當前線程可以參與 - 條件三：JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達的是 = sc == (rs<<16) + MAX_RESIZERS
true-> 表示當前參與并發(fā)擴容的線程達到了最大值 65535 - 1
false->表示當前線程可以參與進來
private final void addCount(long x, int check) {
//as 表示 LongAdder.cells
//b 表示LongAdder.base
//s 表示當前map.table中元素的數(shù)量
CounterCell[] as; long b, s;
//條件一：true->表示cells已經(jīng)初始化了，當前線程應(yīng)該去使用hash尋址找到合適的cell 去累加數(shù)據(jù)
// false->表示當前線程應(yīng)該將數(shù)據(jù)累加到 base
//條件二：false->表示寫base成功，數(shù)據(jù)累加到base中了，當前競爭不激烈，不需要創(chuàng)建cells
// true->表示寫base失敗，與其他線程在base上發(fā)生了競爭，當前線程應(yīng)該去嘗試創(chuàng)建cells。
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
//有幾種情況進入到if塊中？
//1.true->表示cells已經(jīng)初始化了，當前線程應(yīng)該去使用hash尋址找到合適的cell 去累加數(shù)據(jù)
//2.true->表示寫base失敗，與其他線程在base上發(fā)生了競爭，當前線程應(yīng)該去嘗試創(chuàng)建cells。
//a 表示當前線程hash尋址命中的cell
CounterCell a;
//v 表示當前線程寫cell時的期望值
long v;
//m 表示當前cells數(shù)組的長度
int m;
//true -> 未競爭 false->發(fā)生競爭
boolean uncontended = true;
//條件一：as == null || (m = as.length - 1) < 0
//true-> 表示當前線程是通過 寫base競爭失敗 然后進入的if塊，就需要調(diào)用fullAddCount方法去擴容 或者 重試.. LongAdder.longAccumulate
//條件二：a = as[ThreadLocalRandom.getProbe() & m]) == null 前置條件：cells已經(jīng)初始化了
//true->表示當前線程命中的cell表格是個空，需要當前線程進入fullAddCount方法去初始化 cell，放入當前位置.
//條件三：!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)
// false->取反得到false，表示當前線程使用cas方式更新當前命中的cell成功
// true->取反得到true,表示當前線程使用cas方式更新當前命中的cell失敗，需要進入fullAddCount進行重試 或者 擴容 cells。
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);
//考慮到fullAddCount里面的事情比較累，就讓當前線程 不參與到 擴容相關(guān)的邏輯了，直接返回到調(diào)用點。
return;
}
if (check <= 1)
return;
//獲取當前散列表元素個數(shù)，這是一個期望值
s = sumCount();
}
//表示一定是一個put操作調(diào)用的addCount
if (check >= 0) {
//tab 表示map.table
//nt 表示map.nextTable
//n 表示map.table數(shù)組的長度
//sc 表示sizeCtl的臨時值
Node<K,V>[] tab, nt; int n, sc;
/**
* sizeCtl < 0
* 1. -1 表示當前table正在初始化（有線程在創(chuàng)建table數(shù)組），當前線程需要自旋等待..
* 2.表示當前table數(shù)組正在進行擴容 ,高16位表示：擴容的標識戳 低16位表示：（1 + nThread） 當前參與并發(fā)擴容的線程數(shù)量
*
* sizeCtl = 0，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
*
* sizeCtl > 0
*
* 1. 如果table未初始化，表示初始化大小
* 2. 如果table已經(jīng)初始化，表示下次擴容時的 觸發(fā)條件（閾值）
*/
//自旋
//條件一：s >= (long)(sc = sizeCtl)
// true-> 1.當前sizeCtl為一個負數(shù) 表示正在擴容中..
// 2.當前sizeCtl是一個正數(shù)，表示擴容閾值
// false-> 表示當前table尚未達到擴容條件
//條件二：(tab = table) != null
// 恒成立 true
//條件三：(n = tab.length) < MAXIMUM_CAPACITY
// true->當前table長度小于最大值限制，則可以進行擴容。
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
//擴容批次唯一標識戳
//16 -> 32 擴容 標識為：1000 0000 0001 1011
int rs = resizeStamp(n);
//條件成立：表示當前table正在擴容
// 當前線程理論上應(yīng)該協(xié)助table完成擴容
if (sc < 0) {
//條件一：(sc >>> RESIZE_STAMP_SHIFT) != rs
// true->說明當前線程獲取到的擴容唯一標識戳 非 本批次擴容
// false->說明當前線程獲取到的擴容唯一標識戳 是 本批次擴容
//條件二： JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達的是 = sc == (rs << 16 ) + 1
// true-> 表示擴容完畢，當前線程不需要再參與進來了
// false->擴容還在進行中，當前線程可以參與
//條件三：JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達的是 = sc == (rs<<16) + MAX_RESIZERS
// true-> 表示當前參與并發(fā)擴容的線程達到了最大值 65535 - 1
// false->表示當前線程可以參與進來
//條件四：(nt = nextTable) == null
// true->表示本次擴容結(jié)束
// false->擴容正在進行中
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
//前置條件：當前table正在執(zhí)行擴容中.. 當前線程有機會參與進擴容。
//條件成立：說明當前線程成功參與到擴容任務(wù)中，并且將sc低16位值加1，表示多了一個線程參與工作
//條件失?。?.當前有很多線程都在此處嘗試修改sizeCtl，有其它一個線程修改成功了，導致你的sc期望值與內(nèi)存中的值不一致 修改失敗
// 2.transfer 任務(wù)內(nèi)部的線程也修改了sizeCtl。
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
//協(xié)助擴容線程，持有nextTable參數(shù)
transfer(tab, nt);
}
//1000 0000 0001 1011 0000 0000 0000 0000 +2 => 1000 0000 0001 1011 0000 0000 0000 0010
//條件成立，說明當前線程是觸發(fā)擴容的第一個線程，在transfer方法需要做一些擴容準備工作
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
//觸發(fā)擴容條件的線程 不持有nextTable
transfer(tab, null);
s = sumCount();
}
}
}
2.5 擴容
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
//nextTab 引用的是 fwd.nextTable == map.nextTable 理論上是這樣。
//sc 保存map.sizeCtl
Node<K,V>[] nextTab; int sc;
//條件一：tab != null 恒成立 true
//條件二：(f instanceof ForwardingNode) 恒成立 true
//條件三：((ForwardingNode<K,V>)f).nextTable) != null 恒成立 true
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
//拿當前標的長度 獲取 擴容標識戳 假設(shè) 16 -> 32 擴容：1000 0000 0001 1011
int rs = resizeStamp(tab.length);
//條件一：nextTab == nextTable
//成立：表示當前擴容正在進行中
//不成立：1.nextTable被設(shè)置為Null 了，擴容完畢后，會被設(shè)為Null
// 2.再次出發(fā)擴容了...咱們拿到的nextTab 也已經(jīng)過期了...
//條件二：table == tab
//成立：說明 擴容正在進行中，還未完成
//不成立：說明擴容已經(jīng)結(jié)束了，擴容結(jié)束之后，最后退出的線程 會設(shè)置 nextTable 為 table
//條件三：(sc = sizeCtl) < 0
//成立：說明擴容正在進行中
//不成立：說明sizeCtl當前是一個大于0的數(shù)，此時代表下次擴容的閾值，當前擴容已經(jīng)結(jié)束。
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
//條件一：(sc >>> RESIZE_STAMP_SHIFT) != rs
// true->說明當前線程獲取到的擴容唯一標識戳 非 本批次擴容
// false->說明當前線程獲取到的擴容唯一標識戳 是 本批次擴容
//條件二： JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達的是 = sc == (rs << 16 ) + 1
// true-> 表示擴容完畢，當前線程不需要再參與進來了
// false->擴容還在進行中，當前線程可以參與
//條件三：JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達的是 = sc == (rs<<16) + MAX_RESIZERS
// true-> 表示當前參與并發(fā)擴容的線程達到了最大值 65535 - 1
// false->表示當前線程可以參與進來
//條件四：transferIndex <= 0
// true->說明map對象全局范圍內(nèi)的任務(wù)已經(jīng)分配完了，當前線程進去也沒活干..
// false->還有任務(wù)可以分配。
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;
}
核心擴容方法，核心分為兩大步驟：
- 1）給當前線程分配任務(wù)區(qū)間；維護當前線程任務(wù)進度（i 表示當前處理的桶位）；維護map對象全局范圍內(nèi)的進度transferIndex
- 2）遷移自己負責的任務(wù)區(qū)間：鏈表和紅黑樹
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
//n 表示擴容之前table數(shù)組的長度
//stride 表示分配給線程任務(wù)的步長
int n = tab.length, stride;
//方便講解源碼 stride 固定為 16
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
//條件成立：表示當前線程為觸發(fā)本次擴容的線程，需要做一些擴容準備工作
//條件不成立：表示當前線程是協(xié)助擴容的線程..
if (nextTab == null) { // initiating
try {
//創(chuàng)建了一個比擴容之前大一倍的table
@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 ，方便協(xié)助擴容線程 拿到新表
nextTable = nextTab;
//記錄遷移數(shù)據(jù)整體位置的一個標記。index計數(shù)是從1開始計算的。
transferIndex = n;
}
//表示新數(shù)組的長度
int nextn = nextTab.length;
//fwd 節(jié)點，當某個桶位數(shù)據(jù)處理完畢后，將此桶位設(shè)置為fwd節(jié)點，其它寫線程 或讀線程看到后，會有不同邏輯。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
//推進標記
boolean advance = true;
//完成標記
boolean finishing = false; // to ensure sweep before committing nextTab
//i 表示分配給當前線程任務(wù)，執(zhí)行到的桶位
//bound 表示分配給當前線程任務(wù)的下界限制
int i = 0, bound = 0;
//自旋
for (;;) {
//f 桶位的頭結(jié)點
//fh 頭結(jié)點的hash
Node<K,V> f; int fh;
/**
* 1.給當前線程分配任務(wù)區(qū)間
* 2.維護當前線程任務(wù)進度（i 表示當前處理的桶位）
* 3.維護map對象全局范圍內(nèi)的進度
*/
while (advance) {
//分配任務(wù)的開始下標
//分配任務(wù)的結(jié)束下標
int nextIndex, nextBound;
//CASE1:
//條件一：--i >= bound
//成立：表示當前線程的任務(wù)尚未完成，還有相應(yīng)的區(qū)間的桶位要處理，--i 就讓當前線程處理下一個 桶位.
//不成立：表示當前線程任務(wù)已完成 或 者未分配
if (--i >= bound || finishing)
advance = false;
//CASE2:
//前置條件：當前線程任務(wù)已完成 或 者未分配
//條件成立：表示對象全局范圍內(nèi)的桶位都分配完畢了，沒有區(qū)間可分配了，設(shè)置當前線程的i變量為-1 跳出循環(huán)后，執(zhí)行退出遷移任務(wù)相關(guān)的程序
//條件不成立：表示對象全局范圍內(nèi)的桶位尚未分配完畢，還有區(qū)間可分配
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//CASE3:
//前置條件：1、當前線程需要分配任務(wù)區(qū)間 2.全局范圍內(nèi)還有桶位尚未遷移
//條件成立：說明給當前線程分配任務(wù)成功
//條件失?。赫f明分配給當前線程失敗，應(yīng)該是和其它線程發(fā)生了競爭吧
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
//CASE1：
//條件一：i < 0
//成立：表示當前線程未分配到任務(wù)
if (i < 0 || i >= n || i + n >= nextn) {
//保存sizeCtl 的變量
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
//條件成立：說明設(shè)置sizeCtl 低16位 -1 成功，當前線程可以正常退出
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
//1000 0000 0001 1011 0000 0000 0000 0000
//條件成立：說明當前線程不是最后一個退出transfer任務(wù)的線程
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
//正常退出
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
//前置條件：【CASE2~CASE4】 當前線程任務(wù)尚未處理完，正在進行中
//CASE2:
//條件成立：說明當前桶位未存放數(shù)據(jù)，只需要將此處設(shè)置為fwd節(jié)點即可。
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//CASE3:
//條件成立：說明當前桶位已經(jīng)遷移過了，當前線程不用再處理了，直接再次更新當前線程任務(wù)索引，再次處理下一個桶位 或者 其它操作
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
//CASE4:
//前置條件：當前桶位有數(shù)據(jù)，而且node節(jié)點 不是 fwd節(jié)點，說明這些數(shù)據(jù)需要遷移。
else {
//sync 加鎖當前桶位的頭結(jié)點
synchronized (f) {
//防止在你加鎖頭對象之前，當前桶位的頭對象被其它寫線程修改過，導致你目前加鎖對象錯誤...
if (tabAt(tab, i) == f) {
//ln 表示低位鏈表引用
//hn 表示高位鏈表引用
Node<K,V> ln, hn;
//條件成立：表示當前桶位是鏈表桶位
if (fh >= 0) {
//lastRun
//可以獲取出 當前鏈表 末尾連續(xù)高位不變的 node
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;
}
}
//條件成立：說明lastRun引用的鏈表為 低位鏈表，那么就讓 ln 指向 低位鏈表
if (runBit == 0) {
ln = lastRun;
hn = null;
}
//否則，說明lastRun引用的鏈表為 高位鏈表，就讓 hn 指向 高位鏈表
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;
}
//條件成立：表示當前桶位是 紅黑樹 代理結(jié)點TreeBin
else if (f instanceof TreeBin) {
//轉(zhuǎn)換頭結(jié)點為 treeBin引用 t
TreeBin<K,V> t = (TreeBin<K,V>)f;
//低位雙向鏈表 lo 指向低位鏈表的頭 loTail 指向低位鏈表的尾巴
TreeNode<K,V> lo = null, loTail = null;
//高位雙向鏈表 lo 指向高位鏈表的頭 loTail 指向高位鏈表的尾巴
TreeNode<K,V> hi = null, hiTail = null;
//lc 表示低位鏈表元素數(shù)量
//hc 表示高位鏈表元素數(shù)量
int lc = 0, hc = 0;
//迭代TreeBin中的雙向鏈表，從頭結(jié)點 至 尾節(jié)點
for (Node<K,V> e = t.first; e != null; e = e.next) {
// h 表示循環(huán)處理當前元素的 hash
int h = e.hash;
//使用當前節(jié)點 構(gòu)建出來的 新的 TreeNode
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
//條件成立：表示當前循環(huán)節(jié)點 屬于低位鏈 節(jié)點
if ((h & n) == 0) {
//條件成立：說明當前低位鏈表 還沒有數(shù)據(jù)
if ((p.prev = loTail) == null)
lo = p;
//說明 低位鏈表已經(jīng)有數(shù)據(jù)了，此時當前元素 追加到 低位鏈表的末尾就行了
else
loTail.next = p;
//將低位鏈表尾指針指向 p 節(jié)點
loTail = p;
++lc;
}
//當前節(jié)點 屬于 高位鏈 節(jié)點
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.6 remove()
這里最后有一個紅黑樹刪除節(jié)點，然后調(diào)用untreeify操作
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
可以從removeTreeNode方法中看到，一般情況下，其返回的false，只有當樹節(jié)點很少時，才會返回true。
if (first == null) {
root = null;
return true;
}
if ((r = root) == null || r.right == null || // too small
(rl = r.left) == null || rl.left == null)
return true;
這里紅黑樹的刪除，首先是從雙向鏈表中刪除，然后才是從紅黑樹中刪除。如果節(jié)點較少，直接從雙向鏈表刪除就返回，然后紅黑樹節(jié)點也不刪除。然后untreeify操作直接遍歷的就是雙向鏈表，自然而然就是刪除節(jié)點后的樣子，這里代碼設(shè)計的操作非常精簡。
public V remove(Object key) {
return replaceNode(key, null, null);
}
final V replaceNode(Object key, V value, Object cv) {
//計算key經(jīng)過擾動運算后的hash
int hash = spread(key.hashCode());
//自旋
for (Node<K,V>[] tab = table;;) {
//f表示桶位頭結(jié)點
//n表示當前table數(shù)組長度
//i表示hash命中桶位下標
//fh表示桶位頭結(jié)點 hash
Node<K,V> f; int n, i, fh;
//CASE1：
//條件一：tab == null true->表示當前map.table尚未初始化.. false->已經(jīng)初始化
//條件二：(n = tab.length) == 0 true->表示當前map.table尚未初始化.. false->已經(jīng)初始化
//條件三：(f = tabAt(tab, i = (n - 1) & hash)) == null true -> 表示命中桶位中為null，直接break， 會返回
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
//CASE2：
//前置條件CASE2 ~ CASE3：當前桶位不是null
//條件成立：說明當前table正在擴容中，當前是個寫操作，所以當前線程需要協(xié)助table完成擴容。
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//CASE3:
//前置條件CASE2 ~ CASE3：當前桶位不是null
//當前桶位 可能是 "鏈表" 也可能 是 "紅黑樹" TreeBin
else {
//保留替換之前的數(shù)據(jù)引用
V oldVal = null;
//校驗標記
boolean validated = false;
//加鎖當前桶位 頭結(jié)點，加鎖成功之后會進入 代碼塊。
synchronized (f) {
//判斷sync加鎖是否為當前桶位 頭節(jié)點，防止其它線程，在當前線程加鎖成功之前，修改過 桶位 的頭結(jié)點。
//條件成立：當前桶位頭結(jié)點 仍然為f，其它線程沒修改過。
if (tabAt(tab, i) == f) {
//條件成立：說明桶位 為 鏈表 或者 單個 node
if (fh >= 0) {
validated = true;
//e 表示當前循環(huán)處理元素
//pred 表示當前循環(huán)節(jié)點的上一個節(jié)點
Node<K,V> e = f, pred = null;
for (;;) {
//當前節(jié)點key
K ek;
//條件一：e.hash == hash true->說明當前節(jié)點的hash與查找節(jié)點hash一致
//條件二：((ek = e.key) == key || (ek != null && key.equals(ek)))
//if 條件成立，說明key 與查詢的key完全一致。
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
//當前節(jié)點的value
V ev = e.val;
//條件一：cv == null true->替換的值為null 那么就是一個刪除操作
//條件二：cv == ev || (ev != null && cv.equals(ev)) 那么是一個替換操作
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
//刪除 或者 替換
//將當前節(jié)點的值 賦值給 oldVal 后續(xù)返回會用到
oldVal = ev;
//條件成立：說明當前是一個替換操作
if (value != null)
//直接替換
e.val = value;
//條件成立：說明當前節(jié)點非頭結(jié)點
else if (pred != null)
//當前節(jié)點的上一個節(jié)點，指向當前節(jié)點的下一個節(jié)點。
pred.next = e.next;
else
//說明當前節(jié)點即為 頭結(jié)點，只需要將 桶位設(shè)置為頭結(jié)點的下一個節(jié)點。
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
//條件成立：TreeBin節(jié)點。
else if (f instanceof TreeBin) {
validated = true;
//轉(zhuǎn)換為實際類型 TreeBin t
TreeBin<K,V> t = (TreeBin<K,V>)f;
//r 表示 紅黑樹 根節(jié)點
//p 表示 紅黑樹中查找到對應(yīng)key 一致的node
TreeNode<K,V> r, p;
//條件一：(r = t.root) != null 理論上是成立
//條件二：TreeNode.findTreeNode 以當前節(jié)點為入口，向下查找key（包括本身節(jié)點）
// true->說明查找到相應(yīng)key 對應(yīng)的node節(jié)點。會賦值給p
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
//保存p.val 到pv
V pv = p.val;
//條件一：cv == null 成立：不必對value，就做替換或者刪除操作
//條件二：cv == pv ||(pv != null && cv.equals(pv)) 成立：說明“對比值”與當前p節(jié)點的值 一致
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é)點時，當前線程 sync 頭結(jié)點 鎖錯對象時，validated 為false，會進入下次for 自旋
if (validated) {
if (oldVal != null) {
//替換的值 為null，說明當前是一次刪除操作，oldVal ！=null 成立，說明刪除成功，更新當前元素個數(shù)計數(shù)器。
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}
