HasMap之remove详解(一)

1. 导读

本期分享的是本人对于HashMap::remove的理解以及红黑树删除知识准备, 主要是围绕:
.1 removeNode;
.2 红黑树删除节点;
这两块内容来展开的;

2. HashMap::removeNode

我们先来看下HashMap::remove(JAVA8)的主流程:

HashMap::removeNode是分了两步: 找节点和删除节点;
.1 先根据key找到对应的节点, 非首节点时, 需要判断是红黑树还是链表;
.2 如果节点不存在, 返回null;
.3 找到对应节点后, 如果是红黑树, 调用红黑树的removeTreeNode方法删除节点;
.4 如果是链表, 判断是否为首节点, 如果是首节点, 直接移除首节点即可;
.5 非首节点时, 需要将x(目标节点)的父节点p的子节点更改为x的子节点;
.6 返回删除的节点;

HashMap::removeNode当节点存在时, 会返回删除的节点, 不存在时返回null;

3. 红黑树删除节点

链表的节点删除还是很简单的, 下面重点关注下红黑树的节点删除;在进入主题前, 我们先来看下红黑树节点删除的预备知识:

首先因为红黑树是有序的, 那么当我们要删除8节点时, 怎么办?
有两种方法:
.1 找到左子树中最大节点, 用6替换掉8, 这种方式叫找前驱;
.2 找到右子树中最小节点, 用11替换掉8, 这种方式叫找后继;
.3 如果左右子树都为空, 那么直接删除即可;
为什么要使用找前驱(后继)来替换原有节点再删除呢?
因为如果直接删除最差情况是该节点最多有两个子节点, 但是使用找前驱替换, 可以把判断两个字节点的情况转换为判断至多一个子节点的情况; 下面我们用前驱法详细说明下红黑树节点删除的过程(注意, 叶子节点也视为子节点):
.1 如果找到的这个节点是红色的, 其子节点必然是黑色, 直接移除红色节点不会影响红黑树的特性, 故直接使用子节点;
.2 如果这个节点是黑色的, 我们需要判断他的子节点是红色还是黑色的, 如果是红色的:

这时候如果直接移除一个黑节点, 过这个移除节点的路径就会少一个黑节点; 为了重新平衡, 只需要将子节点变成黑色, 然后顶替掉移除节点即可(路径上少一个红节点对红黑树的特性没有影响);
上面两种是比较简单的情况, 我们来看下需移除节点和其子节点都是黑色的情况(这种情况我只想到x是叶子节点);
后面为方便表诉, 约定需移除节点为e, e的右子节点是x, e的父节点是p, e的兄弟节点是s, s的左子节点是sl, s的右节点是sr;
.3 case1: s是红色的:

因为移除e后, 从根节点过p到两边的叶子路径上的黑色节点数目就不一致了, 我们需要对右子树进行处理;
因为左子树少了一个黑色节点, 那么只需要想办法让左子树增加个黑色节点即可;

绕p进行左旋后, 把s变黑, p变红, 虽然这时候基于s的小子树已经平衡了, 但是原本左子树移除的一个黑节点这时候还没被填补进来; 这时候红黑树还需要重新平衡:

只要把p变成黑色, sl变成红色, 那么原本过sl的黑色节点数目仍然是2个, 而p替换了原本的e;这次再平衡过程适用于下一种情况:

.4 case2: s是黑色了, 但是p是红色; 也就是case1第一次变换过后的情形, 处理这种情况的方法也就是case1的第二次变换;

.5 case3: p是黑色, s也是黑色;

看了这个图, 是不是发现和case1很像, 只要把s变成红色就可以当做case1处理了; 所以case3的处理方式也就是将s置红;

.6 case4: 这次假定sr存在, 且sr为红色(这时候sl为叶子节点, 或者为红色节点);

把e移除掉以后, 左边子树少了一个黑色节点, 那我们把p左旋到左子树, 这时候右子树少了一个黑色节点, 那么只要把sr置为黑色即可;
在变换过程中, 我们发现p的颜色对最终变换结果没有影响, 只需要把s的颜色变成p的初始颜色即可再次平衡, 这是为什么呢?

从结果来看,
.1 sl变成了p的右子节点, 原本作为s的子节点时, 路径上的黑色节点由s和p决定, 变换过后, 路径上的黑色节点也是由p和s决定, 这两只是交换了颜色而已;
.2 原本过sr路径的黑色节点由s和p决定, 变换过后, sr变成了s的颜色(黑), 所以相当于sr顶替了原本s的位置, 过sr路径的黑色节点数目也是没有改变;
.3 那么受影响的两个节点都可以确定p的颜色对结果没有影响, 那么p的原本颜色对最终结果是没有影响的;

.7 case5: sl为红色时:

只需要绕s右旋, 把sl置黑, s置红即可当case4 处理;

上面的红黑树删除节点的内容不知道大家有没有看懂, 如果有那部分没看懂可以再评论中交流;
红黑树删除节点需要分两步:
.1 第一步是找到删除节点的前驱(后继)节点, 然后将前驱节点与需删除节点交换;
.2 判断交换过后的前驱节点的颜色, 若为红色可直接删除;
.3 如果前驱节点与其子节点都是黑色的, 需要分5种情况来考虑; 这五种情况的基本要诀就是用右子树的红色节点数目来替补左子树删除过后的黑色节点数目;

本期分享就是这些了, 下期我们继续分享HashMap中红黑树删除的具体实现;
红黑树的删除比较复杂, 如果上面内容中有讲解不清楚或者错误的地方, 欢迎在评论区中交流;
如果看了上面的内容对你有所帮助, 烦请转发并点赞, 感谢;