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

63 阅读 0 评论 42 点赞
我是靠谱客的博主粗心飞鸟，最近开发中收集的这篇文章主要介绍1、JAVA1.8 HashMap元素删除方法解析（图文并茂），觉得挺不错的，现在分享给大家，希望可以做个参考。
概述

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