Map源码解析之HashMap
上一篇文章分析了HashMap的源码，但关于红黑树的部分都是粗略带过，这一篇文章则将着重分析HashMap中和红黑树相关的逻辑代码。
红黑树的理论知识可以参考红黑树(一)之 原理和算法详细介绍进行了解。
一. 红黑树的特性
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点（空节点，NIL节点）是黑色。
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
二. 基础方法
1. 左旋 TreeNode#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;
}
主要分3步，p为支点节点，r为p节点的右儿子。
（1）r节点的左二子成为p节点的右儿子。
（2）p节点的父节点成为r节点的父节点。如果原来p节点为根节点，那么此时r节点成为了根节点，需要将颜色置为黑色。
（3）p节点成为r节点的左儿子。
2. 右旋TreeNode#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;
}
逻辑和左旋差不多，只不过旋转的方向不同，分3步，p为支点节点，l为p节点的左儿子。
（1）l节点的右儿子成为p节点的左儿子。
（2）p节点的父节点成为l节点的父节点。如果原来p节点为根节点，那么此时l节点成为了根节点，需要将颜色置为黑色。
（3）p节点成为l节点的右儿子。
3. TreeNode#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);
}
}
方法并不复杂，如果第一个节点并不是根节点，使得根节点first的前一个节点和后一个节点进行连接，然后根节点作为first节点的前一个节点。
4. treeNode#root方法
遍历找到红黑树的根节点。
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
5. HashMap#comparableClassFor方法
如果x的类型形如class C implements Comparable，则返回类型，否则返回null。
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
6. HashMap#compareComparables方法
使用HashMap#comparableClassFor方法返回的comparable类比较大小。
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
三. 树化
1. HashMap#treeifyBin方法
上一篇文章已经讲到在HashMap#putVal方法中当加入节点后链表长度超过树化阈值，会调用HashMap#treeify方法准备树化。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
在方法中，分两种情况进行处理：
（1）容量（即数组长度）小于最小树化容量，进行扩容。
（2）容量（即数组长度）不小于最小树化容量，将节点Node转化为TreeNode，并将链表转化为双向链表，然后调用TreeNode#treeify方法进行树化。
2. TreeNode#treeify方法
TreeNode#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;
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);
}
可以看到从链表的头结点开始进行遍历。
（1）如果是第一个节点（即根节点不存在），将该节点作为红黑树的根节点，节点颜色置为黑色。
（2）如果不是第一个节点（即存在根节点），由于红黑树按照节点的hash值进行排序的，因此从根节点开始作为参照节点，根据目标节点和参照节点的hash值的比较结果dir进入对应的子节点，并以对应的子节点作为参照节点继续进行循环，一直到参照节点不存在子节点为止。将目标节点作为参照节点的子节点插入，然后调用balanceInsertion方法对红黑树进行修正。
（3）遍历完成后，调用moveRootToFront方法保证根节点是第一个节点。
3. TreeNode#balanceInsertion方法
TreeNode#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;;) {
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);
}
}
}
}
}
}
可以看到，我们首先默认将节点x颜色置为红色，因为插入一个红色节点，不会违背“从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点”的特性。
接下来，我们分情况对红黑树进行处理，使得其不违背其它特性。
（1）x节点是根节点，颜色置为黑色，符合所有特性，结束流程。
（2）x节点的父节点是黑色节点，符合所有特性，结束流程。
（3）x节点的父节点是红色，需要进行处理以保证其符合“如果一个节点是红色的，则它的子节点必须是黑色的”特性，又细分为一下情况
（3.1）父节点是祖父节点的左节点
（3.1.1）叔父节点（祖父节点的另一个子节点）为红色
父节点和叔父节点置为黑色，祖父节点置为红色，祖父节点作为当前节点继续循环处理。
（3.1.2）叔父节点为黑色（叔父节点不存在即NIL按照红黑树视为黑色节点）
首先，如果当前节点是父节点的右儿子，父节点作为当前节点，并以其为支点进行左旋。
其次，如果当前节点的父节点存在，父节点颜色置为黑色。注意这一步的当前节点已经和上一步的而当前节点不同。
然后，如果当前节点的祖父节点存在，祖父节点置为红色，并以祖父节点为支点节点进行右旋。
（3.2）父节点是祖父节点的右儿子
（3.2.1）叔父节点为红色
同3.1.1的处理
（3.2.2）叔父节点为黑色（叔父节点不存在即NIL按照红黑树视为黑色节点）
与3.1.2也类似
首先，如果当前节点时父节点的左儿子，父节点作为当前节点，并以其为支点进行右旋。
其次，如果当前节点的父节点存在，父节点颜色置为黑色。注意这一步的当前节点已经和上一步的而当前节点不同。
然后，如果当前节点的祖父节点存在，祖父节点置为红色，并以祖父节点为支点节点进行左旋。
以3.1.2的场景举例，如下图所示
四. 查找节点
1. TreeNode#getTreeNode方法
上一篇已经分析过，在HashMap#getNode方法中，如果数组的某一个元素是红黑树，会调用TreeNode#getTreeNode方法进行查找。
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
调用根节点的find方法进行查找。
2.TreeNode#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;
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;
//如果key与当前节点的key值大小相等但不相同，先尝试在右儿子查找，找到则返回，找不到则在左儿子找
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
方法不复杂，其实和普通的二叉查找树查询节点的逻辑一致，从根节点开始作为当前节点开始，用当前节点的key值与key进行比较，进入相应的子节点进行循环，知道找到目标节点，否则返回null。
五. 插入/覆盖节点
1. TreeNode#putTreeVal方法
上一篇文章已经分析到，在HashMap#putVal方法中，如果数组元素是红黑树，会调用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;
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);
}
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;
}
}
}
逻辑也不复杂，先按照二叉查找树的方式进行遍历查找，如果找到则返回对应节点，找不到则新建节点并作为当前节点的子节点，并且作为当前节点的下一个节点。
然后调用TreeNode#balanceInsertion方法进行修正保证插入节点后依旧是一颗红黑树。
最后调用TreeNode#moveRootToFront方法保证根节点是第一个节点。
六. 删除节点
1. TreeNode#removeTreeNode方法
根据上一篇文章的分析，在HashMap#removeNode方法中如果匹配到的节点时红黑树的节点，会调用TreeNode#removeTreeNode对当前节点进行删除。
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)))
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);
}
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;
}
}
}
先从理论上描述一下红黑树删除节点的过程，分3种。删除节点后在修正红黑树。
（1）被删除的节点没有子节点，直接删除即可。
（2）被删除的节点只有一个子节点，直接删除该节点，用其子节点代替该节点的位置。
（3）被删除的节点有两个子节点，会稍微复杂一点，找到其右儿子的最左节点（左儿子的最右节点也能符合要求），两者交换位置和颜色，因为其右儿子的最左节点大于等于其所有的左分支节点，小于等于所有的右分支节点，二叉查找树的性质不会改变，依旧是有序的。交换以后，根据其右儿子的最左节点没有子节点和只有右节点的情况有分别按照（1）、（2）进行删除处理即可。
删除节点后，如果删除的节点是黑色的，需要进行修正，保证删除节点后依旧是一颗红黑树。
接着我们看代码，从代码角度分析：
（1）先处理prev和next属性的问题。
如果被删除的是第一个节点（正常情况下就是根节点），将其next对应的节点作为第一个节点。
如果不是第一个节点，将其prev对应的节点的next属性指向其next对应的节点。
如果不是最后一个节点，将其next对应的节点的prev属性指向其prev对应的节点。
（2）校验节点
如果已经没有节点存在，结束流程。
（3）确认根节点
（4）如果红黑树节点数量过少（root == null || root.right == null || (rl = root.left) == null || rl.left == null），需要进行去树化，结束流程。
（5）接下来处理parent、left、right属性的问题，将当前节点记为p，代替当前节点在红黑树中的位置的后继节点记为replacement。从这一步才开始我们上面讲的删除红黑树节点的过程。
（5.1）如果当前节点左儿子和右儿子都存在，需要找到其右儿子的最左节点，两者交换位置和颜色
（5.1.1）找到当前节点右儿子的最左节点，记为s。
（5.1.2）当前节点p和s颜色互换。
（5.1.3）当前节点p和s位置互换。
首先进行判断，如果s是p节点的右儿子，直接将p节点作为s节点的右儿子。否则将p作为s的父节点的子节点，p初步取代s节点的位置，并将p节点的右儿子作为s节点的右儿子，s也初步取代了p的位置
然后，如果s节点有右儿子，将其作为p节点的右儿子，确保p节点完全取代了s节点的位置。
然后，并将p节点的左儿子和父节点作为s节点的左儿子和父节点，如果不存在父节点，则将s作为根节点，确保s节点完全取代了p节点的位置。
最后确定后继节点replacement，就是现在的p节点（原来的s节点）的右儿子（右儿子存在）或者本身（右儿子不存在）。
（5.2）如果当前节点左儿子存在，右儿子不存在，取左儿子作为后继节点replacement。
（5.3）如果当前节点左儿子不存在，右儿子存在，取右儿子作为后继节点replacement。
（5.4）如果当前节点没有子节点，取当前节点p本身作为replacement。
（6）如果p节点和replacement不相同，即被删除的节点有子节点，将p节点的子节点和p节点的父节点关联起来，删除p节点。
（7）如果p节点是黑色节点，需要调用balanceDeletion方法保证删除后依旧是一颗红黑树。
（8）如果p节点和replacement相同，即被删除的节点没有子节点，删除p节点，删除p节点的父节点中和p对应的子节点信息。
（9）根据movable判断是否需要进行moveRootToFront操作，保证根节点是第一个节点。
从上面的代码我们可以注意到有一点，如果需要删除的节点有子节点，则先删除节点再修正红黑树；如果需要删除的节点没有子节点，则先修正红黑树再删除节点。因此，传入balanceDeletion方法的进行修正的当前节点有可能是被删除的，也有可能是被保留的。
2. TreeNode#balanceDeletion方法
对删除节点后的红黑树进行修正，保证其依旧是一颗红黑树。
有两个参数，第一个表示删除前的红黑树的根节点，第二个表示需要进行修正的当前节点，返回修正后的根节点。
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;
//经过之前的循环调整后，有可能根节点发生了变化，root指向的节点不再是根节点，而x指向的是根节点
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
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）x不存在或x是根节点，置为黑色，结束流程，对应场景6。
（2）x是红色节点，置为黑色，结束流程，对应场景3。
（3）x是黑色节点且不为根节点：再次划分情况
（3.1）x是父节点的左儿子
首先，如果x的兄弟节点是红色，此时父节点和兄弟节点的子节点肯定是黑色。将兄弟节点置为黑色，父节点置为红色，以父节点为支点进行右旋，对应场景1.
接着进行判断
（3.2.1）如果此时x的兄弟节点不存在，以x的父节点作为当前节点继续下一步循环。
（3.2.2）如果x的兄弟节点的子节点都是黑色（NIL视为子节点），x的兄弟节点置为红色，以x的父节点作为当前节点继续下一步循环，对应场景2。否则进入（3.2.3）。
（3.2.3）兄弟节点的右儿子为黑色，那么将兄弟节点的左儿子置为黑色，兄弟节点置为红色，以兄弟节点为支点进行右旋，重新取当前节点x的兄弟节点，对应场景4。
（3.2.4）如果兄弟节点存在，将兄弟节点的颜色和父节点保持一致，如果兄弟节点的右儿子存在，将兄弟节点的右儿子置为黑色，父节点置为黑色，以父节点为支点左旋，将根节点作为当前节点，对应场景5。
（3.2）x是父节点的右儿子，逻辑与（3.1）基本一致，不再展开。
总结一下，共有下面6种场景，和上述步骤对应。
七. 去树化
1. TreeNode#untreeify方法
当红黑树节点数量过少时，会进行去树化。
主要是当数组扩容和删除节点时可能会触发去树化。
数组扩容时，节点数小于去树化阈值（6）时，会触发去树化；删除红黑树节点时，如果（root == null || root.right == null || (rl = root.left) == null || rl.left == null）会触发去树化。
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);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
从红黑树的第一个节点开始遍历，将TreeeNode替换成Node，并组装成链表。
八. 红黑树移植
在HashMap扩容过程中，如果数组对应下标的节点是TreeNode，需要调用HashMap#split方法进行移植。
1. HashMap#split方法
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#split方法分两部分
（1）和链表的移植逻辑类似，遍历并组装层两条链表
（2）根据链表的长度和树化阈值进行比较，链表长度大于树化阈值，则调用TreeNode#treeify方法进行树化，否则调用TreeNode#untreeify进行去树化。