谈谈JDK1.8的TreeMap实现原理

冷不防 2023-01-07 05:56 116阅读 0赞

TreeMap的实现是红黑树算法，要了解TreeMap实现还需要先了解红黑树。

# 红黑树简介 #

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

**红黑树的特性**（红黑树的时间复杂度为: O(lgn)）：

*  **每个节点或者是黑色，或者是红色。**
 *  **根节点是黑色。**
 *  **每个叶子节点（NIL）是黑色。 \[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！\]**
 *  **如果一个节点是红色的，则它的子节点必须是黑色的。如果一个节点是黑色的，则它的子节点可能是红色的，也可能是黑色的**
 *  **从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。**
 *  **新增加点都为红色**

红黑树示意图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDM3NDc4_size_16_color_FFFFFF_t_70][]

#  红黑树的基本操作：左旋、右旋 #

红黑树的基本操作是**新增**、**删除**。而进行新增删除操作可能会改变红黑树结构（有可能不满足红黑树的特性），这个时候就需要通过**旋转（左旋、右旋）**来转变为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。

<table> 
 <tbody> 
  <tr> 
   <td style="width:39px;"> <h3>左旋</h3> </td> 
   <td style="width:254px;"><img alt="" height="128" src="https://img-blog.csdnimg.cn/img_convert/a1090f8cf6445fa0d1cfa50ab4bd2928.png" width="233"></td> 
   <td style="width:462px;"> <p><strong>旋转说明：</strong></p> <p><code>前提：这里假设x的右孩子为y。下面开始正式操作<br> 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子<br> 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x</code></p> <p><code>将 “x的父亲” 设为 “y的父亲”<br> 情况1：如果 “x的父亲” 是空节点，则将y设为根节点<br> 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”<br> 情况3：如果 x是它父节点的右孩子，&nbsp;将y设为“x的父节点的右孩子”</code></p> </td> 
   <td style="width:40px;"> <h3>右旋</h3> </td> 
   <td style="width:294px;"><img alt="" height="152" src="https://img-blog.csdnimg.cn/img_convert/5a6bd6da95b5f76c23f07dc6be1304d3.png" width="277"></td> 
   <td style="width:469px;"> <p>&nbsp;<strong>旋转说明：</strong></p> <p><code>前提：这里假设y的左孩子为x。下面开始正式操作<br> 将 “x的右孩子” 设为 “y的左孩子”，即 将β设为y的左孩子<br> 将 “y” 设为 “x的右孩子的父亲”，即 将β的父亲设为y<br> 将 “y的父亲” 设为 “x的父亲”<br> 情况1：如果 “y的父亲” 是空节点，则将x设为根节点<br> 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子”<br> 情况3：如果 y是它父节点的左孩子，则将x设为“y的父节点的左孩子”</code></p> </td> 
  </tr> 
  <tr> 
   <td colspan="6">总结：左旋 和 右旋 是相对的两个概念，原理类似。理解一个也就理解了另一个。</td> 
  </tr> 
 </tbody> 
</table>

# TreeMap put()方法实现分析 #

**       **在TreeMap的put()的实现方法中主要分为两个步骤，第一：构建排序二叉树，第二：平衡二叉树。

对于排序二叉树的创建，其添加节点的过程如下：

**       **1、以根节点为初始节点进行检索。

**       **2、与当前节点进行比对，若新增节点值较大，则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。

**       **3、循环递归2步骤知道检索出合适的叶子节点为止。

**       **4、将新增节点与3步骤中找到的节点进行比对，如果新增节点较大，则添加为右子节点；否则添加为左子节点。

按照以上规则就能把节点放在最合适的位置，源码实现如下：

public V put(K key, V value) {  
               //用t表示二叉树的当前节点  
                Entry<K,V> t = root;  
                //t为null表示一个空树，即TreeMap中没有任何元素，直接插入  
                if (t == null) {  
                    //比较key值，个人觉得这句代码没有任何意义，空树还需要比较、排序？  
                    compare(key, key); // type (and possibly null) check  
                    //将新的key-value键值对创建为一个Entry节点，并将该节点赋予给root  
                    root = new Entry<>(key, value, null);  
                    //容器的size = 1，表示TreeMap集合中存在一个元素  
                    size = 1;  
                    //修改次数 + 1  
                    modCount++;  
                    return null;  
                }  
                int cmp;     //cmp表示key排序的返回结果  
                Entry<K,V> parent;   //父节点  
                // split comparator and comparable paths  
                Comparator<? super K> cpr = comparator;    //指定的排序算法  
                //如果cpr不为空，则采用既定的排序算法进行创建TreeMap集合  
                // 该判断主要是为了循环找出当前子节点存放位置的父节点
                if (cpr != null) {  
                    do {  
                        parent = t;      //parent指向上次循环后的t  
                        //比较新增节点的key和当前节点key的大小  
                        cmp = cpr.compare(key, t.key);  
                        //cmp返回值小于0，表示新增节点的key小于当前节点的key，则以当前节点的左子节点作为新的当前节点  
                        if (cmp < 0)  
                            t = t.left;  
                        //cmp返回值大于0，表示新增节点的key大于当前节点的key，则以当前节点的右子节点作为新的当前节点  
                        else if (cmp > 0)  
                            t = t.right;  
                        //cmp返回值等于0，表示两个key值相等，则新值覆盖旧值，并返回新值  
                        else  
                            return t.setValue(value);  
                    } while (t != null);  
                }  
                //如果cpr为空，则采用默认的排序算法进行创建TreeMap集合  
                else {  
                    if (key == null)     //key值为空抛出异常  
                        throw new NullPointerException();  
                    /* 下面处理过程和上面一样 */  
                    Comparable<? super K> k = (Comparable<? super K>) key;  
                    do {  
                        parent = t;  
                        cmp = k.compareTo(t.key);  
                        if (cmp < 0)  
                            t = t.left;  
                        else if (cmp > 0)  
                            t = t.right;  
                        else  
                            return t.setValue(value);  
                    } while (t != null);  
                }  
                //将新增节点当做parent的子节点  
                Entry<K,V> e = new Entry<>(key, value, parent);  
                //如果新增节点的key小于parent的key，则当做左子节点  
                if (cmp < 0)  
                    parent.left = e;  
              //如果新增节点的key大于parent的key，则当做右子节点  
                else  
                    parent.right = e;  
                /*  
                 *  上面已经完成了排序二叉树的的构建，将新增节点插入该树中的合适位置  
                 *  下面fixAfterInsertion()方法就是对这棵树进行调整、平衡，具体过程参考上面的五种情况  
                 */  
                fixAfterInsertion(e);  
                //TreeMap元素数量 + 1  
                size++;  
                //TreeMap容器修改次数 + 1  
                modCount++;  
                return null;  
            }

以上算法就是实现排序二叉树的排序算法，但是排序二叉树有可能出现不平衡的情况，会导致查询复杂的为O(N)，所以我们还需要跳转为一个平衡二叉树（红黑树），平衡可能需要左旋，右旋，着色等操作。

排序算法内容在 **fixAfterInsertion(e); ** 里，我们进一步分析：

private void fixAfterInsertion(Entry<K,V> x) {  
                x.color = RED;    //新增节点的颜色为红色  
      
                //循环 直到 x不是根节点，且x的父节点不为红色  
                while (x != null && x != root && x.parent.color == RED) {  
                    //如果X的父节点（P）是其父节点的父节点（G）的左节点  
                    if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {  
                        //获取X的叔节点(U)  
                        Entry<K,V> y = rightOf(parentOf(parentOf(x)));  
                        //如果X的叔节点（U） 为红色
                        if (colorOf(y) == RED) {       
                            //将X的父节点（P）设置为黑色  
                            setColor(parentOf(x), BLACK);  
                            //将X的叔节点（U）设置为黑色  
                            setColor(y, BLACK);  
                            //将X的父节点的父节点（G）设置红色  
                            setColor(parentOf(parentOf(x)), RED);  
                            x = parentOf(parentOf(x));  
                        }  
                        //如果X的叔节点（U为黑色）；这里会存在两种情况 
                        else {     
                            //如果X节点为其父节点（P）的右子树，则进行左旋转
                            if (x == rightOf(parentOf(x))) {  
                                //将X的父节点作为X  
                                x = parentOf(x);  
                                //右旋转  
                                rotateLeft(x);  
                            }  
                            //将X的父节点（P）设置为黑色  
                            setColor(parentOf(x), BLACK);  
                            //将X的父节点的父节点（G）设置红色  
                            setColor(parentOf(parentOf(x)), RED);  
                            //以X的父节点的父节点（G）为中心右旋转  
                            rotateRight(parentOf(parentOf(x)));  
                        }  
                    }  
                    //如果X的父节点（P）是其父节点的父节点（G）的右节点  
                    else {  
                        //获取X的叔节点（U）  
                        Entry<K,V> y = leftOf(parentOf(parentOf(x)));  
                      //如果X的叔节点（U） 为红色 
                        if (colorOf(y) == RED) {  
                            //将X的父节点（P）设置为黑色  
                            setColor(parentOf(x), BLACK);  
                            //将X的叔节点（U）设置为黑色  
                            setColor(y, BLACK);  
                            //将X的父节点的父节点（G）设置红色  
                            setColor(parentOf(parentOf(x)), RED);  
                            x = parentOf(parentOf(x));  
                        }  
                      //如果X的叔节点（U为黑色）；这里会存在两种情况
                        else {  
                            //如果X节点为其父节点（P）的左子树，则先进行右旋转  
                            if (x == leftOf(parentOf(x))) {  
                                //将X的父节点作为X  
                                x = parentOf(x);  
                               //右旋转  
                                rotateRight(x);  
                            }  
                            //将X的父节点（P）设置为黑色  
                            setColor(parentOf(x), BLACK);  
                            //将X的父节点的父节点（G）设置红色  
                            setColor(parentOf(parentOf(x)), RED);  
                            //以X的父节点的父节点（G）为中心右旋转  （左旋）
                            rotateLeft(parentOf(parentOf(x)));  
                        }  
                    }  
                }  
                //将根节点G强制设置为黑色  
                root.color = BLACK;  
            }

左旋：rotateLeft()

private void rotateLeft(Entry<K,V> p) {  
            if (p != null) {  
                //获取P的右子节点，其实这里就相当于新增节点N（情况四而言）  
                Entry<K,V> r = p.right;  
                //将R的左子树设置为P的右子树  
                p.right = r.left;  
                //若R的左子树不为空，则将P设置为R左子树的父亲  
                if (r.left != null)  
                    r.left.parent = p;  
                //将P的父亲设置R的父亲  
                r.parent = p.parent;  
                //如果P的父亲为空，则将R设置为跟节点  
                if (p.parent == null)  
                    root = r;  
                //如果P为其父节点（G）的左子树，则将R设置为P父节点(G)左子树  
                else if (p.parent.left == p)  
                    p.parent.left = r;  
                //否则R设置为P的父节点（G）的右子树  
                else  
                    p.parent.right = r;  
                //将P设置为R的左子树  
                r.left = p;  
                //将R设置为P的父节点  
                p.parent = r;  
            }  
        }

右旋：rotateRight()

private void rotateRight(Entry<K,V> p) {  
            if (p != null) {  
                //将L设置为P的左子树  
                Entry<K,V> l = p.left;  
                //将L的右子树设置为P的左子树  
                p.left = l.right;  
                //若L的右子树不为空，则将P设置L的右子树的父节点  
                if (l.right != null)   
                    l.right.parent = p;  
                //将P的父节点设置为L的父节点  
                l.parent = p.parent;  
                //如果P的父节点为空，则将L设置根节点  
                if (p.parent == null)  
                    root = l;  
                //若P为其父节点的右子树，则将L设置为P的父节点的右子树  
                else if (p.parent.right == p)  
                    p.parent.right = l;  
                //否则将L设置为P的父节点的左子树  
                else   
                    p.parent.left = l;  
                //将P设置为L的右子树  
                l.right = p;  
                //将L设置为P的父节点  
                p.parent = l;  
            }  
        }

着色：setColor()

private static <K,V> void setColor(Entry<K,V> p, boolean c) {  
            if (p != null)  
                p.color = c;  
        }

左旋、右旋的示意图如下：

![SouthEast][]![SouthEast 1][]

左旋                                                          右旋

# TreeMap delete()方法 #

**红黑树节点删除**

针对于红黑树的增加节点而言，删除显得更加复杂，使原本就复杂的红黑树变得更加复杂。同时删除节点和增加节点一样，同样是找到删除的节点，删除之后调整红黑树。但是这里的删除节点并不是直接删除，而是通过走了“弯路”通过一种捷径来删除的：**找到被删除的节点D的子节点C，用C来替代D，不是直接删除D，因为D被C替代了，直接删除C即可。**所以这里就将删除父节点D的事情转变为了删除子节点C的事情，这样处理就将复杂的删除事件简单化了。**子节点C的规则是：右分支最左边，或者 左分支最右边的。**

![SouthEast 2][]

**      **红黑树删除节点同样会分成几种情况，这里是按照待删除节点有几个儿子的情况来进行分类：

**       **1、没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。

**       **2、只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。

**       **3、有两个儿子。这种情况比较复杂，但还是比较简单。上面提到过用子节点C替代代替待删除节点D，然后删除子节点C即可。

通过上面的分析，我们已经初步了解了红黑树的删除节点情况，相对于增加节点而言它确实是选的较为复杂。下面我将看到在Java TreeMap中是如何实现红黑树删除的。

public V remove(Object key) {
            Entry<K,V> p = getEntry(key);// 获取该当前要删除的节点信息
            if (p == null)
                return null;
    
            V oldValue = p.value; // 记录当前节点值
            deleteEntry(p); //具体删除逻辑 
            return oldValue;
        }

**deleteEntry()方法实现**

private void deleteEntry(Entry<K,V> p) {
            modCount++;  // 修改次数+1
            size--;  // 元素个数-1
            
            // 如果当前节点有左子树跟右子树
            if (p.left != null && p.right != null) {
                // 查找p的替代节点，规则为当前节点的右节点的最左边或左节点的最右边
                Entry<K,V> s = successor(p);
                // 替换p节点
                p.key = s.key;
                p.value = s.value;
                p = s;
            } // p has 2 children
    
            // replacement为替代节点，如果P的左子树存在那么就用左子树替代，否则用右子树替代 
            Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    
            // 如果替代节点存在
            if (replacement != null) {
                // 
                replacement.parent = p.parent;
                //若P没有父节点，则根节点直接变成replacement  
                if (p.parent == null)
                    root = replacement;
                //如果P为左节点，则用replacement来替代为左节点  
                else if (p == p.parent.left)
                    p.parent.left  = replacement;
                //如果P为右节点，则用replacement来替代为右节点  
                else
                    p.parent.right = replacement;
    
                //同时将P节点从这棵树中剔除掉  
                p.left = p.right = p.parent = null;
    
                /* 
                 * 若P为红色直接删除，红黑树保持平衡 
                 * 但是若P为黑色，则需要调整红黑树使其保持平衡 
                 */   
                if (p.color == BLACK)
                    fixAfterDeletion(replacement);
            } 
              // p没有子节点，
              // 如果p没有父节点，表示为P根节点，直接删除即可  
              else if (p.parent == null) { 
                root = null;
            } 
              // 如果p没有子节点，说明是叶子节点
              else {
                // 如果当前节点颜色为黑色
                if (p.color == BLACK)
                    fixAfterDeletion(p);
                // 如果当前节点父节点不为null
                if (p.parent != null) {
                    // 如果当前节点是其父节点的左子树，将左子树直接置为null（删除）
                    if (p == p.parent.left)
                        p.parent.left = null;
                    // 如果当前节点是其父节点的右子树，将右子树直接置为null（删除）
                    else if (p == p.parent.right)
                        p.parent.right = null;
                    p.parent = null;
                }
            }
        }

如果当前节点为黑色，调用fixAfterDeletion()方法实现

private void fixAfterDeletion(Entry<K,V> x) {
            // 删除节点需要一直迭代，直到 x 不是根节点，且 x 的颜色是黑色
            while (x != root && colorOf(x) == BLACK) {
                if (x == leftOf(parentOf(x))) {
                    // 获取当前节点的兄弟节点（父节点的右节点）
                    Entry<K,V> sib = rightOf(parentOf(x));
    
                    // 如果sib节点为红色，则交换当前节点的父节点跟sib节点颜色，并进行一次左旋
                    if (colorOf(sib) == RED) {
                        setColor(sib, BLACK);
                        setColor(parentOf(x), RED);
                        rotateLeft(parentOf(x));
                        sib = rightOf(parentOf(x));
                    }
                    /* 
                     * 若兄弟节点的两个子节点都为黑色 
                     * 策略：将兄弟节点变成红色 
                     */  
                    if (colorOf(leftOf(sib))  == BLACK &&
                        colorOf(rightOf(sib)) == BLACK) {
                        setColor(sib, RED);
                        x = parentOf(x);
                    } else {
                        /* 
                         * 如果兄弟节点只有右子树为黑色
                         * 策略：将兄弟节点与其左子树进行颜色互换然后进行右转 
                         */  
                        if (colorOf(rightOf(sib)) == BLACK) {
                            setColor(leftOf(sib), BLACK);
                            setColor(sib, RED);
                            rotateRight(sib);
                            sib = rightOf(parentOf(x));
                        }
                        /* 
                         * 策略：交换兄弟节点和父节点的颜色， 
                         * 同时将兄弟节点右子树设置为黑色，最后左旋转 
                         */  
                        setColor(sib, colorOf(parentOf(x)));
                        setColor(parentOf(x), BLACK);
                        setColor(rightOf(sib), BLACK);
                        rotateLeft(parentOf(x));
                        x = root;
                    }
                } else { // symmetric
                    Entry<K,V> sib = leftOf(parentOf(x));
    
                    if (colorOf(sib) == RED) {
                        setColor(sib, BLACK);
                        setColor(parentOf(x), RED);
                        rotateRight(parentOf(x));
                        sib = leftOf(parentOf(x));
                    }
    
                    if (colorOf(rightOf(sib)) == BLACK &&
                        colorOf(leftOf(sib)) == BLACK) {
                        setColor(sib, RED);
                        x = parentOf(x);
                    } else {
                        if (colorOf(leftOf(sib)) == BLACK) {
                            setColor(rightOf(sib), BLACK);
                            setColor(sib, RED);
                            rotateLeft(sib);
                            sib = leftOf(parentOf(x));
                        }
                        setColor(sib, colorOf(parentOf(x)));
                        setColor(parentOf(x), BLACK);
                        setColor(leftOf(sib), BLACK);
                        rotateRight(parentOf(x));
                        x = root;
                    }
                }
            }
    
            setColor(x, BLACK);
        }

这就是TreeMap的删除源码，其中包括了对红黑树的颜色转换，树的左（右）旋转来保持红黑树的平衡操作，可能直接看逻辑会有点吃力，大家可以打断点一步步看数据结构是怎么变化的，便于理解！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDM3NDc4_size_16_color_FFFFFF_t_70]: /images/20221119/50d0aa1b83e64dd18aac9294fdd12b83.png
[SouthEast]: https://img-blog.csdn.net/20140523091739328?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY2hlbnNzeQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: /images/20221119/2c66011e1cd44cf99f16813111990090.png
[SouthEast 2]: /images/20221119/d99cfc76985d48188ad0b114e0852117.png