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，关于树的细节暂告一段落，如果今后有时间继续研究的话，会继续更新
