Java中的STL-HashMap中红黑树的原理和应用
Java中的STL-HashMap中红黑树的原理和应用
红黑树
我相信大部分程序员对红黑树这个数据结构都不陌生。下面来巩固一下红黑树数据结构。
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。它有以下几个特点。
- 1、 每个节点或者是黑色，或者是红色。
- 2 、根节点是黑色。
- 3 、每个叶子节点（NIL）是黑色(这里叶子节点，是指为空(NIL或NULL)的叶子节点, 而不是左右孩子为null的节点)。
- 4 、如果一个节点是红色的，则它的子节点必须是黑色的。
- 5 、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点，这就确保了任意一颗红黑树的左右子树的深度比不会大于2
红黑树长这样。
一棵含有n个节点的红黑树的高度至多为2log(n+1). 数学归纳可以很容易的证明，详见大神博客
左旋和右旋
红黑树的左旋和右旋和平衡二叉树的左旋右旋操作相同，目的都是为了保证红黑树的上面几条性质。
左旋
右旋
具体的算法我就不赘述了，无非是指针或者引用的改变。
红黑树插入节点
插入节点前, 先将节点涂红，为什么要涂成红色？因为这样上面红黑树的第五条从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点就不会违背。
插入节点可能会违背第四条如果一个节点是红色的，则它的子节点必须是黑色的。,如何解决这个问题使它成为一颗正确的红黑树呢？在利用二叉查找树的方式插入节点之后，先将新节点设置为红色，然后按照不同的情况对红黑树的节点颜色进行改变和旋转，使其重新成为一颗标准的红黑树。详细的算法参考 大神博客， 非常详细。
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);
}
...
}
- 可以看到它是继承LinkedHashMap.Entry ， 利用了它的next属性来定义树的后继节点。
- 自己定义了prev，当前节点的前驱节点。
- 当前节点的父节点parent，和左右子节点left、right
我们主要看TreeNode中的以下几个函数。
-
final TreeNode<K,V> find(int h, Object k, Class<?> kc), 对应与HashMap 的get(K k)方法。 -
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v),对应HashMap的put(K k, V v)方法。 -
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable), 删除树节点。 -
final void treeify(Node<K,V>[] tab), 将一个Node形成的链表进行树化。 -
final Node<K,V> untreeify(HashMap<K,V> map), 将一个已经树化的Node，再转化成链表。
关于红黑树插入删除节点后有关维护其特性的算法，这里不在赘述，网上有很多资料。
find函数
红黑树本身是一个二叉查找树，准确的说是根据Key的hash值构造的二叉查找树, find是非常迅速的，时间复杂度是log(n), 速度极快。我们看JDK1.8中的源代码。
// 查找hash值为h的k的TreeNode并返回，kc是k的父类中实现Comparable接口的类
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
//先让p指向当前节点
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
// 当前节点的hash > key的hash值
if ((ph = p.hash) > h)
p = pl; // 往左走
else if (ph < h) //当前节点的hash < key的hash
p = pr; // 往右走
else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 当前节点等于k，找到了，返回。
return p;
else if (pl == null) // 上面的没有满足，说明k的hash等于p.hash,但是 k != p.key 且 !k.equals(p.key)
p = pr;
else if (pr == null)
p = pl;
// 下面是查找k的父类中直接实现了Comparable接口的类，赋值给kc, 如果pk实现了comparable，kc一定是pk.getClass(),
// compareComparables实现见下方
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) // 没办法了，从右边开始查找，递归查找，查找结果给q
return q;
else //右边没查到，让p等于左边，继续循环。
p = pl;
} while (p != null);
return null; //最后都没有查到，返回空。
}
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
putTreeVal函数
红黑树的putTreeVal涉及到两大步：
- 二叉查找树的插入方法，插入一个节点。
- 将新的节点规定为红色，并维护红黑树。
JDK1.8的源代码如下。
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))) // 已经存在了，直接返回p
return p;
//这个时候 k 和 p.key的hash值相同，但是k != p.key且 !k.equals(p.key)，用k的compareTo方法比较也是相同的。
else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
// 别问，问就找到了
searched = true;
// 如果左右子树中存在k，返回q (q和k相等)
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;
}
// 左右子树都没找到k，tieBreakOrder(打破排序)这个函数实现在下面。我给大家解释一下；
// 当k和p.key 有完全相同的hash码，但是k != p.key 且 k 没有实现Comparable接口时，则比较
// k和p.key的identityHashCode， identityHashCode是由对象在内存中的位置计算得来的hash，
// p.key和k的identityHashCode不可能相等，因为 k!=p.key，说明k和p.key不是同一个对象的引用。
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
// 要插入的位置刚好的Null，直接插入，并且维护红黑树就好
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 让xpn是p的后继节点（后继指的是原链表中的后继，而不是树的中序遍历的后继）
Node<K,V> xpn = xp.next;
// 新建x节点，并让x的后继是xp的后继
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// xp的后继等于x
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 维护红黑树返回新的root，并且把root移动到tab的第一个位置。这个不讲了，具体算法和《算法导论》中的算法一致。
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
removeTreeNode函数
removeTreeNode比putTreeVal要复杂个人觉得，因为putTreeVal一定是插入到某个叶子节点，而删除可能删除的是一棵树的根节点，需要很复杂的变化才能维护好红黑树。
JDK1.8的源码
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;
// first赋值为树的root节点，这里的tab[index]就是树的root，moveRootToFront方法保证的，moveRootToFront方法很好理解，
// 维护好红黑树之后，树的root节点不一定是原来的root节点，因为会涉及到红黑树的旋转。moveRootToFront就是将旋转后的root
// 移动到链表头。这里为什么说是链表呢？因为TreeNode有prev和next，所以可以这样理解，TreeNode即使一颗红黑树的节点，也是
// 一个链表中的节点。
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// succ赋值为当前节点的后继，pred为当前节点的前驱
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;
if (first == null) // 到这里说明当前节点的前驱和后继都是null，就这一个节点，直接return就好了，上面tab[index] = first = succ;已经删除了它。
return;
if (root.parent != null)
root = root.root(); // 确保root是树的根节点。
// 下面这个判断，是用来判断树的节点是不是过少，如果root == null，或者root的左或右子树NULL，或者root的左子树分左子树为NULL
// 均说明节点过少。如果root的左子树的左子树是NULL，则这棵树最多有6个节点，大概是下面这种形状：
// b
// / \
// b r
// \ / \
// r b b
if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // 将树转化为链表
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
/*********************************************二叉查找树的删除节点方式*****************begin*************************/
// 找到当前节点的后继赋值给s，用s填补当前节点的位置，注意这里的后继不是链表的后继
// 而是红黑树中序遍历的后继。
while ((sl = s.left) != null) // find successor
s = sl;
// 让其后继和当前节点的颜色互换 ，下面一整段代码都是将删除当前节点转化为删除当前节点的后继节点，
// 这种转化是非常巧妙的，因为任意一个红黑树节点的后继的左孩子一定是NULL，这样删除后继之后，只要把
// 后继的右孩子代替该后继的位置即可。
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;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
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.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;
}
/****************************************************end*************************************************/
// 如果删除的是一个红色节点，并不改变红黑树的性质，如果删除的是一个黑色节点，
// 则经过这个黑色节点的路径的黑长度都会 -1， 需要进行balanceDeletion，具体方法见红黑树删除节点的详解。
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// 这里如果p是一个叶子节点(左右都是Nil)，直接把p删除就可以
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);
}
treeify函数
当table中某个盒子中的节点个数大于阀值，说明hash函数使用不当，需要把链表进行树化。
树化的过程就是将链表中的节点一个一个插入树的过程，每一次插入，先按照二叉查找树的方式插入，然后对红黑树进行维护
JDK1.8的源代码如下，这个代码相对上面putTreeVal有一些重复的地方，就不加注释了。
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.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
untreeify函数
当盒子中的节点数目小于一个阀值的时候，就要将红黑树再转化成链表结构，使用 untreeify来完成
JDK1.8中的代码如下。非常简单，重构一个链表，hd是链表头，tl是链表尾。最后形成一个链表之后返回链表头。
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);//将q替换成null，返回替换对象的引用
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
好了，到此HashMap的源码就理解到这，两天半的时间阅读HashMap的所有源码和学习红黑树，收获很多。