HashMap源码分析JDK8：balanceInsertion方法

蔚落 2023-06-24 04:53 79阅读 0赞

**一、插入的所有情况**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70]  
**二、源码**

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {
        
                //新插入树节点默认红色                                        
                x.red = true;
                //x是新插入节点、xp是新插入节点的父节点、xpp是新插入节点的祖父节点、
                //xppl是新插入节点的左叔叔节点、xppr是新插入节点的右叔叔节点
                for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        
                	//1.空树
                    if ((xp = x.parent) == null) {
        
                    	//新插入节点颜色变为黑色
                        x.red = false;
                        return x;
                    }
                    //2.父节点黑色或祖父节点为空
                    else if (!xp.red || (xpp = xp.parent) == null)
                        return root;
                    //3.父节点红色
                    //3.1父节点是祖父节点的左儿子
                    if (xp == (xppl = xpp.left)) {
        
                    	//3.1.1叔叔节点红色
                        if ((xppr = xpp.right) != null && xppr.red) {
        
                            xppr.red = false;
                            xp.red = false;
                            xpp.red = true;
                            x = xpp;
                        }
                        //3.1.2叔叔节点不存在
                        else {
        
                        	//3.1.2.1新插入节点是父节点右儿子
                            if (x == xp.right) {
        
                            	//左旋
                                root = rotateLeft(root, x = xp);
                                xpp = (xp = x.parent) == null ? null : xp.parent;
                            }
                            //3.1.2.2新插入节点是父节点左儿子
                            if (xp != null) {
        
                                xp.red = false;
                                if (xpp != null) {
        
                                    xpp.red = true;
                                    //右旋
                                    root = rotateRight(root, xpp);
                                }
                            }
                        }
                    }
                    //3.2父节点是祖父节点右儿子
                    else {
        
                    	//3.2.1叔叔节点红色
                        if (xppl != null && xppl.red) {
        
                            xppl.red = false;
                            xp.red = false;
                            xpp.red = true;
                            x = xpp;
                        }
                        //3.2.2叔叔节点不存在
                        else {
        
                        	//3.2.2.1新插入节点是父节点左儿子
                            if (x == xp.left) {
        
                            	//右旋
                                root = rotateRight(root, x = xp);
                                xpp = (xp = x.parent) == null ? null : xp.parent;
                            }
                            //3.2.2.2新插入节点是父节点右儿子
                            if (xp != null) {
        
                                xp.red = false;
                                if (xpp != null) {
        
                                    xpp.red = true;
                                    //左旋
                                    root = rotateLeft(root, xpp);
                                }
                            }
                        }
                    }
                }
            }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191122150104576.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg==,size_16,color_FFFFFF,t_70