JDK1.8 HashMap源码之添加数据时putVal函数中处理红黑树的putTreeVal系列方法分析（四）

Dear 丶 2022-11-19 04:09 53阅读 0赞

今天分析往红黑树中添加数据时的方法，分析之前先需要先预习：[参考文档][Link 1]，和 [预先参考][Link 2]。

一、首先简要分析一下 putVal 函数，调用此方法的地方都多处，我们列举一下：

1、初始化有集合参数的构造函数中 putMapEntries 方法里会调用到此方法，核心代码如下：

for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
        K key = e.getKey();
        V value = e.getValue();
        putVal(hash(key), key, value, false, evict);
    }

2、常用的put方法里会调用到此方法

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

3、常用的  putIfAbsent 方法里会调用到此方法，[和put方法的区别][put]

@Override
    public V putIfAbsent(K key, V value) {
        return putVal(hash(key), key, value, true, true);
    }

4、readObject 方法也用到此方法：核心代码如下

// Read the keys and values, and put the mappings in the HashMap
    for (int i = 0; i < mappings; i++) {
        @SuppressWarnings("unchecked")
            K key = (K) s.readObject();
        @SuppressWarnings("unchecked")
            V value = (V) s.readObject();
        putVal(hash(key), key, value, false, false);
    }

总之，hashMap 中有这四个地方调用，当然入口处可能更多，比如有 好几个地方调用 putMapEntries 方法：

1)、初始化：

public HashMap(Map<? extends K,? extends V> m){
    
        this.loadFactor = DEFAULT_LOAD_FACTOR;//默认的加载因子
    
        putMapEntries(m,false);//初始化数据
    }

2)、调用putAll方法时：

public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }

3)、clone复制数据时：

@Override
    public Object clone() {
        HashMap<K,V> result;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
        result.reinitialize();
        result.putMapEntries(this, false);
        return result;
    }

二，正式分析 putTreeVal 方法

1、putVal方法中的入口处：

else if (p instanceof TreeNode)// hash值不相等，即key不相等，并且已经为红黑树结点（即至少已经发生超过8次hash冲突）
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 放入红黑树中，下面会重点分析。

2、进入 putTreeVal 方法：

/**
     * 当存在hash碰撞的时候，且元素数量大于8个时候，就会以红黑树的方式将这些元素组织起来
     * map 当前节点所在的HashMap对象
     * tab 当前HashMap对象的元素数组
     * h   指定key的hash值
     * k   指定key
     * v   指定key上要写入的值
     * 返回：指定key所匹配到的节点对象，针对这个对象去修改V（返回空说明创建了一个新节点）
     *
     * 如果两个key的hash值相同，那么对应数组位置上就需要用链表的方式将这两个数据组织起来，当同一个位置上链表中的元素达到8个的时候，
     *  就会再将这些元素构建成一个红黑树（参见：treeifyBin方法分析），同时把原来的单链表结构变成了双链表结构，
     *   也就是这些元素即维持着红黑树的结构又维持着双链表的结构。当第9个相同hash值的键值对put过来时，发现该位置已经是一个树节点了，
     *  那么就会调用putTreeVal方法，将这个新的值设置到指定的key上。
     */
    final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                   int h, K k, V v) {
        Class<?> kc = null;// 定义k的Class对象
        // 标识是否已经遍历过一次树，未必是从根节点遍历的，但是遍历路径上一定已经包含了后续需要比对的所有节点。
        boolean searched = false;
        TreeNode<K,V> root = (parent != null) ? root() : this;// 父节点不为空那么查找根节点，为空那么自身就是根节点
        for (TreeNode<K,V> p = root;;) {// 从根节点开始遍历，没有终止条件，只能从内部退出
            int dir, ph; K pk;// 声明方向、当前节点hash值、当前节点的键对象
            if ((ph = p.hash) > h)// 如果当前节点hash 大于 指定key的hash值
                dir = -1;// 要添加的元素应该放置在当前节点的左侧
            else if (ph < h)// 如果当前节点hash 小于 指定key的hash值
                dir = 1;// 要添加的元素应该放置在当前节点的右侧
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))// 如果当前节点的键对象 和 指定key对象相同
                return p;// 那么就返回当前节点对象，在外层方法会对v进行写入
                // 走到这一步说明 当前节点的hash值  和 指定key的hash值  是相等的，但是equals不等
            else if ((kc == null &&
                    (kc = comparableClassFor(k)) == null) ||
                    (dir = compareComparables(kc, k, pk)) == 0) {
                // 走到这里说明：指定key没有实现comparable接口 或者 实现了comparable接口并且和当前节点的键对象比较之后相等（仅限第一次循环)，上篇已分析
    
                /*
                 * searched 标识是否已经对比过当前节点的左右子节点了
                 * 如果还没有遍历过，那么就递归遍历对比，看是否能够得到那个键对象equals相等的的节点
                 * 如果得到了键的equals相等的的节点就返回
                 * 如果还是没有键的equals相等的节点，那说明应该创建一个新节点了
                 */
                if (!searched) {// 如果还没有比对过当前节点的所有子节点
                    TreeNode<K,V> q, ch;// 定义要返回的节点、和子节点
                    searched = true;// 标识已经遍历过一次了
                    /*
                     * 红黑树也是二叉树，所以只要沿着左右两侧遍历寻找就可以了
                     * 这是个短路运算，如果先从左侧就已经找到了，右侧就不需要遍历了
                     * find 方法内部还会有递归调用。参见：find方法解析
                     */
                    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;// 找到了指定key键对应的
                }
                // 走到这里就说明，遍历了所有子节点也没有找到和当前键equals相等的节点
                dir = tieBreakOrder(k, pk);// 再比较一下当前节点键和指定key键的大小，上篇已分析
            }
    
            TreeNode<K,V> xp = p;// 定义xp指向当前节点
            /*
             * 如果dir小于等于0，那么看当前节点的左节点是否为空，如果为空，就可以把要添加的元素作为当前节点的左节点，如果不为空，还需要下一轮继续比较
             * 如果dir大于等于0，那么看当前节点的右节点是否为空，如果为空，就可以把要添加的元素作为当前节点的右节点，如果不为空，还需要下一轮继续比较
             * 如果以上两条当中有一个子节点不为空，这个if中还做了一件事，那就是把p已经指向了对应的不为空的子节点，开始下一轮的比较
             */
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
                // 如果恰好要添加的方向上的子节点为空，此时节点p已经指向了这个空的子节点
                Node<K,V> xpn = xp.next;// 获取当前节点的next节点
                TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);// 创建一个新的树节点，重点看一下
                if (dir <= 0)
                    xp.left = x;// 左孩子指向到这个新的树节点
                else
                    xp.right = x;// 右孩子指向到这个新的树节点
                xp.next = x;// 链表中的next节点指向到这个新的树节点
                x.parent = x.prev = xp;// 这个新的树节点的父节点、前节点均设置为 当前的树节点
                if (xpn != null)// 如果原来的next节点不为空
                    ((TreeNode<K,V>)xpn).prev = x;// 那么原来的next节点的前节点指向到新的树节点
                moveRootToFront(tab, balanceInsertion(root, x));// 重新平衡，以及新的根节点置顶，上篇已分析
                return null;// 返回空，意味着产生了一个新节点
            }
        }
    }

3、find 方法解析

/**
     * 这个方法是TreeNode类的一个实例方法，调用该方法的也就是一个TreeNode对象，
     * 该对象就是树上的某个节点，以该节点作为根节点，查找其所有子孙节点，
     * 看看哪个节点能够匹配上给定的键对象
     * h k的hash值
     * k 要查找的对象
     * kc k的Class对象，该Class应该是实现了Comparable<K>的，否则应该是null
     */
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        TreeNode<K,V> p = this; // 把当前对象赋给p，表示当前节点
        do { // 循环
            int ph, dir; K pk; // 定义当前节点的hash值、方向（左右）、当前节点的键对象
            TreeNode<K,V> pl = p.left, pr = p.right, q; // 获取当前节点的左孩子、右孩子。定义一个对象q用来存储并返回找到的对象
            if ((ph = p.hash) > h) // 如果当前节点的hash值大于k得hash值h，那么后续就应该让k和左孩子节点进行下一轮比较
                p = pl; // p指向左孩子，紧接着就是下一轮循环了
            else if (ph < h) // 如果当前节点的hash值小于k得hash值h，那么后续就应该让k和右孩子节点进行下一轮比较
                p = pr; // p指向右孩子，紧接着就是下一轮循环了
            else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 如果h和当前节点的hash值相同，并且当前节点的键对象pk和k相等（地址相同或者equals相同）
                return p; // 返回当前节点
    
                // 执行到这里说明 hash比对相同，但是pk和k不相等
            else if (pl == null) // 如果左孩子为空
                p = pr; // p指向右孩子，紧接着就是下一轮循环了
            else if (pr == null)
                p = pl; // p指向左孩子，紧接着就是下一轮循环了
    
                // 如果左右孩子都不为空，那么需要再进行一轮对比来确定到底该往哪个方向去深入对比
                // 这一轮的对比主要是想通过comparable方法来比较pk和k的大小
            else if ((kc != null ||
                    (kc = comparableClassFor(k)) != null) &&
                    (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr; // dir小于0，p指向右孩子，否则指向右孩子。紧接着就是下一轮循环了
    
                // 执行到这里说明无法通过comparable比较  或者 比较之后还是相等
                // 从右孩子节点递归循环查找，如果找到了匹配的则返回
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
            else // 如果从右孩子节点递归查找后仍未找到，那么从左孩子节点进行下一轮循环
                p = pl;
        } while (p != null);
        return null; // 为找到匹配的节点返回null
    }

4、点击 newTreeNode(h, k, v, xpn); 方法：创建树上的一个新节点

// Create a tree bin node
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        return new TreeNode<>(hash, key, value, next);
    }

5、  其中的comparableClassFor、compareComparables、tieBreakOrder、moveRootToFront、balanceInsertion方法上篇已经分析，[参考即可][Link 1]

到此，putTreeVal系列方法分析完毕，下篇我们分析HashMap 中删除节点相关的源码，敬请期待！

[Link 1]: https://blog.csdn.net/nandao158/article/details/115678631
[Link 2]: https://blog.csdn.net/nandao158/article/details/115530449
[put]: https://blog.csdn.net/cnds123321/article/details/113793574