1、JAVA1.8 HashMap元素删除方法解析（图文并茂）

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
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
 public V remove(Object key) {
Node<K,V> e;
// 删除元素
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
// p = tab[index]
(p = tab[index = (n - 1) & hash]) != null) {
// tab 有元素 且 key所在的索引位置元素不为空
// node -> 删除的元素
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 找到删除的元素
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
// 从红黑树中查找元素
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
// 找到删除的元素，结束循环
node = e;
break;
}
p = e;
// 直到找到删除的元素 或者已经没有下一个元素了
} while ((e = e.next) != null);
}
}
// matchValue = true 的时候，node.value需要和value相等才会删除元素
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// node 不是TreeNode类型的，所以p == node 或者 p是 node的父节点
else if (node == p)
// 当 node == p 时，说明删除的节点是第一个节点
// 第一节点指向 node.next，这样第一个节点就从链表中移除了
tab[index] = node.next;
else
// p.next = node.next 这样node 就从链表中移除了
p.next = node.next;
++modCount;
--size;
// 空方法，LinkedHashMap 才会实现这个方法
afterNodeRemoval(node);
// 返回删除的节点
return node;
}
// --------------
从红黑树中删除节点 ---------------------
// movable -> 是否把根节点移动到链表的第一个位置
// 注意： this就是当前要删除的节点
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
// n = tab.length
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
// root = first， 连续进行删除操作，第一个节点未必是根节点，
// 如果first不是真正的根节点，下面会重新计算根节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// succ: successor
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
// ------------
修改链表结构 -----------------
if (pred == null)
// 若删除的节点是第一个节点，修改 tab[index] 和 first 为succ，
// 即第一个节点指向了next，原来的第一个节点就从链表中断开了
tab[index] = first = succ;
else
// pred.next 指向 succ，这样就将当前节点从链表中移除了(当前节点就是要删除的节点)
pred.next = succ;
if (succ != null)
// 修改succ 的上一个节点
succ.prev = pred;
if (first == null) // 当前索引位置已经没有元素了
return;
if (root.parent != null)
// 重新计算根节点，连续进行删除操作，第一个节点未必是根节点
root = root.root();
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
// 若删除的节点是第一个节点，那么现在first已经指向 succ了
// 节点太少了，将红黑树转成链表结构，前面删除的元素已经从链表中移除了
tab[index] = first.untreeify(map);
// too small
return;
}
// ----------
从红黑树中删除元素 ----------------
// 经过上面的判断，从红黑树中删除元素，红黑树的结构深度至少以下是这样的，否则就直接把红黑树转成链表了
// 所以如果删除的节点若是根节点，那么其左右子树都不可能为空，因为和根节点右子树的最小节点互焕颜色
// 和位置之后，根节点还是黑色的。从而就保证了根节点肯定是黑色的。
//
root
//
/

//
rl
rr
//
/
//
rll
// this 就是要删除的节点
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
// 删除的元素左右孩子都不为空
TreeNode<K,V> s = pr, sl;
//
p
//
/ 
//
pl
s(pr)
//
/
//
sl
// 1、查找右子树中最小的元素，比如上图中的s1
while ((sl = s.left) != null) // find successor
s = sl;
// 现在 s 是删除元素右子树中最小的元素
// 2、 s 和 p 互换颜色和位置，然后再去删除p
//
2.1 互换颜色
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
// 右子树中最小的元素左节点一定为空，所以只要先把s的右节点保存下来就行了
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
//
2.2 把S 和 P互换位置
// 判断s(右子树最小的元素) 是否是 p的右节点，这个判断很重要，否则就会出现 p.parent = p
if (s == pr) { // p was s's direct parent
// s 的右子树已经赋值给 sr了，下面会把sr 添加到 p的右子树
p.parent = s;
// p.right，p.left 还没修改，下面会去修改，和else情况是公共的逻辑
s.right = p;
// s.left，s.parent 还没修改，下面会去修改，和else情况是公共的逻辑
}
// s不是p的右节点
else {
TreeNode<K,V> sp = s.parent;
// p.parent = sp
if ((p.parent = sp) != null) {
if (s == sp.left) // s 在 sp的左子树
sp.left = p;
// sp的左子树变成 p
else
sp.right = p; // sp的右子树变成 p
}
// s.right = pr
if ((s.right = pr) != null)
pr.parent = s;
}
// p 和 s互换位置，s是p右子树的最小元素，所以s的左子树一定为空，换位置后 p.left = null
p.left = null;
// p.right = sr
if ((p.right = sr) != null)
sr.parent = p;
// s.left = pl
if ((s.left = pl) != null)
pl.parent = s;
// s.parent = pp
if ((s.parent = pp) == null)
// pp == null，说明p是根节点，换位置后s变成根节点
root = s;
// 修改pp的子节点
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
// 左右子树一个为空、或者都为空的情况
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
// ------ replacement != p 的 p 节点删除
if (replacement != p) {
// replacement != p，只要用 replacement替换 p就行了，然后颜色变成p的颜色即可
// ----- 使用replacement节点替换p节点，然后变色是在balanceDeletion() 方法里面 ----
// replacement.parent = p.parent
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
// 如果 p是根节点，那么现在 replacement 变成了根节点
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
// p的左右节点和父亲都设置为null
p.left = p.right = p.parent = null;
}
// p的左右节点至少有一个为空，如果p 的颜色是红色的，那么p的左右节点肯定都为空(因为不能连续两个红色的节点)
// 所以如果p 的颜色是红色的，那么直接删除即可
// 删除的节点是黑色的，才会调用 balanceDeletion()方法
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// ------- replacement == p 的p 节点删除
if (replacement == p) {
// detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
// x -> replacement
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;)
{
if (x == null || x == root)
// todo
没有修改根节点的颜色为黑色？
//
==> 没有必要修改根节点的颜色，因为如果x == root,只有一种情况，就是 x是根节点的右子节点，x和原来的根节点互换了颜色和位置，
//
那么此时x的颜色肯定是黑色的，不需要修改. (根节点的左右子树都不会为空，因为如果有一个为空就直接转成链表了)
return root;
else if ((xp = x.parent) == null) {
// todo xp == null 那么 x不就是根节点了吗? 根本不会进入到这里面?
// xp == null 说明x 就是根节点，设置x的颜色为黑色
x.red = false;
return x;
}
else if (x.red) {
// x 的颜色为红色的，设置x的颜色为黑色即可
// 1、此时x可能是删除的元素本身，这时候元素已经移除了，设置颜色也不会影响；
// 2、x也可能是删除元素的左节点，或者右节点，此时已经使用x替换了删除元素的位置，只要把颜色设置为黑色即可
// 3、上溯过程中，如果x的颜色是红色的，设置为黑色的即可
x.red = false;
return root;
}
else if ((xpl = xp.left) == x) {
// x 是xp的左子树
// 走到这里说明 x是删除的元素本身而且颜色是黑色，且x 没有子节点
// 这时候需要分以下几种情况：
// 1、x的兄弟节点s是否是红色的
// 2、x的兄弟节点s是黑色，s是否有红色的孩子
// 3、x的兄弟节点s是黑色的，且没有红色的孩子，父节点是否是红色的
// 4、如果以上情况都不是，s设置为红色，然后上溯，最坏情况下，到达根节点，把根节点的另一个子节点变成红色的，
//
这样，整棵树的所有路径少了一个黑色的节点。上溯过程中也始终不会修改根节点的颜色，所以也不用维护根节点的颜色。
// xpr -> x的兄弟节点
if ((xpr = xp.right) != null && xpr.red) {
// 1、 x的兄弟节点是红色，通过旋转解决
//
P(b)
S(b)
S(b)
//
/

第一步
/

第二步
/

//
D(b)
S(r)
====>
P(r)
SR(b)
====>
P(b)
SR(b)
//
/

/

/

//
SL(b) SR(b)
D(b) SL(b)
D(r) SL(r)
// 这里只完成了上面的第一步
xpr.red = false;
// 兄弟节点颜色变成黑色的
xp.red = true;
// xp的颜色变成红色的
root = rotateLeft(root, xp);
// 旋转后位置变了，重新赋值： xp = x.parent； xpr = xp.right
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null) // todo 什么情景？ x的颜色是黑色的，所以xpr不可能为空的
x = xp;
else {
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
// 2、x的兄弟节点xpr是黑色的，且xpr没有红色的孩子，把兄弟节点设置为红色，把 x 指向 xp 进行上溯
// 上面的情景1的第二步在这里得到解决
xpr.red = true;
x = xp;
}
else {
// 3、S 的左节点是红色的，通过旋转和颜色变换把场景变成场景4
//
P(b)
P(b)
//
/

/

//
D(b)
S(b)
====>
D(b)
SL(b)
//
/

//
SL(r)
S(R)
if (sr == null || !sr.red) { // 如果左右节点都是红色的，那么只需要进行单旋转就行了
if (sl != null)
// sl 的颜色设置为黑色的
sl.red = false;
xpr.red = true; // 把xpr颜色变成红的
root = rotateRight(root, xpr);
// xpr指向上图的SL位置
xpr = (xp = x.parent) == null ?
null : xp.right;
}
// 4. S的右节点颜色是红色的
//
原理：旋转变色后右子树黑色节点个数不变，左子树黑色节点个数多了一个
//
P(b)
S(b)
//
/

/

//
D(b)
S(b)
====>
P(b)
SR(b)
//

/
//
SR(r)
D(r)
//
P(r)
S(r)
//
/

/

//
D(b)
S(b)
====>
P(b)
SR(b)
//

/
//
SR(r)
D(r)
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red; // xp节点也可能是红的，所以设置成xp的颜色
if ((sr = xpr.right) != null)
sr.red = false; // 设置sr颜色为黑色的
}
if (xp != null) {
xp.red = false; // 设置xp颜色为黑色的，对应上图的P节点
root = rotateLeft(root, xp);
}
// 通过x = root 退出循环
x = root;
}
}
}
else { // symmetric
// 删除的元素在父节点的右边
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}