TreeMap的put之后底层经历了什么（个人经验总结）

「爱情、让人受尽委屈。」 2022-04-12 13:15 224阅读 0赞

**一：TreeMap的实现就是红黑树的实现，红黑树的五点特质：**

1、每个节点都只能是红色或者黑色

2、根节点是黑色

3、每个叶节点（NIL节点，空节点）是黑色的。

4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

**二：以下五种情况涵盖了绝大部分的新增可能，不管这棵红黑树多么复杂，都可以根据这五种情况来进行生成：**

1：若新插入的节点N没有父节点，则直接当做根据节点插入即可，同时将颜色设置为黑色。

![20181203164813157.png][]

2:父节点为黑色(B)，并且新增节点(A)为父节点的左子节点，可以直接插入，也不会打乱红色树的五大特质。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70][]

3若父节点A和叔父节点B都是红色，父节点的父节点C是黑色，这样就不能直接插入了，设置节点A和B为黑色，设置节点C为红色,这样满足条件，但是C节点的父节点或许也是红色，这样以C节点为新增节点，向上进行调整。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 1][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 2][]

4：这种情况多数是由情况三变色，向上调整所出现情况。新增节点为父节点A的左子节点，并且都为红色，新增节点的父节点的父节点C为黑色，叔叔节点B为黑色或者NULL。这样以节点C为中心进行右单旋并着色。相反进行左单旋并着色。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 3][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 5][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 6][]

5：这种情况多数是由情况三变色，向上调整所出现情况。新增节点为父节点A的右子节点，父节点A为父节点的父节点C的左子节点。首先以父节点A为中心经行左单旋，然后以父节点A的父节点C为中心进行右单旋。相反则先以父节点A为中心右旋，然后再以节点C为中心左旋。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 7][]![2018120410420843.png][]![201812041044174.png][]

**三： 当我们使用TreeMap的put方法后：**

1：判断key值是否为空，如果为空，并且没有重写Comparable，就会报出Exception in thread “main” java.lang.NullPointerException  空指针异常

2：首先判断根节点是否为空，如果为空，把key-value创建出一个entry节点对象，并把返回节点对象，

如果不为空，根据key采用排序算法，找到当前节点，构建TreeMap集合。

3 :新增节点的key小于当前节点的key，则以当前节点的左子节点作为新的当前节点,新增节点的key大于当前节点的key，则以当前节点的右子节点作为新的当前节点,相等则覆盖当前节点

4：插入之后根据上面的情况对树进行调整。

源码如下：

public V put(K key, V value) {
        Entry<K,V> t = root;     //红黑树的根节点
        if (t == null) {        //红黑树是否为空
            compare(key, key); // type (and possibly null) check
            //构造根节点，因为根节点没有父节点，传入null值。 
            root = new Entry<>(key, value, null);  
            size = 1;     //size值加1
            modCount++;    //改变修改的次数
            return null;    //返回null 
        }
        int cmp;
        Entry<K,V> parent;    //定义节点
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;     //获取比较器
        if (cpr != null) {      //如果定义了比较器，采用自定义比较器进行比较
            do {
                parent = t;      //将红黑树根节点赋值给parent
                cmp = cpr.compare(key, t.key);     //比较key, 与根节点的大小
                if (cmp < 0)      //如果key < t.key , 指向左子树
                    t = t.left;   //t = t.left  , t == 它的做孩子节点
                else if (cmp > 0)
                    t = t.right;  //如果key > t.key , 指向它的右孩子节点
                else
                    return t.setValue(value);      //如果它们相等，替换key的值
            } while (t != null);        //循环遍历
        }
        else {
            //自然排序方式，没有指定比较器
            if (key == null)
                throw new NullPointerException();  //抛出异常
            Comparable<? super K> k = (Comparable<? super K>) key;    //类型转换
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)     // key < t.key 
                    t = t.left;   //左孩子
                else if (cmp > 0)   // key > t.key 
                    t = t.right;    //右孩子
                else
                    return t.setValue(value);   //t == t.key , 替换value值
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);   //创建新节点，并制定父节点
        //根据比较结果，决定新节点为父节点的左孩子或者右孩子
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);   //新插入节点后重新调整红黑树 
        size++;
        modCount++;
        return null;
    }
    //比较方法，如果comparator==null ,采用comparable.compartTo进行比较，否则采用指定比较器比较大小
    final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }
    
    private void fixAfterInsertion(Entry<K,V> x) {
        //插入的节点默认的颜色为红色
        x.color = RED;    //
        //情形1： 新节点x 是树的根节点，没有父节点不需要任何操作
        //情形2： 新节点x 的父节点颜色是黑色的，也不需要任何操作
    
        while (x != null && x != root && x.parent.color == RED) {
        //情形3：新节点x的父节点颜色是红色的
        //判断x的节点的父节点位置，是否属于左孩子
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
              //获取x节点的父节点的兄弟节点，上面语句已经判断出x节点的父节点为左孩子，所以直接取右孩子
             Entry<K,V> y = rightOf(parentOf(parentOf(x)));
             //判断是否x节点的父节点的兄弟节点为红色。
             if (colorOf(y) == RED) {
                  setColor(parentOf(x), BLACK); // x节点的父节点设置为黑色
                  setColor(y, BLACK);           // y节点的颜色设置为黑色
                  setColor(parentOf(parentOf(x)), RED); // x.parent.parent设置为红色
                  x = parentOf(parentOf(x)); // x == x.parent.parent ,进行遍历。
             } else {
                   //x的父节点的兄弟节点是黑色或者缺少的
                   if (x == rightOf(parentOf(x))) {   //判断x节点是否为父节点的右孩子
                        x = parentOf(x);     //x == 父节点
                        rotateLeft(x);    //左旋转操作
                   }
                   //x节点是其父的左孩子
                   setColor(parentOf(x), BLACK);
                   setColor(parentOf(parentOf(x)), RED);  //上面两句将x.parent 和x.parent.parent的颜色做调换
                   rotateRight(parentOf(parentOf(x)));   //进行右旋转
                }
            } else {
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));  //y 是x 节点的祖父节点的左孩子
                if (colorOf(y) == RED) {    //判断颜色
                    setColor(parentOf(x), BLACK);    //父节点设置为黑色
                    setColor(y, BLACK);         //父节点的兄弟节点设置为黑色
                    setColor(parentOf(parentOf(x)), RED);   //祖父节点设置为红色
                    x = parentOf(parentOf(x));   //将祖父节点作为新插入的节点，遍历调整
                } else {
                    if (x == leftOf(parentOf(x))) {     //x 是其父亲的左孩子
                        x = parentOf(x);
                        rotateRight(x);    //以父节点为旋转点，进行右旋操作
                    }
                    setColor(parentOf(x), BLACK);    //父节点为设置为黑色
                    setColor(parentOf(parentOf(x)), RED);  //祖父节点设置为红色
                    rotateLeft(parentOf(parentOf(x)));  //以父节点为旋转点，进行左旋操作
                }
            }
        }
        root.color = BLACK; //通过节点位置的调整，最终将红色的节点条调换到了根节点的位置，根节点重新设置为黑色
    }

[20181203164813157.png]: /images/20220412/570f9a771aa244999184ae3b881e0ae8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70]: /images/20220412/7bac2f514fc34efc8b339c902ab07fc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20181204091341453.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 2]: /images/20220412/5861b2d62fb8415fbdfae04ee70de400.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2018120410082588.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 4]: /images/20220412/956e864f268e45b096337582fe74ddfd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20181204101515608.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 6]: /images/20220412/f45e9a41a51b438bb7144ab346115f02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20181204103825764.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDU3MDMz,size_16,color_FFFFFF,t_70
[2018120410420843.png]: https://img-blog.csdnimg.cn/2018120410420843.png
[201812041044174.png]: /images/20220412/49de19ea11ce4942bfefc4a057fe5943.png