一、红黑树
1.1 红黑树的定义
红黑树是一种自平衡的二叉查找树，它的节点的颜色为红色和黑色。它不严格控制左、右子树高度或节点数之差小于等于1。通过左旋、右旋、变色保证平衡
1.每个节点非红即黑；
2.根节点总是黑色的；
3.每个叶子节点都是黑色；
4.红节点的子节点一定是黑色的。
5.从任一节点到叶子节点必须包含相同数量的黑色节点。
AVL树是高度平衡的而红黑树不是高度平衡的，它只要求部分地达到平衡要求，结合变色，降低了对旋转的要求从而提高了性能。在最坏的情况下也可以保证O(logN)，二叉查找树最坏情况下O(N)。
树、红黑树
二、hashMap 2.1 HashMap结构
红黑树调节平衡
红黑树进行调整的几种情况
1.父结点是黑色，不用进行调整
2.父结点是红色
1.叔叔结点是空的，旋转+变色
2.叔叔结点是红色，父结点+叔叔结点变黑色，祖父结点变为红色
3.叔叔结点是黑色，旋转+变色
2.2.2 父结点为null
1.叔叔结点是红色，父结点+叔叔结点变黑色，祖父结点变为红色
2.todo，博主已绕晕
真正的树化逻辑
向红黑树里插入新结点之前，肯定要判断插入到哪个位置，确定好它的父结点，然后，判断，到底走左边，还是走右边。这就需要跟里面的值进行比较，这里比较主要用了下面几个参数进行比较
注意：这里同一个链表或者同一个树的数组下标一样，hashCode并不一定一样。
另外：hash冲突就是，不同的key经过hash计算，得到的数组下标都一样了，这就产生了hash冲突，所以用链表或红黑树来解决hash冲突。
/**
* 树版本的putVal。
* 会在树中插入一个新节点，或者将原有节点返回，在putVal里面对它的value进行修改
*/
final TreeNode putTreeVal(HashMap map, Node[] tab,
int h, K k, V v) {
Class kc = null;
boolean searched = false;
// p = tab[i = (n - 1) & hash]
// ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// p是这个hash对应tab里的桶，也就是自己this
// root为自己这个节点的root节点
TreeNode root = (parent != null) ? root() : this;
// 将root赋值给p
// 下面for的大循环的目的是，从root开始，根据hash和key，不断向下，遍历孩子，
// 直到找到对应节点，或者对应节点没有，插入节点并维持红黑树平衡
for (TreeNode p = root;;) {
int dir, ph; K pk;
// 下面的那个大if，是为了得到dir，确定下次迭代时，p=p.left/right
// 大if中，如果hash和key相同，直接返回p
// 如果hash相同，key无法比较，调用find方法，如果找到，返回q
// 将p的hash赋值给ph
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
// 到这里ph与h相同
// 将p的key赋值给pk
// 如果找到key和hash对应的节点p，将p返回
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 如果hash相同，key不同
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
// dir为k与pk比较的结果
(dir = compareComparables(kc, k, pk)) == 0) {
// 如果比较结果为0
if (!searched) {
TreeNode q, ch;
// 注意：由于searched的关系 直接调用find方法只会有一次！
searched = true;
// 对left和right调用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;
}
// 如果hash相同，key不同，比较结果为0，find没找到，调用tieBreakOrder赋值给dir
// 即对两者的className和默认的hashcode进行依次比较
dir = tieBreakOrder(k, pk);
}
//上面的那个不断if else的语句结束，已经找到了节点或者得到了dir
// p赋值给xp
TreeNode xp = p;
// 根据dir，p=p.left/right
// 但是如果赋值后p为null，代表没有找到对应节点，新增一个节点，并维持平衡
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// xp.next赋值给xpn
Node xpn = xp.next;
// return new TreeNode<>(hash, key, value, next);
// 根据hash，key，value，xpn新建一个TreeNode给x
TreeNode x = map.newTreeNode(h, k, v, xpn);
// 根据dir，将xp（原来的p）.left/right赋值给x
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 设置xp.next为x
xp.next = x;
// 设置x.parent和x.prev为xp
x.parent = x.prev = xp;
// 如果xpn不为null，设置xpn.prev=x
if (xpn != null)
((TreeNode)xpn).prev = x;
// 先设置孩子关系，xp.left/right = x ， x.parent = xp
// 然后设置双向链表的前后关系
// 原来 xp xpn
// 现在 xp x xpn
// xp为x的父节点
// 先维持插入x后的平衡
// 然后将平衡后的红黑树的新的root节点放到tab的最开始
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
2.3.4 resize()
/**
* 实现Map.put并且关联方法。
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent 如果true，则不改变已经存在的value
* @param evict 如果false，哈希表处于创建阶段。
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
// 把table赋值给tab，table的长度赋值给n
if ((tab = table) == null || (n = tab.length) == 0)
// 如果tab为null或者长度为0，则调用resize方法 // 返回初始化后的节点数组，赋值给tab，同时table的长度赋值给n
n = (tab = resize()).length;
// 把哈希表中对应的桶赋值给p
if ((p = tab[i = (n - 1) & hash]) == null)
//如果hash对应的桶为null，则新建一个节点，赋值给那个桶
tab[i] = newNode(hash, key, value, null);
else {
// 如果对应的桶不为null
Node e;
K k;
// 下面的代码目的是找到在p这个桶下，hash和key对应的已经存在的那个节点，赋值给e // 把p的key赋值给k
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 如果p的hash和key正确，将p赋给e
else if (p instanceof TreeNode)
// 如果p是TreeNode，调用putTreeVal方法，将返回值赋给e
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 将p.next赋给e，如果e为null，说明链表到头，构造新节点，hash，key，value，然后设置给p.next，然后跳出
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); //尾插法
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// binCount为原来的数目-1，binCount+1为原来的数目
// 如果binCount+1>=TREEIFY_THRESHOLD=8
// 原来的数目>=8，加入后，有9个节点，则树化桶，已经有8个元素了，再加一个就进行树化
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break; // 如果e的数据正确，跳出
p = e; // 将e赋给p，就是p=p.next
}
}
if (e != null) { // 这种情况不是新增节点，而是对已经存在节点进行修改
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//1.7hashmap扩容还判断了table[i]是否为null,如果不为null才进行扩容，jdk1.8去出了这个判断
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* 初始化或者倍化表的大小（*2）。
* 如果表为null，使用字段threshold作为初始容量目标，分配空间。
* 否则，因为我们使用2的幂的扩展，每个桶的元素，要么待在同一个index的桶，要么index+新表中2的幂。
* 比如110+1000=1110，就是加了2的幂
*
* @return the table
*/
final Node[] resize() {
// 将现在的table赋值给oldTab
Node[] oldTab = table;
// 如果现在的table，oldCap=0，否则为table.length
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 将threshold赋值给oldThr
int oldThr = threshold;
int newCap, newThr = 0;
// 下面的代码是得到新的容量和阀值，即newCap, newThr
if (oldCap > 0) {
// 如果oldCap>0,说明是扩容（*2）的情况
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果oldCap超过限制，则设置threshold = Integer.MAX_VALUE，将现在的table直接返回
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 将oldCap << 1 赋值给newCap
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 如果nexCap=16，
// 将oldThr << 1 赋值给newThr
newThr = oldThr << 1; // double threshold
}
// 到这里说明是哈希表新建的情况
else if (oldThr > 0) // threshold字段保存了初始容量（如果设置了）
// 将oldThr 赋值给newCap
newCap = oldThr;
else { // 没有指定初始容量，即threshold为0，则容量为默认值。
// 将16赋值给newCap
// 将12赋值给newThr
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 这里说明要么新建哈希表指定了初始容量，要么nexCap>MAXIMUM_CAPACITY , oldCap < 16
// 根据newCap和loadFactor重新设置threshold
float ft = (float)newCap * loadFactor;
// 如果nexCap>MAXIMUM_CAPACITY，则newThr=Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 将newThr赋值给threshold
// 将new Node[newCap]赋值给newTab
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
// 将newTab赋值给table
table = newTab;
if (oldTab != null) {
// 如果oldTab != null，则是扩容状态，对旧表的数据向新表迁移
for (int j = 0; j < oldCap; ++j) {
Node e;
// 对oldTab进行遍历，将oldTab[j]赋值给e
if ((e = oldTab[j]) != null) {
// 如果e不为null，则迁移
// 将旧表清空，oldTab[j] = null
oldTab[j] = null;
if (e.next == null)
// 如果只有一个节点，新的index为 e.hash & (newCap - 1)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果e是TreeNode，调用e的split方法进行重新分配
((TreeNode)e).split(this, newTab, j, oldCap);
else { // 保持顺序
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next; // 将e.next赋值给next
// oldCap=1000，newCap=10000
// 本来要放入新桶的hash & (newCap-1) = hash & 1111
// 现在hash & oldCap = hash & 1000 hash= 1****
// 如果结果为0，hash为0xxx，说明 hash & 1111=hash & 0111，还是在原来的桶 & oldC= 10000 = 10000
// 如果结果不为0，hash为1xxx，
if ((e.hash & oldCap) == 0) {
//(e.hash & oldCap) == 0，说明还是在原来的桶
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
// 在lo中，形成一个链表，第一个为head，接下来不断放在tail的next
// newTab[j] = loHead;
}
else {
// 说明在另一个桶
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
// 在hi中，形成一个链表，第一个为head，接下来不断放在tail的next
// newTab[j + oldCap] = hiHead;
}
} while ((e = next) != null);
//设置完两个链表后，将两个head赋值给新表中两个桶
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
2.3.5 split
相当于把红黑树里面的两个元素，也拆成了两个链表。
/**
* 将一个树桶的节点分割为低位和高位的树桶，或者如果当前的太小了，反树化。
* 仅仅当resize时调用，看上面关于分割的位的讨论。
*
* @param map the map
* @param tab the table for recording bin heads
* @param index the index of the table being split
* @param bit the bit of hash to split on
*/
final void split(HashMap map, Node[] tab, int index, int bit) {
//bit->oldCap
TreeNode b = this;
// Relink into lo and hi lists, preserving order
TreeNode loHead = null, loTail = null;
TreeNode hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// oldTab[j]赋值给e
// ((TreeNode)e).split(this, newTab, j, oldCap);
// 设置e为b，也就是this，也就是树桶的第一个节点
// 从e开始，不断e.next进行循环
for (TreeNode e = b, next; e != null; e = next) {
next = (TreeNode)e.next;
// 设置e.next为null
e.next = null;
// bit就是oldCap，二进制位10000
// 如果hash&bit为0，放在lo的队尾,lc++
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
// 如果hash&bit为1，放在hi的队尾,hc++
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//把这个树拆成两个链表后，如果低位的链表元素个数，小于等于6
if (loHead != null) {
//UNTREEIFY_THRESHOLD=6,如果红黑树的个数小于等于6，就把它改为链表
if (lc <= UNTREEIFY_THRESHOLD)
// 如果lc<=6，tab[index]为loHead的反树化结果
// loHead:TreeNode类型 loHead.untreeify返回类型Node
tab[index] = loHead.untreeify(map);
else {
// 如果lc>6,tab[index] = loHead
//loHead相当于还是红黑树的头部，再赋值给新的数组
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
// 如果hiHead不为null，树化loHead
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
// 如果hc<=6，tab[index + bit]为hiHead的反树化结果
tab[index + bit] = hiHead.untreeify(map);
else {
// 如果hc>6,tab[index + bit] = hiHead
tab[index + bit] = hiHead;
if (loHead != null)
// 如果loHead不为null，树化hiHead
hiHead.treeify(tab);
}
}
}
2.4 get方法
1.get
2.getNode
3.getTreeNode
1.remove
2.removeNode
3.removeTreeNode
/**
* 删除给定的节点（就是this），那个节点必须在这次调用前存在。
* 这比典型的红黑树删除节点更加混乱，因为我们因为我们不能使用由“next”指针固定的叶子后续来交换内部节点的内容，
* 而“next”指针在遍历过程中是可独立访问的。
* 所以，替代地，我们交换树的连接顺序。
* 如果当前的树看上去有着过少的节点，桶被转换为普通的桶。（触发条件是2-6个节点间，取决于树的结构）
*/
final void removeTreeNode(HashMap map, Node[] tab,
boolean movable) {
int n;
// 如果tab为null或者长度为0，则直接返回
// tab.length赋值给n
if (tab == null || (n = tab.length) == 0)
return;
// index为hash对应的桶的index
int index = (n - 1) & hash;
// tab[index]赋值给first
// first赋值给root
TreeNode first = (TreeNode)tab[index], root = first, rl;
// 删除有两个部分，一个是对节点的next和prev关系的删除
// 一个是对节点parent和孩子关系的删除
// 步骤1：下面先对节点的next和prev关系的删除
// this为被删除的节点
// this.next赋值给succ
// this.prev赋值给pred
// 前后关系 pred this succ
TreeNode succ = (TreeNode)next, pred = prev;
// 这个if，设置pred的next
if (pred == null)
// 如果没有prev，将succ赋值给first，再赋值给tab[index]，相当于跳过this
tab[index] = first = succ;
else
// 有prev，succ赋值给pred.next
pred.next = succ;
// 这个if，设置succ的prev
if (succ != null)
// 如果有next，pred赋值给succ.prev
succ.prev = pred;
// 如果first为null，即代表succ和pred都是null，直接将这个桶设置为null，即可，已经做了，就直接返回
if (first == null)
return;
// 将root的根节点赋值给root
if (root.parent != null)
root = root.root();
// 步骤2：如果root，root的right或left，root的left的left，有一个为null，
// 说明红黑树太稀疏了，反树化，调用first.untreeify(map)，赋值给tab[index]，然后返回
// root.left赋值给rl，退化为链表
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
// 步骤3：判断树节点的情况
// p = tab[index = (n - 1) & hash]
// node = ((TreeNode)p).getTreeNode(hash, key);
// ((TreeNode)node).removeTreeNode(this, tab, movable);
// this是hash对应的桶下，对应的key对应的节点，然后对它调用removeTreeNode方法
// this赋值给p，left赋值给pl，right赋值给pr
TreeNode p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
// 如果pl和pr都不为null
// pr赋值给s
TreeNode s = pr, sl;
// 将s最最左孩子赋值给s（即被删除节点的右孩子的最最左孩子）
while ((sl = s.left) != null) // find successor
s = sl;
// 步骤3.1：将s和p的颜色转换
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
// s.right赋值给sr
TreeNode sr = s.right;
// p.parent赋值给pp
TreeNode pp = p.parent;
// 步骤3.2 设置p和s以及它们的孩子，父亲间的关系
if (s == pr) { // p was s's direct parent
// 如果s和pr相同，代表p的右孩子是s，而且s没有左孩子，p是s的父亲
// 设置p.parent为s，s.right为p，互换父子关系
p.parent = s;
s.right = p;
}
else {
// p不是s的父亲，s.parent赋值给sp
TreeNode sp = s.parent;
// sp赋值给p.parent
if ((p.parent = sp) != null) {
// 如果sp不为null，设置sp的left/right为p
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
// pr赋值给s.right
if ((s.right = pr) != null)
// 如果pr不为null，设置pr.parent为s
pr.parent = s;
}
// 步骤3.3：设置p，sr，pl，
// 设置p.left为null
p.left = null;
// 设置p.right为sr
if ((p.right = sr) != null)
// 如果sr不为null，设置sr.parent为null
sr.parent = p;
// 设置s.left为pl
if ((s.left = pl) != null)
// 如果pl不为null，设置pl.parent为s
pl.parent = s;
// 设置s.parent为pp
if ((s.parent = pp) == null)
// 如果pp为null，设置root为s
root = s;
// 如果pp不为null，设置pp.left/right为s
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
// 如果sr不为null，设置replacement为sr，否则为p
if (sr != null)
replacement = sr;
else
replacement = p;
}
// 如果p只有左孩子，replacement = pl
// 如果p只有右孩子，replacement = pr
// 如果p没有孩子，replacement = p
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
if (replacement != p) {
// 如果replacement不为p，即p有左或右孩子，或者sr为null
// 设置replacement.parent = p.parent
// 设置pp为p.parent
TreeNode pp = replacement.parent = p.parent;
if (pp == null)
// 如果pp为null，设置root为replacement
root = replacement;
// 否则，设置pp.left/right为replacement
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
// p的left，right，parent都设置为null
p.left = p.right = p.parent = null;
}
// 如果p为红色，则删除即可，r为root节点
// 如果p为黑色，删除影响平衡，调用balanceDeletion，r为返回的节点
TreeNode r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
// 如果replacement为p
// 设置pp为p.parent
TreeNode pp = p.parent;
// 设置p的parent为null
p.parent = null;
if (pp != null) {
// 设置pp的left/right为null
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
// 一般movable为true
if (movable)
// 将r变成tab的桶节点
moveRootToFront(tab, r);
}
视频教程、参考博客
