ConcurrentHashMap源码解析_06 红黑树的代理类(TreeBin)

• 本篇为ConcurrentHashMap源码系列的最后一篇，来分析一下TreeBin 红黑树代理节点的源码：

1、TreeBin内部类分析

• TreeBin是红黑树的代理，对红黑树不太了解的，可以参考：HashMap底层红黑树实现(自己实现一个简单的红黑树)

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; }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
  
134
  
135
  
136
  
137
  
138
  
139
  
140
  
141
  
142
  
143
  
144
  
145
  
146
  
147
  
148
  
149
  
150
  
151
  
152
  
153
  
154
  
155
  
156
  
157
  
158
  
159
  
160
  
161
  
162
  
163
  
164
  
165
  
166
  
167
  
168
  
169
  
170
  
171
  
172
  
173
  
174
  
175
  
176
  
177
  
178
  
179
  
180
  
181
  
182
  
183
  
184
  
185
  
186
  
187
  
188
  
189
  
190
  
191
  
192
  
193
  
194
  
195
  
196
  
197
  
198
  
199
  
200
  
201
  
202
  
203
  
204
  
205
  
206
  
207
  
208
  
209
  
210
  
211
  
212
  
213
  
214
  
215
  
216
  
217
  
218
  
219
  
220
  
221
  
222
  
223
  
224
  
225
  
226
  
227
  
228
  
229
  
230
  
231
  
232
  
233
  
234
  
235
  
236
  
237
  
238
  
239
 

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)); } } } }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
 

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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
 

到此为止，ConcurrentHashMap的源码分析就告一段落了，祝大家变得更强~

文章来源: csp1999.blog.csdn.net，作者：兴趣使然の草帽路飞，版权归原作者所有，如需转载，请联系作者。

原文链接：csp1999.blog.csdn.net/article/details/116502352