1, 树介绍

这里用的是红黑树，比普通的二叉树多了个标志符，一般的二叉树结构如下

     a
    /\
   /  \
  b    c

二叉树有个缺点，像上面b节点下如果还有其他多个节点，c下面没有，则这个树是非平衡的，非平衡树的缺点很明显就是遍历的层级可能会很多，对效率的提升可能不是很明显，平衡树指的的是它的左右两个子树的高度差的绝对值不超过1
红黑树也算是平衡二叉树的一种，只是子和父之间的颜色不同，正常来讲应该由以下几点组成

//结点数据结构
private class Node{
    private Key key;//键
    private Value value;//值
    private Node left, right;//指向子树的链接:左子树和右子树.
    private int N;//以该节点为根的子树中的结点总数
    boolean color;//由其父结点指向它的链接的颜色也就是结点颜色.

1，每个节点要么是红色，要么是黑色。
2，根节点必须是黑色
3，红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
4，对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。

为何要红黑树，可能是和上面的定义有关，在插入数据时，为了保证树的平衡型，会考虑对整个树进行左旋和右旋，如果想系统的学习红黑树请参考：https://www.cnblogs.com/CarpenterLee/p/5503882.html
这里只说一下和hashmap有关的内容，下面是treenode的定义

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

先说继承部分，LinkedHashMap.Entry<K,V> 最终又继承了 hashmap 中的 node类，所以在hashmap中的数组中的元素可以直接是treenode

static class Entry<K,V> extends HashMap.Node<K,V> {

2, 链表转换为红黑树

在hashmap 的put方法中有涉及, 第一个是转换为tree，还有就是在tree中增加元素，另外就是在get方法中从tree中获取元素

//put方法转换为tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    // 如果链表长度大于8，链表转化为红黑树，执行插入
    treeifyBin(tab, hash);
break;

//put方法中插入元素
else if (p instanceof TreeNode)
    // 如果p是红黑树类型，调用putTreeVal方式赋值
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

//get方法中获取元素
if (first instanceof TreeNode)
    return ((TreeNode<K,V>)first).getTreeNode(hash, key);

3, put 方法转换为tree

//入参1为当前table，入参2为当前hash，此方法是发生在链表已经插入数据后，长度大于8时
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果tab 不存在，或者长度小于64 则进行扩容(暂不知道这种情况何时发生)
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //判断 tab hash下标 中的第一个元素不为null 
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            //将普通 node 转为 treeNode
            TreeNode<K,V> p = replacementTreeNode(e, null);
            //第一次 执行时为null，将第一个元素 赋值给 hd，tl表示上一个，在else里就将所有元素串联起来了
            //这里do while 仅仅是完成了treenode 的链表链接，并没有转换成一棵树
            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);
    }
}

上面的方法比较特殊，仅仅是将普通的node节点转为treenode的链表结构，并没有直接转为tree结构，接着继续看hd.treeify(tab);方法

//方法本身是 treenode 对象的一个方法，下面this 指 tab中 头对象
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //从this 开始遍历，声明两个treenode， x第一次时是this，this的下一个next，遍历的递增条件就是x=next
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        //第一次循环中 next 和root 是同一个，但root作为树的根节点，再后续的插入元素过程中可能会因为旋转而发生改变
        //next 元素就变为了链表 获取next元素的源头，保证链表的便利继续进行
        next = (TreeNode<K,V>)x.next;
        //执行时 将当前遍历的左右树置空
        x.left = x.right = null;
        //root表示第一个元素，仅有第一次遍历时才会执行这个方法，确定x也就是this是root根节点，red为黑树
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            //拿到当前遍历元素的 key 和 hash
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            //内部二次遍历，也是从root开始遍历，从整棵树的根节点进行大小对比，确定摆放位置
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                //如果 当前元素hash小于 二次遍历中的元素时，dir 为-1 ，大于为1，hash相等暂不考虑
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                //暂不知道这行的意思，应该是hash一样时，再对比key的大小
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                //二次遍历中，根据大小关系对比，如果左右位置为null，则直接放置
                //否则会继续遍历，if语句中，p元素已经为当前遍历的左右分支，可以继续遍历
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    //因为p 在if中已经完成了‘next’操作，所以xp就代表二次循环中的当前元素，一次遍历中当前元素x 的parent就是xp
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    //这个方法表示，对当前树进行平衡操作，并返回新的root，这个时候更新root节点并不影响一次遍历中的next
                    //内部就是根据root节点和刚插入的x元素，来判断是否平衡
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //root作为树的根节点和最初table中的第一个元素可能已经不是同一个，确保给定的根是其仓的第一个节点
    moveRootToFront(tab, root);
}

此方法中还缺少一个点，在执行此方法时，本身是一个链表存在，现在并没有将链接关系结束，这一点可能在 moveRootToFront 或者 balanceInsertion 中有涉及，本文章主要讲解hashmap，关于树的细节暂告一段落，如果今后有时间继续研究的话，会继续更新