序
-
写下这篇笔记，是用于记录我点点滴滴的成长，把自己会的东西记录成笔记，一是做个记录，二是再次用到的时候不用再百度别人的，都是自己看的东西，有不对的地方还望雅正
-
我在简书创建了一个专题，叫 源码阅读笔记 ，目的是为了记录自己看过的源码，希望能结交到和我一样喜欢研究源码的你，我认为，没有人是孤独的，只是或许没有找到自己的圈子，专题不用做大，能吸引几个朋友一起经常交流一下我就心满意足了。
-
HashMap使用Node[] 中存储TreeNode的形式作为数据的存储结构，故要掌握HashMap需要先看懂TreeNode
正文
TreeNode结构
static final class TreeNode<K,V>{
//Node
hash //[(n-1) & hash]定位数组的位置
key //key.hashCode()为hash提供原始hashCode
value //值
next //与prev联合使用实现链栈结构
//LinkedHashMap.Entry<K,V>，TreeNode内暂未涉及
before
after
//TreeNode
parent //与left、right联合使用实现树结构
left
right
prev
red //bool，记录树节点颜色
/**
* 红黑树操作
* 包括：树旋转、插入/删除节点后平衡红黑树
*/
/**
* 基本操作
* 包括：树化、链栈化、增删查节点、根节点变更
*/
}
链栈：prev + next实现，节点数<7
树：parent + left + right实现
TreeNode具备红黑树的性质，但又有异于红黑树，由于两种存储形式的存在，插入或删除都要实现两部分的逻辑以及进行当前存储形式的判断
方法目录
- 树旋转(rotateLeft + rotateRight)
- 存储模式转换(treeify + untreeify)
- 根节点操作(root + moveRootToFront)
- 节点合理检查(checkInvariants)
- 查询节点(find)
- 插入节点(putTreeVal + balanceInsertion)
- 删除节点(removeTreeNode + balanceDeletion)
- 节点拆分(split)
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;
}
方法实现，本质上就是把r换到p的位置，其他的节点根据大小放到相应的位置
rotateLeft
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;
}
方法实现，本质上就是把L换到p的位置，其他的节点根据大小放到相应的位置
rotateRight
treeify
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;
//根据hash值判断树节点的位置
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);
}
方法实现，链栈 => 树
- 从链栈根据next依次取出清空left and right的节点
- 根据hash值创建树节点，树节点颜色由balanceInsertion实现(每次插入都默认为红色节点再平衡插入)
untreeify
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) {
//replacementNode new一个Node，根据q的k,v,h,next
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
方法实现，根据当前节点的next关系提取节点，节点提供key，value，hash用于new Node节点创建链栈
root
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
方法实现，根据parent向上查找根节点
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];
if (root != first) {
Node<K,V> rn;
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;
//root移至first的prev形成根节点
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
方法实现，把操作节点从链栈中取出，移至根节点的prev形成新的根节点
checkInvariants
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
//得到当前节点有关的所有节点
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
//检查链栈节点链接
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
//检查树节点链接
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
//检查当前节点颜色
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
//递归向下检查节点
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
方法实现，检查链栈 + 红黑树
- 链栈，prev + next，双向判断检查
- 红黑树，parent + left and right，
1 双向判断检查
2 红黑树节点颜色判断 - 递归实现向下查询
find
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;
//对比hash值
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
//hash值相同时
//判断是否为结果
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//hash值相同，一侧节点为空则直接进入
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
//使用HashMap定义的方法判断结果在哪侧
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;
}
方法实现，h表示使用HashMap规则的key的hash值，
- hash值不同
1 通过与查找节点的hash值对比确定方向向下寻找 - hash值相同
1 判断当前节点是否为查询的key
2 一侧为空直接向下查询
3 使用HashMap定义的对比方法来判断向下查询的方向
4 递归进入右侧寻找
5 只剩下左边了
这是一个非常有意思的方法，它包含了TreeNode中的所有用于向下判断方向的方法
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;
//通过hash和key判断
//hash值不相同
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//hash值相同
//key已存在，不能存在相同的key
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//不同key的hash值相同，需要用到HashMap定义的判断方法
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;
}
}
}
方法实现，判断key若不存在(HashMap中不能存在相同的key)，定位 + 插入
- 定位，根据hash值判断，向下遍历
1 hash值不同，根据大小判断向下循环的方向
2 hash值相同，可能性不大，但是存在，HashMap事先预想到这种情况已经实现了判断的方法，hash值相同则调用HashMap的方法实现判断方向 - 插入，循环遍历到空节点时可进行插入，
1 链接perv + next
2 链接parent + left and right
3 设定颜色和平衡红黑树 - 总结
1 可能的插入情况
.jpg
balanceInsertion
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//插入的节点默认为红色
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//return 根节点
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//return 根节点的子节点
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) {
root = rotateLeft(root, x = xp);
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);
}
}
}
}
}
}
方法实现，确定输出情况 + 分别处理可能的插入情况
- 输出情况，插入节点为根节点或父节点为黑色节点
- 处理可能的插入情况
1 叔父节点为红色，简单的颜色变更
2 插入节点为右节点需要旋转至左节点，再旋转父节点平衡树
情况1
- 平衡树有可能导致根节点发生改变，每次平衡树后都应该在table数组中重置新节点
- 最多两次树旋转
1 插入节点为右节点
2 旋转祖父节点平衡插入当前节点
removeTreeNode
/**
* Removes the given node, that must be present before this call.
* This is messier than typical red-black deletion code because we
* cannot swap the contents of an interior node with a leaf
* successor that is pinned by "next" pointers that are accessible
* independently during traversal. So instead we swap the tree
* linkages. If the current tree appears to have too few nodes,
* the bin is converted back to a plain bin. (The test triggers
* somewhere between 2 and 6 nodes, depending on tree structure).
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
// section 1：通过prev和next删除当前节点
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;
if (first == null)
return;
// section 2：当节点数量小于7时转换成链栈的形式存储
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;
}
// section 3：判断当前树节点情况
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;
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;
// section 4：实现删除树节点逻辑
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;
}
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);
}
方法实现，链栈 + 树实现删除当前节点
链栈：prev、next
树：parent、left、right
具体步骤为，
- 先通过prev和next实现删除逻辑
- 由节点数判断当前存储形式
- 若为树则追加实现parent、left、right
- 由根节点的left.left节点作为判断当前存储状态的核心，链栈的节点数最多为6个
判断数据存储形式
-
删除树节点的方法，删除时使其满足节点位于单链上(操作简便)
树节点删除
balanceDeletion
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
//结束循环条件1，平衡节点 == root
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//循环结束条件2，平衡节点为红色
else if (x.red) {
x.red = false;
return root;
}
//向上平衡
//平衡节点位于左节点
else if ((xpl = xp.left) == x) {
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;
else {
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
}
else {
if (sr == null || !sr.red) {
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != 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;
}
}
}
}
}
方法实现，由结束判断 + 向上平衡两部分实现
-
结束判断，平衡节点为root或red，颜色变更结束平衡
-
向上平衡(平衡节点 = xp)，循环实现从删除节点开始向父节点逐步平衡，每次平衡需要判断兄弟节点和兄弟节点的内侧子节点的颜色，红色则需要通过树旋转来实现平衡
-
平衡树有可能导致根节点发生改变，每次平衡树后都应该在table数组中重置新节点
split
/**
* 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 = 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;
}
}
//保存留在数组原位置的节点，根据节点数判断存储类型
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);
}
}
//保存提取到数组扩容新位置的节点，根据节点数判断存储类型
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
//补充：
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
方法实现，节点拆分 + 判断链接 + 重新存储
- 节点拆分，通过next=null
- 判断链接，
1 通过bit&hash区分 ==0(lo) 和 !=(hi)，根据注释介绍，该方法只有resize调用，进入该方法发现bit是原数组的长度
2 创建lo和hi两组节点来分别记录两种情况，如lo，loH--头节点，loT--尾节点，lc，记录节点数 - 根据头节点非空和节点数判断存储形式存入数组相应位置
个人
- TreeNode中我收获最大的一个方法，主要体现在bit&hash的判断上，查看resize可知，bit表示原数组长度，即 原数组长度&hash
1 比如原数组为32，resize后为64，则用当前节点的hash&32，
即 当前节点的二进制后六位&10 0000，
2 根据&的计算方式，实际上就是判断当前节点的二进制后六位中的第一位是否为1，第一位为1表示后六位>=10 0000(32)，应该放到table[index + bit]，即table[31]
3 总结，resize用循环拆分原数组的每个位置，如32=>64，则实现table[1]中的节点留在 table[1] 还是 table[31] 。
后记
- 在TreeNode的源码中，我学会了，
1 红黑树，红黑树的性质和操作都懂了，就是有些时候可能的情况分析或者为什么要这样操作这点上还有欠缺，学无止境，我会持续保存关注
2 对于红黑树，TreeNode的红黑树和通常的红黑树是有区别的，没能完全掌握区别，比如，TreeNode没有提到的NIL叶子节点等
3 对于hash值相同的情况，左右节点的判断中，使用HashMap定义的判断方法都是一笔带过，后续看完HashMap后会补充
4 splite方法中的拆分判断条件 bit & hash ，惊叹之余，受益匪浅
网友评论