HashMap是如何将链表转换成红黑树的
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;
// 通过key和value比较得到节点应该放在树的左面还是右面
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); // 将树的根节点指向数组
}