HashMap源码分析上-红黑树
简介
红黑树是一种自平衡二叉查找树（不是平衡二叉树，只不过红黑树近似于平衡的状态）,它相对于二叉查找树性能会更加高效(查找、删除、添加等操作需要O(log n),其中n为树中元素的个数),但实现较为复杂(需要保持自身的平衡)。
红黑树的规则：
- 每个节点要么是红色，要么是黑色
- 根节点是黑色
- 如果一个节点是红色，那么它的两个孩子都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）
- 从根到叶节点或空子节点的每条路径，必须包含相同的黑色节点
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> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
插入操作
插入一个节点，默认节点颜色是红色。插入操作分成5种情况讨论
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)))
// hash一样，key是一个对象或者key经过equals方法得出也是一样的
// 那么直接返回这个节点p，不会插入重复对象
return p;
// 到这里，说明hash值一样，但是key不相等，所以检查这个key有没有实现Comparable接口
else if ((kc == null &&
// k是否实现Comparable接口
(kc = comparableClassFor(k)) == null) ||
// 如果k实现了Comparable接口，就调用它的compareTo方法，比较k和pk的大小
(dir = compareComparables(kc, k, pk)) == 0) {
// 上面的compareTo方法得出了相等结果,或者没有实现Comparable接口
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) {
// xp已经到叶节点了
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;
}
}
}
find
以当前调用对象为节点，寻找有没有hash值一样，key一样的节点。有就返回该目标节点，没有就返回null。
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
// hash值小的节点都在左边
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
// key对象相等，或者key的equals相等，返回找到的节点
return p;
// hash值相等，但是key不相等
else if (pl == null)
// 左节点结束，继续往右节点找
p = pr;
else if (pr == null)
// 右节点结束，继续往左节点找
p = pl;
// 到这里，说明与当前节点的hash值一样，所以检查这个key有没有实现Comparable接口
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
// hash一样，但是key没有实现Comparable接口，或者可以实现了Comparable接口，但是compareTo方法得出的结果不相等
// 往右子树找合适的位置
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
平衡红黑树balanceInsertion
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {
// 默认新添加的节点颜色是红色的
x.red = true;
// xp:x节点的父节点
// xpp:xp节点的父节点
// xppl:xpp的左子节点
// xppr:xpp的左子节点
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
// 情况1
// x自己就是根节点
// 把颜色染黑即可
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
// 情况2
// 父节点是黑色节点，插入一个红色的子节点，不影响红黑树平衡
// 或者xp自己就是根节点，根节点都是黑色的，插入一个红色的子节点，不会影响红黑树平衡
return root;
// 上面两种情况很好理解
// 下面的是一种对称情况
if (xp == (xppl = xpp.left)) {
// 左边
if ((xppr = xpp.right) != null && xppr.red) {
// 情况3
// 这种情况，不能有两个连续的红色节点，则xpp一定是黑色的，
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
// 情况4
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
// 剩下的就是情况5了
xp.red = false; // 把x的父节点染成黑色
if (xpp != null) {
// 把xp的父节点染成红色
xpp.red = true;
// 对xpp右旋
root = rotateRight(root, xpp);
}
}
}
}
else {
// 对称
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
情况1
情况2
情况3
情况4
情况5
删除操作
removeTreeNode主体逻辑分为两部分，第一部分：
1、在TreeNode构成的双向链表中删除node节点，这部分逻辑相对简单，调整前后驱关系即可完成
2、在TreeNode构成的红黑树中删除node节点，这部分逻辑设计最为复杂也是最难理解的，需要分开多个情况处理。
相较于插入操作，红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子，如果有两个孩子，不能直接删除该节点。而是要先找到该节点的前驱（该节点左子树中最大的节点）或者后继（该节点右子树中最小的节点），然后将前驱或者后继的值复制到要删除的节点中，最后再将前驱或后继删除。
由于前驱和后继至多只有一个孩子节点，这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题，问题被简化了一些。我们并不关心最终被删除的节点是否是我们开始想要删除的那个节点，只要节点里的值最终被删除就行了，至于树结构如何变化，这个并不重要。
红黑树删除操作的复杂度在于删除节点的颜色，当删除的节点是红色时，直接拿其孩子节点补空位即可。
当删除的节点是黑色时，那么所有经过该节点的路径上的黑节点数量少了一个。如果该节点的孩子为红色，直接拿孩子节点替换被删除的节点，并将孩子节点染成黑色即可。但如果孩子节点为黑色，处理起来就要复杂的多。
第1部分：将节点从链表中删除
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;
// 先取出index桶位的头节点first，同时first节点也是红黑树的root根节点，因此也有root=first,rl是root节点的左子节点
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)
// 如果当前node节点的前驱节点为空,说明前节点node就位于桶位头节点上，
// 即要删除的是这个root节点
tab[index] = first = succ;
else
pred.next = succ;
if (succ != null)
succ.prev = pred;
//------------------第一部分结束-----------------------------------------
if (first == null)
// 已经被删完了，直接退出
return;
第2部分：检查红黑树是否能转成链表结构
//------------第二部分：检查红黑树是否能转成链表结构--------------------------
// 替换上来的节点可能不是红黑树的root节点，所以这里先获取红黑树的root节点
if (root.parent != null)
root = root.root();
// 红黑树结构节点很少时，直接将该树转成链表即可，不需要再实施树平衡操作
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
//------------------第二部分结束-------------------------------
第3部分：
如果待删除节点p没有孩子，删除的就是自己，使用replacement表示这个节点。
如果待删除节点p有1个孩子，用它的孩子节点替换p，使用replacement表示这个孩子节点。
如果待删除节点p有左右2个孩子，就找它的后继节点s（该节点右子树中最小的节点），注意这个后继节点s，如果s是黑色的，s是不可能有黑孩子的，最多只有一个红色的右孩子；如果s是红的，s是没有孩子的。然后s和s交换位置，颜色也交换。
// pl：节点p的左节点
// pr：节点p的右节点
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
// p的左右节点都存在
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
// 后继（该节点右子树中最小的节点）
// 后继没有左孩子，最多有一个右孩子
while ((sl = s.left) != null) // find successor
s = sl;
// 交换节点p和它的后继节点的颜色
// 因为后面节点p会被它的后继节点替换掉，删除一个节点实际就等于在删除它的后继节点，把后继节点中的值全部复制到节点p中
// 然后删除后继节点
// 思路是这样，实际代码中先把节点p和它的后继进行了叫唤位置
// 节点p孩子节点的情况就会转变成最多只有一个右孩子的情况，注意只是最多，可能还没有
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
// 后继节点的右孩子，可能是null
TreeNode<K,V> sr = s.right;
// 节点p的父节点
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
// 后继节点s就是节点p的右节点
// 交换节点p的节点s的位置，它俩交换了，还差一个pp节点进行关联
p.parent = s;
s.right = p;
}
else {
// s不是p的直接右节点
// 下面也是在交换p和s的位置
// 先把s的父节点找到
TreeNode<K,V> sp = s.parent;
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和s交换位置之后，p是没有左孩子的，所以这里把左孩子删掉
p.left = null;
// 如果之前s有右孩子，sr的parent是指向s的，交换位置后，将sr的parent重新指向p
if ((p.right = sr) != null)
sr.parent = p;
// 如果p之前有左孩子，就将s和pl进行关联
if ((s.left = pl) != null)
pl.parent = s;
// s和pp关联
if ((s.parent = pp) == null)
// pp是null，说明之前的p就是root节点，现在s替换掉p，s变成可root节点
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
// 要删除节点p，先找到p的后继s，把p和s的位置进行交换，注意颜色还是要和没交换之前颜色一样，所以上面才有交换颜色。
// 那么p的位置就会被s占据，s的位置现在变成了p，但是没交换前后继s可能还有右孩子sr
// 现在删除p，这个空出来的位置将会由sr顶上来替换
// 当然s可能也没有右孩子，即sr == null，交换位置后p是叶子节点，左右孩子都没有，删除p，要是p是红色的直接删除就行，
// 如果交换位置后p是黑色的，这就要讨论了
if (sr != null)
replacement = sr;
else
replacement = p;
}
// p的左节点存在，但是右节点不存在
else if (pl != null)
replacement = pl;
// p的左节点不存在，但是右节点存在
else if (pr != null)
replacement = pr;
// p没有左右节点
else
replacement = p;
- 第1种，待删除节点p有左右孩子
找到这个p的后继节点s，交换s和p的位置，注意还要交换颜色。s原来是红色的，替换到了p的位置上，这个位置还是原来p的颜色。p被替换到原来s的位置上，原来s是什么颜色，p替换过来后还是什么颜色。
这样将原来p有两个孩子的情况转为最多只有一个孩子的情况。
但是这里注意，后继节点如果是黑色的，这个节点不可能有黑色子节点，这个很隐晦。黑色的后继节点最多有一个右孩子，且右孩子一定是红色。
如果后继节点是红色的，它的右孩子一定是null，即这个红色的后继节点没有左右孩子，可以直接删除这个红色的节点。
如果s是p的直接子节点
交换s和p后，记得交换颜色，当然图中都是黑的。
-
第2种，待删除节点p只有一个孩子
-
-
第3种，待删除节点p没有孩子
-
第4部分：在replacement与p不相等下，删除节点p，replacement节点替换掉节点p
if (replacement != p) {
// 把p删掉，replacement替换原来p的位置
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
// 说明p就是根节点，
(root = replacement).red = false;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
// 删除这个p节点
p.left = p.right = p.parent = null;
}
第5部分：对红黑树进行平衡
// 如果p是红色的，删除一个红色节点不会影响黑高度，即直接结束
// 如果是黑色，就要讨论
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)
// 平衡后，红黑树的root节点可能已经不是table数组中槽点那个位置的节点了
//
moveRootToFront(tab, r);
}
平衡红黑树balanceDeletion
如果删除的节点p的颜色是红色的，直接使用x进行替换就行。就不会执行balanceDeletion方法了。
所以这里被删除的节点p是黑色的
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
if (x == null || x == root)
// 情形1
// x已经是根节点了，直接结束
return root;
else if ((xp = x.parent) == null) {
// x 是根节点
x.red = false;
return x;
}
else if (x.red) {
// 情形2
// 替换上来的节点x是红色节点，染黑即可
x.red = false;
return root;
}
// 到这里说明x的颜色是黑色,我们知道黑色的后继节点最多只有一个红色的右孩子,只有一个右孩子的情形就是情形2
// 所以这里的x就是我们后面需要删除的节点，且x没有孩子节点
// 下面两个else是对称的，讨论一个即可
else if ((xpl = xp.left) == x) {
// x是左节点
if ((xpr = xp.right) != null && xpr.red) {
// 情形3
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
// 情形4
x = xp;
else {
// 到这里说明xpr不为null节点，且xpr是黑色的
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
// 情形5，sr，sl一定是null，如果不为null，sr与sl的颜色一定是红色
xpr.red = true;
// xp的子树已经平衡，但是xp可能会影响其他子树，所以还需要对xp处理
x = xp;
}
else {
// 能到这里，以下条件都可以
// 1. sr == null , sl != null && sl.red = true
// 2. sr == null , sl != null && sl.red = true
// 3. sr != null && sr.red = false , sl != null && sl.red = true // 不存在
// 4. sr != null && sr.red = true , sl == null
// 5. sr != null && sr.red = true , sl == null
// 6. sr != null && sr.red = true , sl != null && sl.red = false // 不存在
// 7. sr != null && sr.red = true , sl != null && sl.red = true
if (sr == null || !sr.red) {
// 到这里说明 sl!=null && sl.red == true
// 情形6，当然sl也可以为null，不影响
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
// xpr右旋后，xp的right就变成了sl，所以更新xpr节点为sl
xpr = (xp = x.parent) == null ?
null : xp.right;
}
// 如果是 sr != null && sr.red = tru，则sl可以为null，也可以是sl != null && sl.red = true
// 这个和情形5类似，但是情形5的sl，sr都是黑色的，这里的sr是红色的，所以不能按照情形5处理
if (xpr != null) {
// 如果xpr等于null，就是之前的sl为null
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
}
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
情形1
情形2
情形3
情形4
情形5
情形6
如果sr是红色，也是可以用这样的步骤恢复平衡
rotateLeft
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
rotateRight
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
moveRootToFront
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];
// 插入或者删除红黑树节点，平衡后，root节点已经不是之前的first了
if (root != first) {
Node<K,V> rn;
// 把数组index位置的元素替换为根节点对象
tab[index] = root;
// 从链表中删除root节点
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
// 将之前的根节点first添加到root节点链表的后面
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
参考：
置
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 插入或者删除红黑树节点，平衡后，root节点已经不是之前的first了
if (root != first) {
Node<K,V> rn;
// 把数组index位置的元素替换为根节点对象
tab[index] = root;
// 从链表中删除root节点
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
// 将之前的根节点first添加到root节点链表的后面
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
参考：
https://zh.m.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91