JDK1.8 HashMap源码之删除数据时 remove 系列方法分析（六）

小咪咪 2022-11-19 04:19 78阅读 0赞

今天我们分析查询的源码get(Object key)方法：其他方法相关源码可以参考前几期文章。

1、常用的 remove 方法：

/**
     * 从HashMap中删除掉指定key对应的键值对，并返回被删除的键值对的值
     * 如果返回空，说明key可能不存在，也可能key对应的值就是null
     * 如果想确定到底key是否存在可以使用containsKey方法
     */
    public V remove(Object key){
        Node<K,V> e;// 定义一个节点变量，用来存储要被删除的节点（键值对）
        return (e = removeNode(hash(key),key,null,false,true)) == null ? null : e.value;// 调用removeNode方法
    }

2、进入 removeNode 方法：

/**
     * 方法为final，不可被覆写，子类可以通过实现afterNodeRemoval方法来增加自己的处理逻辑（解析中有描述）
     *
     * @param hash key的hash值，该值是通过hash(key)获取到的
     * @param key 要删除的键值对的key
     * @param value 要删除的键值对的value，该值是否作为删除的条件取决于matchValue是否为true
     * @param matchValue 如果为true，则当key对应的键值对的值equals(value)为true时才删除；否则不关心value的值
     * @param movable 删除后是否移动节点，如果为false，则不移动
     * @return 返回被删除的节点对象，如果没有删除任何节点则返回null
     */
    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; // 声明节点数组、当前节点、数组长度、索引值
        /*
         * 如果 节点数组tab不为空、数组长度n大于0、根据hash定位到的节点对象p（该节点为 树的根节点 或 链表的首节点）不为空
         * 需要从该节点p向下遍历，找到那个和key匹配的节点对象
         */
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v; // 定义要返回的节点对象，声明一个临时节点变量、键变量、值变量
    
            // 如果当前节点的键和key相等，那么当前节点就是要删除的节点，赋值给node
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
    
                /*
                 * 到这一步说明首节点没有匹配上，那么检查下是否有next节点
                 * 如果没有next节点，就说明该节点所在位置上没有发生hash碰撞, 就一个节点并且还没匹配上，也就没得删了，最终也就返回null了
                 * 如果存在next节点，就说明该数组位置上发生了hash碰撞，此时可能存在一个链表，也可能是一颗红黑树
                 */
            else if ((e = p.next) != null) {
                // 如果当前节点是TreeNode类型，说明已经是一个红黑树，那么调用getTreeNode方法从树结构中查找满足条件的节点
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);//重点分析
                    // 如果不是树节点，那么就是一个链表，只需要从头到尾逐个节点比对即可
                else {
                    do {
                        // 如果e节点的键是否和key相等，e节点就是要删除的节点，赋值给node变量，调出循环
                        if (e.hash == hash &&
                                ((k = e.key) == key ||
                                        (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
    
                        // 走到这里，说明e也没有匹配上
                        p = e; // 把当前节点p指向e，这一步是让p存储的永远下一次循环里e的父节点，如果下一次e匹配上了，那么p就是node的父节点
                    } while ((e = e.next) != null); // 如果e存在下一个节点，那么继续去匹配下一个节点。直到匹配到某个节点跳出 或者 遍历完链表所有节点
                }
            }
    
            /*
             * 如果node不为空，说明根据key匹配到了要删除的节点
             * 如果不需要对比value值  或者  需要对比value值但是value值也相等
             * 那么就可以删除该node节点了
             */
            if (node != null && (!matchValue || (v = node.value) == value ||
                    (value != null && value.equals(v)))) {
                if (node instanceof TreeNode) // 如果该节点是个TreeNode对象，说明此节点存在于红黑树结构中，调用removeTreeNode方法（该方法单独解析）移除该节点
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);//重点分析
                else if (node == p) // 如果该节点不是TreeNode对象，node == p 的意思是该node节点就是首节点
                    tab[index] = node.next; // 由于删除的是首节点，那么直接将节点数组对应位置指向到第二个节点即可
                else // 如果node节点不是首节点，此时p是node的父节点，由于要删除node，所有只需要把p的下一个节点指向到node的下一个节点即可把node从链表中删除了
                    p.next = node.next;
                ++modCount; // HashMap的修改次数递增
                --size; // HashMap的元素个数递减
                afterNodeRemoval(node); // 调用afterNodeRemoval方法，该方法HashMap没有任何实现逻辑，目的是为了让子类根据需要自行覆写
                return node;
            }
        }
        return null;
    }

3、点击 getTreeNode 方法，里面的 find 方法  文章[参考][Link 1]：

final TreeNode<K,V> getTreeNode(int h, Object k) {
        return ((parent != null) ? root() : this).find(h, k, null);
    }

4、进入removeTreeNode 方法：里面的 untreeify、moveRootToFront方法源码，[参考][Link 2]

/**
     * 这个方法是TreeNode的内部方法，调用该方法的节点为待删除节点
     *   
     * @param map     删除操作的map
     * @param tab     map存放数据的链表
     * @param movable 是否移动跟节点到头节点
     * @return void
     * @Author muyi
     * @Date 9:34 2020/8/5
     */
    final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                              boolean movable) {
        int n;
        if (tab == null || (n = tab.length) == 0)
            return;
        // 获取索引值
        int index = (n - 1) & hash;
        /**
         * first-头节点，数组存放数据索引位置存在存放的节点值
         * root-根节点,红黑树的根节点，正常情况下二者是相等的
         * rl-root节点的左孩子节点,succ-后节点,pred-前节点
         */
        TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl;
        // succ-调用这个方法的节点（待删除节点）的后驱节点，prev-调用这个方法的节点（待删除节点）的前驱节点
        TreeNode<K, V> succ = (TreeNode<K, V>) next, pred = prev;
        /**
         * 维护双向链表（map在红黑树数据存储的过程中，除了维护红黑树之外还对双向链表进行了维护）
         * 从链表中将该节点删除
         * 如果前驱节点为空，说明删除节点是头节点，删除之后，头节点直接指向了删除节点的后继节点
         */
        if (pred == null)
            tab[index] = first = succ;
        else
            pred.next = succ;
        if (succ != null)
            succ.prev = pred;
        // 如果头节点（即根节点）为空，说明该节点删除后，红黑树为空，直接返回
        if (first == null)
            return;
        // 如果父节点不为空，说明删除后，调用root方法重新获取当前树的根节点
        if (root.parent != null)
            root = root.root();
        /**
         * 当以下三个条件任一满足时，当满足红黑树条件时，说明该位置元素的长度少于6（UNTREEIFY_THRESHOLD），需要对该位置元素链表化
         * 1、root == null：根节点为空，树节点数量为0
         * 2、root.right == null：右孩子为空，树节点数量最多为2
         * 3、(rl = root.left) == null || rl.left == null)：
         *      (rl = root.left) == null：左孩子为空，树节点数最多为2
         *      rl.left == null：左孩子的左孩子为NULL，树节点数最多为6
         */
        if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
            // 链表化，因为前面对链表节点完成了删除操作，故在这里完成之后直接返回，即可完成节点的删除
            tab[index] = first.untreeify(map);
            return;
        }
        /**
         * p-调用此方法的节点（待删除节点），pl-待删除节点的左子节点，pr-待删除节点的右子节点，replacement-替换节点
         * 以下是对红黑树进行维护
         */
        TreeNode<K, V> p = this, pl = left, pr = right, replacement;
        // 1、删除节点有两个子节点
        if (pl != null && pr != null) {
            // 第一步：找到当前节点的后继节点（注意与后驱节点的区别，值大于当前节点值的最小节点，以右子树为根节点，查找它对应的最左节点）
            TreeNode<K, V> s = pr, sl;
            // 循环右子树中查找后继节点(大于当前节点的最小值)
            while ((sl = s.left) != null) // find successor
                s = sl;
            // 第二步：交换后继节点和删除节点的颜色，最终的删除是删除后继节点，故平衡是否是以后继节点的颜色来判断的
            boolean c = s.red;
            s.red = p.red;
            p.red = c; // swap colors
            // sr-后继节点的右孩子（后继节点是肯定不存在左孩子的，如果存在的话，那么它肯定不是后继节点）
            TreeNode<K, V> sr = s.right;
            // pp-待删除节点的父节点
            TreeNode<K, V> pp = p.parent;
            // 第三步：修改当前节点和后继节点的父节点
            // 如果后继节点与当前节点的右孩子相等，类似于当前节点只有一个右孩子
            if (s == pr) { // p was s's direct parent
                // 交换两个节点的位置，父节点变子节点，子节点变父节点
                p.parent = s;
                s.right = p;
            } else {
                // 如果当前节点的右子树不止一个节点，记录sp-后继节点的父节点
                TreeNode<K, V> sp = s.parent;
                // 交换待删除节点和后继节点的的父节点，如果后继节点父节点不为null，指定后继节点父节点的孩子节点
                if ((p.parent = sp) != null) {
                    // 如果前后节点是其父节点的左孩子，修改父节点左孩子值
                    if (s == sp.left)
                        sp.left = p;
                        // 如果后继节点是其父节点的右孩子，修改父节点右孩子值
                    else
                        sp.right = p;
                }
                // 修改后继节点的右孩子值，如果不为null，同时指定其父节点的值
                if ((s.right = pr) != null)
                    pr.parent = s;
            }
            // 第四步：修改当前节点和后继节点的孩子节点，当前节点现在变成后继节点了，故其左孩子为null.
            p.left = null;
            // 修改当前节点的右孩子值，如果其不为空，同时修改其父节点指向当前节点
            if ((p.right = sr) != null)
                sr.parent = p;
            // 修改后继节点的左孩子值，如果其不为空，同时修改其父节点指向后继节点
            if ((s.left = pl) != null)
                pl.parent = s;
            // 修改后继节点的父节点值，如果其为null，说明后继节点现在变成了root节点
            if ((s.parent = pp) == null)
                root = s;
                // 当前节点是其父节点的左孩子
            else if (p == pp.left)
                pp.left = s;
                // 当前节点是其父节点的右孩子
            else
                pp.right = s;
            /**
             * sr-后继节点的右孩子节点（有一个孩子节点），
             * 如果右孩子节点不为空，删除节点后，替代节点就是其右孩子节点
             * 如果为空，那么替代节点就是其本身
             */
            if (sr != null)
                replacement = sr;
            else
                replacement = p;
            // 2、删除节点有一个左子节点，左子节点作为替代节点
        } else if (pl != null)
            replacement = pl;
            // 3、删除节点有一个右子节点，右子节点作为替代节点
        else if (pr != null)
            replacement = pr;
            // 4、删除节点没有子节点，直接删除当前节点
        else
            replacement = p;
        /**
         * 如果删除节点存在两个孩子节点，最终与后继节点交换后，删除的节点的位置位于后继节点的位置，那么此时删除节点所处的位置演变成：
         * a、只有一个孩子节点：(replacement = p.right) != p
         * b、没有孩子节点：replacement == p
         * 只有当删除节点与替换节点不相等的时候，才对删除节点进行删除操作
         */
        if (replacement != p) {
            // 从红黑树中将待删除节点（即当前节点移除）
            TreeNode<K, V> pp = replacement.parent = p.parent;
            // 是否为根节点
            if (pp == null)
                root = replacement;
                // 其父节点的左子节点
            else if (p == pp.left)
                pp.left = replacement;
                // 其父节点的右子节点
            else
                pp.right = replacement;
            // 节点的指向全部置NULL
            p.left = p.right = p.parent = null;
        }
        /**
         * 如果删除节点的颜色是红色，不会影响整棵树的黑色高度，毋需自平衡，根节点不会变化，如果是黑色，则需要进行自平衡，重新获取根节点
         * 注意：
         * 自平衡的时候 替代节点可能与删除节点相等：replacement == p
         * 自平衡的时候 替代节点可能与删除节点不相等：replacement ！= p
         */
        TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);//重点分析
        /**
         * 当 replacement == p 时，是先进行了红黑树的进行了平衡操作，再将这个节点从红黑树中移除
         * 这个地方我也没明白原理是什么，但是我按照这个步骤去走了一遍，确实这样操作来完成平衡，如果有哪位大神明白的，麻烦指导一下，谢谢！
         */
        if (replacement == p) {  // detach
            // pp-存储当前节点的父节点值
            TreeNode<K, V> pp = p.parent;
            // 当前节点的父节点指向NULL
            p.parent = null;
            // 如果父节点不为空，根据当前节点位于父节点的不同子节点，修改父节点的孩子节点值
            if (pp != null) {
                if (p == pp.left)
                    pp.left = null;
                else if (p == pp.right)
                    pp.right = null;
            }
        }
        // movable为true，需要将根节点移动到头节点，即数组所以位置指向的节点
        if (movable)
            moveRootToFront(tab, r);
    }

5、进入 balanceDeletion 方法：里面的rotateLeft 和rotateRight方法 [参考][Link 2]

/**
     * 红黑树删除节点后，平衡红黑树的方法
     *   
     * @param root 根节点
     * @param x    节点删除后，替代其位置的节点，这个节点可能是一个节点，也可能是一棵平衡的红黑树，在此处就当作一个节点，在该节点以上部分需要自平衡
     * @return 返回新的根节点
     * @Author muyi
     * @Date 11:33 2020/8/5
     */
    static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                               TreeNode<K,V> x) {
        /**
         * 进入这个方法，说明被替代的节点之前是黑色的，如果是红色的不会影响黑色高度，黑色的会影响以其作为根节点子树的黑色高度
         * xp-父节点,xpl-父节点的左孩子,xpr-父节点的右孩子节点
         * 注意：
         *    进入该方法的时候 替代节点可能与删除节点相等：x == replacement == p
         *                  替代节点可能与删除节点不相等：x == replacement ！= p
         */
        for (TreeNode<K, V> xp, xpl, xpr; ; ) {
            /**
             * 1、x == null，当 replacement == p 时，删除节点不存在，返回；
             *      因为当 replacement ！= p 时，replacement 肯定不会为null.在移除节点的方法中有三个地方对 replacement 进行赋值。
             *          1、if (sr != null) replacement = sr;
             *          2、if (pl != null) replacement = pl;
             *          3、if (pr != null) replacement = pr;
             * 2、x == root，如果替代完成后，该节点就是整棵红黑树的根节点，本身就是平衡的，直接返回
             */
            if (x == null || x == root)
                return root;
            else if ((xp = x.parent) == null) {
                // 如果父节点为空，说明当前节点就是根节点，设置根节点的颜色为黑色，返回
                x.red = false;
                return x;
            } else if (x.red) {
                /**
                 * 被替换节点（删除节点）的颜色是黑色的，删除之后黑色高度减1，如果替换节点是红色，将其设置为黑色，可以保证
                 * 1、与替换之前的黑色高度相等
                 * 2、满足红黑树的所有特性
                 * 达到平衡返回
                 */
                x.red = false;
                return root;
                /**
                 * 如果替换节点是黑色的，替换之前的节点也是黑色的，替换之后，以替换节点作为根节点子树黑色高度减少1，需要进行相关的自平衡操作
                 * 1、替换节点是父节点的左孩子
                 */
            } else if ((xpl = xp.left) == x) {
                /**
                 * 情况1、父节点的右孩子（兄弟节点）存在且为红色
                 * 处理方式：兄弟节点变黑，父节点变红，以父节点为支点进行左旋，重新获取兄弟节点，继续参与自平衡
                 */
                if ((xpr = xp.right) != null && xpr.red) {
                    xpr.red = false;
                    xp.red = true;
                    root = rotateLeft(root, xp);
                    xpr = (xp = x.parent) == null ? null : xp.right;
                }
    
                // 不存在兄弟节点，x指向父节点，向上调整
                if (xpr == null)
                    x = xp;
                else {
                    // sl-兄弟节点的左孩子，sr-兄弟节点的右孩子
                    TreeNode<K, V> sl = xpr.left, sr = xpr.right;
                    /**
                     * 情况2-1：兄弟节点存在，且两个孩子的颜色均为黑色
                     * 1、sr == null || !sr.red：兄弟的右孩子为黑色（空节点的颜色其实也是黑色）
                     * 2、sl == null || !sl.red：兄弟的左孩子为黑色（空节点的颜色其实也是黑色）
                     * 处理方式：兄弟节点为红色，替换节点指向父节点，继续参与自平衡
                     */
                    if ((sr == null || !sr.red) && (sl == null || !sl.red)) {
                        xpr.red = true;
                        x = xp;
                    } else {
                        /**
                         * 该条件综合评价为：兄弟节点的右孩子为黑色
                         * 1、sr == null：兄弟的右孩子为黑色（空节点的颜色其实也是黑色）
                         * 2、!sr.red：兄弟节点的右孩子颜色为黑色
                         */
                        if (sr == null || !sr.red) {
                            /**
                             * sl != null：兄弟的左孩子是存在且颜色是红色的
                             * 情况2-2、兄弟节点右孩子为黑色、左孩子为红色
                             * 处理方式：兄弟节点的左孩子设为黑色，兄弟节点设为红色，以兄弟节点为支点进行右旋，重新设置x的兄弟节点，继续参与自平衡
                             */
                            if (sl != null)
                                sl.red = false;
                            xpr.red = true;
                            root = rotateRight(root, xpr);
                            xpr = (xp = x.parent) == null ? null : xp.right;
                        }
                        /**
                         * 情况2-3、兄弟节点的右孩子是红色
                         * 处理方式：
                         * 1、如果兄弟节点存在，兄弟节点的颜色设置为父节点的颜色
                         * 2、兄弟节点的右孩子存在，颜色设为黑色
                         * 3、如果父节点存在，将父节点的颜色设为黑色
                         * 4、以父节点为支点进行左旋
                         */
                        if (xpr != null) {
                            xpr.red = (xp == null) ? false : xp.red;
                            if ((sr = xpr.right) != null)
                                sr.red = false;
                        }
                        // 父节点不为空
                        if (xp != null) {
                            xp.red = false;
                            root = rotateLeft(root, xp);
                        }
                        // 替换节点指向根节点，平衡完成
                        x = root;
                    }
                }
            } else {
                /**
                 * 替换节点是父节点的右孩子节点
                 * 情况1、兄弟节点存在且为红色
                 * 处理方式：兄弟节点变黑，父节点变红，以父节点为支点进行左旋，重新获取兄弟节点，继续参与自平衡
                 */
                if (xpl != null && xpl.red) {
                    xpl.red = false;
                    xp.red = true;
                    root = rotateRight(root, xp);
                    xpl = (xp = x.parent) == null ? null : xp.left;
                }
                // 不存在兄弟节点，x指向父节点，向上调整
                if (xpl == null)
                    x = xp;
                else {
                    // sl-兄弟节点的左孩子，sr-兄弟节点的右孩子
                    TreeNode<K, V> sl = xpl.left, sr = xpl.right;
                    /**
                     * 情况2-1：兄弟节点存在，且两个孩子的颜色均为黑色
                     * 1、sr == null || !sr.red：兄弟的右孩子为黑色（空节点的颜色其实也是黑色）
                     * 2、sl == null || !sl.red：兄弟的左孩子为黑色（空节点的颜色其实也是黑色）
                     * 处理方式：兄弟节点为红色，替换节点指向父节点，继续参与自平衡
                     */
                    if ((sl == null || !sl.red) && (sr == null || !sr.red)) {
                        xpl.red = true;
                        x = xp;
                    } else {
                        /**
                         * 该条件综合评价为：兄弟节点的左孩子为黑色
                         * 1、sr == null：兄弟的左孩子为黑色（空节点的颜色其实也是黑色）
                         * 2、!sr.red：兄弟节点的左孩子颜色为黑色
                         */
                        if (sl == null || !sl.red) {
                            /**
                             * sl != null：兄弟的右孩子是存在且颜色是红色的
                             * 情况2-2、兄弟节点左孩子为黑色、右孩子为红色
                             * 处理方式：兄弟节点的右孩子设为黑色，兄弟节点设为红色，以兄弟节点为支点进行左，重新设置x的兄弟节点，继续参与自平衡
                             */
                            if (sr != null)
                                sr.red = false;
                            xpl.red = true;
                            root = rotateLeft(root, xpl);
                            xpl = (xp = x.parent) == null ? null : xp.left;
                        }
                        /**
                         * 情况2-3、兄弟节点的左孩子是红色
                         * 处理方式：
                         * 1、如果兄弟节点存在，兄弟节点的颜色设置为父节点的颜色
                         * 2、兄弟节点的左孩子存在，颜色设为黑色
                         * 3、如果父节点存在，将父节点的颜色设为黑色
                         * 4、以父节点为支点进行右旋
                         */
                        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;
                    }
                }
            }
        }
    }

到此，HashMap源码删除数据时分析结束，下篇我们分析线程安全的ConcurrentHashMap源码，敬请期待！

[Link 1]: https://blog.csdn.net/nandao158/article/details/115694232
[Link 2]: https://blog.csdn.net/nandao158/article/details/115678631