3分钟让你大白：HashMap之红黑树树化进程

我们看一下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。

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!