解析ConcurrentHashMap: 紅黑樹的代理類(TreeBin)
前一章是get、remove方法分析，喜歡的朋友點擊查看。本篇為ConcurrentHashMap源碼系列的最後一篇，來分析一下TreeBin 紅黑樹代理節點的源碼：
1、TreeBin內部類分析
TreeBin是紅黑樹的代理，對紅黑樹不太瞭解的，可以參考：
static final class TreeBin<K,V> extends Node<K,V> {
// 紅黑樹根節點
TreeNode<K,V> root;
// 鏈表的頭節點
volatile TreeNode<K,V> first;
// 等待者線程（當前lockState是讀鎖狀態）
volatile Thread waiter;
/**
* 鎖的狀態：
* 1.寫鎖狀態 寫是獨占狀態，以散列表來看，真正進入到TreeBin中的寫線程 同一時刻隻能有一個線程。
* 2.讀鎖狀態 讀鎖是共享，同一時刻可以有多個線程 同時進入到 TreeBin對象中獲取數據。 每一個線程 都會給 lockStat + 4
* 3.等待者狀態（寫線程在等待），當TreeBin中有讀線程目前正在讀取數據時，寫線程無法修改數據，那麼就將lockState的最低2位設置為 0b 10 ：即，換算成十進制就是WAITER = 2;
*/
volatile int lockState;
// values for lockState（lockstate的值）
static final int WRITER = 1; // set while holding write lock 寫鎖狀態
static final int WAITER = 2; // set when waiting for write lock 等待者狀態（寫線程在等待）
static final int READER = 4; // increment value for setting read lock 讀鎖狀態
/**
* TreeBin構造方法：
*/
TreeBin(TreeNode<K,V> b) {
// 設置當前節點hash為-2 表示此節點是TreeBin節點
super(TREEBIN, null, null, null);
// 使用first 引用 treeNode鏈表
this.first = b;
// r 紅黑樹的根節點引用
TreeNode<K,V> r = null;
// x表示遍歷的當前節點
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
// 強制設置當前插入節點的左右子樹為null
x.left = x.right = null;
// ----------------------------------------------------------------------
// CASE1：
// 條件成立：說明當前紅黑樹是一個空樹，那麼設置插入元素為根節點
// 第一次循環，r一定是null
if (r == null) {
// 根節點的父節點 一定為 null
x.parent = null;
// 顏色改為黑色
x.red = false;
// 讓r引用x所指向的對象。
r = x;
}
// ----------------------------------------------------------------------
// CASE2：r != null
else {
// 非第一次循環，都會來帶else分支，此時紅黑樹根節點已經有數據瞭
// k 表示 插入節點的key
K k = x.key;
// h 表示 插入節點的hash
int h = x.hash;
// kc 表示 插入節點key的class類型
Class<?> kc = null;
// p 表示 為查找插入節點的父節點的一個臨時節點
TreeNode<K,V> p = r;
// 這裡的for循環，就是一個查找並插入的過程
for (;;) {
// dir (-1, 1)
// -1 表示插入節點的hash值大於 當前p節點的hash
// 1 表示插入節點的hash值 小於 當前p節點的hash
// ph p表示 為查找插入節點的父節點的一個臨時節點的hash
int dir, ph;
// 臨時節點 key
K pk = p.key;
// 插入節點的hash值 小於 當前節點
if ((ph = p.hash) > h)
// 插入節點可能需要插入到當前節點的左子節點 或者 繼續在左子樹上查找
dir = -1;
// 插入節點的hash值 大於 當前節點
else if (ph < h)
// 插入節點可能需要插入到當前節點的右子節點 或者 繼續在右子樹上查找
dir = 1;
// 如果執行到 CASE3，說明當前插入節點的hash 與 當前節點的hash一致，會在case3 做出最終排序。最終
// 拿到的dir 一定不是0，（-1， 1）
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// xp 想要表示的是 插入節點的 父節點
TreeNode<K,V> xp = p;
// 條件成立：說明當前p節點 即為插入節點的父節點
// 條件不成立：說明p節點 底下還有層次，需要將p指向 p的左子節點 或者 右子節點，表示繼續向下搜索。
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 設置插入節點的父節點 為 當前節點
x.parent = xp;
// 小於P節點，需要插入到P節點的左子節點
if (dir <= 0)
xp.left = x;
// 大於P節點，需要插入到P節點的右子節點
else
xp.right = x;
// 插入節點後，紅黑樹性質 可能會被破壞，所以需要調用 平衡方法
r = balanceInsertion(r, x);
break;
}
}
}
}
// 將r 賦值給 TreeBin對象的 root引用。
this.root = r;
assert checkInvariants(root);
}
/**
* Acquires write lock for tree restructuring.
* 加鎖：基於CAS的方式更新LOCKSTATE的值，期望值是0，更新值是WRITER（1，寫鎖）
*/
private final void lockRoot() {
// 條件成立：說明lockState 並不是 0，說明此時有其它讀線程在treeBin紅黑樹中讀取數據。
if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
// 競爭鎖的過程
contendedLock(); // offload to separate method
}
/**
* Releases write lock for tree restructuring.
* 釋放鎖
*/
private final void unlockRoot() {
// lockstate置為0
lockState = 0;
}
/**
* Possibly blocks awaiting root lock.
*/
private final void contendedLock() {
boolean waiting = false;
// 表示lock值
int s;
for (;;) {
// ~WAITER = 11111....01
// 條件成立：說明目前TreeBin中沒有讀線程在訪問 紅黑樹
// 條件不成立：有線程在訪問紅黑樹
if (((s = lockState) & ~WAITER) == 0) {
// 條件成立：說明寫線程 搶占鎖成功
if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
if (waiting)
// 設置TreeBin對象waiter 引用為null
waiter = null;
return;
}
}
// lock & 0000...10 = 0, 條件成立：說明lock 中 waiter 標志位 為0，此時當前線程可以設置為1瞭，然後將當前線程掛起。
else if ((s & WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
waiting = true;
waiter = Thread.currentThread();
}
}
// 條件成立：說明當前線程在CASE2中已經將 treeBin.waiter 設置為瞭當前線程，並且將lockState 中表示 等待者標記位的地方 設置為瞭1
// 這個時候，就讓當前線程 掛起。。
else if (waiting)
LockSupport.park(this);
}
}
/**
* Finds or adds a node.
* @return null if added
*/
final TreeNode<K,V> putTreeVal(int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if (p == null) {
first = root = new TreeNode<K,V>(h, k, v, null, null);
break;
}
else if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.findTreeNode(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.findTreeNode(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 當前循環節點xp 即為 x 節點的爸爸
// x 表示插入節點
// f 老的頭結點
TreeNode<K,V> x, f = first;
first = x = new TreeNode<K,V>(h, k, v, f, xp);
// 條件成立：說明鏈表有數據
if (f != null)
// 設置老的頭結點的前置引用為 當前的頭結點。
f.prev = x;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
if (!xp.red)
x.red = true;
else {
// 表示 當前新插入節點後，新插入節點 與 父節點 形成 “紅紅相連”
lockRoot();
try {
// 平衡紅黑樹，使其再次符合規范。
root = balanceInsertion(root, x);
} finally {
unlockRoot();
}
}
break;
}
}
assert checkInvariants(root);
return null;
}
}
2、treeifyBin方法分析
treeifyBin：TreeBin的成員方法，轉換鏈表為紅黑樹的方法：
/**
* 將鏈表轉換成紅黑樹
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
// b：
// n: tab的長度
// sc: sizeCtl
Node<K,V> b; int n, sc;
if (tab != null) {
// ---------------------------------------------------------------------------
// CASE1:
// 條件成立：說明當前table數組長度未達到 64，此時不進行樹化操作，而進行擴容操作。
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// table進行擴容
tryPresize(n << 1);
// ---------------------------------------------------------------------------
// CASE2:
// 條件成立：說明當前桶位有數據，且是普通node數據。
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
// 給頭元素b加鎖
synchronized (b) {
// 條件成立：表示加鎖沒問題，b沒有被其他線程修改過
if (tabAt(tab, index) == b) {
// 下面的for循環邏輯，目的就是把桶位中的單鏈表轉換成雙向鏈表，便於樹化~
// hd指向雙向列表的頭部，tl指向雙向鏈表的尾部
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;
}
// 把node單鏈表轉換的雙向鏈表轉換成TreeBin對象
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
3、find方法分析
find：TreeBin中的查找方法。
final Node<K,V> find(int h, Object k) {
if (k != null) {
// e 表示循環迭代的當前節點：迭代的是first引用的鏈表
for (Node<K,V> e = first; e != null; ) {
// s 保存的是lock臨時狀態
// ek 鏈表當前節點 的key
int s; K ek;
// ----------------------------------------------------------------------
// CASE1：
// (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;
}
// ----------------------------------------------------------------------
// CASE2：
// 前置條件：當前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.當前線程查詢紅黑樹結束，釋放當前線程的讀鎖 就是讓 lockstate 值 - 4
// (READER|WAITER) = 0110 => 表示當前隻有一個線程在讀，且“有一個線程在等待”
// 當前讀線程為 TreeBin中的最後一個讀線程。
// 2.(w = waiter) != null 說明有一個寫線程在等待讀操作全部結束。
if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
(READER|WAITER) && (w = waiter) != null)
// 使用unpark 讓 寫線程 恢復運行狀態。
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}
三、總結
到此為止，ConcurrentHashMap的源碼分析就告一段落瞭，祝大傢變得更強~也希望大傢多多關註WalkonNet的其他內容！
推薦閱讀：
- 解析ConcurrentHashMap: get、remove方法分析
- 淺談Java源碼ConcurrentHashMap
- JDK1.8中的ConcurrentHashMap使用及場景分析
- HashMap底層實現原理詳解
- 解析ConcurrentHashMap:成員屬性、內部類、構造方法