解析ConcurrentHashMap: 紅黑樹的代理類(TreeBin)
更新時(shí)間：2021年06月11日 15:01:39 作者：興趣使然の草帽路飛
ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)，今天給大家普及java面試常見問題---ConcurrentHashMap知識(shí)，一起看看吧
前一章是get、remove方法分析，喜歡的朋友點(diǎn)擊查看。本篇為ConcurrentHashMap源碼系列的最后一篇，來分析一下TreeBin 紅黑樹代理節(jié)點(diǎn)的源碼：
1、TreeBin內(nèi)部類分析
TreeBin是紅黑樹的代理，對(duì)紅黑樹不太了解的，可以參考：
static final class TreeBin<K,V> extends Node<K,V> {
// 紅黑樹根節(jié)點(diǎn)
TreeNode<K,V> root;
// 鏈表的頭節(jié)點(diǎn)
volatile TreeNode<K,V> first;
// 等待者線程（當(dāng)前l(fā)ockState是讀鎖狀態(tài)）
volatile Thread waiter;
/**
* 鎖的狀態(tài)：
* 1.寫鎖狀態(tài) 寫是獨(dú)占狀態(tài)，以散列表來看，真正進(jìn)入到TreeBin中的寫線程 同一時(shí)刻只能有一個(gè)線程。
* 2.讀鎖狀態(tài) 讀鎖是共享，同一時(shí)刻可以有多個(gè)線程 同時(shí)進(jìn)入到 TreeBin對(duì)象中獲取數(shù)據(jù)。 每一個(gè)線程 都會(huì)給 lockStat + 4
* 3.等待者狀態(tài)（寫線程在等待），當(dāng)TreeBin中有讀線程目前正在讀取數(shù)據(jù)時(shí)，寫線程無法修改數(shù)據(jù)，那么就將lockState的最低2位設(shè)置為 0b 10 ：即，換算成十進(jìn)制就是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構(gòu)造方法：
*/
TreeBin(TreeNode<K,V> b) {
// 設(shè)置當(dāng)前節(jié)點(diǎn)hash為-2 表示此節(jié)點(diǎn)是TreeBin節(jié)點(diǎn)
super(TREEBIN, null, null, null);
// 使用first 引用 treeNode鏈表
this.first = b;
// r 紅黑樹的根節(jié)點(diǎn)引用
TreeNode<K,V> r = null;
// x表示遍歷的當(dāng)前節(jié)點(diǎn)
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
// 強(qiáng)制設(shè)置當(dāng)前插入節(jié)點(diǎn)的左右子樹為null
x.left = x.right = null;
// ----------------------------------------------------------------------
// CASE1：
// 條件成立：說明當(dāng)前紅黑樹是一個(gè)空樹，那么設(shè)置插入元素為根節(jié)點(diǎn)
// 第一次循環(huán)，r一定是null
if (r == null) {
// 根節(jié)點(diǎn)的父節(jié)點(diǎn) 一定為 null
x.parent = null;
// 顏色改為黑色
x.red = false;
// 讓r引用x所指向的對(duì)象。
r = x;
}
// ----------------------------------------------------------------------
// CASE2：r != null
else {
// 非第一次循環(huán)，都會(huì)來帶else分支，此時(shí)紅黑樹根節(jié)點(diǎn)已經(jīng)有數(shù)據(jù)了
// k 表示 插入節(jié)點(diǎn)的key
K k = x.key;
// h 表示 插入節(jié)點(diǎn)的hash
int h = x.hash;
// kc 表示 插入節(jié)點(diǎn)key的class類型
Class<?> kc = null;
// p 表示 為查找插入節(jié)點(diǎn)的父節(jié)點(diǎn)的一個(gè)臨時(shí)節(jié)點(diǎn)
TreeNode<K,V> p = r;
// 這里的for循環(huán)，就是一個(gè)查找并插入的過程
for (;;) {
// dir (-1, 1)
// -1 表示插入節(jié)點(diǎn)的hash值大于 當(dāng)前p節(jié)點(diǎn)的hash
// 1 表示插入節(jié)點(diǎn)的hash值 小于 當(dāng)前p節(jié)點(diǎn)的hash
// ph p表示 為查找插入節(jié)點(diǎn)的父節(jié)點(diǎn)的一個(gè)臨時(shí)節(jié)點(diǎn)的hash
int dir, ph;
// 臨時(shí)節(jié)點(diǎn) key
K pk = p.key;
// 插入節(jié)點(diǎn)的hash值 小于 當(dāng)前節(jié)點(diǎn)
if ((ph = p.hash) > h)
// 插入節(jié)點(diǎn)可能需要插入到當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn) 或者 繼續(xù)在左子樹上查找
dir = -1;
// 插入節(jié)點(diǎn)的hash值 大于 當(dāng)前節(jié)點(diǎn)
else if (ph < h)
// 插入節(jié)點(diǎn)可能需要插入到當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn) 或者 繼續(xù)在右子樹上查找
dir = 1;
// 如果執(zhí)行到 CASE3，說明當(dāng)前插入節(jié)點(diǎn)的hash 與 當(dāng)前節(jié)點(diǎn)的hash一致，會(huì)在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é)點(diǎn)的 父節(jié)點(diǎn)
TreeNode<K,V> xp = p;
// 條件成立：說明當(dāng)前p節(jié)點(diǎn) 即為插入節(jié)點(diǎn)的父節(jié)點(diǎn)
// 條件不成立：說明p節(jié)點(diǎn) 底下還有層次，需要將p指向 p的左子節(jié)點(diǎn) 或者 右子節(jié)點(diǎn)，表示繼續(xù)向下搜索。
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 設(shè)置插入節(jié)點(diǎn)的父節(jié)點(diǎn) 為 當(dāng)前節(jié)點(diǎn)
x.parent = xp;
// 小于P節(jié)點(diǎn)，需要插入到P節(jié)點(diǎn)的左子節(jié)點(diǎn)
if (dir <= 0)
xp.left = x;
// 大于P節(jié)點(diǎn)，需要插入到P節(jié)點(diǎn)的右子節(jié)點(diǎn)
else
xp.right = x;
// 插入節(jié)點(diǎn)后，紅黑樹性質(zhì) 可能會(huì)被破壞，所以需要調(diào)用 平衡方法
r = balanceInsertion(r, x);
break;
}
}
}
}
// 將r 賦值給 TreeBin對(duì)象的 root引用。
this.root = r;
assert checkInvariants(root);
}
/**
* Acquires write lock for tree restructuring.
* 加鎖：基于CAS的方式更新LOCKSTATE的值，期望值是0，更新值是WRITER（1，寫鎖）
*/
private final void lockRoot() {
// 條件成立：說明lockState 并不是 0，說明此時(shí)有其它讀線程在treeBin紅黑樹中讀取數(shù)據(jù)。
if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
// 競(jìng)爭(zhēng)鎖的過程
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)
// 設(shè)置TreeBin對(duì)象waiter 引用為null
waiter = null;
return;
}
}
// lock & 0000...10 = 0, 條件成立：說明lock 中 waiter 標(biāo)志位 為0，此時(shí)當(dāng)前線程可以設(shè)置為1了，然后將當(dāng)前線程掛起。
else if ((s & WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
waiting = true;
waiter = Thread.currentThread();
}
}
// 條件成立：說明當(dāng)前線程在CASE2中已經(jīng)將 treeBin.waiter 設(shè)置為了當(dāng)前線程，并且將lockState 中表示 等待者標(biāo)記位的地方 設(shè)置為了1
// 這個(gè)時(shí)候，就讓當(dāng)前線程 掛起。。
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) {
// 當(dāng)前循環(huán)節(jié)點(diǎn)xp 即為 x 節(jié)點(diǎn)的爸爸
// x 表示插入節(jié)點(diǎn)
// f 老的頭結(jié)點(diǎn)
TreeNode<K,V> x, f = first;
first = x = new TreeNode<K,V>(h, k, v, f, xp);
// 條件成立：說明鏈表有數(shù)據(jù)
if (f != null)
// 設(shè)置老的頭結(jié)點(diǎn)的前置引用為 當(dāng)前的頭結(jié)點(diǎn)。
f.prev = x;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
if (!xp.red)
x.red = true;
else {
// 表示 當(dāng)前新插入節(jié)點(diǎn)后，新插入節(jié)點(diǎn) 與 父節(jié)點(diǎn) 形成 “紅紅相連”
lockRoot();
try {
// 平衡紅黑樹，使其再次符合規(guī)范。
root = balanceInsertion(root, x);
} finally {
unlockRoot();
}
}
break;
}
}
assert checkInvariants(root);
return null;
}
}
2、treeifyBin方法分析
treeifyBin：TreeBin的成員方法，轉(zhuǎn)換鏈表為紅黑樹的方法：
/**
* 將鏈表轉(zhuǎn)換成紅黑樹
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
// b：
// n: tab的長(zhǎng)度
// sc: sizeCtl
Node<K,V> b; int n, sc;
if (tab != null) {
// ---------------------------------------------------------------------------
// CASE1:
// 條件成立：說明當(dāng)前table數(shù)組長(zhǎng)度未達(dá)到 64，此時(shí)不進(jìn)行樹化操作，而進(jìn)行擴(kuò)容操作。
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// table進(jìn)行擴(kuò)容
tryPresize(n << 1);
// ---------------------------------------------------------------------------
// CASE2:
// 條件成立：說明當(dāng)前桶位有數(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)邏輯，目的就是把桶位中的單鏈表轉(zhuǎ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單鏈表轉(zhuǎn)換的雙向鏈表轉(zhuǎn)換成TreeBin對(duì)象
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)迭代的當(dāng)前節(jié)點(diǎn)：迭代的是first引用的鏈表
for (Node<K,V> e = first; e != null; ) {
// s 保存的是lock臨時(shí)狀態(tài)
// ek 鏈表當(dāng)前節(jié)點(diǎn) 的key
int s; K ek;
// ----------------------------------------------------------------------
// CASE1：
// (WAITER|WRITER) => 0010 | 0001 => 0011
// lockState & 0011 != 0 條件成立：說明當(dāng)前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：
// 前置條件：當(dāng)前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.當(dāng)前線程查詢紅黑樹結(jié)束，釋放當(dāng)前線程的讀鎖 就是讓 lockstate 值 - 4
// (READER|WAITER) = 0110 => 表示當(dāng)前只有一個(gè)線程在讀，且“有一個(gè)線程在等待”
// 當(dāng)前讀線程為 TreeBin中的最后一個(gè)讀線程。
// 2.(w = waiter) != null 說明有一個(gè)寫線程在等待讀操作全部結(jié)束。
if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
(READER|WAITER) && (w = waiter) != null)
// 使用unpark 讓 寫線程 恢復(fù)運(yùn)行狀態(tài)。
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}
總結(jié)
到此為止，ConcurrentHashMap的源碼分析就告一段落了，祝大家變得更強(qiáng)~也希望大家多多關(guān)注腳本之家的其他內(nèi)容！
相關(guān)文章
Java?對(duì)象在?JVM?中的內(nèi)存布局超詳細(xì)解說
這篇文章主要介紹了Java?對(duì)象在?JVM?中的內(nèi)存布局超詳細(xì)解說，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-09-09
這篇文章主要介紹了 java基礎(chǔ)之反射和泛型以及注解的相關(guān)資料,需要的朋友可以參考下2017-07-07
這篇文章主要介紹了Mybatis-plus 查詢條件為空不生效問題及解決，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-01-01
如何實(shí)現(xiàn)自己的spring boot starter
這篇文章主要介紹了如何實(shí)現(xiàn)自己的spring boot starter,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-08-08
java關(guān)鍵字final用法知識(shí)點(diǎn)
在本篇文章里小編給大家分享的是關(guān)于java關(guān)鍵字final用法知識(shí)點(diǎn)以及相關(guān)實(shí)例內(nèi)容，有需要的朋友們可以學(xué)習(xí)下。2019-09-09
這篇文章主要為大家詳細(xì)介紹了java連接Access數(shù)據(jù)庫的方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-05-05
Java開發(fā)者結(jié)合Node.js編程入門教程
這篇文章主要介紹了Java開發(fā)者結(jié)合Node.js編程入門教程,我將先向您展示如何使用Java EE創(chuàng)建一個(gè)簡(jiǎn)單的Rest服務(wù)來讀取 MongoDB數(shù)據(jù)庫。然后我會(huì)用node.js來實(shí)現(xiàn)相同的功能,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了Spring boot跨域設(shè)置實(shí)例詳解，簡(jiǎn)單介紹了跨域的定義，原因，使用場(chǎng)景及解決方案，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11
Java利用Easyexcel導(dǎo)出excel表格的示例代碼
這篇文章主要為大家詳細(xì)介紹了Java利用Easyexcel導(dǎo)出excel表格的示例代碼，文中的代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起了解一下2022-07-07
這篇文章主要介紹了簡(jiǎn)述Java編程語言中的逃逸分析，包括其定義、作用、類型及理論基礎(chǔ)等相關(guān)內(nèi)容，十分具有參考價(jià)值，需要的朋友可以了解下。2017-09-09