本篇为ConcurrentHashMap源码系列的最后一篇，来分析一下TreeBin 红黑树代理节点的源码：
1、TreeBin内部类分析
TreeBin是红黑树的代理，对红黑树不太了解的，可以参考：HashMap底层红黑树实现(自己实现一个简单的红黑树)
static final class TreeBin extends Node { // 红黑树根节点 TreeNode root; // 链表的头节点 volatile TreeNode 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 b) { // 设置当前节点hash为-2 表示此节点是TreeBin节点 super(TREEBIN, null, null, null); // 使用first 引用 treeNode链表 this.first = b; // r 红黑树的根节点引用 TreeNode r = null; // x表示遍历的当前节点 for (TreeNode x = b, next; x != null; x = next) { next = (TreeNode)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 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 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 putTreeVal(int h, K k, V v) { Class kc = null; boolean searched = false; for (TreeNode p = root;;) { int dir, ph; K pk; if (p == null) { first = root = new TreeNode(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 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 xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { // 当前循环节点xp 即为 x 节点的爸爸 // x 表示插入节点 // f 老的头结点 TreeNode x, f = first; first = x = new TreeNode(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[] tab, int index) { // b： // n: tab的长度 // sc: sizeCtl Node 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 hd = null, tl = null; for (Node e = b; e != null; e = e.next) { TreeNode p = new TreeNode(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(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 find(int h, Object k) { if (k != null) { // e 表示循环迭代的当前节点：迭代的是first引用的链表 for (Node 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 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的源码分析就告一段落了，祝大家变得更强~
任务调度 数据结构
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
暂时没有评论，来抢沙发吧~