解析ConcurrentHashMap: 紅黑樹的代理類(TreeBin)
更新時間：2021年06月11日 15:01:39 作者：興趣使然の草帽路飛
ConcurrentHashMap是由Segment數(shù)組結構和HashEntry數(shù)組結構組成。Segment的結構和HashMap類似，是一種數(shù)組和鏈表結構，今天給大家普及java面試常見問題---ConcurrentHashMap知識，一起看看吧
前一章是get、remove方法分析，喜歡的朋友點擊查看。本篇為ConcurrentHashMap源碼系列的最后一篇，來分析一下TreeBin 紅黑樹代理節(jié)點的源碼：
1、TreeBin內部類分析
TreeBin是紅黑樹的代理，對紅黑樹不太了解的，可以參考：
static final class TreeBin<K,V> extends Node<K,V> {
// 紅黑樹根節(jié)點
TreeNode<K,V> root;
// 鏈表的頭節(jié)點
volatile TreeNode<K,V> first;
// 等待者線程（當前l(fā)ockState是讀鎖狀態(tài)）
volatile Thread waiter;
/**
* 鎖的狀態(tài)：
* 1.寫鎖狀態(tài) 寫是獨占狀態(tài)，以散列表來看，真正進入到TreeBin中的寫線程 同一時刻只能有一個線程。
* 2.讀鎖狀態(tài) 讀鎖是共享，同一時刻可以有多個線程 同時進入到 TreeBin對象中獲取數(shù)據(jù)。 每一個線程 都會給 lockStat + 4
* 3.等待者狀態(tài)（寫線程在等待），當TreeBin中有讀線程目前正在讀取數(shù)據(jù)時，寫線程無法修改數(shù)據(jù)，那么就將lockState的最低2位設置為 0b 10 ：即，換算成十進制就是WAITER = 2;
*/
volatile int lockState;
// values for lockState（lockstate的值）
static final int WRITER = 1; // set while holding write lock 寫鎖狀態(tài)
static final int WAITER = 2; // set when waiting for write lock 等待者狀態(tài)（寫線程在等待）
static final int READER = 4; // increment value for setting read lock 讀鎖狀態(tài)
/**
* TreeBin構造方法：
*/
TreeBin(TreeNode<K,V> b) {
// 設置當前節(jié)點hash為-2 表示此節(jié)點是TreeBin節(jié)點
super(TREEBIN, null, null, null);
// 使用first 引用 treeNode鏈表
this.first = b;
// r 紅黑樹的根節(jié)點引用
TreeNode<K,V> r = null;
// x表示遍歷的當前節(jié)點
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
// 強制設置當前插入節(jié)點的左右子樹為null
x.left = x.right = null;
// ----------------------------------------------------------------------
// CASE1：
// 條件成立：說明當前紅黑樹是一個空樹，那么設置插入元素為根節(jié)點
// 第一次循環(huán)，r一定是null
if (r == null) {
// 根節(jié)點的父節(jié)點 一定為 null
x.parent = null;
// 顏色改為黑色
x.red = false;
// 讓r引用x所指向的對象。
r = x;
}
// ----------------------------------------------------------------------
// CASE2：r != null
else {
// 非第一次循環(huán)，都會來帶else分支，此時紅黑樹根節(jié)點已經(jīng)有數(shù)據(jù)了
// k 表示 插入節(jié)點的key
K k = x.key;
// h 表示 插入節(jié)點的hash
int h = x.hash;
// kc 表示 插入節(jié)點key的class類型
Class<?> kc = null;
// p 表示 為查找插入節(jié)點的父節(jié)點的一個臨時節(jié)點
TreeNode<K,V> p = r;
// 這里的for循環(huán)，就是一個查找并插入的過程
for (;;) {
// dir (-1, 1)
// -1 表示插入節(jié)點的hash值大于 當前p節(jié)點的hash
// 1 表示插入節(jié)點的hash值 小于 當前p節(jié)點的hash
// ph p表示 為查找插入節(jié)點的父節(jié)點的一個臨時節(jié)點的hash
int dir, ph;
// 臨時節(jié)點 key
K pk = p.key;
// 插入節(jié)點的hash值 小于 當前節(jié)點
if ((ph = p.hash) > h)
// 插入節(jié)點可能需要插入到當前節(jié)點的左子節(jié)點 或者 繼續(xù)在左子樹上查找
dir = -1;
// 插入節(jié)點的hash值 大于 當前節(jié)點
else if (ph < h)
// 插入節(jié)點可能需要插入到當前節(jié)點的右子節(jié)點 或者 繼續(xù)在右子樹上查找
dir = 1;
// 如果執(zhí)行到 CASE3，說明當前插入節(jié)點的hash 與 當前節(jié)點的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 想要表示的是 插入節(jié)點的 父節(jié)點
TreeNode<K,V> xp = p;
// 條件成立：說明當前p節(jié)點 即為插入節(jié)點的父節(jié)點
// 條件不成立：說明p節(jié)點 底下還有層次，需要將p指向 p的左子節(jié)點 或者 右子節(jié)點，表示繼續(xù)向下搜索。
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 設置插入節(jié)點的父節(jié)點 為 當前節(jié)點
x.parent = xp;
// 小于P節(jié)點，需要插入到P節(jié)點的左子節(jié)點
if (dir <= 0)
xp.left = x;
// 大于P節(jié)點，需要插入到P節(jié)點的右子節(jié)點
else
xp.right = x;
// 插入節(jié)點后，紅黑樹性質 可能會被破壞，所以需要調用 平衡方法
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紅黑樹中讀取數(shù)據(jù)。
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中已經(jīng)將 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) {
// 當前循環(huán)節(jié)點xp 即為 x 節(jié)點的爸爸
// x 表示插入節(jié)點
// f 老的頭結點
TreeNode<K,V> x, f = first;
first = x = new TreeNode<K,V>(h, k, v, f, xp);
// 條件成立：說明鏈表有數(shù)據(jù)
if (f != null)
// 設置老的頭結點的前置引用為 當前的頭結點。
f.prev = x;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
if (!xp.red)
x.red = true;
else {
// 表示 當前新插入節(jié)點后，新插入節(jié)點 與 父節(jié)點 形成 “紅紅相連”
lockRoot();
try {
// 平衡紅黑樹，使其再次符合規(guī)范。
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數(shù)組長度未達到 64，此時不進行樹化操作，而進行擴容操作。
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// table進行擴容
tryPresize(n << 1);
// ---------------------------------------------------------------------------
// CASE2:
// 條件成立：說明當前桶位有數(shù)據(jù)，且是普通node數(shù)據(jù)。
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
// 給頭元素b加鎖
synchronized (b) {
// 條件成立：表示加鎖沒問題，b沒有被其他線程修改過
if (tabAt(tab, index) == b) {
// 下面的for循環(huán)邏輯，目的就是把桶位中的單鏈表轉換成雙向鏈表，便于樹化~
// 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 表示循環(huán)迭代的當前節(jié)點：迭代的是first引用的鏈表
for (Node<K,V> e = first; e != null; ) {
// s 保存的是lock臨時狀態(tài)
// ek 鏈表當前節(jié)點 的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 讓 寫線程 恢復運行狀態(tài)。
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}
總結
到此為止，ConcurrentHashMap的源碼分析就告一段落了，祝大家變得更強~也希望大家多多關注腳本之家的其他內容！
相關文章
SpringBoot整合Servlet和Filter和Listener組件詳解
這篇文章主要介紹了SpringBoot整合Servlet和Filter和Listener組件詳解,在整合某報表插件時就需要使用Servlet,Spring Boot中對于整合這些基本的Web組件也提供了很好的支持,需要的朋友可以參考下2024-01-01
Spring中網(wǎng)絡請求客戶端WebClient的使用詳解
作為替代,Spring 官方已在 Spring 5 中引入了 WebClient 作為非阻塞式 Reactive HTTP 客戶端,本文將通過樣例演示如何使用 WebClient,希望對大家有所幫助2024-04-04
這篇文章主要給大家介紹了關于LRU算法及Apache?LRUMap源碼解析的相關資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2021-11-11
大家好，本篇文章主要講的是Java實現(xiàn)猜數(shù)字小游戲，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
java實現(xiàn)excel導入數(shù)據(jù)的工具類
這篇文章主要介紹了java實現(xiàn)的excel導入數(shù)據(jù)的工具類,需要的朋友可以參考下2014-03-03
這篇文章主要為大家詳細介紹了java使用dbcp2數(shù)據(jù)庫連接池的相關資料,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-10-10
在java中，方法就是用來完成解決某件事情或實現(xiàn)某個功能的辦法。方法實現(xiàn)的過程中，會包含很多條語句用于完成某些有意義的功能——通常是處理文本，控制輸入或計算數(shù)值，這篇文章我們來探究一下帶返回值的方法的定義和調用2022-04-04
在本篇文章里小編給各位分享了關于Java中動態(tài)代理和反射機制的相關知識點內容，有需要的朋友們學習下。2019-01-01
Spring ApplicationListener源碼解析
這篇文章主要為大家介紹了Spring ApplicationListener源碼解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-01-01
下面小編就為大家?guī)硪黄贘ava中最常用的集合類框架之HashMap(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-11-11