HashMap源码分析之putTreeVal方法

小灰灰 2021-11-29 17:18 340阅读 0赞

###### 1、概要 ######

Hashmap的put方法在进行操作的时候会，先根据key找到 该元素应该存在数组上的具体位置------table\[i\]。其中有一步操作是`(p instanceof TreeNode)`，也就是判断该节点是不是树形节点。也就是判断此时，该位置的链表是否已经构建成红黑树。如果是的话将执行`.putTreeVal(this, tab, hash, key, value);`方法。

###### 2、具体方法`putTreeVal` ######

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                           int h, K k, V v) { 
               // map 当前Hashmap对象
               //tab Hashmap对象中的table数组
               //h hash值
               // K key
               // V value
                Class<?> kc = null;
                boolean searched = false;  	//标识是否被收索过
                TreeNode<K,V> root = (parent != null) ? root() : this; // 找到root根节点
                for (TreeNode<K,V> p = root;;) { 	//从根节点开始遍历循环
                    int dir, ph; K pk;
                    // 根据hash值 判断方向
                    if ((ph = p.hash) > h)
                    // 大于放左侧
                        dir = -1;
                    else if (ph < h)
                    // 小于放右侧
                        dir = 1;
                        // 如果key 相等 直接返回该节点的引用 外边的方法会对其value进行设置
                    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                        return p;
    				
    				/** *下面的步骤主要就是当发生冲突 也就是hash相等的时候 * 检验是否有hash相同 并且equals相同的节点。 * 也就是检验该键是否存在与该树上 */
    				//说明进入下面这个判断的条件是 hash相同 但是equal不同
    				// 没有实现Comparable<C>接口或者 实现该接口 并且 k与pk Comparable比较结果相同
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0) { 
    					//在左右子树递归的寻找 是否有key的hash相同 并且equals相同的节点
                        if (!searched) { 
                            TreeNode<K,V> q, ch;
                            searched = true;
                            if (((ch = p.left) != null &&
                                 (q = ch.find(h, k, kc)) != null) ||
                                ((ch = p.right) != null &&
                                 (q = ch.find(h, k, kc)) != null))
                                 //找到了 就直接返回
                                return q;
                        }
    
    
                        //说明红黑树中没有与之equals相等的 那就必须进行插入操作
                        //打破平衡的方法的 分出大小 结果 只有-1 1 
                        dir = tieBreakOrder(k, pk);
                    }
    				//下列操作进行插入节点
    				//xp 保存当前节点
                    TreeNode<K,V> xp = p;
                    //找到要插入节点的位置
                    if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                        Node<K,V> xpn = xp.next;
                        //创建出一个新的节点
                        TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                        if (dir <= 0)
                        //小于父亲节点 新节点放左孩子位置
                            xp.left = x;
                        else
                        //大于父亲节点 放右孩子位置
                            xp.right = x;
                        
                        //维护双链表关系
                        xp.next = x;
                        x.parent = x.prev = xp;
                        if (xpn != null)
                            ((TreeNode<K,V>)xpn).prev = x;
                        //将root移到table数组的i 位置的第一个节点
                        //插入操作过红黑树之后 重新调整平衡。
                        moveRootToFront(tab, balanceInsertion(root, x));
                        return null;
                    }
                }
            }

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

##### 3、小结： #####

添加树形节点，与添加双链表节点个过程类似：  
1、从root节点开始寻找 如果目标k.hash 小于 当前节点的 hash ,那么到左树寻找，大于那么从右树寻找。如果找到key相同并且equals相同的节点 p 那就直接返回。  
2、如果`hash相同 但是equal不同` 进而通过`Comparable`接口，进行比较，如果比较的结果如果还是相等，则在左右子树递归的寻找是否有与要插入的key equals相同的元素。如果有那么直接return返回。  
（也即是没实现`Comparable`接口，大小由`hash`判定。实现了，则由`Comparable`接口的比较方法判定）  
3、如果遍历完所有的节点 并未找到equals相同的节点。那就需要插入该新节点。必须分出大小，所以通过执行`tieBreakOrder`方法，该方法的返回值是-1，1。如果是-1则插入到左边节点，1就插入到右边节点。  
4、插入完成之后，需要重新移动root节点 到table数组的i位置的第一个节点上 并且需重新平衡红黑树。