认真研究HashMap的结点移除【1】removeNode【2】树节点的查找【3】树节点的删除

57 阅读 0 评论 38 点赞

我是靠谱客的博主老实皮带，最近开发中收集的这篇文章主要介绍认真研究HashMap的结点移除【1】removeNode【2】树节点的查找【3】树节点的删除，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

关联博文
数据结构之Map基础入门与详解
认真学习Java集合之HashMap的实现原理
认真研究HashMap的读取和存放操作步骤
认真研究HashMap的初始化和扩容机制
认真研究JDK1.7下HashMap的循环链表和数据丢失问题
认真研究HashMap中的平衡插入
认真研究HashMap中的平衡删除

前面系列博文，我们研究了HashMap的数据结构、get、put操作以及put后的红黑树平衡，本文我们分析HashMap的结点移除。本文基于jdk1.8环境。

我们常用的remove方法有如下两种，其本质都是委派给了removeNode方法。

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


@Override
public boolean remove(Object key, Object value) {
   return removeNode(hash(key), key, value, true, true) != null;
}

【1】removeNode

接下来我们详细分析removeNode方法，其中boolean matchValue表示只有和检测到的value值相等才进行移除。

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;
    //定位到哈希桶中位置
    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;

        // 直接检索到-挺幸运
        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 = 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.next = node.next;//把node割离出来

			//结构调整计数器+1
            ++modCount;
	        // 总数目-1
            --size;
            
            //移除后的操作 linkedhashmap实现了这个方法
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

可以看到整体流程还是很清晰的，这里麻烦在于树结点的查找和移除。

【2】树节点的查找

如下所示，其首先判断当前结点是否为根节点，然后触发find方法。也就是说要保证从根节点开始往下遍历查找。

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

我们继续看find方法，h表示hash(key),k就是key。

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
       
        // 大于h就往左侧找
        if ((ph = p.hash) > h)
            p = pl;
         //小于h就往右侧找   
        else if (ph < h)
            p = pr;
        //key相等--太幸运了直接返回    
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        
        // hash值相等的情况下
        //如果pl为null，就往右侧找   
        else if (pl == null)
            p = pr;
        //如果pr为null，就往左侧找    
        else if (pr == null)
            p = pl;
        // 都不为null，就必须确定是pl 还是pr ，首先使用compareTo进行比较
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
                 //尝试触发compareTo方法 如果k<pk 则p=ol 否则p=pr
            p = (dir < 0) ? pl : pr;
        //迫于无奈往右侧寻找    
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
        // 最后p=pl往左侧寻找
            p = pl;
    } while (p != null);
    return null;
}

comparableClassFor： 如果对象x的类是C，如果C实现了Comparable<C>接口，那么返回C，否则返回null。这个方法的作用就是查看对象x是否实现了Comparable接口

compareComparables：如果x的类型是kc，返回k.compareTo(x)的比较结果。如果x为空，或者类型不是kc，返回0

方法流程梳理如下：

如果ph>h，则将pl赋予p;
如果ph<h，则将pr赋予p;
如果ph==h,且pk==k , 直接返回p;
如果pl == null，则p=pr;从右侧找
如果pr == null，则 p = pl;从左侧找
如果kc不为null，尝试调用其compareTo方法进行比较，如果k<pk 则p=pl 否则p=pr;
最后手段如果q = pr.find(h, k, kc)!=null，返回q;也就是从右侧找
最终手段，直接 p = pl;往左侧找
如果前面没有return，且p不为null，则进行下次循环。否则返回null

总结就是根据hash判断左右，然后根据左右是否为null确定左右。如果尝试使用compareTo得不到左右分支那么就尝试在右侧分支查找，最终去左侧分支查找。

【3】树节点的删除

代码如下所示，首先确定当前哈希桶中索引位置，也就是int index = (n - 1) & hash：

① 进行prev、next的处理
② 确定replacement
③ 使用replacement替代掉当前结点
④ 移除后的树平衡
⑤ 将root指定到tab[index]位置。

其中关于第二步确定replacement，如果pl且pr不为null，那么需要找到当前结点p的后继结点交换颜色、交换位置，然后尝试使用后继结点的right替代掉p(如果后继结点的right存在)。

//前置触发
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);

//如下hash是当前结点的hash
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;

	//确定当前hash位置的头结点first，并赋予root=first
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;

    //记录当前结点的next、prev
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;

	//说明当前结点是头结点，那么直接将next前移
    if (pred == null)
        tab[index] = first = succ;
    else
        pred.next = succ;//node.prev.next = node.next 把node割离出来
    
	//如果next结点存在，node.next.prev=node.prev 把node割离出来
	if (succ != null)
        succ.prev = pred;
// ---------注意，到这里，当前结点node前后 prev next已经改变----------------
    
    //first什么情况下为null？    
    //first为null的情况下无需额外处理，直接返回即可
    if (first == null)
        return;
     
     //确认根节点   
    if (root.parent != null)
        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;

-----------------------------------确定replacement----------------------------------
	// 如果pl 、 pr都不为null
    if (pl != null && pr != null) {
        TreeNode<K,V> s = pr, sl;
       
        // s 为右侧子树的最小左孩子，也就是当前结点的后继结点
        while ((sl = s.left) != null) // find successor
            s = sl;

        //交换后继结点与当前结点的颜色 --第一步  
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        
        //sr可能为null， 后继结点的right
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        
        //p没有左孩子，只有右孩子，且右孩子没有左孩子， 交换sp
        if (s == pr) { // p was s's direct parent
            p.parent = s;
            s.right = p;
        }
        else {
        // p 与 s 交换位置，此时P还在树结构中哦 -第二步
            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;
        }

		//因为前面s.left为null
        p.left = null;

		//sr的新parent为p
        if ((p.right = sr) != null)
            sr.parent = p;
		//pl的新parent为s
        if ((s.left = pl) != null)
            pl.parent = s;
        
        //s的新parent为pp,如果为null，那么 s 就是root    
        if ((s.parent = pp) == null)
            root = s;
         
         //如果 p 是 pp 的左孩子，那么新的左孩子是s   
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        
        // 确定替换结点--也就是哪个结点替换p
        //1.P与后继结点交换；
        //2.“替换结点”替代掉P
        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    // pl不为null，pr为null
    else if (pl != null)
        replacement = pl;
    //    pr不为null，pl为null
    else if (pr != null)
        replacement = pr;
    //     pl=pr=null
    else
        replacement = p;

----------------------------------------------------------------     
     //这一步是用   replacement替换掉 p  --第三步 注意这时 replacement != p
     // replacement 比如sr pl pr
    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;

        // p 从树结构中脱离    
        p.left = p.right = p.parent = null;
    }
	
	//同平衡插入一样，这里有平衡删除，也就是移除结点后进行平衡  --第四步
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

 // 第三步的第二种情况，比如pr pl都为null，或者sr为null，
 // 这一步同样是把p从树结构中割离
    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;
        }
    }
    // 把root结点移动到tab[index]位置
    if (movable)
        moveRootToFront(tab, r);
}