源码研究——TreeMap

你的名字 2023-10-08 13:07 63阅读 0赞

继List之后，笔者又开始了Set与Map的源码探究，本次研究HashMap,HashSet,TreeMap,TreeSet。但是点进去后发现，`HashSet`与`TreeSet`点进去后其实就是`HashMap`与`TreeMap`。。。。。。先分析Map再分析Set  
![在这里插入图片描述][7d4cde0f9cf145a3953fccb0a2e3eb4e.png]  
  于是乎，先看TreeMap叭  
  首先让我们点开类图，看看里面的参数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70]

如上图，继承自谁，实现了哪些接口一目了然

> comparator:比较器  
> root:根节点  
> size:集合大小  
> modCount:修改次数

还有一个很重要的，保存 key-value 的 Entry。  
Entry 中包含了 key、value、left、right、parent、color

// 键值对
        static final class Entry<K,V> implements Map.Entry<K,V> {
        
            K key; // key 值
            V value; // value 值
            java.util.TreeMap.Entry<K,V> left;  // 左边子的节点
            java.util.TreeMap.Entry<K,V> right; // 右边子的节点
            java.util.TreeMap.Entry<K,V> parent; // 父节点
            boolean color = BLACK; // 默认节点颜色 黑
    
            // 初始化 Entry
            Entry(K key, V value, java.util.TreeMap.Entry<K,V> parent) {
        
                this.key = key;
                this.value = value;
                this.parent = parent;
            }
    
            public K getKey() {
        
                return key;
            }
    
            public V getValue() {
        
                return value;
            }
    
            public V setValue(V value) {
        
                V oldValue = this.value;
                this.value = value;
                return oldValue;
            }
    
            public boolean equals(Object o) {
        
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    
                return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
            }
    
            public int hashCode() {
        
                int keyHash = (key==null ? 0 : key.hashCode());
                int valueHash = (value==null ? 0 : value.hashCode());
                return keyHash ^ valueHash;
            }
    
            public String toString() {
        
                return key + "=" + value;
            }
        }

里面方法不少，我们还是像分析List时一样，从创建和增删开始

#### TreeMap的构造方法 ####

4个构造方法：  
构造方法一：  
1、默认构造方法会创建一颗空树。  
2、默认使用key的自然顺序来构建有序树，所谓自然顺序，意思是key的类型是什么，就采用该类型的compareTo方法来比较大小，决定顺序。例如key为String类型，就会用String类的compareTo方法比对大小，如果是Integer类型，就用Integer的compareTo方法比对。Java自带的基本数据类型及其装箱类型都实现了Comparable接口的compareTo方法。  
3.要去key必须事实现Comparable接口，以保证key的有序性。

public TreeMap() {
        
            comparator = null;
        }

构造方法二：  
除了用默认比较器，TreeMap还提供了支持外部比较器来初始化构造方法。

public TreeMap(Comparator<? super K> comparator) {
        
            this.comparator = comparator;
        }

构造方法三：  
制定一个Map的TreeMap.

public TreeMap(Map<? extends K, ? extends V> m) {
        
            comparator = null;
            putAll(m);
        }

构造方法四：  
制定一个SortedMap的TreeMap.

public TreeMap(SortedMap<K, ? extends V> m) {
        
            comparator = m.comparator();
            try {
        
                buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
            } catch (java.io.IOException cannotHappen) {
        
            } catch (ClassNotFoundException cannotHappen) {
        
            }
        }

#### put()方法 ####

public V put(K key, V value) {
        
            // 将root赋值给局部变量 t
            Entry<K,V> t = root;//记住这个变量！！！！！！，【每次比较的当前对象】
            if (t == null) {
        //检查根节点是否为空
                // 初始操作
                // 检查key是否为空
                compare(key, key); // type (and possibly null) check
    			// 将要添加的key、 value封装为一个Entry对象 并赋值给root
                root = new Entry<>(key, value, null);
                size = 1;//大小+1
                modCount++;//操作次数+1
                return null;
            }
            int cmp;
            Entry<K,V> parent; // 父节点
            // split comparator and comparable paths
            Comparator<? super K> cpr = comparator; // 获取比较器
            if (cpr != null) {
        //获取到比较器的情况下
                // 一直找到插入节点的父节点
                do {
        //这个循环目的是找到将新节点插到哪个地方
                    // 将root赋值给了parent，从根节点开始比较
                    parent = t;
                    // 和root节点比较值得大小
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0)//t的值比根节点值小
                        // 将根节点的左子节点赋给了t，下一轮比较与此节点进行比较
                        t = t.left;
                    else if (cmp > 0)//t的值比根节点值大
                        t = t.right; // 将父节点的右节点赋给了t，下一轮比较与此节点进行比较
                    else//当没有子节点时①
                        // 直接和父节点的key相等，直接修改值
                        return t.setValue(value);
                } while (t != null);//当没有子节点时②
            }
            else {
        //没获取到比较器,逻辑与获取到时一样
                if (key == null)
                    throw new NullPointerException();
                @SuppressWarnings("unchecked")
                    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);
            }
            // t 就是我们要插入节点的父节点 parent
            // 将我们要插入的key value 封装成了一个Entry对象
            Entry<K,V> e = new Entry<>(key, value, parent);
            if (cmp < 0)
                parent.left = e; // 插入的节点在parent节点的左侧
            else
                parent.right = e; // 插入的节点在parent节点的右侧
            fixAfterInsertion(e); // 实现红黑树的平衡，关键点！
            size++;
            modCount++;
            return null;
        }

每一行代码的意思在已经标明注释了，这里不多说了，重点说下实现红黑树平衡的方法  
`fixAfterInsertion(e);` // 实现红黑树的平衡

> 红黑树还不熟悉的，请看关于红黑树的讲解  
> 链接: [还没写红黑树讲解。。。嘿嘿，我尽快，尽快][Link 1].  
> 请熟读并理解这张图，理解了，红黑树的平衡这个方法看起来就比较容易了，不理解。。。。  
> 那这个方法你看起来估计会看不懂·······  
> ![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70 1]

上代码：

private void fixAfterInsertion(Entry<K,V> x) {
        
        // 设置添加节点的颜色为 红色
        x.color = RED;
    	// 循环的条件 添加的节点不为空  不是root节点  父节点的颜色为红色
        while (x != null && x != root && x.parent.color == RED) {
        
            // 父节点是否是 祖父节点的左侧节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
        
                // 获取父节点的 兄弟节点  叔叔节点
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
         // 叔叔节点是红色
                    // 变色
                    setColor(parentOf(x), BLACK); // 设置 父节点的颜色为黑色
                    setColor(y, BLACK); // 设置叔叔节点的颜色为 黑色
                    setColor(parentOf(parentOf(x)), RED); // 设置 祖父节点的颜色是 红色
                    // 将祖父节点设置为 插入节点
                    x = parentOf(parentOf(x));
                } else {
         // 叔叔节点是黑色
                    if (x == rightOf(parentOf(x))) {
        
                        // 判断插入节点是否是 父节点的右侧节点
                        x = parentOf(x); // 将父节点作为插入节点
                        rotateLeft(x); // 左旋
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));// 右旋
                }
            } else {
        // 父节点是祖父节点的右侧子节点
                // 获取叔叔节点
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
         // 叔叔节点为红色
                    // recolor 变色
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
        
                    // 插入节点在父节点的右侧
                    if (x == leftOf(parentOf(x))) {
        
                        x = parentOf(x);
                        rotateRight(x); // 右旋
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x))); // 左旋
                }
            }
        }
        // 根节点的颜色为黑色
        root.color = BLACK;
    }

左旋右旋的方法：

private void rotateLeft(Entry<K,V> p) {
            对红黑树的节点(x)进行左旋转
            if (p != null) {
        
                Entry<K,V> r = p.right;
                p.right = r.left;
                if (r.left != null)
                    r.left.parent = p;
                r.parent = p.parent;
                if (p.parent == null)
                    root = r;
                else if (p.parent.left == p)
                    p.parent.left = r;
                else
                    p.parent.right = r;
                r.left = p;
                p.parent = r;
            }
        }
    
        /** From CLR */
        private void rotateRight(Entry<K,V> p) {
            对红黑树的节点(x)进行右旋转
            if (p != null) {
        
                Entry<K,V> l = p.left;
                p.left = l.right;
                if (l.right != null) l.right.parent = p;
                l.parent = p.parent;
                if (p.parent == null)
                    root = l;
                else if (p.parent.right == p)
                    p.parent.right = l;
                else p.parent.left = l;
                l.right = p;
                p.parent = l;
            }
        }

#### remove()方法 ####

remove方法要比put更加复杂。从源码来看主要两步：  
先以二叉查找树方式删除节点，然后恢复红黑树性质（平衡）。

public V remove(Object key) {
        
            Entry<K,V> p = getEntry(key);     首先根据key查找到对应的节点对象
            if (p == null)
                return null;
    
            V oldValue = p.value;          记录key对应的value，供返回使用
            deleteEntry(p);           删除节点
            return oldValue;       返回旧结点value
        }

remove通过deleteEntry(方法实现。

private void deleteEntry(Entry<K,V> p) {
        
            modCount++;  改变加1
            size--;       map大小减1
    
            // If strictly internal, copy successor's element to p and then make p
            // point to successor.
            if (p.left != null && p.right != null) {
              情况一：待删除的节点有两个孩子
                Entry<K,V> s = successor(p);       查找p的可替代节点（删除有两个孩子的节点时用到）
                p.key = s.key;
                p.value = s.value;
                p = s;
            } // p has 2 children
    
            // Start fixup at replacement node, if it exists.
            Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    
            if (replacement != null) {
            情况二：待删除的节点仅有一个孩子
                // Link replacement to parent
                replacement.parent = p.parent;
                if (p.parent == null)
                    root = replacement;
                else if (p == p.parent.left)
                    p.parent.left  = replacement;
                else
                    p.parent.right = replacement;
    
                // Null out links so they are OK to use by fixAfterDeletion.
                p.left = p.right = p.parent = null;
    
                // Fix replacement
                if (p.color == BLACK)  情况三：待删除的节点是父节点，直接删除！
                    fixAfterDeletion(replacement);    回复红黑树根据性质
            } else if (p.parent == null) {
         // return if we are the only node.
                root = null;
            } else {
         //  No children. Use self as phantom replacement and unlink.
                if (p.color == BLACK)
                    fixAfterDeletion(p);
    
                if (p.parent != null) {
        
                    if (p == p.parent.left)  情况四：无子节点！
                        p.parent.left = null;
                    else if (p == p.parent.right)
                        p.parent.right = null;
                    p.parent = null;
                }
            }
        }

故TreeMap删除节点remove分四种情况：  
1、树只有根节点：直接删除即可。  
2、待删除节点无孩子：直接删除即可。  
3、待删除节点只有一个孩子节点：删除后，用孩子节点替换自己即可。  
4、待删除节点有两个孩子：删除会复杂点，见下文介绍。（用到前三个方法）

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        
            if (t == null)
                return null;
            else if (t.right != null) {
        
                Entry<K,V> p = t.right;        
                while (p.left != null)   找右子树的最左，即最小节点，用来作替换。。
                    p = p.left;
                return p;
            } else {
        
                Entry<K,V> p = t.parent;
                Entry<K,V> ch = t;
                while (p != null && ch == p.right) {
        
                    ch = p;
                    p = p.parent;
                }
                return p;
            }
        }

查找要删除节点的替代节点。

private void fixAfterInsertion(Entry<K,V> x) {
        
            x.color = RED;
    
            while (x != null && x != root && x.parent.color == RED) {
        
                if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
        
                    Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                    if (colorOf(y) == RED) {
        
                        setColor(parentOf(x), BLACK);
                        setColor(y, BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        x = parentOf(parentOf(x));
                    } else {
        
                        if (x == rightOf(parentOf(x))) {
        
                            x = parentOf(x);
                            rotateLeft(x);
                        }
                        setColor(parentOf(x), BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        rotateRight(parentOf(parentOf(x)));
                    }
                } else {
        
                    Entry<K,V> y = leftOf(parentOf(parentOf(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 = parentOf(x);
                            rotateRight(x);
                        }
                        setColor(parentOf(x), BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        rotateLeft(parentOf(parentOf(x)));
                    }
                }
            }
            root.color = BLACK;
        }

恢复红黑树的性质。  
删除有两个子节点的父节点时：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70 2]  
删除过程：找到节点3右子树中最小的节点2，将3和2节点进行交换，然后删除3节点，3删除后，将原来的4节点变为5节点的子节点。  
如果3节点和2节点被替换后，3节点下仍有两个孩子节点，重复利用上述规则删除即可。这种方式的巧妙之处在于，总是将删除的当前节点向叶子节点方向移动，保证最后没有两个孩子节点时就可以执行真正的删除了，而利用右子树的最小节点与自身交换的动作并不会破坏二叉查找树的任何特性。

#### clear()方法 ####

/**
         * 清除所有元素
         * The map will be empty after this call returns.
         */
        public void clear() {
        
            modCount++;
            size = 0;
            root = null;
        }

#### get()查询方法 ####

public V get(Object key) {
        
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p. value);
    }
    
    final Entry<K,V> getEntry(Object key) {
        
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            // 如果外部比较器为不为空，就用此比较器，用key作为比较器查询
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
       Comparable<? super K> k = (Comparable<? super K>) key;
        // 取得root节点
        Entry<K,V> p = root;
        // 从root节点开始查找，根据比较器判断是在左子树还是右子树
        while (p != null) {
        
            int cmp = k.compareTo(p.key );
            if (cmp < 0)
                p = p. left;
            else if (cmp > 0)
                p = p. right;
            else
                return p;
        }
        return null;
    }
    
    final Entry<K,V> getEntryUsingComparator(Object key) {
        
       K k = (K) key;
        Comparator<? super K> cpr = comparator ;
        if (cpr != null) {
        
            Entry<K,V> p = root;
            while (p != null) {
        
                int cmp = cpr.compare(k, p.key );
                if (cmp < 0)
                    p = p. left;
                else if (cmp > 0)
                    p = p. right;
                else
                    return p;
            }
        }
        return null;
    }

[7d4cde0f9cf145a3953fccb0a2e3eb4e.png]: https://img-blog.csdnimg.cn/7d4cde0f9cf145a3953fccb0a2e3eb4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/8b1db2f33ebc4c33bd09352e00050ba9.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw==,size_16,color_FFFFFF,t_70
[Link 1]: https://www.baidu.com/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/a0b38e41ac1b4f019c6214c53bb9a0e9.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/3f0696ccbf5244e7bd7ab07cacf95800.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw==,size_16,color_FFFFFF,t_70