目录

1、putTreeVal()

2、root()

3、find()

4、untreeify()、treeify()、treeifyBin()总结

4.1 treeifyBin()和treeify()

4.2 untreeify()

HashMap中的putVal()添加元素方法会触发一系列的TreeNode类的方法，依次为：putTreeVal()、root()、find()。

下面我们将按照添加操作流程依次详细讲解方法源码。

调用开始位置：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    ......
    // 若p节点是红黑树，则直接在树中插入或者更新键值对
    else if (p instanceof TreeNode){
        e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    }
    ......
    // 插入节点后，判断是否需要链表转红黑树，
    // 链表元素数大于8才转，因为这里是从第二个节点开始的，所以 TREEIFY_THRESHOLD - 1 = 7 ，又因为binCount是从0开始的，所以用的是>=号。
    // 例如bigCount=7，表示循环了进行了7次，加上原来的那个头节点，表示该链表原先有8个节点，然后新元素又进行了尾插入，此时该链表就有9个元素了，所以此时就得树化操作
    if (binCount >= TREEIFY_THRESHOLD - 1)
        treeifyBin(tab, hash); // 树化操作
    ......
}

1、putTreeVal()

向红黑树插入 or 更新数据（键值对），遍历红黑树，如果找到与新数据key相同的节点，则直接返回该节点；如果找不到相同的key，则创建新节点并插入，然后重新平衡红黑树。

putTreeVal的两种情况：

1. key已经存在这个红黑树中当中了，就直接放回对应的那个节点；
2. 从红黑树的root节点开始遍历，定位到要插入的叶子节点，插入新节点；

putTreeVal除了要维护红黑树的平衡外，还需要维护节点之间的前后关系，也就是同时在维护双向链表关系。

final TreeNode putTreeVal(HashMap map, Node[] tab, int h, K k, V v) {
    // 新数据的key的Class类型
    Class kc = null;
    // 是否调用find方法进行查找，默认没调用
    boolean searched = false;
    // 查找根节点, 索引位置的头节点并不一定为红黑树的根节点，所以需要通过调用root()方法来遍历红黑树结构进而找到根节点
    // 此处的this就是调用该方法的TreeNode实例，
    TreeNode root = (parent != null) ? root() : this;
    // 将根节点赋值给p节点，从根节点开始遍历红黑树，从内部终止遍历
    for (TreeNode p = root;;) {
        // dir：表示向哪个子树查找，-1左，1右； p：当前节点，ph：当前树节点的hash，pk：当前树节点的key
        int dir, ph; K pk;
        // 将当前节点p的hash赋值给ph，
        // 并且新数据的hash小于当前树节点的hash，则向p的左子树查找
        if ((ph = p.hash) > h)
            // dir赋值为-1
            dir = -1;
        // 否则向p的右子树查找
        else if (ph < h)
            // dir赋值为1
            dir = 1;
        // 当前树节点的key等于新数据的key，直接返回当前节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        
        else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            // 还没有调用find方法进行查找
            if (!searched) {
                TreeNode q, ch;
                // 改为已经调用find方法进行查找了，
                searched = true;
                // 从p节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则并终止循环，返回q；
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    // 找到了相同key的节点，直接返回该节点
                    return q;
            }
            // 使用定义的一套规则来比较p节点的key和新数据的key大小, 用来决定向左还是向右查找
            dir = tieBreakOrder(k, pk);// dir<0 则代表 k xp = p;
        // dir<=0则向p左边查找，否则向p右边查找，如果为null,说明已经到达了叶子节点，红黑树插入新节点都会插入到叶子结点的位置，遍历到了null则代表该位置即为新插入节点x的应该插入的位置，进入if分支内进行插入操作
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // 走进来代表已经找到x要插入的位置，只需将x放到该位置即可
            Node xpn = xp.next;
            // 创建新的节点, 其中x的next节点为xpn, 即将x节点插入xp与xpn之间
            TreeNode x = map.newTreeNode(h, k, v, xpn);
            // 调整x、xp、xpn之间的属性关系
            if (dir <= 0) // 如果时dir <= 0, 则代表x节点为xp的左节点
                xp.left = x;
            else // 如果时dir> 0, 则代表x节点为xp的右节点
                xp.right = x;
            // 将xp的next节点设置为x
            xp.next = x; 
            // 将x的parent和prev节点设置为xp
            x.parent = x.prev = xp; 
            // 如果xpn不为空,则将xpn的prev节点设置为x节点,与上文的x节点的next节点对应
            if (xpn != null)
                ((TreeNode)xpn).prev = x;
            // 进行红黑树的插入平衡调整，调用了balanceInsertion和moveRootToFront
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

2、root()

查找红黑树的根节点。向上层遍历，通过判断有没有父节点来找出根节点

final TreeNode root() {
    for (TreeNode r = this, p;;) {
        // 当节点没有父节点的时候，该节点即为根节点
        if ((p = r.parent) == null)
            return r;
        // 当前遍历到的节点设置为其父节点，实现向上层遍历
        r = p;
    }
}

3、find()

从调用此方法的节点开始查找, 对左右子树进行递归遍历，通过hash值和key找到对应的节点。查找过程是比较hash，判断往左找还是往右找，特殊情况就是一边为空，那就只往另一边找，比较key是否相等，递归遍历直到找到相等的key时，就代表找到了。

final TreeNode find(int h, Object k, Class kc) {
    // 1.将p节点赋值为调用此方法的节点，即为红黑树根节点
    TreeNode p = this;
    // 2.从p节点开始向下遍历
    do {
        // ph p的hash，pk p的key
        int ph, dir; K pk;
        TreeNode pl = p.left, pr = p.right, q;
        // 3.如果传入的hash值小于p节点的hash值，则往p节点的左边遍历
        if ((ph = p.hash) > h)
            p = pl;
        // 4.如果传入的hash值大于p节点的hash值，则往p节点的右边遍历
        else if (ph < h)
            p = pr;
        // 5.如果传入的hash值和key值等于p节点的hash值和key值,则p节点为目标节点,返回p节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 6.p节点的左节点为空则将向右遍历
        else if (pl == null)    
            p = pr;
        // 7.p节点的右节点为空则向左遍历
        else if (pr == null)    
            p = pl;
        // 8.如何k的hash值等于pk的hash值，但是k和pk不相等，则将继续用其他的方法对p节点与k进行比较
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) && // 8.1 kc不为空代表k实现了Comparable
                 (dir = compareComparables(kc, k, pk)) != 0)// 8.2 kpk则dir>0
            // 8.3 k 
4、untreeify()、treeify()、treeifyBin()总结 
上一章节讲了untreeify()和treeify()两个TreeNode类的方法，在HashMap源码讲解的文章里讲了HashMap类的treeifyBin()方法。下面将这三个方法拿到一起对比总结一下。
 
4.1 treeifyBin()和treeify() 
在向一个HashMap中添加数值时，算法会根据已经计算过的节点数binCount来控制是否需要将链表转化为红黑树，如果着实需要，那么会将当前hash值映射的桶进行树化。在本节最开始也贴出了，插入数据时进行树化需要调用treeifyBin()方法，然后treeifyBin()方法再去调用treeify()方法。
 
在树化的过程中使用的这两个方法，其中，treeifyBin()是将链接的链表线索化，即为每个二叉树的节点添加前驱和后继节点，形成线索，也就是维护了双向链表的结构，并且将节点都转换成红黑树节点。在完成线索化后，算法会调用treeify函数将已经线索化的链表转化为红黑树。
 
除了这两个方法之外，还有replacementTreeNode()和newTreeNode()两个方法用来完成Node节点和TreeNode节点之间的相互转化。由于TreeNode没有表达next的语义，所以虽然TreeNode继承自Node，但在算法中调用replacementTreeNode()时，形参next被赋予null。在Node转向TreeNode后，next语义由left，right两个字段表达。
 
treeifyBin小结：
 
判断是否真的需要转换红黑树，如果数组长度小于MIN_TREEIFY_CAPACITY 将会对HashMap进行扩容，不会去进行树化。
如果符合转换的条件。将指定链表上的节点转换成树形节点，并且构造成双链表，为调用treeify()转换成红黑树结构做准备。
treeify小结：
 
该方法的主要作用就是，将链表的元素一个一个的插入到树中，构造出符合红黑树特性的结构，来将链表结构真正转换为红黑树结构。真正构建红黑树结构就是在这个方法内实现的。
 
4.2 untreeify() 
这个方法就相对简单很多，就是将红黑树转变为链表，具体的实现就是使用红黑树节点的链表结构进行遍历，将所有的TreeNode节点都转换为Node节点，只是对节点的类型进行了转换，并没有修改红黑树和链表的结构。
 

相关文章：【Java集合】HashMap系列（一）——底层数据结构分析
                   【Java集合】HashMap系列（二）——底层源码分析
                   【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树
                   【Java集合】HashMap的扩容操作源码详解