TreeMap 源码解析——20211104

哈喽，大家好，我是指北君。
本篇文章给大家介绍基于树实现的数据结构——TreeMap

1、TreeMap 定义

听名字就知道，TreeMap 是由Tree 和 Map 集合有关的，没错，TreeMap 是由红黑树实现的有序的 key-value 集合。

PS:想要学懂TreeMap的实现原理，红黑树的了解是必不可少的！！！

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap 首先继承了 AbstractMap 抽象类，表示它具有散列表的性质，也就是由 key-value 组成。

其次 TreeMap 实现了 NavigableMap 接口，该接口支持一系列获取指定集合的导航方法，比如获取小于指定key的集合。

最后分别实现 Serializable 接口以及 Cloneable 接口，分别表示支持对象序列化以及对象克隆。

2、字段定义

　　①、Comparator

/**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     */
    private final Comparator<? super K> comparator;

　　可以看上面的英文注释，Comparator 是用来维护treemap集合中的顺序，如果为null，则按照key的自然顺序。

　　Comparator 是一个接口，排序时需要实现其 compare 方法，该方法返回正数，零，负数分别代表大于，等于，小于。那么怎么使用呢？这里举个例子：

　　这里有一个Person类，里面有两个属性pname，page，我们将该person对象放入ArrayList集合时，需要对其按照年龄进行排序。

package com.ys.test;

/**
 * Create by YSOcean
 */
public class Person {
    private String pname;
    private Integer page;

    public Person() {
    }

    public Person(String pname, Integer page) {
        this.pname = pname;
        this.page = page;
    }

    public String getPname() {
        return pname;
    }

    public void setPname(String pname) {
        this.pname = pname;
    }

    public Integer getPage() {
        return page;
    }

    public void setPage(Integer page) {
        this.page = page;
    }

    @Override
    public String toString() {
        return "Person{" +
                "pname='" + pname + '
　　打印结果为：


　　②、Entry

1
2 private transient Entry<K,V> root;


　　对于Entry详细源码这里不列举了，主要看几个字段：
1
2
3
4
5
6 K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;

　　相信对红黑树这种数据结构了解的人，一看这几个字段就明白了，这也印证了前面所说的TreeMap底层有红黑树这种数据结构。

　　③、size

1
2
3
4
5     /**
     * The number of entries in the tree
     */
    private transient int size = 0;


　　用来表示entry的个数，也就是key-value的个数。

　　④、modCount

1
2
3
4
5     /**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;


　　基本上前面讲的在ArrayList,LinkedList,HashMap等线程不安全的集合都有此字段，用来实现Fail-Fast 机制，如果在迭代这些集合的过程中，有其他线程修改了这些集合，就会抛出ConcurrentModificationException异常。

　　⑤、红黑树常量

1
2
3     private static final boolean RED   = false;
    private static final boolean BLACK = true;


3、构造函数
　　①、无参构造函数

1
2
3
4 1     public TreeMap() {
2         comparator = null;
3     }


　　将比较器 comparator 置为 null，表示按照key的自然顺序进行排序。

　　②、带比较器的构造函数

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


　　需要自己实现Comparator。

　　③、构造包含指定map集合的元素

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


　　使用该构造器创建的TreeMap,会默认插入m表示的集合元素，并且comparator表示按照自然顺序进行插入。

　　④、带 SortedMap的构造函数

1
2
3
4
5
6
7
8 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) {
        }
    }

　　和上面带Map的构造函数不一样，map是无序的，而SortedMap 是有序的，使用 buildFromSorted() 方法将SortedMap集合中的元素插入到TreeMap 中。

4、添加元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 //添加元素
    public V put(K key, V value) {
        TreeMap.Entry<K,V> t = root;
        //如果根节点为空，即TreeMap中一个元素都没有，那么设置新添加的元素为根节点
        //并且设置集合大小size=1,以及modCount+1，这是用于快速失败
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new TreeMap.Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        TreeMap.Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        //如果比较器不为空，即初始化TreeMap构造函数时，有传递comparator类
        //那么插入新的元素时，按照comparator实现的类进行排序
        if (cpr != null) {
            //通过do-while循环不断遍历树，调用比较器对key值进行比较
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    //遇到key相等，直接将新值覆盖到原值上
                    return t.setValue(value);
            } while (t != null);
        }
        //如果比较器为空，即初始化TreeMap构造函数时，没有传递comparator类
        //那么插入新的元素时，按照key的自然顺序
        else {
            //如果key==null，直接抛出异常
            //注意，上面构造TreeMap传入了Comparator，是可以允许key==null
            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);
        }
        //找到父亲节点，根据父亲节点创建一个新节点
        TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        //修正红黑树（包括节点的左旋和右旋，具体可以看我Java数据结构和算法中对红黑树的介绍）
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

　　添加元素，如果初始化TreeMap构造函数时，没有传递comparator类，是不允许插入key==null的键值对的，相反，如果实现了Comparator，则可以传递key=null的键值对。

　　另外，当插入一个新的元素后（除了根节点），会对TreeMap数据结构进行修正，也就是对红黑树进行修正，使其满足红黑树的几个特点，具体修正方法包括改变节点颜色，左旋，右旋等操作，这里我不做详细介绍了.
5、删除元素
　　①、根据key删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 public V remove(Object key) {
        //根据key找到该节点
        TreeMap.Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;
        //获取该节点的value，并返回
        V oldValue = p.value;
        //调用deleteEntry()方法删除节点
        deleteEntry(p);
        return oldValue;
    }

    private void deleteEntry(TreeMap.Entry<K,V> p) {
        modCount++;
        size--;

        //如果删除节点的左右节点都不为空，即有两个孩子
        if (p.left != null && p.right != null) {
            //得到该节点的中序后继节点
            TreeMap.Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        TreeMap.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);

            //TreeMap中只有待删除节点P，也就是只有一个节点，直接返回nul即可
        } 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;
            }
        }
    }

　　删除节点分为四种情况：

　　1、根据key没有找到该节点：也就是集合中不存在这一个节点，直接返回null即可。

　　2、根据key找到节点，又分为三种情况：

　　　　①、待删除节点没有子节点，即为叶子节点：直接删除该节点即可。

　　　　②、待删除节点只有一个子节点：那么首先找到待删除节点的子节点，然后删除该节点，用其唯一子节点顶替该节点。

　　　　③、待删除节点有两个子节点：首先找到该节点的中序后继节点，然后把这个后继节点的内容复制给待删除节点，然后删除该中序后继节点，删除过程又转换成前面①、②两种情况了，这里主要是找到中序后继节点，相当于待删除节点的一个替身。

6、查找元素
　　①、根据key查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 public V get(Object key) {
        TreeMap.Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

    final TreeMap.Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        TreeMap.Entry<K,V> p = 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;
    }

7、遍历元素
　　通常有下面两种方法，第二种方法效率要快很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 TreeMap<String,Integer> map = new TreeMap<>();
map.put("A",1);
map.put("B",2);
map.put("C",3);

//第一种方法
//首先利用keySet()方法得到key的集合，然后利用map.get()方法根据key得到value
Iterator<String> iterator = map.keySet().iterator();
while(iterator.hasNext()){
    String key = iterator.next();
    System.out.println(key+":"+map.get(key));
}

//第二种方法
Iterator<Map.Entry<String,Integer>> iterator1 = map.entrySet().iterator();
while(iterator1.hasNext()){
    Map.Entry<String,Integer> entry = iterator1.next();
    System.out.println(entry.getKey()+":"+entry.getValue());
}

8、小结
　　好了，这就是JDK中java.util.TreeMap 类的介绍。

　　我是指北君，操千曲而后晓声，观千剑而后识器。感谢各位人才的：点赞、收藏和评论，我们下期更精彩！

' +
                ", page=" + page +
                '}';
    }
}

　　打印结果为：

　　②、Entry

private transient Entry<K,V> root;

　　对于Entry详细源码这里不列举了，主要看几个字段：

K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;

　　相信对红黑树这种数据结构了解的人，一看这几个字段就明白了，这也印证了前面所说的TreeMap底层有红黑树这种数据结构。

　　③、size

    /**
     * The number of entries in the tree
     */
    private transient int size = 0;

　　用来表示entry的个数，也就是key-value的个数。

　　④、modCount

    /**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;

　　基本上前面讲的在ArrayList,LinkedList,HashMap等线程不安全的集合都有此字段，用来实现Fail-Fast 机制，如果在迭代这些集合的过程中，有其他线程修改了这些集合，就会抛出ConcurrentModificationException异常。

　　⑤、红黑树常量

    private static final boolean RED   = false;
    private static final boolean BLACK = true;

3、构造函数

　　①、无参构造函数

   public TreeMap() {
       comparator = null;
   }

　　将比较器 comparator 置为 null，表示按照key的自然顺序进行排序。

　　②、带比较器的构造函数

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

　　需要自己实现Comparator。

　　③、构造包含指定map集合的元素

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

　　使用该构造器创建的TreeMap,会默认插入m表示的集合元素，并且comparator表示按照自然顺序进行插入。

　　④、带 SortedMap的构造函数

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) {
        }
    }

　　和上面带Map的构造函数不一样，map是无序的，而SortedMap 是有序的，使用 buildFromSorted() 方法将SortedMap集合中的元素插入到TreeMap 中。

4、添加元素

//添加元素
    public V put(K key, V value) {
        TreeMap.Entry<K,V> t = root;
        //如果根节点为空，即TreeMap中一个元素都没有，那么设置新添加的元素为根节点
        //并且设置集合大小size=1,以及modCount+1，这是用于快速失败
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new TreeMap.Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        TreeMap.Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        //如果比较器不为空，即初始化TreeMap构造函数时，有传递comparator类
        //那么插入新的元素时，按照comparator实现的类进行排序
        if (cpr != null) {
            //通过do-while循环不断遍历树，调用比较器对key值进行比较
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    //遇到key相等，直接将新值覆盖到原值上
                    return t.setValue(value);
            } while (t != null);
        }
        //如果比较器为空，即初始化TreeMap构造函数时，没有传递comparator类
        //那么插入新的元素时，按照key的自然顺序
        else {
            //如果key==null，直接抛出异常
            //注意，上面构造TreeMap传入了Comparator，是可以允许key==null
            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);
        }
        //找到父亲节点，根据父亲节点创建一个新节点
        TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        //修正红黑树（包括节点的左旋和右旋，具体可以看我Java数据结构和算法中对红黑树的介绍）
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

　　添加元素，如果初始化TreeMap构造函数时，没有传递comparator类，是不允许插入key==null的键值对的，相反，如果实现了Comparator，则可以传递key=null的键值对。

　　另外，当插入一个新的元素后（除了根节点），会对TreeMap数据结构进行修正，也就是对红黑树进行修正，使其满足红黑树的几个特点，具体修正方法包括改变节点颜色，左旋，右旋等操作，这里我不做详细介绍了.

5、删除元素

　　①、根据key删除

public V remove(Object key) {
        //根据key找到该节点
        TreeMap.Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;
        //获取该节点的value，并返回
        V oldValue = p.value;
        //调用deleteEntry()方法删除节点
        deleteEntry(p);
        return oldValue;
    }

    private void deleteEntry(TreeMap.Entry<K,V> p) {
        modCount++;
        size--;

        //如果删除节点的左右节点都不为空，即有两个孩子
        if (p.left != null && p.right != null) {
            //得到该节点的中序后继节点
            TreeMap.Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        TreeMap.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);

            //TreeMap中只有待删除节点P，也就是只有一个节点，直接返回nul即可
        } 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;
            }
        }
    }

　　删除节点分为四种情况：

　　1、根据key没有找到该节点：也就是集合中不存在这一个节点，直接返回null即可。

　　2、根据key找到节点，又分为三种情况：

　　　　①、待删除节点没有子节点，即为叶子节点：直接删除该节点即可。

　　　　②、待删除节点只有一个子节点：那么首先找到待删除节点的子节点，然后删除该节点，用其唯一子节点顶替该节点。

　　　　③、待删除节点有两个子节点：首先找到该节点的中序后继节点，然后把这个后继节点的内容复制给待删除节点，然后删除该中序后继节点，删除过程又转换成前面①、②两种情况了，这里主要是找到中序后继节点，相当于待删除节点的一个替身。

6、查找元素

　　①、根据key查找

public V get(Object key) {
        TreeMap.Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

    final TreeMap.Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        TreeMap.Entry<K,V> p = 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;
    }

7、遍历元素

　　通常有下面两种方法，第二种方法效率要快很多。

TreeMap<String,Integer> map = new TreeMap<>();
map.put("A",1);
map.put("B",2);
map.put("C",3);

//第一种方法
//首先利用keySet()方法得到key的集合，然后利用map.get()方法根据key得到value
Iterator<String> iterator = map.keySet().iterator();
while(iterator.hasNext()){
    String key = iterator.next();
    System.out.println(key+":"+map.get(key));
}

//第二种方法
Iterator<Map.Entry<String,Integer>> iterator1 = map.entrySet().iterator();
while(iterator1.hasNext()){
    Map.Entry<String,Integer> entry = iterator1.next();
    System.out.println(entry.getKey()+":"+entry.getValue());
}

8、小结

　　好了，这就是JDK中java.util.TreeMap 类的介绍。

　　我是指北君，操千曲而后晓声，观千剑而后识器。感谢各位人才的：点赞、收藏和评论，我们下期更精彩！