深入解析 HashMap 的 remove() 方法及其相关实现

HashMap 是 Java 中最常用的集合类之一，它提供了高效的键值对存储和检索功能。本文将详细解析 HashMap 的 remove() 方法及其相关的内部实现，包括 removeNode() 和 removeTreeNode() 方法。通过这些方法，我们可以了解 HashMap 如何高效地移除指定的键值对，并在必要时重新平衡红黑树结构。
给出大致流程图，让我们来跟着流程图看源码。

HashMap remove()方法

    public V remove(Object key) {
        Node<K,V> e;
        //hash(key):计算给定键的哈希码，用来确定在HashMap中的位置
        //v2:key要移除的键
        //v3:null用于处理批量删除操作中的前一节节点
        //v4:false表示仅匹配键而不匹配键值,传false表示需要同时匹配键和值
        //v5:true表示是否移动其他节点以填补空缺,true表示移动节点
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

removeNode()流程图：

removeNode方法

removeNode 方法是 HashMap 中用于移除指定键值对的核心方法。它负责查找并移除与给定键和值匹配的节点，并在必要时重新平衡红黑树结构。以下是该方法的大致步骤总结：

• 检查桶数组：
  • 确保桶数组不为空且长度大于0。
  • 计算索引并获取桶位置的头节点。
• 查找要移除的节点：
  • 检查第一个节点是否是要移除的节点。
  • 如果不是，遍历链表或红黑树查找匹配的节点。
• 移除节点：
  • 根据节点类型（链表或红黑树）进行相应的移除操作。
  • 更新桶数组或其他节点的引用。
  • 更新 modCount 和 size。
  • 调用 afterNodeRemoval 钩子函数。
  • 返回被移除的节点。
• 返回结果：
  • 如果没有找到要移除的节点，返回 null。

    /**
     * 
     * @param hash 键的哈希码
     * @param key 要移除的键
     * @param value 要匹配的值
     * @param matchValue 是否需要匹配匹配值,如果为true,则只有当键和值都匹配时才移除
     * @param movable 是否允许移动其他节点以填补空缺
     * @return
     */
    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;
        //如果当前的桶数组不为空且桶数组的长度大于0且桶数组中的索引位置不为空,执行
        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;
            //检查第一个节点是否是要移除的节点,如果哈希码和键都匹配，则将p赋值给node
            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)//如果p是一个红黑树节点,则使用getTreeNode方法查找节点
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {//否则,遍历链表查找节点
                    //do...while循环遍历链表，直到找到匹配的节点或链表结束
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //如果找到了要移除的节点node并且不需要匹配值,或者值夜匹配,则进行移除操作
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)//如果node是一个红黑树节点，则调用removeTreeNode方法移除节点
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)//如果node是桶数组中的第一个节点,则更新桶数组中的引用
                    tab[index] = node.next;
                else//否则更新前一个节点的next引用
                    p.next = node.next;
                ++modCount;//更新修改计数器和大小
                --size;
                afterNodeRemoval(node);//调用钩子函数afterNOdeRemoval,用于在节点移除后一些额外的操作
                return node;//返回被移除的节点
            }
        }
        return null;//如果没有找到要移除的节点,则返回null
    }

removeTreeNode()方法

removeTreeNode 方法是 HashMap 中用于从红黑树结构中移除节点的方法。这个方法处理了红黑树的删除操作，包括更新指针、重新平衡树以及在必要时将树转换回链表形式。以下是该方法的主要步骤总结：

• 检查桶数组：
  • 确保桶数组不为空且长度大于0。
  • 计算索引并获取桶位置的头节点。
• 更新双向链表引用：
  • 更新前驱节点和后继节点的引用。
• 找到真正的根节点：
  • 如果 root 的父节点不为空，找到真正的根节点。
• 检查树的大小：
  • 如果树太小，将其转为链表形式。
• 获取要移除的节点及其子节点：
  • 根据子节点情况选择替换节点。
• 处理有两个子节点的情况：
  • 找到后继节点，交换颜色，更新子节点和父节点引用。
• 处理有一个子节点或没有子节点的情况：
  • 选择合适的替换节点。
• 更新父节点的引用：
  • 更新父节点的引用，清空被移除节点的子节点和父节点引用。
• 重新平衡树：
  • 如果被移除的节点是黑色节点，调用 balanceDeletion 方法重新平衡树。
• 分离被移除的节点：
  • 分离被移除节点与父节点的连接。
• 移动新的根节点：
  • 在必要时，将新的根节点移动到桶数组的前面。

    final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {
        int n;
        if (tab == null || (n = tab.length) == 0)//如果桶数组tab为空或长度为0,则直接返回
            return;
        int index = (n - 1) & hash;//计算键在桶数组中的索引位置
        //获取该索引位置上的第一个节点first,并将root指向first
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
        //获取当前节点的前去节点pred和后继结点succ
        TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
        if (pred == null)//如果pred为空,则更新桶数组中的引用
            tab[index] = first = succ;
        else//否则更新pred的next引用
            pred.next = succ;
        if (succ != null)//如果succ不为空,更新succ的prev引用
            succ.prev = pred;
        if (first == null)//如果first为空,则直接返回
            return;
        if (root.parent != null)//如果root的父节点不为空，则找到真正的根节点root
            root = root.root();
        //如果树太小(只有一个节点或两个节点),则将树转为链表形式并返回
        if (root == null || root.right == null ||
            (rl = root.left) == null || rl.left == null) {
            tab[index] = first.untreeify(map);  // too small
            return;
        }
        //获取要移除的节点p及其左右子节点
        TreeNode<K,V> p = this, pl = left, pr = right, replacement;
        if (pl != null && pr != null) {//如果p有两个子节点
            TreeNode<K,V> s = pr, sl;
            //找到p的后继结点s
            while ((sl = s.left) != null) // find successor
                s = sl;
            //交换p和s的颜色
            boolean c = s.red; s.red = p.red; p.red = c; // swap colors
            TreeNode<K,V> sr = s.right;//获取s的右子节点
            TreeNode<K,V> pp = p.parent;//获取p的父节点
            //如果s是p的直接右子节点
            if (s == pr) { // p was s's direct parent
                p.parent = s;
                s.right = p;
            }
            else {//否则,调整指针以替换p为s
                TreeNode<K,V> sp = s.parent;
                if ((p.parent = sp) != null) {
                    if (s == sp.left)
                        sp.left = p;
                    else
                        sp.right = p;
                }
                if ((s.right = pr) != null)
                    pr.parent = s;
            }
            //更新p和s的子节点和父节点
            p.left = null;
            if ((p.right = sr) != null)
                sr.parent = p;
            if ((s.left = pl) != null)
                pl.parent = s;
            if ((s.parent = pp) == null)
                root = s;
            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;
        if (replacement != p) {//如果替换节点不是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;
            p.left = p.right = p.parent = null;
        }
        //重新平衡树
        TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
        //分离被移除的节点
        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);
    }

balanceDeletion()方法

balanceDeletion 方法是 HashMap 中用于在删除红黑树节点后重新平衡树的方法。这个方法通过一系列的旋转和颜色调整来确保红黑树的性质得到保持。以下是该方法的主要步骤总结：

• 检查基本情况：
  • 如果 x 为空或已经是根节点，直接返回根节点。
  • 如果 x 是新的根节点，将其设为黑色并返回。
  • 如果 x 是红色节点，将其设为黑色并返回根节点。
• 处理 x 是父节点的左子节点的情况：
  • 根据兄弟节点的颜色和子节点情况进行相应的旋转和颜色调整。
  • 如果需要，更新兄弟节点并继续向上调整。
• 处理 x 是父节点的右子节点的情况（对称情况）：
  • 对称地处理兄弟节点的颜色和子节点情况，进行相应的旋转和颜色调整。
  • 如果需要，更新兄弟节点并继续向上调整。

    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)//如果x为空或x已经是根节点,则直接返回根节点
                return root;
            else if ((xp = x.parent) == null) {//如果x没有父节点(即x是新的根节点),将x设为黑色并返回x
                x.red = false;
                return x;
            }
            else if (x.red) {//如果x是红色节点,则将其设为黑色并返回根节点
                x.red = false;
                return root;
            }
            else if ((xpl = xp.left) == x) {//判断x是否是父节点xp的左子结点
                if ((xpr = xp.right) != null && xpr.red) {//如果x的兄弟节点xpr存在且是红色
                    //将xpr设为黑色,xp设为红色,并进行左旋
                    xpr.red = false;
                    xp.red = true;
                    root = rotateLeft(root, xp);
                    xpr = (xp = x.parent) == null ? null : xp.right;//更新x的兄弟节点xpr
                }
                if (xpr == null)//如果x的兄弟节点xpr不存在
                    x = xp;//将x设置为其父节点xp,继续向上调整
                else {
                    TreeNode<K,V> sl = xpr.left, sr = xpr.right;//获取xpr的左右子节点
                    if ((sr == null || !sr.red) &&
                        (sl == null || !sl.red)) {//如果xpr的两个子节点都是黑色
                        xpr.red = true;//将xpr设为红色,并将x设置为其父节点xp
                        x = xp;
                    }
                    else {
                        if (sr == null || !sr.red) {//如果xpr的右子节点sr不存在或不是红色
                            if (sl != null)//如果xpr的左子节点s1存在,将其设置为黑色
                                sl.red = false;
                            xpr.red = true;//将xpr设为红色,并对xpr进行右旋
                            root = rotateRight(root, xpr);
                            xpr = (xp = x.parent) == null ?
                                null : xp.right;//更新x的兄弟节点xpr
                        }
                        if (xpr != null) {//如果xpr存在
                            xpr.red = (xp == null) ? false : xp.red;//将xpr的颜色设置为其父节点的颜色
                            if ((sr = xpr.right) != null)//如果xpr的右子节点sr存在,将其设为黑色
                                sr.red = false;
                        }
                        if (xp != null) {//如果xp存在,将其设为黑色,并对xp进行左旋
                            xp.red = false;
                            root = rotateLeft(root, xp);
                        }
                        x = root;//将x设为新的根节点
                    }
                }
            }
            else { // symmetric  对称情况:x是其父节点xp的右子节点
                if (xpl != null && xpl.red) {//如果x的兄弟节点xpl存在且是红色
                    //将xpl设为黑色,xp设为红色,并进行右旋
                    xpl.red = false;
                    xp.red = true;
                    root = rotateRight(root, xp);
                    xpl = (xp = x.parent) == null ? null : xp.left;//更新x的兄弟节点xpl
                }
                if (xpl == null)//如果x的兄弟节点xpl不存在
                    x = xp;//将x设置为其父节点xp,继续向上调整
                else {
                    TreeNode<K,V> sl = xpl.left, sr = xpl.right;//获取xpl的左右子节点
                    if ((sl == null || !sl.red) &&
                        (sr == null || !sr.red)) {//如果xpl的两个子节点都是黑色
                        xpl.red = true;//将xpl设为红色，并将x设置为其父节点xp
                        x = xp;
                    }
                    else {
                        if (sl == null || !sl.red) {//如果xpl的左子节点sl不存在或不是黑色
                            if (sr != null)//如果xpl的右子节点sr存在,将其设置为黑色
                                sr.red = false;
                            xpl.red = true;//将xpl设为红色,并对xpl进行左旋
                            root = rotateLeft(root, xpl);
                            xpl = (xp = x.parent) == null ?
                                null : xp.left;//更新x的兄弟节点xpl
                        }
                        if (xpl != null) {//如果xpl存在
                            xpl.red = (xp == null) ? false : xp.red;//将xpl的颜色设置为其节点的颜色
                            if ((sl = xpl.left) != null)//如果xpl的左子节点sl存在,将其设为黑色
                                sl.red = false;
                        }
                        if (xp != null) {//如果xp存在,将其设置为黑色,并对xp进行右旋
                            xp.red = false;
                            root = rotateRight(root, xp);
                        }
                        x = root;//将x设置为新的根节点
                    }
                }
            }
        }
    }

moveRootToFront()

moveRootToFront 方法是 HashMap 中用于将红黑树的根节点移动到桶数组中对应索引位置的第一个节点的方法。这个方法确保了在删除操作后，新的根节点能够被正确地放置在桶数组中的正确位置。以下是该方法的主要步骤总结：

• 检查输入参数：
  • 确保根节点和桶数组不为空，并获取桶数组的长度。
• 计算根节点在桶数组中的索引位置：
  • 使用哈希码计算根节点在桶数组中的索引位置。
• 获取当前索引位置上的第一个节点：
  • 获取索引位置上的第一个节点 first。
• 检查并移动根节点：
  • 如果根节点不是当前索引位置上的第一个节点，则进行以下操作：
    • 存储根节点的下一个节点 rn。
    • 将根节点设置为索引位置上的第一个节点。
    • 更新根节点及其相邻节点的双向链表引用。
    • 将根节点的前一个节点引用设为 null。
• 断言检查红黑树的不变性：
  • 调用 checkInvariants(root) 确保红黑树的性质没有被破坏。

    static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
                int n;
        if (root != null && tab != null && (n = tab.length) > 0) {//检查根节点和桶数组是否为空,并获取桶数组的长度
            int index = (n - 1) & root.hash;//计算根节点在桶数组中的索引位置
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index];//获取该索引位置上的第一个节点
            if (root != first) {//如果根节点不是该索引位置上的第一个节点,则进行移动操作
                Node<K,V> rn;//用于存储根节点的下一个节点
                tab[index] = root;//将根节点设置为该索引位置上的第一个节点
                TreeNode<K,V> rp = root.prev;//获取根节点的前一个节点
                if ((rn = root.next) != null)//如果根节点有下一个节点
                    ((TreeNode<K,V>)rn).prev = rp;//更新根节点的下一个节点的前一个节点引用
                if (rp != null)//如果根节点有前一个节点
                    rp.next = rn;//更新根节点的前一个节点的下一个节点引用
                if (first != null)//如果原来的第一个节点不为空
                    first.prev = root;//更新原来第一个节点的前一个节点引用,指向新的根节点
                root.next = first;//更新根节点的下一个节点引用,指向原来的第一个节点
                root.prev = null;//将根节点的前一个节点引用设为null
            }
            assert checkInvariants(root);//断言检查红黑树的不变形
        }
    }

rotateLeft()方法

rotateLeft 方法是 HashMap 中用于执行红黑树左旋操作的方法。左旋操作是一种重要的树结构调整方法，它有助于保持红黑树的平衡性和红黑树的性质。以下是该方法的主要步骤总结：

• 检查输入参数：
  • 确保节点 p 和它的右子节点 r 存在。
• 更新指针：
  • 定义变量 r、pp 和 rl。
  • 如果 r 的左子节点 rl 存在，更新 rl 的父节点为 p。
  • 更新 r 的父节点为 p 的父节点 pp。
  • 根据 p 是 pp 的左子节点还是右子节点来更新 pp 的相应子节点引用。
  • 将 r 的左子节点设为 p，并将 p 的父节点设为 r。
• 返回旋转后的根节点：
  • 返回旋转后的根节点 root。

    static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                          TreeNode<K,V> p) {
        TreeNode<K,V> r, pp, rl;// 定义变量 r 为节点 p 的右子节点，pp 为节点 p 的父节点，rl 为节点 p 的右子节点的左子节点
        if (p != null && (r = p.right) != null) { //检查节点 p 和它的右子节点 r 是否存在
            if ((rl = p.right = r.left) != null) // 如果 r 存在且 r 的左子节点 rl 存在，则更新 rl 的父节点为 p
                rl.parent = p;
            if ((pp = r.parent = p.parent) == null)  // 更新 r 的父节点为 p 的父节点 pp
                (root = r).red = false; // 如果 p 是根节点（即 pp 为空），则将 r 设为新的根节点，并将其颜色设为黑色
            else if (pp.left == p)// 否则，根据 p 是其父节点 pp 的左子节点还是右子节点来更新 pp 的相应子节点引用
                pp.left = r;
            else
                pp.right = r;
            // 将 r 的左子节点设为 p，并更新 p 的父节点为 r
            r.left = p;
            p.parent = r;
        }
        return root;//返回旋转后的根节点
    }

rotateRight()方法

rotateRight 方法是 HashMap 中用于执行红黑树右旋操作的方法。右旋操作与左旋操作类似，也是为了保持红黑树的平衡性和红黑树的性质。以下是该方法的主要步骤总结：

• 检查输入参数：
  • 确保节点 p 和它的左子节点 l 存在。
• 更新指针：
  • 定义变量 l、pp 和 lr。
  • 如果 l 的右子节点 lr 存在，更新 lr 的父节点为 p。
  • 更新 l 的父节点为 p 的父节点 pp。
  • 根据 p 是 pp 的左子节点还是右子节点来更新 pp 的相应子节点引用。
  • 将 l 的右子节点设为 p，并将 p 的父节点设为 l。
• 返回旋转后的根节点：
  • 返回旋转后的根节点 root。

    static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
        // 定义变量 l 为节点 p 的左子节点，pp 为节点 p 的父节点，lr 为节点 p 的左子节点的右子节点
        TreeNode<K,V> l, pp, lr;
        if (p != null && (l = p.left) != null) { // 检查节点 p 和它的左子节点 l 是否存在
            if ((lr = p.left = l.right) != null) // 如果 l 存在且 l 的右子节点 lr 存在，则更新 lr 的父节点为 p
                lr.parent = p;
            if ((pp = l.parent = p.parent) == null)// 更新 l 的父节点为 p 的父节点 pp
                (root = l).red = false; // 如果 p 是根节点（即 pp 为空），则将 l 设为新的根节点，并将其颜色设为黑色
            else if (pp.right == p)// 否则，根据 p 是其父节点 pp 的左子节点还是右子节点来更新 pp 的相应子节点引用
                pp.right = l;
            else
                pp.left = l;
            // 将 l 的右子节点设为 p，并更新 p 的父节点为 l
            l.right = p;
            p.parent = l;
        }
        return root;// 返回旋转后的根节点
    }

通过本文的解析，我们深入了解了 HashMap 的 remove() 方法及其相关实现。HashMap 通过一系列复杂的操作，确保了高效的键值对移除，并在必要时重新平衡红黑树结构。希望本文能够帮助你更好地理解和使用 HashMap。
更多内容，请关注以下公众号

原文地址：https://blog.csdn.net/qq_41934990/article/details/142882919

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！