HashMap红黑树源码深度解析
前言
HaspMap源码深度分析（一）
在上篇博客的分析中，没有涉及到红黑树的分析，因此这里统一对HashMap中的红黑树进行统一分析它的源码。在阅读本篇博客前，是需要提前了解一下红黑树的，主要有红黑树的特性、如何维持红黑树的平衡等。
源码分析
TreeNode分析
hashMap转换为树的过程，首先要将单链表转换为双链表，那节点之间的关系则是靠继承到的LinkedHashMap.Entry中的next来维护的。在经过转换双链表之后，再转换为树，那转换为树的过程并没有删掉节点之间的关联关系，因此HashMap中的红黑树，也保留着双链表的关系。
/**
* 红黑树，这里继承了LinkedHashMap.Entry, 里面维护了next来指向下一个节点，
* 说明由双链表转换为红黑树后，仍然保留了双向链表的关系。
*/
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);
}
}
root方法分析
root方法的作用是获取红黑树的根节点，比较简单。
/**
* 获取红黑树的根节点。
*/
final TreeNode<K,V> root() {
/*
* this实际是指向调用root()方法的节点，如：e.root(), 那么this指向的就是e。
* 这里的就是从当前节点开始，一直向上遍历，知道遍历节点的父节点为空，那么这个节点
* 就是根节点了。
*/
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
split方法分析
split方法主要发生在resize方法内，用于将旧数组中的红黑树的迁移处理。
/**
* 将红黑树进行拆分
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
//---------------------------------这一块的具体的逻辑与resize中的分析差不多 start************************************
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 = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//---------------------------------这一块的具体的逻辑与resize中的分析差不多 start************************************
/*
* 低位的头节点不位空处理流程
*/
if (loHead != null) {
//如果低位树节点的个数小于6，那么就将红黑树转换位链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
//如果低位树节点的个数大于6，那么将新数组的索引指向拆分后的树的头节点，并再次进行红黑树树化的处理，以维持红黑树的平衡
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
treeify方法分析
HashMap由链表转换树的过程，主要的思想就是，从根节点遍历红黑树，以找到新增节点的插入位置并将新增节点插入到红黑树了，最后需要维护红黑树的平衡。
/**
* 将双向链表转换位红黑树。
* 这里需要知道红黑树的一些特性：
* （1）每个节点或者是黑色，或者是红色。
* （2）根节点是黑色。
* （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
* （4）如果一个节点是红色的，则它的子节点必须是黑色的。
* （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
*/
final void treeify(Node<K,V>[] tab) {
//root表示根节点
TreeNode<K,V> root = null;
/*
* 这里需要搞清楚，this实际指向的是调用treeify方法的节点，
* x: 指向当前节点
* next: 指向x的下一个节点
*/
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
//x左孩子节点以及右孩子节点都置空
x.left = x.right = null;
/*
* 如果根节点为空，那么就将x节点作为根节点，根据以上红黑树特性（2），可知将x的父节点置空，
* 并且将x的颜色改为黑色
*/
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
/*
* root不为空，那么这里就要从root节点进行遍历，以便x节点插入的位置
*/
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
//dir标识方向（左右）, ph标识当前遍历树节点的hash值
int dir, ph;
//当前遍历节点的key
K pk = p.key;
//如果遍历节点的hash值大于当前树节点的hash值，则将dir设置为-1，标识当前节点会放到当前树节点的左侧
if ((ph = p.hash) > h)
dir = -1;
//如果遍历节点的hash值小于当前树节点的hash值，则将dir设置为1，标识当前节点会放到当前树节点的右侧
else if (ph < h)
dir = 1;
/*
* 如果两个节点的hash值相等，则判断当前节点的key是否实现了Comparable接口，并且当前树节点与遍历节点是相同Class实例，那么通过
* comparable的方式再比较两者，如果还是相等，最后再通过tieBreakOrder比较一次。
*/
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
//保存当前遍历节点
TreeNode<K,V> xp = p;
/*
* 如果dir <=0 : 当前树节点一定放置在树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子或者更深层次的节点
* 如果dir > 0 : 当前树节点一定放置在树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子或者更深层次的节点。
* 如果当前遍历的节点不是叶子节点，那么最终会以当前遍历节点的左孩子还是右孩子为起始节点，再重新进行遍历，直到找到叶子节点。
* 如果当前遍历的节点是叶子节点，那么根据dir的值，就可以把当前树节点挂载到当前遍历节点的左或者右侧了。
* 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表进行处理了。
*/
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;
}
}
}
}
//以上的操作仅仅是将双向链表组合成了红黑树，如何将整个红黑树的根节点放到tab的首位，需要进行以下处理
moveRootToFront(tab, root);
}
moveRootToFront方法分析
在红黑树中添加节点后，并且经过红黑树的平衡处理后，那红黑树的root节点可能发生了改变，因此在维持红黑树的平衡过程中，会发生左旋转以及右旋转，那么HashMap为了保证root节点一定要位于数组槽的第一个节点，因此存在以下的处理。这个方法理解起来是会有点难度的，从源码上看，它并没有改变红黑树之间的结构，仅仅是改变节点在双向链表之间的关系（红黑树也保留着双向链表的关系），而且在红黑树查找节点的过程中，主要都是靠左右孩子的关联关系去找，因此这里不会改变红黑树之间的结构。
/**
* 把红黑树的根节点设置为其所在数组的第一个元素
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
//如果根节点不为空，数组槽也不为空并且数组槽的长度大于0，就进行以下处理
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) {
//用这个变量来指向根节点的后一个节点，就是把root.next红黑树结构缓存起来
Node<K,V> rn;
//将头节点替换为根节点
tab[index] = root;
//缓存根节点的前一个节点
TreeNode<K,V> rp = root.prev;
/*
* 判断根节点的下一个节点是否不为空，若不为空，那么就将rn的前一个节点指向到根节点的前一个节点，这一步就相当于把根节点删掉了。
*/
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);
}
}
find方法分析
这个方法实现了红黑树查找节点的方法。
/**
* 根据key的hash值、key以及key所属的Class对象进行查询。
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
//this实际是指向调用root()方法的节点，如：e.root(), 那么this指向的就是e。
//p指定当前调用find()方法的结点
TreeNode<K,V> p = this;
do {
//ph代表当前遍历结点的的hash值，dir代表红黑树的方向，小于等于0，则为左子树，大于0则为右子树，pk代表当前遍历结点的key
int ph, dir; K pk;
//获取当前遍历结点的左子树以及右子树，q用来记录查找到的结点
TreeNode<K,V> pl = p.left, pr = p.right, q;
//如果当前遍历结点的hash值大于需要查找key的hash值，那么p将从左子树开始找，并进行下一次循环
if ((ph = p.hash) > h)
p = pl;
//如果当前遍历结点的hash值小于需要查找key的hash值，那么将p从右子树开始找，并进行下一次循环
else if (ph < h)
p = pr;
//运行到这里，说明hash值是相等的，如果key也相等，那就找到了，直接返回
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
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;
//执行到这里说明无法通过comparable比较, 或者比较之后还是相等,那就从右孩子节点递归循环查找，如果找到了匹配的则返回。
else if ((q = pr.find(h, k, kc)) != null)
return q;
//如果从右孩子节点递归查找后仍未找到，那么从左孩子节点进行下一轮循环
else
p = pl;
} while (p != null);
return null;
}
/**
* 获取树节点
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
//判断调用此方法结点的父结点是否为空，若不为空，那就从根结点开始查找，如果为空，那就从调用此方法的结点开始找
return ((parent != null) ? root() : this).find(h, k, null);
}
untreeify方法分析
这个方法主要是将红黑树转换链表的操作，也就是反树化的过程，经过以上的说明，都知道红黑树也保留了双向链表之间的关系，因此反树化的过程，就是将红黑树的节点转换为普通的结点就可以了，不需要经过太多处理。这样处理真系太秒了。
/**
* 反树化，将树节点转换成链表节点
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
//hd代表头节点， t1代表尾节点
Node<K,V> hd = null, tl = null;
/*
* this实际是指向调用root()方法的节点，如：e.root(), 那么this指向的就是e。
* 从this指向的节点开始进行遍历
*/
for (Node<K,V> q = this; q != null; q = q.next) {
//将树节点替换为普通的链表节点
Node<K,V> p = map.replacementNode(q, null);
//如果尾节点为空，那么就将p节点作为头节点
if (tl == null)
hd = p;
//如果尾节点为空，那么尾节点的下一个节点指向p
else
tl.next = p;
//尾节点下移
tl = p;
}
//返回替换后的头节点
return hd;
}
putTreeVal方法分析
在往红黑树中添加结点，是通过putTreeVal方法进行处理的。这个方法的大概处理流程就是，先判断树中是否已经包含了新增的结点，如果已经包含了，那就返回了。如果没有包含，那就在进一步判断以获得该结点的插入位置。最后将新增结点插入到红黑树中，并维护红黑树的平衡。
/**
* 往红黑树中添加节点。
* @params map 当前节点所在的HashMap对象
* @params tab 当前HashMap对象的数组槽
* @params h 需要添加到红黑树的key的hash值
* @params k 需要添加到红黑树的key
* @params v 需要添加到红黑树的v'a'l'ye
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
//前提：this实际是指向调用root()方法的节点，如：e.root(), 那么this指向的就是e。
//定义k的Class对象
Class<?> kc = null;
//标识是否已经查找过一次树了，这里未必是从root节点开始遍历的。
boolean searched = false;
//如果调用此putTreeVal的节点没有父节点，那么就认为此节点为父节点，否则则调用root()方法获取根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
//从根结点开始遍历，以找到新增结点的插入位置
for (TreeNode<K,V> p = root;;) {
//dir标识树的方向，dir<=0：左子树 dir>0: 右子树。ph：代表当前遍历结点的hash值。pk:代表当前遍历结点的key
int dir, ph; K pk;
//如果遍历的结点的hash值大于新增结点的hash值，那么说明新增的结点应该在红黑树的左子树
if ((ph = p.hash) > h)
dir = -1;
//如果遍历的结点的hash值小于新增结点的hash值，那么说明新增结点应该在红黑树的右子树
else if (ph < h)
dir = 1;
//运行到这里，说明遍历节点的hash值与新增结点的hash值一样，这样的话，再比较遍历结点的key是否一样，若一样，则说明新增的结点已存在，直接返回即可。
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//运行到这里，说明虽然hash值一样，但是key不一样(通过equals比较)，这一块做的就是更进一步的比较，
//指定的key没有实现comparable接口或者实现了comparable接口并且和当前结点的键对象相等
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);
}
//定义xp结点指向当前遍历结点
TreeNode<K,V> xp = p;
//如果dir小于等于0，那就说明新增的结点应该在当前遍历结点的左子树，否则在右子树
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//获取遍历结点的下一个结点
Node<K,V> xpn = xp.next;
//创建一个新的树结点，这个数结点指向xpn
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;
}
}
}
balanceInsertion方法分析
这个方法主要是维护红黑树的平衡，主要的方法有：变色、左旋转、右旋转。理解这块最好还是根据图示来理解。
参考链接有：平衡插入图示说明、平衡插入图示说明
/**
* 红黑树添加节点后，通过此方法来维持树的平衡。
* 维持红黑树的平衡主要有以下三种手段：
* 1）变色
* 2）左旋转
* 3）右旋转
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//新插入的节点标为红色
x.red = true;
//xp: 当前节点的父节点 xpp：当前节点的爷爷节点 xppl: 当前节点的左叔叔节点 xppr: 当前节点的右叔叔节点
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//xp指向当前节点的父节点，如果xp为空，那么把当前节点改为黑色并返回
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//父节点不为空（xp）
//判断父节点是否为黑色，或者父节点为空色并且当前节点的爷爷节点为空，那就返回根节点。---这里不是很理解
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//如果父节点是爷爷节点的左孩子节点
if (xp == (xppl = xpp.left)) {
//如果爷爷节点的右孩子节点不为空，并且为红色，这里实际是操作到了变色来维持红黑树的平衡。
if ((xppr = xpp.right) != null && xppr.red) {
//将右叔叔节点置为黑色
xppr.red = false;
//将父节点置为黑色
xp.red = false;
//将爷爷节点置为红色
xpp.red = true;
//将爷爷节点当作下次处理的其实节点，再次进行循环
x = xpp;
}
//运行到这里，说明不满足变色的条件，需要进行左右旋转的操作来维持红黑树的平衡
else {
//如果添加的节点，为父节点的右节点，并且其叔叔节点是黑色的
if (x == xp.right) {
//将x节点指向其父节点，以父节点作为旋转节点进行左旋转
root = rotateLeft(root, x = xp);
//经过左旋转后，重新定位x节点的父节点，以及爷爷节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//经过左旋转后，判断父节点是否为空，不为空则继续处理
if (xp != null) {
//将父节点置为黑色
xp.red = false;
//如果爷爷节点不为空，那么将爷爷节点置为红色，再进行右旋转操作
if (xpp != null) {
xpp.red = true;
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);
}
}
}
}
}
}
/**
* 看懂此方法需要对红黑树的左旋有一定的了解。
* 红黑树的左旋转
* root: 红黑树的根结点
* p：需要左旋转的结点。
*/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
//r: 指向需要左选择结点的右孩子，pp指向需要左选择结点的父结点，rl指向旋转节点的右子节点的左子节点
TreeNode<K,V> r, pp, rl;
//左旋转，需要保证左旋转的开始结点以及其右孩子结点不为空，这里r指向了旋转结点的右子结点
if (p != null && (r = p.right) != null) {
//如果p的右结点存在左孩子结点，那么这里就将p的右结点指向p的右结点的左结点，并维护其p的右结点的左结点的父结点
if ((rl = p.right = r.left) != null)
rl.parent = p;
//这里实际就是旋转了，p的下一个结点r将会替代p结点，因此这里将r的父结点指向p的父结点。
//如果p的父结点为空，那么r就作为根结点了，将其改为黑色。
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
//运行到这里，说明r的父结点不为空，那么这里判断下p是在其父结点的左侧，如果是，那么p的父结点的左结点就指向r
else if (pp.left == p)
pp.left = r;
//如果是在右侧，那么p的父结点的右结点就指向r
else
pp.right = r;
//发生了左旋转，p就作为r的左结点了
r.left = p;
p.parent = r;
}
return root;
}
/**
* 与左旋差不多的意思，这里不再分析
*/
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;
}
总结
红黑树这块还是要花点心思去理解的，我个人也是花了比较多时间才去对HashMap的源码了解个大概，关于以上的源码分析可能存在不正确的地方，如果有，希望能够提出来，大家一起学习。最后，希望以上的分析能够对你们有帮助。
