HashMap之TreeNode
HashMap之TreeNode
##简述
在分析HashMap之前先说一下内部类TreeNode。TreeNode类是一颗红黑树的各种操作。当然TreeNode不只是简单的红黑树操作，还有与HashMap业务相关的代码
先看一下类的继承关系
Entry是一个接口，主要有一些让子类去实现的get、set方法
Node是一个单向链表
最后就是TreeNode红黑树了
先看一下简单的Node单向链表，然后再看复杂一点的TreeNode
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
很简单，一个Node相当于链表的一个节点，next属性对应着下一个节点
TreeNode
TreeNode也是，一个TreeNode代表红黑树的一个节点
红黑树是在二叉查找树基础上，对每一个节点添加一个颜色属性形成的，同时整个红黑二叉树需要同时满足一下五条性质
- 每个节点或是红色，或是黑色的
- 跟节点是黑色的
- 每个叶节点（NIL）是黑色的
- 如果一个节点是红色的，则它的两个子节点都是黑色的
- 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数码的黑节点
如图
叶节点（NIL）不包含任何数据，只是一个标记，没有实际意义
下面通过红黑树的插入、删除、查找、左旋、右旋进一步了解TreeNode
先看一下构造
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
可以看到调用了父类的构造方法，也就是说，TreeNode是红黑树的同时也是一个单项链表
##旋转
先说一下左旋和右旋操作
添加和删除操作肯能会违反红黑树的的性质，而保持红黑树的性质是通过旋转来操作的
如添加了一个红节点N就违反了性质4，在通过2个动图看一下是怎么旋转的
左旋
右旋
以上面的静态图来说明右旋操作，左旋一样，只是操作是相反的
上图添加了节点N违反性质4，右旋G节点：
- 使P成为根节点并变成黑色满足性质2
- G成为P的右节点
- P的右节点成为G的左节点
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;
}
代码虽然不多，但是有点乱，我们一点一点的分析。我们假设传入的参数roo是G节点，p也是G节点
参数root是根节点，p是被旋转的节点
变量l是p的左节点、pp是p的父节点、lr是l右节点
第4行判断p不等于null并把左节点赋值给l，如果l为null的话就不能右旋了
第5行是完成上面性质c，并把值赋值给lr
第7行把p的父节点赋值给l的父节点，并把值赋值给pp，因为我们传入的参数G没有父节点，所以pp为null，为了满足红黑树的性质2，把颜色设置成黑色
第9行和第11行，是判断p是左节点还是右节点，如果是右节点则吧父节点的右节点设置成l，反之亦然
第13行设置l的右节点为p，也就是P的右节点设置成G
第14行设置p的父节点为l，也就是设置G的父节点为P
##查找
从当前节点查找指定节点，根据参数h判断是从左边还是右边查找
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)
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;
}
参数h是TreeNode的hash，而hash就是保持平衡二叉树的字段，通过它进行比较，小的放左边，大的放右边
参数k是要查找的节点的key
参数kc是要查找节点实现的key的运行时类型
第2行p赋值当前节点，从当前节点开始查找
变量ph是当前节点的hash
变量dir是Comparable接口的比较结果
变量pl当前节点的左节点
变量pr当前节点的右节点
变量q是右节点查找时候的返回值，如果找到了返回找到的节点
分3点来说find方法
1.find方法根据当前节点的hash与参数的h比较，如果大于pl赋值给p，如果小于pr赋值给p，相等的情况通过当前节点的key与参数的key比较，不相等在通过equals方法比较。
2.接下来在判断如果pl等于null把br赋值给p，pr等于null的话吧pl赋值给p，都不等于空的话在根据key实现的Comparable比较。comparableClassFor方法是获取k的运行时类型，compareComparables方法先判断，key与运行时kc是同类型，在通过调用k和kc实现的Comparable接口的compareTo进行比较
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
3.以上这些条件如果都不满足，那右节点通过递归比较找到则返回，找不到，把左节点赋值给p，进入下次循环在比较
##插入
从根节点遍历，然后通过hash比较，找到合适的位置插入
插入的代码不多，但描述起来有点费劲，所以我分成3段来说明
1.
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;
参数map是用来创建新的节点，通过条用map的newTreeNode
参数tab
参数h是节点的hash，find方法说过hash的作用，不再敖述
参数k是插入节点的key
参数v是插入节点的value
变量kc与find的kc作用一样
变量 searched用来判断只搜索一次的标记
变量root是根节点，如果parent不为空会通过root方法来获取
final TreeNode<K, V> root() {
for (TreeNode<K, V> r = this, p; ; ) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
就剩下一个for循环了
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);
}
变量dir，如果小于等于0，节点插入到左边，否则插入到右边
变量ph，当前遍历节点的hash
变量pk，当前节点的key
第1-8行，根据hash判断节点放在一边，如果hash值相等，并且key相等，不插入，直接返回节点
9-21行，在用key实现的接口去比较如果还是相等，如果是第一次搜索，那么分别通过左节点和右节点搜索，如果搜索到了也不插入，直接返回。搜索不到会调用tieBreakOrder方法通过key的hasCode比较
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;
}
通过条用System.identityHashCode进行比较
3.
插入的最后一段代码，如果上面找到了合适的位置那么这里就插入
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;
}
变量xp是当前遍历的节点
2行根据dir判断是左节点还是右节点，然后为null就插入
3行，上面说TreeNode是红黑树，但它的父类是个链表，所以可以通过xp.next获得下一个节点
4行通过map.newTreeNode创建一个新节点，稍后查看是怎么创建一个新节点的
5-8行，判断节点x放在左还是右
9-12行，设置链表的相关属性
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
return new TreeNode<>(hash, key, value, next);
}
没什么特别的就是创建一个TreeNode
13行，插入一个节点肯能会破坏红黑树的性质，所以调用balanceInsertion方法保持红黑树的性质。在说方法moveRootToFront之前得说一下参数tab，tab是HashMap存节点的数组，每一个节点都是一颗红黑树，下一章在细说这个tab，这里只知道它是一个红黑树的数组。
balanceInsertion方法保持红黑树性质，根节点可能会被换掉，上面说过红黑树同时还是一个链表，根节点换了，那么链表头也就换了，所以moveRootToFront所做的是更正链表头。先看balanceInsertion方法，之后再看moveRootToFront方法
有3种情况会打乱红黑树的性质
1.插入节点的父节点是红色，父节点的邻居称叔节点，同时叔节点也是红色的情况。通过把父节点和爷爷节点变色来满足红黑树的性质，如图
2.叔节点也是黑色，父节点是红色，并且节点是一个右子节点。通过左旋父节点变成情况3，如图
3.叔节点也是黑色，父节点是红色，并且节点是一个左子节点。通过右旋父节点使红黑树满足条件
代码也是针对上面的3中情况来处理的
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;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
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);
}
}
}
}
}
}
第3行，让插入的节点默认为红色。然后就是一个for循环了，直到满足红黑树的性质后返回
第4行，变量xp是x的父节点，xpp是x的爷爷节点，xppl是爷爷节点的左节点，xppr是爷爷节点的右节点。
第5-8行判断如果没有父节点，那么当前节点就是跟节点，然后返回
第9-10行判断如果父节点是黑色，或者爷爷节点为空返回
第11-31与32-52行是相反的操作，上面说的打乱红黑树的3种情况，第2、3种在32-52行也会相应的反过来，所以这里只说明11-31行，余下代码就明白了
第11行判断，如果父节点是爷爷节点的左节点
第12-17行判断就是上面说的第一种情况，父节点和叔节点都是红色，然后把爷爷的右节点变为黑色，父节点变为黑色，爷爷节点变为红色，把爷爷节点赋值给x，继续循环，直到满足条件
18-32行的else包含了上述的2、3两种情况，这个就不做过多的解释了，上述描述已经解释过这两种情况
好了，现在在来看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;
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);
}
}
上面解释了tab参数，第5行取出经过balanceInsertion摧残之后的根节点，第6行判断如果与摧残之前的节点不同，通过7-17的代码调整链表顺序
##删除
删除比较复杂一些，大流程和插入一样，先删除节点，然后可能会不满足红黑树的性质，在进行调整
先说删除节点方法removeTreeNode，之后再说调整节点方法balanceDeletion，在删除完就会被调用
removeTreeNode方法是删除调用当前方法的节点，删除节点的时候分为3种情况
1.如果没有子节点，那么直接删除，并修改一下父节点
2.如果只有一个孩子节点，将孩子节点提上来，并修改父节点，如图（a）和（b）
3.如果有两个孩子节点，从右节点找到没有左节点的位置，并与要删除的节点互换。分两种情况，一种是图（c），z是被删除的节点，y没有左孩子与z互换，y是z的右孩子这种情况比较简单。另一种情况图（d)当z与y互换时，涉及到l、r、x节点，y移到z的位置，x成为r的左节点
图片截自《算法导论》
代码处理这三种情况时，是先交换z与y的位置和颜色，然后在删除
代码过程，我们来分段阅读
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;
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;
}
3-5行，非空判断，并把tab的长度赋值给n，tab与插入方法的参数tab相同
6行找到当前节点在tab的下标
7-8行，变量first为当前节点，变量root为跟节点默认值为first，变量rl根节点的左节点，变量succ当前链表的下一个节点，变量prev当前链表的上一个节点
9-14行，从链表中删除当前节点
17-18行，把根节点赋值到root变量
19-23行，判断如果当前没有很多节点，就不用红黑树，转换成链表返回
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;
}
变量p当前节点，变量pl当前节点的左节点，pr当前节点的右节点，变量replacement用来替换被删除节点的位置
2行，是情况1，左右节点都不为null的情况
3行，变量s是当前节点的右节点，然后通过查找没有左节点的节点，变量sl，s的左节点
4-5行，找到s节点
6行，交换s和p也就是被删除节点的颜色
7-8行，变量sr是s的右节点，变量pp是当前节点的父节点
9-12行，是判断当前节点的右节点没有左节点，s节点和当前节点互换位置
13-23行，否则，还是s节点和当前节点互换位置，这段代码和9-12要做的事情是一样的，只是涉及到了s的父节点的属性要赋值
24-26行，如果s有右节点，把p设置成sr的父节点
27-28行，把p的左节点交接给s
29-34行，把p的父节点交接给s
35-39行，如果sr不为null替换p的节点就是sr，否则为p
处理完左右节点都不为空的情况，接下来该处理，左节点不为null右节点为null、右节点不为null左节点为null、左右都为null
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;
}
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
1-10行，上面把要删除的节点设置成了replacement的parent，这里把要删除的移除掉，并把移除掉节点的相关属性设置为null
12行，就是调用矫正红黑树性质的方法balanceDeletion的地方，我们先把删除方法看完，然后再说这个方法
这里删除节点通过判断replacement != p，那么如果replacement == 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);
}
根据上面有种情况会相等，一种是sr为null的情况，另一种是被删除的节点没有左右节点的情况，这两种情况其实都是被删除的节点没有子节点。2-9行移除当前节点
11-12行，movable大部分情况都为true，moveRootToFront方法如上面所述
好了现在说一下balanceDeletion方法，如果被删除的是黑色，为了便于理解balanceDeletion方法，我们假设替换被删除的节点，会继承被删除节点的颜色，使被替换节点拥有2种颜色，如果被替换节点是红色现在就是红加黑，如果是黑色现在就是黑加黑，这里所说的继承只是一种假设，只是为了便于理解下面的代码。如果我们不做这个假设，而被删除的是黑节点，那么性质5就会被破坏。
分简单和复杂两种情况
简单：如果replacement现在是跟节点黑加黑，什么也不做。或者当前是红黑色，只需要把当前节点染成黑色，就恢复了红黑树的性质
复杂分四种情况：
1.replacement的兄弟节点是红色（注意，现在replacement以及替换到了被删除节点的位置，而且颜色肯定是黑加黑）
2.replacement的兄弟节点是黑色，而且两个孩子都是黑色节点
3.replacement的兄弟节点是黑色，但左节点为红色，右节点为黑色
4.replacement的兄弟节点是黑色，但右节点为红色，左节点为黑色
接下来根据代码来解决这些问题
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)
return root;
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
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
参数root是上面传过来的根节点，参数x是上面传过来的替换被删除的节点
第3行，变量xp是x的父节点，xpl是xp的左节点，xpr是xp的右节点
4-13行，就是简单的情况
15-51行，就是复杂的4种情况。52行是对称的情况
15-20行，是上面所说的第一种情况，兄弟节点为红色，所以子节点必定是黑色，通过改变兄弟节点和x节点的颜色，然后通过左旋，就把情况转成了2、3或4了，因为x的新兄弟节点为黑色。19行对兄弟节点重新赋值
21-22行，如果兄弟节点为null的话，把父节点付给x，继续从下向上遍历，直到满足条件
24行，变量sl是兄弟节点的左节点，sr是兄弟节点的右节点
25-29行，是上面所说的第二种情况，通过把兄弟节点设置为红色，并把x的黑色在遗传给父节点，通过把父节点赋值给x，继续向上遍历，直至满足上面所说简单的情况（也就是把上面所假设的双颜色变成了单颜色）
蓝色只是我随便画的一个颜色，意义是这个颜色是什么颜色都行
31-38行，是上面所说的第三种情况，兄弟节点与兄弟节点的左节点颜色交换，然后右旋，现在就成了情况4
39-48行，是上面所说的第四种情况，正常情况下这里xpr和xp都不会为null，改变兄弟节点和兄弟节点的又节点颜色，然后改变父节点颜色，左旋，去掉了x的双重黑色并满足红黑树的性质，48行，把root赋值给x，之后到简单情况的代码就退出循环了
TreeNode与红黑树相关的操作就这些了，旋转、查找、出入、删除。为了满足HashMap重置内部数组大小，还有一个拆分方法。当HashMap需要扩容时候，就会调用拆分方法，把红黑树拆分成两个链表，如果两个链表大于一定的值，那么就还转成红黑树，否则就转换成链表
拆分
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);
}
}
}
如上所说这个方法在重置HashMap大小时候回被调用
参数map和tab没什么可说的和上面一样，index是拆分的树在tab数组中的位置，调用这个方法方法之前数组已经扩容了，参数bit是扩容之前的大小
10-25行，拆分一颗红黑树是通过用节点的hash值与bit进行并操作，然后把节点赋值给不同的链表，并通过lc和hc进行计数
28-45行，就是如果链表小于等于UNTREEIFY_THRESHOLD就把红黑树转换成Node链表，否则就转换成红黑树。转换成红黑树是通过treeify方法，转换成链表是通过untreeify这两个方法比较简单，条件判断什么的跟上面讲的都差不多
static final int UNTREEIFY_THRESHOLD = 6;
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);
}
inal 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;
}
到这里TreeNode就说完了，这样下一篇看HashMap分析的时候就会轻松很多了