解析ConcurrentHashMap: 红黑树的代理类(TreeBin)

前一章是，喜欢的朋友点击查看。本篇为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的源码分析就告一段落了，祝大家变得更强~也希望大家多多关注www.887551.com的其他内容！