TreeMap源码解析

程序员文章站 2022-05-23 14:17:54

...

前言

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

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参数定义和初始化方法：

我们先开看一下 TreeMap 参数定义，比较重要的有有三个：
comparator：对比器，对比key之间的大小。
root：根节点，整个红黑树的根，例如上面的图 d 节点就是根节点
size：集合大小
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

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

 	// 键值对
    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 介绍：

我们通过上面的 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的遍历方式：

第一种：根据entrySet()获取TreeMap的“键值对”的Set集合【推荐】
第二种: 根据keySet()获取TreeMap的“键”的Set集合, 然后再根据key取得Value值【不推荐】
第三种: 根据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源码解析

前言

TreeMap简单示例：

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

TreeMap 中保存 key-value 的 Entry

put 方法

get 方法

TreeMap 中的 comparator 介绍：

TreeMap的遍历方式：

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

asp.net开发中常见公共捕获异常方式总结(附源码)

Python中 Lambda表达式全面解析

Json数据解析模拟美团界面显示

Java输出通过InetAddress获得的IP地址数组详细解析

Android编程解析XML方法详解(SAX,DOM与PULL)

浅谈react-router@4.0 使用方法和源码分析

C#解析JSON实例

全面解析Java中的GC与幽灵引用

自定义javascript验证框架示例【附源码下载】

C# DES加密算法中向量的作用详细解析

TreeMap源码解析

前言

TreeMap简单示例：

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

TreeMap 中保存 key-value 的 Entry

put 方法

get 方法

TreeMap 中的 comparator 介绍：

TreeMap的遍历方式：

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

asp.net开发中常见公共捕获异常方式总结(附源码)

Python中 Lambda表达式全面解析

Json数据解析模拟美团界面显示

Java输出通过InetAddress获得的IP地址数组详细解析

Android编程解析XML方法详解(SAX,DOM与PULL)

浅谈react-router@4.0 使用方法和源码分析

C#解析JSON实例

全面解析Java中的GC与幽灵引用

自定义javascript验证框架示例【附源码下载】

C# DES加密算法中向量的作用详细解析

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