JDK8：HashMap源码解析：remove方法、removeNode方法

比眉伴天荒 2024-04-20 08:20 9阅读 0赞

一、概述

在HashMap中如果要根据key删除这个key对应的键值对，需要调用remove(key)方法，该方法将会根据查找到匹配的键值对，将其从HashMap中删除，并且返回键值对的值。

二、方法解析

我们先来看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方法
    }

可以发现remove方法底层实际上是调用了removeNode方法来删除键值对节点，并且根据返回的节点对象取得key对应的值，那么我们再来详细分析下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;
    }