阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方，欢迎指正~
转载请注明出处https://blog.lzoro.com。
前言
基于JDK1.8。
JDK1.8之前，HashMap并没有采用红黑树，所以哈希桶上的链表过长时，就会有效率问题。
JDK1.8，则在HashMap引入了红黑树，当链表长度超过指定阈值(默认为8)，则进行树化并提供相关操作(增删查等)，提高了操作效率。
之前阅读了HashMap的源码，但是由于篇幅关系，略过了链表树化后红黑树的相关操作，本着打破砂锅问到底的精神，来看下红黑树在HashMap中的应用。
打破沙锅问到底，是一个成语，拼音为：dǎ pò shā guō wèn dào dǐ，其 比喻追究事情的根底，其出处自 宋·黄庭坚《拙轩颂》。
红黑树
什么是红黑树？
是这样的吗（开个玩笑，不存在的）。
树？
是这样的，这才对吧，有红有黑。
红黑树
科普时间，it KePu's tims.
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
以上科普信息由度娘提供。
性质
红黑树不仅是二叉查找树，它还必须满足5个性质
- 1.节点非黑即红
- 2.根节点是黑色
- 3.每个叶节点（NIL节点，空节点）是黑色的
- 4.每个红色节点的两个子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
满足了以上性质的二叉查找树的就是红黑树，如果是初次接触的话，是不是看完有点懵，不要慌，接着往下看。
红黑树的效率相对较高，所以它被用来存储相关数据，基本的操作有增加/删除/查找，在这些操作之后可能会破坏红黑树的性质，所以需要相关操作来维护以让红黑树符合上面的性质要求。
而这里提到的相关操作有
- 变色
- 左旋
- 右旋
左旋右旋
是不是对红黑树的任意操作之后，它都还能满足上面的提交的条件呢。
答案是No。
所以也就有了旋转的存在。
旋转跳跃，我闭着眼，尘嚣看不见 你沉醉了没。（请不要唱，快拉回你的心思）
旋转跳跃
嗯，旋转分为左旋和右旋。
左旋
将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，并修改相关引用。
左旋
右旋
是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，并修改相关的引用。
右旋
是不是还是有点迷糊，那么再来两张动图帮助下理解~
左旋
右旋
懒人自有妙计，不过要有版权意识。
动图来源：https://blog.csdn.net/sun_tttt/article/details/65445754
是不是明白一些了~~
基本的关于红黑树概念介绍完毕，需要深入了解的小伙伴请移步搜索引擎。
接下来，坐好了，将车门焊死，准备发车了。
发车
HashMap中的红黑树
先看下HashMap内部类TreeNode<K,V>的定义，它继承了LinkedHashMap.Entry<K,V>
类java.util.HashMap
第1791行起
/**
* 二叉树实体. 继承 LinkedHashMap.Entry (顺序扩展节点)
*
* linked node.
*/
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);
}
/**
* 返回根节点
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
//先略去部分功能代码
...
}
在看相关的功能代码之前，先来看下HahsMap中红黑树左旋和右旋的实现
HashMap中的红黑树 - 左旋
/**
* 红黑树左旋操作
*/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
//p不为null且p的右子树不为null
if (p != null && (r = p.right) != null) {
//将r(p的右子树)的左子树变成p的右子树
//有点拗口 o(╥﹏╥)o
//下面会用一个图示来说明
if ((rl = p.right = r.left) != null)
//修改父节点引用，rl是r(p的右子树)的左子树
rl.parent = p;
//将r(p的右子树)的父节点变成p的父节点（左旋过程，将右子树变成自己的父节点）
if ((pp = r.parent = p.parent) == null)
//如果p节点的父节点为null，证明p是根节点（子树的根节点）
//将r变成根节点（子树的根节点），并变成黑色（符合性质）
(root = r).red = false;
//如果存在父节点且p是该节点的左子树
else if (pp.left == p)
//将r(p的右子树)变成该节点的左子树
pp.left = r;
//如果存在父节点且p节点是该节点的右子树
else
//将r(p的右子树)变成该节点的右子树
pp.right = r;
//将r(p的左子树)变成p（左旋中，将左子树变成自己的父节点）
r.left = p;
//r变成p的父节点
p.parent = r;
}
return root;
}
下面用图示来说明上面的步骤，会比较简单明了不拗口
一、p没有父节点（可以理解为p是根节点）
左旋演示1
一、p有父节点
左旋演示2
HashMap中的红黑树 - 右旋
/**
* 红黑树右旋操作
*/
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
//p不为null且p的左子树不为null
if (p != null && (l = p.left) != null) {
//将l(p的左子树)的右子树变成p的左子树
if ((lr = p.left = l.right) != null)
//修改父节点引用，lr是l(p的左子树)的右子树
lr.parent = p;
//将l(p的右子树)的父节点变成p的父节点（右旋过程，将左子树变成自己的父节点）
if ((pp = l.parent = p.parent) == null)
//将l变成根节点（子树的根节点），并变成黑色（符合性质）
(root = l).red = false;
//如果存在父节点且p是该节点的右子树
else if (pp.right == p)
pp.right = l;
//如果存在父节点且p是该节点的左子树
else
pp.left = l;
//将l(p的右子树)变成p（右旋中，将右子树变成自己的父节点）
l.right = p;
p.parent = l;
}
return root;
}
类似的下面用图演示过程
一、p没有父节点（可以理解为p是根节点）
右旋演示1
一、p有父节点
右旋演示2
右旋
理解了HashMap中红黑树的左旋和右旋，下面看一下几个比较重要的方法
treeify
顾名思义：树化。当哈希桶中的链表长度超过阈值(默认8)的话，就会对链表进行树化，具体来看一下实现。
调用链如下
1、HashMap第643行treeifyBin(tab, hash);，判断阈值，超过则进行树化
2、HashMap第754行，treeifyBin实现，第771行调用TreeNode的树化实现
/**
* 替换哈希桶中给定哈希索引的元素
* 如果哈希桶太小，则resize
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//判断哈希桶
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//调整扩容
resize();
//在哈希桶中获取指定位置的元素
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//替换成树节点
do {
//这里的replacementTreeNode调用了TreeNode的构造函数进行构造
TreeNode<K,V> p = replacementTreeNode(e, null);
//维护顺序
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);
}
}
3、HashMap第1897行，treeify实现
/**
* 红黑树化
* @return 树的根节点
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//循环整理
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//取出下一个链表节点
next = (TreeNode<K,V>)x.next;
//将x节点的左右节点设置为null
x.left = x.right = null;
//判断当前红黑树是否有根节点
if (root == null) {
//如果没有根节点
//当前节点的父节点设置为null
x.parent = null;
//设置颜色为黑色（根节点为黑色）
x.red = false;
//将x节点设置为根节点
root = x;
}
//当前红黑树存在根节点
else {
//获取x节点的key
K k = x.key;
//获取x节点的hash
int h = x.hash;
//key的class
Class<?> kc = null;
//从根节点遍历，将x节点插入到红黑树中
for (TreeNode<K,V> p = root;;) {
//定义dir(方向),ph(节点hash)
int dir, ph;
//取出p节点的key
K pk = p.key;
//当p节点的hash大于x节点的hash时
if ((ph = p.hash) > h)
//左侧
dir = -1;
else if (ph < h)
//右侧
dir = 1;
//如果上面的if分支没走，则证明两个节点key的hash值相等，需要通过其他方式进行比较
//如果当前节点(x)的key的类实现了comparable接口，且当前循环节点(p)是相同Class的实例
//那么就通过comparable进行比较
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//若还是相等，就通过tieBreakOrder比较
dir = tieBreakOrder(k, pk);
//先缓存p节点
TreeNode<K,V> xp = p;
//根据dir方向，来选择在左侧还是右侧插入
//并判断是否为null
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//选择的左/右子树为null
//将原来的p节点(现xp)设置为x的父节点
x.parent = xp;
//如果dir 小于等于0
//将x节点放置在原p(现xp)节点的左侧
if (dir <= 0)
xp.left = x;
//如果dir 大于0
//将x节点放置在原p(现xp)节点的右侧
xp.right = x;
//调用balanceInsertion进行插入平衡
root = balanceInsertion(root, x);
break;
}
}
}
}
//确保哈希桶指定位置存储的节点是红黑树的根节点
moveRootToFront(tab, root);
}
/**
* 确保哈希桶指定位置存储的节点是红黑树的根节点
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//索引位置
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果不是红黑树的根节点
if (root != first) {
Node<K,V> rn;
//指向红黑树的根节点
tab[index] = root;
TreeNode<K,V> rp = root.prev;
//整理节点顺序
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
//递归做一个恒定校验
assert checkInvariants(root);
}
}
4、HashMap第2206行，balanceInsertion实现
这个方法实现了红黑树插入节点后的平衡(为了满足平衡性)，方法的分支较多，如果没有很透彻理解红黑树的相关概念和操作，一时间会容易迷惑，下面代码对整体流程进行了注释，但是仍然比较晦涩，后面会带上图示，加深理解。
/**
* 插入平衡
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//将x节点设为红色（新插入节点一开始为红色）
x.red = true;
//一个没有边界的循环(需要内部跳出)
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//取出x的父节点并判断是否为null
if ((xp = x.parent) == null) {
//x没有父节点
x.red = false;//变色(黑色)
return x;//x为根节点发那会
}
//如果x存在父节点且x的父节点为黑色或x的父父节点不存在
else if (!xp.red || (xpp = xp.parent) == null)
//返回root
return root;
//如果x的父节点是父父节点的左孩子
if (xp == (xppl = xpp.left)) {
//父父节点的右孩子不为null且为红色
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;//变色(黑)
xp.red = false;//变色(黑)
xpp.red = true;//变色(红)
x = xpp;
}
else {
//x是父节点的右孩子
if (x == xp.right) {
//左旋
root = rotateLeft(root, x = xp);
//处理x的父父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//x的父节点存在
if (xp != null) {
xp.red = false;//变色
//x的父父节点存在
if (xpp != null) {
xpp.red = true;//变色
//右旋
root = rotateRight(root, xpp);
}
}
}
}
//如果x的父节点是父父节点的右孩子
else {
//x的父父节点的左孩子存在且为红色
if (xppl != null && xppl.red) {
xppl.red = false;//变色(黑)
xp.red = false;//变色(黑)
xpp.red = true;//变色(红)
x = xpp;
}
else {
//如果x是父节点的左孩子
if (x == xp.left) {
//右旋
root = rotateRight(root, x = xp);
//处理x的父父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果x的父节点存在
if (xp != null) {
xp.red = false;//变色(黑)
//如果x的父父节点存在
if (xpp != null) {
xpp.red = true;//变色(红)
//左旋
root = rotateLeft(root, xpp);
}
}
}
}
}
}
下面用图示，举个栗子~
栗子在这里
举个栗子
假如有如下一个链表，里面的数字代表hash值（先不考虑hash分布）
链表
然后按照链表顺序取出节点进行红黑树插入，以及插入后平衡操作（左旋右旋/变色），来看一下整个过程
插入节点过程1
插入节点过程2
综合上面的描述和图示，大概可以把链表转红黑树的操作总结如下
1、将链表的首节点当做临时的红黑树根节点，左右孩子置为null
2、循环按顺序取出链表的节点，进行红黑树插入，和插入后平衡
2.1、取出链表节点，经过hash比较，插入到红黑树合适的位置(保证平衡性)
2.2、由于插入的节点会破坏红黑树的性质，所以需要进行插入后平衡
2.2.1、新插入的节点置为红色
2.2.2、父节点和父父节点的null判断和颜色判断
2.2.2.1、判断新插入节点的父节点是否存在，不存在则返回
2.2.2.1、如果父节点是黑色的，或者父父节点不存在着，则返回
2.2.3、父节点是父父节点的左孩子还是右孩子判断
2.2.3.1、是左孩子且兄弟节点存在并且是红色，则执行相应的变色，然后进行下一轮判断。
2.2.3.2、是左孩子当兄弟节点不存在（或者是黑色），则执行相应的左旋/右旋。
2.2.3.3、是右孩子且兄弟节点存在并且是红色，则执行相应的变色，然后进行下一轮判断。
2.2.3.4、是右孩子当兄弟节点不存在（或者是黑色），则执行相应的左旋/右旋。
3、链表循环完毕后，确保哈希桶指定位置存储的是红黑树的根节点
嗯，没了。细节请看源码和图示，如果觉得迷糊，可以自己动手画画图，或者Debug。
untreeify
有了树化，肯定也有非树化。
有起有落，月缺月圆，凡事要有平衡。一本正经地胡说八道。
举个栗子
突然就斗起了表情。
没错，这个方法就是将红黑树退化成链表，俗称链表化。
入口有几个地方
- 节点删除时，红黑树的大小低于阈值，退化成链表。2035行
tab[index] = first.untreeify(map); // too small - 扩容/调整容量时，调用
split方法
/**
* 红黑树链表化
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
//循环，将红黑树转成链表
for (Node<K,V> q = this; q != null; q = q.next) {
//构造一个普通链表节点
Node<K,V> p = map.replacementNode(q, null);
//维护顺序
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
putTreeVal
嗯，没什么好说的，红黑树的节点插入。
对应上篇博客的链表节点插入，但相比链表来说会比较复杂。不过流程与之前提到过的树化当中的单一节点插入没有太大区别，也是从红黑树的根节点进行遍历，寻找合适的位置插入，并进行插入后的平衡(变色/左旋/右旋)，待插入平衡后，确保存储在哈希桶指定位置的节点是红黑树的根节点。
/**
* 红黑树版本的节点插入
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//取出根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
//从根节点进行遍历，选择合适的位置插入节点(无边界遍历，需要内部跳出)
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//判断方向
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
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) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
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;
}
dir = tieBreakOrder(k, pk);
}
//先缓存当前遍历的树节点
TreeNode<K,V> xp = p;
//判断该树节点下是否有子节点
//如果没有，则根据之前判断的方向（左侧/右侧）进行插入
//如果已有，则向下遍历继续上面的步骤，直到插入合适的位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//插入到合适的位置和，可能破坏红黑树的性质，所以需要进行插入平衡
//插入平衡后，需要确保哈希桶下标位置上存储的节点是红黑树的节点
//这些在上面的树化过程都有提到，此处不再赘述
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
getTreeNode
红黑树中的节点查找。
对应链表的节点查找，在链表树化后，节点的查找就是红黑树实现的。查找的逻辑还是比较清晰的，因为红黑树是自平衡二叉查找树，节点左子树都比自己小，右子树都比自己大，所以根据给定的hash，可以确定从左子树还是右子树查找，然后循环进行定位，知道最终找到节点或者不存在该节点时，结束查找。
/**
* 红黑树节点查找的入口方法
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
/**
* 根据给定的hash和key，从红黑树的根节点开始进行查找
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
//取出左子树和右子树，根据hash和key进行查找
TreeNode<K,V> pl = p.left, pr = p.right, q;
//根据hash大小决定取左子树还是右子树
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
//如果在节点相等，就返回
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
removeTreeNode
移除红黑树节点。
对应链表节点的移除，红黑树版本的节点移除相比链表会复杂一些，因为涉及到维护红黑树的平衡性和相关性质。
/**
* 移除给定节点, 调用该方法时要确保节点存在.
* 因为无法交换存在叶子节点的内部节点内容，所以这会比典型的红黑树节点删除来得复杂
* 遍历过程中"next"指针指向的继任节点是可访问的，所以我们交换了树的连接.
* 如果当前树节点太少，则将二叉树替换成简单形式
* (2-6节点测试触发，取决于树的结构)
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
//判断哈希桶
if (tab == null || (n = tab.length) == 0)
return;
//下标
int index = (n - 1) & hash;
//取出指定下标的根节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
//继任节点和前置节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
//前置节点不存在，则证明要移除的节点是根节点
if (pred == null)
//将继任节点往前移
tab[index] = first = succ;
else
//前置节点存在，则将继任节点连接到前置节点（移除本节点）
pred.next = succ;
//判断继任节点是否存在
if (succ != null)
//存在的话，修改前置引用
succ.prev = pred;
//这个时候first为null，则表示哈希桶指定位置可能只有一个节点
if (first == null)
//返回
return;
//获取根节点
if (root.parent != null)
root = root.root();
//根节点不存在或者根节点的左子树/右子树不存在或者左左子树不存在
//该判断是作为链表化的阈值
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
//红黑树太小，进行链表化
tab[index] = first.untreeify(map); // too small
return;
}
//取得要移除的节点，左子树，右子树
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
//左右子树同时存在
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
//循环查找继任节点
while ((sl = s.left) != null) // find successor
s = sl;
//交换p和s的颜色
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
//相等则证明p是s的直接父节点（只有一个层级）
if (s == pr) { // p was s's direct parent
//交换位置
p.parent = s;
s.right = p;
}
//如果是多个层级
else {
//取出s的父节点
TreeNode<K,V> sp = s.parent;
//下面操作仍然是交换p和s的位置
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
//清空p的右子树引用
p.left = null;
//调整相关引用
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
//确定替换节点
if (sr != null)
replacement = sr;
else
replacement = p;
}
//只有左子树存在
else if (pl != null)
replacement = pl;
//只有右子树存在
else if (pr != null)
replacement = pr;
//左右子树都不存在
else
replacement = p;
//判断替换的节点是不是自身
if (replacement != p) {
//不是自身的话，则执行相关替换操作
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
//判断p的颜色
//如果p是红色节点，则将根节点赋值给r
//如果p是黑色节点，则进行删除平衡(类似于插入平衡)
//这里的r要存储红黑树的根节点
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//如果替换节点是自身的话
if (replacement == p) { // detach
//进行分离操作
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
//确保哈希桶下标指定位置存储的是红黑树根节点
moveRootToFront(tab, r);
}
split
只有在resize的时候被调用，作用是在哈希桶扩容/调整容量时，将红黑树拆分成两颗树，在红黑树太小时进行链表化等操作。
具体看源码注释。
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* @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<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//拆分成两棵树
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//遍历节点
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
//将e的next引用置空，目的是从e断开
e.next = null;
//将e的hash和bit(其实就是oldCap)相与（是不是很熟悉，其实跟链表的操作类似）
//为0的放到lower树
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
//不为0放到upper树
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//判断lower树是否为null
if (loHead != null) {
//判断是否需要链表化
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
//判断upper树是否为null
if (hiHead != null) {
//判断是否需要链表化
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
到这里，关于HashMap中的红黑树相关内容基本上都介绍完毕了，篇幅有点长，没法面面俱到，呼~~（放松一下）。
后话
本来想着每个方法和每个操作流程都画图解释比较直观。
但是后面花现，画图，真的是他喵了太耗费精力了。
我花4，除了动图之外，其他的图都是我自己画的。对了，开头的那棵树除外。当然，表情包也不是。
其他图示留待后面时间充裕了补上吧。
溜了溜了，有帮助的话给格子点个赞呗。
