TreeMap源码解析

￡神魔★判官ぃ 2023-06-15 07:23 43阅读 0赞

#### 前言 ####

1.  TreeMap实现了SotredMap接口，它是有序的集合。而且由红黑树实现的，每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器，则根据key执行自然排序。
2.  红黑树：  
    红黑树是二叉树的一种优化，保留了二叉树的特性包含一个根节点和两个子节点，其中 【左子节点 < 根节点 < 右子节点】，又增加了每个节点的颜色红和黑，通过二叉树的左右旋转保证其接近最优二叉树。想要了解更多红黑树的知识，可以看一下下面的博文：
    
    1.  教你初步了解红黑树： [https://blog.csdn.net/v\_JULY\_v/article/details/6105630][https_blog.csdn.net_v_JULY_v_article_details_6105630]
    2.  红黑树算法的实现与剖析： [https://blog.csdn.net/v\_JULY\_v/article/details/6109153][https_blog.csdn.net_v_JULY_v_article_details_6109153]
    3.  红黑树模拟网站：[ https://www.cs.usfca.edu/~galles/visualization/RedBlack.html][https_www.cs.usfca.edu_galles_visualization_RedBlack.html]
    4.  根据红黑树模拟网站，生成的一个简单的红黑树示意图：  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1_size_16_color_FFFFFF_t_70]

#### TreeMap简单示例： ####

public class Test { 
    
        public static void main(String[] args) throws ParseException { 
            Map treeMap =  new TreeMap<Integer,String>();
            treeMap.put(1,"11");
            treeMap.put(2,"22");
            treeMap.put(3,"33");
            treeMap.put(4,"44");
    
            Iterator iter = treeMap.entrySet().iterator();
            while(iter.hasNext()) { 
                Map.Entry entry = (Map.Entry)iter.next();
                System.out.println("key = "+entry.getKey()+ ";value = " + entry.getValue());
            }
        }
    }

打印结果：

key = 1;value = 11
    key = 2;value = 22
    key = 3;value = 33
    key = 4;value = 44

#### TreeMap参数定义 和 初始化方法： ####

1.  我们先开看一下 TreeMap 参数定义， 比较重要的有有三个：  
    comparator： 对比器，对比key之间的大小。  
    root：根节点，整个红黑树的根，例如上面的图 d 节点就是根节点  
    size：集合大小
2.  TreeMap 的初始化方法也有三个：  
    TreeMap()：其中comparator=null，在实际运用中会取 key 中定义的 comparator ，例如String类型中就内置了 CaseInsensitiveComparator 作为 Comparator 的实现类。  
    TreeMap(Comparator<? super K> comparator)：带有对比器的初始化方法。  
    TreeMap(SortedMap<K, ? extends V> m)： 带有集合m 的初始化方法，沿用m的对比器, 并将m中键值对放入到TreeMap中

public class TreeMap<K,V>
            extends AbstractMap<K,V>
            implements NavigableMap<K,V>, Cloneable, java.io.Serializable
    { 
        // 对比器
        private final Comparator<? super K> comparator;
    
        // 根节点
        private transient java.util.TreeMap.Entry<K,V> root;
    
        // 集合大小
        private transient int size = 0;
    
        // 对树进行结构修改的次数。
        private transient int modCount = 0;
    
        // 初始化
        public TreeMap() { 
            comparator = null;
        }
    
        // 带有 对比器 的初始化
        public TreeMap(Comparator<? super K> comparator) { 
            this.comparator = comparator;
        }
    
        // 初始化 并将 m 全部放置到 TreeMap 中
        public TreeMap(Map<? extends K, ? extends V> m) { 
            comparator = null;
            putAll(m);
        }
    	..... 
    }

#### TreeMap 中保存 key-value 的 Entry ####

1.  Entry 中包含了 key、value、left、right、parent、color  
    left：表示当前节点的左子节点  
    right：表示当前节点的右子节点  
    parent： 自己的父节点
2.  代码如下：

// 键值对
        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;
            }
        }

#### put 方法 ####

TreeMap 中定义了很多方法，其中最关键的是 put(K key, V value) 方法，该方法将 key-value 包装成了一个 Entry，并通过 Comparator 在红黑树中找到指定的位置将其放置其中，最后通过 fixAfterInsertion 实现红黑树的修复，完成新增操作，下面看源码：

// 添加一个数据
        public V put(K key, V value) { 
            // 获取到红黑树的根节点
            java.util.TreeMap.Entry<K,V> t = root;
            // 根节点为null, TreeMap中没有任何数据
            if (t == null) { 
                // 类型检查（可能为空）
                compare(key, key);
                // 将当前的 key,value 生成根节点Entry
                root = new java.util.TreeMap.Entry<>(key, value, null);
                size = 1;
                // 操作次数 +1
                modCount++;
                return null;
            }
            int cmp;
            // 定义父节点
            java.util.TreeMap.Entry<K,V> parent;
            // 比较器
            Comparator<? super K> cpr = comparator;
            // 用户传入的比较器不为空
            if (cpr != null) { 
                // 循环查找 key在二叉树对应的位置【即找到一个父节点】
                do { 
                    parent = t;
                    // key与当前节点的key进行对比
                    cmp = cpr.compare(key, t.key);
                    // cmp < 0 找到当前节点的左子节点再去对比
                    if (cmp < 0)
                        t = t.left;
                    // cmp > 0 找到当前节点的右子节点再去对比
                    else if (cmp > 0)
                        t = t.right;
                    // cmp = 0 当前节点即是key的节点，用Value值替换掉旧值
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            // 使用 key 数据类型中默认的比较器，后面逻辑相同
            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);
            }
            // 上面的代码如果直接return了表示。TreeMap中原来存在 key=参数key的节点，直接覆盖返回
    
            // 下面的代码表示红黑树中不存在Key，需要为其创建节点， parent上面循环得到的二叉树的叶子及诶到哪
            java.util.TreeMap.Entry<K,V> e = new java.util.TreeMap.Entry<>(key, value, parent);
    
            // cmp < 0 表示当前key生成的Entry是parent的左节点
            if (cmp < 0)
                parent.left = e;
            // cmp > 0 表示当前key生成的Entry是parent的右节点
            else
                parent.right = e;
            // 插入新的节点后，红黑树进行修复【节点颜色变化,左右旋等】，保证其扔就满足红黑树的特性
            fixAfterInsertion(e);
            size++;
            modCount++;
            return null;
        }
    	
    	**
         * 插入节点后，红黑树进行自我修复，保证其仍然满足红黑树的要求
         * 由于技术有限，暂时没有进行解读
         * @param x
         */
        private void fixAfterInsertion(java.util.TreeMap.Entry<K,V> x) { 
            x.color = RED;
    
            while (x != null && x != root && x.parent.color == RED) { 
                if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 
                    java.util.TreeMap.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 { 
                    java.util.TreeMap.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;
        }

如果大家了解二叉树的话【要是懂得红黑树，就更完美了】，上面 put 方法也很容易理解了，每一行代码的意思在已经标明注释了，这里不多说了。关于方法最后 fixAfterInsertion 调整红黑树结构的方法，由于本人对红黑树理解不够透彻，也就没有解读。

#### get 方法 ####

不论是 get 还是 put 方法，都是通过根节点 和 Comparable 对红黑树进行查找，最后实现功能，代码如下：

// 通过 key 获取到Value的值
        public V get(Object key) { 
            java.util.TreeMap.Entry<K,V> p = getEntry(key);
            return (p==null ? null : p.value);
        }
    	
    	// 跟 key 值找到对应的 Entry
        final java.util.TreeMap.Entry<K,V> getEntry(Object key) { 
            // Offload comparator-based version for sake of performance
            if (comparator != null)
                return getEntryUsingComparator(key);
            // TreeMap 中key 不可以为空
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
            // 得到TreeMap 中红黑树的 根节点
            java.util.TreeMap.Entry<K,V> p = root;
            // 循环遍历
            while (p != null) { 
                // key和当前节点的key比较
                int cmp = k.compareTo(p.key);
                // 根据二叉树的原理，
                // cmp < 0 找左节点
                if (cmp < 0)
                    p = p.left;
                // cmp > 0 找右节点
                else if (cmp > 0)
                    p = p.right;
                // 当前节点就是要查找的节点
                else
                    return p;
            }
            return null;
        }

#### TreeMap 中的 comparator 介绍： ####

1.  我们通过上面的 put 和 get 方法，我们发现 comparator 在其中起到了查询导向的作用，那么 comparator 究竟是怎么实现的，我们先来看一下 Comparator 接口：

public interface Comparator<T> { 
        /** * 比较对象 * @param o1 * @param o2 * @return */
        int compare(T o1, T o2);
    }

我们在实际工作中可以编写一个实现类，实现Comparator 并完成 compare 接口，例如我们实现一个Integer 倒序的 TreeMap：

public class Test { 
    
        public static void main(String[] args) throws ParseException { 
            Map treeMap =  new TreeMap<String,String>(new IntegerComparator());
            treeMap.put(1,"11");
            treeMap.put(2,"22");
            treeMap.put(3,"33");
            treeMap.put(4,"44");
            Iterator iter = treeMap.entrySet().iterator();
            while(iter.hasNext()) { 
                Map.Entry entry = (Map.Entry)iter.next();
                System.out.println("key = "+entry.getKey()+ ";value = " + entry.getValue());
            }
        }
    }
    
    class IntegerComparator implements Comparator{ 
    
        @Override
        public int compare(Object o1, Object o2) { 
            return -((Integer) o1 - (Integer)o2);
        }
    }

打印结果：

key = 4;value = 44
    key = 3;value = 33
    key = 2;value = 22
    key = 1;value = 11

#### TreeMap的遍历方式： ####

1.  第一种：根据entrySet()获取TreeMap的“键值对”的Set集合 【推荐】
2.  第二种: 根据keySet()获取TreeMap的“键”的Set集合, 然后再根据key取得Value值 【不推荐】
3.  第三种: 根据value()获取TreeMap的“值”的集合。

代码示例如下：

public class Test { 
    
        public static void main(String[] args) throws ParseException { 
            Map treeMap =  new TreeMap<Integer,String>(new IntegerComparator());
            treeMap.put(1,"11");
            treeMap.put(2,"22");
            treeMap.put(3,"33");
            treeMap.put(4,"44");
    
            System.out.println(" 第一种：根据entrySet()获取TreeMap的“键值对”的Set集合 【推荐】 ");
            Iterator iter1 = treeMap.entrySet().iterator();
            while(iter1.hasNext()) { 
                Map.Entry entry = (Map.Entry)iter1.next();
                System.out.println("key = "+entry.getKey()+ ";value = " + entry.getValue());
            }
    
            System.out.println(" 第二种: 根据keySet()获取TreeMap的“键”的Set集合, 然后再根据key取得Value值 【不推荐，因为会遍历两次Map】 ");
            Integer key = null;
            Iterator iter2 = treeMap.keySet().iterator();
            while(iter2.hasNext()) { 
                key = (Integer) iter2.next();
                System.out.println("key = "+key+ ";value = " + treeMap.get(key));
            }
    
            System.out.println(" 第三种: 根据value()获取TreeMap的“值”的集合。 ");
            String value = null;
            Iterator iter3 = treeMap.values().iterator();
            while(iter3.hasNext()) { 
                value = (String) iter3.next();
                System.out.println( "value = " + value);
            }
        }
    }
    
    class IntegerComparator implements Comparator{ 
    
        @Override
        public int compare(Object o1, Object o2) { 
            return -((Integer) o1 - (Integer)o2);
        }
    }

打印结果：

第一种：根据entrySet()获取TreeMap的“键值对”的Set集合 【推荐】 
    key = 4;value = 44
    key = 3;value = 33
    key = 2;value = 22
    key = 1;value = 11
     第二种: 根据keySet()获取TreeMap的“键”的Set集合, 然后再根据key取得Value值 【不推荐，因为会遍历两次Map】 
    key = 4;value = 44
    key = 3;value = 33
    key = 2;value = 22
    key = 1;value = 11
     第三种: 根据value()获取TreeMap的“值”的集合。 
    value = 44
    value = 33
    value = 22
    value = 11

#### 总结： TreeMap相对比较简单，但是首先要知道什么是二叉树，以及对红黑树有点点认识，剩下的细心点阅读以下源码即可。 ####

[https_blog.csdn.net_v_JULY_v_article_details_6105630]: https://blog.csdn.net/v_JULY_v/article/details/6105630
[https_blog.csdn.net_v_JULY_v_article_details_6109153]: https://blog.csdn.net/v_JULY_v/article/details/6109153
[https_www.cs.usfca.edu_galles_visualization_RedBlack.html]: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191121151905169.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1,size_16,color_FFFFFF,t_70