3分钟让你明白：HashMap之红黑树树化过程(3)

我们看一下treeify代码

final void treeify(Node<K, V>[] tab) 
 { 
 TreeNode<K, V> root = null; 
 // 以for循环的方式遍历刚才我们创建的链表。 
 for (TreeNode<K, V> x = this, next; x != null; x = next) 
 { 
 // next向前推进。 
 next = (TreeNode<K, V>) x.next; 
 x.left = x.right = null; 
 // 为树根节点赋值。 
 if (root == null) 
 { 
 x.parent = null; 
 x.red = false; 
 root = x; 
 } else 
 { 
 // x即为当前访问链表中的项。 
 K k = x.key; 
 int h = x.hash; 
 Class<?> kc = null; 
 // 此时红黑树已经有了根节点，上面获取了当前加入红黑树的项的key和hash值进入核心循环。 
 // 这里从root开始，是以一个自顶向下的方式遍历添加。 
 // for循环没有控制条件，由代码内break跳出循环。 
 for (TreeNode<K, V> p = root;;) 
 { 
 // dir：directory，比较添加项与当前树中访问节点的hash值判断加入项的路径，-1为左子树，+1为右子树。 
 // ph：parent hash。 
 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); 
 // xp：x parent。 
 TreeNode<K, V> xp = p; 
 // 找到符合x添加条件的节点。 
 if ((p = (dir <= 0) ? p.left : p.right) == null) 
 { 
 x.parent = xp; 
 // 如果xp的hash值大于x的hash值，将x添加在xp的左边。 
 if (dir <= 0) 
 xp.left = x; 
 // 反之添加在xp的右边。 
 else 
 xp.right = x; 
 // 维护添加后红黑树的红黑结构。 
 root = balanceInsertion(root, x); 
  
 // 跳出循环当前链表中的项成功的添加到了红黑树中。 
 break; 
 } 
 } 
 } 
 } 
 // Ensures that the given root is the first node of its bin，自己翻译一下。 
 moveRootToFront(tab, root); 
 } 

第一次循环会将链表中的首节点作为红黑树的根，而后的循环会将链表中的的项通过比较hash值然后连接到相应树节点的左边或者右边，插入可能会破坏树的结构所以接着执行balanceInsertion。

（编辑：ASP站长网）