HashMap源码分析之treeifyBin、treeify方法、moveRootToFront方法

ゞ浴缸里的玫瑰 2021-11-29 23:00 392阅读 0赞

##### 一、概述 #####

我们知道hashmap的结构是`数组`\+`链表`。当发生冲突的时候，冲突的节点会以链表的形式存储在对应桶的位置上。当冲突变的越来越多时，hashmap查找的效率愈发底下。因为链表的查询的时间复杂度是O(n)，所以jdk1.8，推出了红黑树，来提高查找效率。具体就是，当链表的节点大于8之后。链表会转换成红黑树的存储形式，红黑树其实也就是一种查找树。然后又多加了额外的性质。使得红黑树的查找效率提高到`O(logn)`.

##### 二、调用时机在`put`方法中 #####

//TREEIFY_THRESHOLD 这个是树型化的临界值 8 
     if ((e = p.next) == null) { 
     		// 插入完这个节点之后 一共链表就是9个节点
             p.next = newNode(hash, key, value, null);
             //count 为7时 
             if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
             //尝试进行树型化
                 treeifyBin(tab, hash);
             break;
    	 }

##### 三、方法细节`treeifyBin` #####

final void treeifyBin(Node<K,V>[] tab, int hash) { 
            int n, index; Node<K,V> e;
            //如果table为null 或者table数组的长度小于MIN_TREEIFY_CAPACITY 64
            //MIN_TREEIFY_CAPACITY这个其实是转化成红黑树的另外一个条件，就是数组长度要大于64
            //如果小于64 就可以通过扩容的方法，来减小冲突，没有必要转换成红黑树，因为红黑树的转换也是需要很大是 时间和空间的代价
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            	//进行扩容
                resize();
             //获得需要树形化的 链表的第一个节点 也就是数组对应的数组节点table[i]
            else if ((e = tab[index = (n - 1) & hash]) != null) { 
                TreeNode<K,V> hd = null, tl = null;
                do { 
                	//将普通的node节点 构造成TreeNode 拥有更多的属性
                	    /** * parent * right * left * red * key * value * next * prev */
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;
                    else { 
                    	//构造成双链表形式
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                //替换成 构造成双链表的节点
                if ((tab[index] = hd) != null)
                //进行红黑树转换
                    hd.treeify(tab);
            }
        }

##### `treeifyBin`小结 #####

1、判断是否真的需要转换红黑树，如果数组长度小于`MIN_TREEIFY_CAPACITY` 将会中扩容代替转换红黑树  
2、如果符合转换的条件。将所有的节点转换成树形节点，并且构造成双链表 为`treeify` 转换成红黑树准备。

--------------------

##### 四、`treeify`方法详情 #####

*/
       final void treeify(Node<K,V>[] tab) { 
           TreeNode<K,V> root = null;	// 定义根节点
           // 循环遍历链表
           for (TreeNode<K,V> x = this, next; x != null; x = next) {  
               next = (TreeNode<K,V>)x.next;	//定义下一个节点
               x.left = x.right = null;		
               if (root == null) { 
               //第一次循环 
               //将x 赋值给root节点 初始化root节点的颜色 黑色（红黑树的根节点 一定是黑色）
                   x.parent = null;
                   x.red = false;
                   root = x;
               }
               //此处开始构造红黑树
               else { 
               	//获得当前节点的 key 和 hash 
                   K k = x.key;
                   int h = x.hash;
                   Class<?> kc = null;
                   // 从根节点开始每次遍历 寻找插入的位置
                   for (TreeNode<K,V> p = root;;) { 
                       int dir, ph;
                       // 获得根节点的 key 
                       //判断key 与root的key的大小 确定dir的值，也就确定了插入的方向 ，是root节点的左边还是右边
                       K pk = p.key;
                       if ((ph = p.hash) > h)
                           dir = -1;
                       else if (ph < h)
                           dir = 1;
    	// 如果key的hash想等 或者实现comparable接口 又或者是实现了该接口 但是两个比较结果也相同
    	//所以为了打破这种平衡必须再次调用tieBreakOrder方法 比较一次 返回值 只有-1 或1 
                       else if ((kc == null &&
                                 (kc = comparableClassFor(k)) == null) ||
                                (dir = compareComparables(kc, k, pk)) == 0)
                            //打破平衡的方法。
                           dir = tieBreakOrder(k, pk);
    	// 小结：如果没有实现`comparable`方法，那么比较就由 hash值之间的大小决定
    
    
    
                       TreeNode<K,V> xp = p;  // 当且节点
                       if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                           x.parent = xp; // 当前链表节点 作为 当前树节点的子节点
                           if (dir <= 0)
                               xp.left = x;	//作为左孩子
                           else
                               xp.right = x;	//作为右孩子
                               
                            // 每次插入完一个节点之后，就要进行红黑树的调整
                           root = balanceInsertion(root, x);	//下一篇讲解 涉及东西较多
                           break;
                       }
                   }
               }
           }
           //根节点目前到底是链表的哪一个节点是不确定的 要将红黑树的根节点 移动至链表节点的第一个位置 也就是 table[i]的位置。
           moveRootToFront(tab, root);
       }

##### `treeify`小结： #####

改方法的主要作用就是，将链表的元素一个一个的插入到树中，并且保持排序树的特性`当左、右子树不为空的时候 左子树小于根节点 右子树大于根节点`。这里的大小通过`comparable`方法比较key的大小。如果`key`没有实现该接口，那么通过比较`hash值`来判定。

--------------------

##### 五、moveRootToFront方法详细解 #####

##### （1）、概述 #####

当我们删除或者增加红黑树节点的时候，`root`节点在双链表中的位置可能会变动，为了保证每次红黑树的根节点都在链表的第一个位置，在操作完成之后 需要`moveRootToFront`方法来进行调整。

> ·`TreeNode<K,V> extends LinkedHashMap.Entry<K,V>`  
> 因为TreeNode继承了Entry.所以它除了它自己几个属性 parent 、left、 right、 prev、 red、之外，还有继承过来的属性  
> hash、key、value 、next;所以它底层其实是双结构的，维护着红黑树 和双链表两种结构。，所以当每次调整好红黑树之后，root节点的位置可能会变动，那我这个时候我们就要维护root在双链表中的关系了（移动双链表中的元素 并不会影响红黑树）

* 
             */
             //tab：hashmap下的table数组
             //root：调整红黑树之后的 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) { 
                	// 获得当红黑树所处在 table数组的哪一个位置 (n - 1) & root.hash效果与取模相同
                    int index = (n - 1) & root.hash;
                    // 获得改位置的节点对象 也就是链表的第一个节点
                    TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
                    //如果这个位置不是 root节点 那么就要进行调整了
                    if (root != first) { 
                    //定义一个临时Node 变量
                        Node<K,V> rn;
                        //直接将链表的第一个位置 指向了root节点 
                        tab[index] = root;
    
    
                        // 获得root节点的前驱
                        //获得root后继 
                        //将前驱和后继相连接 root节点从原链表中脱离出来了
                        TreeNode<K,V> rp = root.prev;
                        if ((rn = root.next) != null)
                            ((TreeNode<K,V>)rn).prev = rp;
                        if (rp != null)
                            rp.next = rn;
    
    					// 将root与原来双链表的第一个节点相连
    					//这样root又回到双链表当中 并且在双链表的第一个位置上
                        if (first != null)
                            first.prev = root;
                        root.next = first;
                        //root节点的前驱节点设置为null 因为他双链表的第一个节点 没有前驱
                        root.prev = null;
    
    
                    }
                    assert checkInvariants(root);
                }
            }