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

现在知道为什么XPPP可以是任意颜色的了吧，因为旋转过后X是黑色的即便XPPP是红色，此时我们又可以对两个红色的子节点进行颜色变换了，变换后X和XPPP有发生了颜色冲突，接着进行旋转直到根。

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)) 
 { 
 // 插入位置父节点在祖父节点的左边。 
 } 
 else 
 { 
 // 插入位置父节点在祖父节点的右边。 
 } 
 } 
 } 

我们值分析了插入位置父节点在祖父节点的左边的情况，并没有分析另外一面的对称情况，其实是一样的因为调用的都是相同的方法。

以上就是在1.8中的HashMap新引进的红黑树树化的过程，与原来的链表相比当同一个bucket上存储很多entry的话树形的查找结构明显要比链表线性的的效率要高。

（编辑：核心网）

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