本篇為ConcurrentHashMap源碼系列的最后一篇，來(lái)分析一下TreeBin 紅黑樹代理節(jié)點(diǎn)的源碼：
1、TreeBin內(nèi)部類分析
TreeBin是紅黑樹的代理，對(duì)紅黑樹不太了解的，可以參考：HashMap底層紅黑樹實(shí)現(xiàn)(自己實(shí)現(xiàn)一個(gè)簡(jiǎn)單的紅黑樹)
static final class TreeBin extends Node { // 紅黑樹根節(jié)點(diǎn) TreeNode root; // 鏈表的頭節(jié)點(diǎn) volatile TreeNode first; // 等待者線程（當(dāng)前l(fā)ockState是讀鎖狀態(tài)） volatile Thread waiter; /** * 鎖的狀態(tài)： * 1.寫鎖狀態(tài) 寫是獨(dú)占狀態(tài)，以散列表來(lá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í)，寫線程無(wú)法修改數(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 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 r = null; // x表示遍歷的當(dāng)前節(jié)點(diǎn) for (TreeNode x = b, next; x != null; x = next) { next = (TreeNode)x.next; // 強(qiáng)制設(shè)置當(dāng)前插入節(jié)點(diǎn)的左右子樹為null x.left = x.right = null; // ---------------------------------------------------------------------- // CASE1： // 條件成立：說(shuō)明當(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ì)來(lái)帶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 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，說(shuō)明當(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 xp = p; // 條件成立：說(shuō)明當(dāng)前p節(jié)點(diǎn) 即為插入節(jié)點(diǎn)的父節(jié)點(diǎn) // 條件不成立：說(shuō)明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() { // 條件成立：說(shuō)明lockState 并不是 0，說(shuō)明此時(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 // 條件成立：說(shuō)明目前TreeBin中沒有讀線程在訪問 紅黑樹 // 條件不成立：有線程在訪問紅黑樹 if (((s = lockState) & ~WAITER) == 0) { // 條件成立：說(shuō)明寫線程 搶占鎖成功 if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) { if (waiting) // 設(shè)置TreeBin對(duì)象waiter 引用為null waiter = null; return; } } // lock & 0000...10 = 0, 條件成立：說(shuō)明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(); } } // 條件成立：說(shuō)明當(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 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) { // 當(dāng)前循環(huán)節(jié)點(diǎn)xp 即為 x 節(jié)點(diǎn)的爸爸 // x 表示插入節(jié)點(diǎn) // f 老的頭結(jié)點(diǎn) TreeNode x, f = first; first = x = new TreeNode(h, k, v, f, xp); // 條件成立：說(shuō)明鏈表有數(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; } }
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的成員方法，轉(zhuǎn)換鏈表為紅黑樹的方法：
/** * 將鏈表轉(zhuǎn)換成紅黑樹 */ private final void treeifyBin(Node[] tab, int index) { // b： // n: tab的長(zhǎng)度 // sc: sizeCtl Node b; int n, sc; if (tab != null) { // --------------------------------------------------------------------------- // CASE1: // 條件成立：說(shuō)明當(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: // 條件成立：說(shuō)明當(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 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單鏈表轉(zhuǎn)換的雙向鏈表轉(zhuǎn)換成TreeBin對(duì)象 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 表示循環(huán)迭代的當(dāng)前節(jié)點(diǎn)：迭代的是first引用的鏈表 for (Node 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 條件成立：說(shuō)明當(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中 等待者線程 或者 寫線程 都沒有 // 條件成立：說(shuō)明添加讀鎖成功 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.當(dāng)前線程查詢紅黑樹結(jié)束，釋放當(dāng)前線程的讀鎖 就是讓 lockstate 值 - 4 // (READER|WAITER) = 0110 => 表示當(dāng)前只有一個(gè)線程在讀，且“有一個(gè)線程在等待” // 當(dāng)前讀線程為 TreeBin中的最后一個(gè)讀線程。 // 2.(w = waiter) != null 說(shuō)明有一個(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; }
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的源碼分析就告一段落了，祝大家變得更強(qiáng)~
任務(wù)調(diào)度 數(shù)據(jù)結(jié)構(gòu)
版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。
