JDK1.8HashMap源码学习-remove操作

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key)
        , key, null, false, true)) == null ?
        null : e.value;
}

/**
* hash 移除key的hash值
* key 要移除的key
* value 要移除的key对应的值 默认传入为null
* matchValue 是否匹配值 默认为false
* movable 是否移除 默认true
*/
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;
    //数组不为空且对应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;
         //数组下标保存的数据hash一致且key一致 即要移除的数据就是该数据
         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 便于接下来的移除操作
                        p = e;
                        //接下来 移动到当前节点的下一个节点进行再次循环判断
                    } while ((e = e.next) != null);
                }
            }
            //找到要移除的节点数据
            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);
                    
                //不是红黑树 移除的是单链的头节点 即数组保存节点改为当前节点的下一个节点
                }else if (node == p){
                    tab[index] = node.next;
                }else{
                    //不是根节点 在前面找节点的时候执行过p的赋值操作即为找到节点的操作 将移除节点的父节点指向移除节点的下一个节点
                    //因为是单链 只能是这么操作
                    p.next = node.next;
                }
                //修改次数+1
                ++modCount;
                
                //map容量-1
                --size;
                
                //无操作 留给子类扩展
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

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;
            //找到树的根节点和链表的头节点
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index],
            root = first, rl;
            //从调用处判断 next和prev应该指的是
            //要移除节点的下一节点和前一节点
            TreeNode<K,V> succ = (TreeNode<K,V>)next, 
            pred = prev;
            //如果移除节点的前节点为空
            //说明移除的是根节点 数组保存数据
            //即为移除节点的下一节点 链的头节点也是
            if (pred == null){
                tab[index] = first = succ;
            //不为空 则将移除节点的前节点的后节点
            //赋值为移除节点的后节点 
            //就是把移除节点的前后节点直接链接 
            //移除掉要移除的节点
            }else{
                pred.next = succ;
            }
            //移除节点的后节点不为空 
            //移除节点的后节点的前节点赋值为移除节点的前节点 
            //完成前后节点的双链链接
            if (succ != null){
                succ.prev = pred;
            }
            //链表头为空 直接返回
            if (first == null){
                return;
            }
            //根节点的父节点不为空 查找树的根节点 
            if (root.parent != null){
                root = root.root();
            }
            //如果节点数很少 转为链表结构
            if (root == null 
                || (movable && (root.right == null 
                   || (rl = root.left) == null 
                    || rl.left == null))) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            /**
             * this 就是要移除的节点 处理树结构怎么移除
             * p 要移除的节点
             * pl 要移除节点的左孩子
             * pr 要移除节点的右孩子
             * replacement 应该是要准备替换到当前移除节点的节点
             * 
             * 整体就是找到要替换到当前移除节点的节点 并把移除节点挂载到移除节点右孩子的最左孩子的位置
             */
            TreeNode<K,V> p = this, 
            pl = left,
            pr = right,
            replacement;
            //移除节点的左右孩子均不为空
            //则替换移除节点和移除节点右孩子的最左孩子 做交换
            if (pl != null && pr != null) {
                //s 移除节点右孩子的最左孩子
                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
                //最左孩子的右孩子
                TreeNode<K,V> sr = s.right;
                //移除节点的父节点
                TreeNode<K,V> pp = p.parent;
                //s 就是移除节点的右孩子 即s没有左孩子
                if (s == pr) { // p was s's direct parent
                    p.parent = s;//赋值操作 将移除节点的父节点改为s
                    s.right = p;//将移除节点的右孩子的右孩子赋值为移除节点
                }else {
                    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.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;
            }
            //到了这里基本就已经完成了 replacement是移除节点本身或者是移除节点的左右孩子 而且再没有叶子节点了
            if (replacement != p) {//如果顶替节点不是本身 主要完成的就是将替换节点挂载到原先移除节点的位置或者是已经移动过的位置 并断开相应的连接
                //赋值顶替节点的父节点为移除节点的父节点
                TreeNode<K,V> pp = replacement.parent = p.parent;
                if (pp == null){//没有父节点 说明replacement就是根节点 赋值根节点
                    root = replacement;
                }else if (p == pp.left){//如果移除节点是父节点的左孩子 赋值父节点的左孩子为顶替节点
                    pp.left = replacement;
                }else{//移除节点肯定是父节点的右孩子 赋值父节点的右孩子为顶替节点
                    pp.right = replacement;
                }
                //将移除节点的左右孩子和父节点赋值为空
                p.left = p.right = p.parent = null;
            }
            //前面做过颜色替换 如果是红则使用root 否则执行删除时平衡树方法
            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);
            }
        }