集合之TreeMap（含JDK1.8源码分析）-白红宇

集合之TreeMap（含JDK1.8源码分析）

阅读量：4563 次

发布时间：2019-06-08

本文共 21605 字，大约阅读时间需要 72 分钟。

一、前言

　　前面所说的hashMap和linkedHashMap都不具备统计的功能，或者说它们的统计性能的时间复杂度都不是很好，要想对两者进行统计，需要遍历所有的entry，时间复杂度比较高，此时，我们就需要使用treeMap。

　　treeMap的key按照自然顺序进行排序或根据创建时提供的comparator接口进行排序，TreeMap为增、删、改、查这些操作提供了log(N)的时间开销，从存储角度而言，这比HashMap与LinkedHashMap的O(1)时间复杂度要差些；但是在统计性能上，TreeMap同样可以保证log(N)的时间开销，这又比HashMap与LinkedHashMap的O(N)时间复杂度好不少。

　　因此，如果只需要存储功能，使用hashMap或linkedHashMap是一种更好的选择；如果还需要保证统计功能或是对key按照一定的规则进行排序，那么使用treeMap是一种更好的选择。

　　四个关注点在treeMap上的答案

二、treeMap的数据结构

　　treeMap底层使用的数据结构是红黑树，下图为典型的红黑树结构，效率很高。

　　用来存储key-value的是treeMap中的Entry类，除了key-value属性，还有该节点的左节点left，右节点right，父节点parent。

三、treeMap源码分析-属性及构造函数

　　3.1 类的继承关系

public class TreeMap
     
          extends AbstractMap
      
           implements NavigableMap
       
        , Cloneable, java.io.Serializable

　　说明：继承了抽象类AbstractMap，AbstractMap实现了Map接口，实现了部分方法。实现了NavigableMap,Cloneable,Serializable接口，其中NavigableMap是继承自SortedMap的接口，定义了一系列规范。

　　3.2 类的属性

/**     * The comparator used to maintain order in this tree map, or     * null if it uses the natural ordering of its keys.     * 比较器，用于维持treeMap中key的顺序，为null时，使用的是key的自然顺序     * @serial     */    private final Comparator
      comparator;    //树的根节点    private transient Entry
     
       root;    /**     * The number of entries in the tree　　树中节点的数量     */    private transient int size = 0;    /**     * The number of structural modifications to the tree.　　对树进行结构性修改的次数     */    private transient int modCount = 0;

　　3.3 类的构造函数

　　1、TreeMap()型

/**     * Constructs a new, empty tree map, using the natural ordering of its     * keys.  All keys inserted into the map must implement the {
    @link     * Comparable} interface.  Furthermore, all such keys must be     * mutually comparable: {
    @code k1.compareTo(k2)} must not throw     * a {
    @code ClassCastException} for any keys {
    @code k1} and     * {
    @code k2} in the map.  If the user attempts to put a key into the     * map that violates this constraint (for example, the user attempts to     * put a string key into a map whose keys are integers), the     * {
    @code put(Object key, Object value)} call will throw a     * {
    @code ClassCastException}.     */    public TreeMap() {        comparator = null;    }

　　说明：定义一个新的，空的treeMap，排序规则是key的自然顺序，所有要存储的元素的key必须实现Comparable接口，而且，这些key要可以互相比较，否则会抛ClassCastException，即类型转换异常。

　　举例：正常情况下，key实现了Comparable接口

public class Test {    public static void main(String[] args) {        TreeMap
     
       treeMap = new TreeMap<>();        treeMap.put("a","aaa");        treeMap.put("d","ddd");        treeMap.put("b","bbb");        treeMap.put("c","ccc");        Set
      
       
        > entries = treeMap.entrySet();        for(Map.Entry
        
          entry : entries) {            System.out.println(entry.getKey() + "========" + entry.getValue());        }    }}

　　结果：

a========aaab========bbbc========cccd========ddd

　　说明：可以看到，treeMap中已经根据key的自然顺序进行排序了，key所属类型String类实现了Comparable接口

public final class String    implements java.io.Serializable, Comparable
     
      , CharSequence

　　key所属String类下的比较规则：

/**     * Compares two strings lexicographically.     * The comparison is based on the Unicode value of each character in     * the strings. The character sequence represented by this     * {
    @code String} object is compared lexicographically to the     * character sequence represented by the argument string. The result is     * a negative integer if this {
    @code String} object     * lexicographically precedes the argument string. The result is a     * positive integer if this {
    @code String} object lexicographically     * follows the argument string. The result is zero if the strings     * are equal; {
    @code compareTo} returns {
    @code 0} exactly when     * the {
    @link #equals(Object)} method would return {
    @code true}.     *      * This is the definition of lexicographic ordering. If two strings are     * different, then either they have different characters at some index     * that is a valid index for both strings, or their lengths are different,     * or both. If they have different characters at one or more index     * positions, let k be the smallest such index; then the string     * whose character at position k has the smaller value, as     * determined by using the < operator, lexicographically precedes the     * other string. In this case, {
    @code compareTo} returns the     * difference of the two character values at position {
    @code k} in     * the two string -- that is, the value:     * 
     
           * this.charAt(k)-anotherString.charAt(k)     * 
     
     * If there is no index position at which they differ, then the shorter     * string lexicographically precedes the longer string. In this case,     * {
    @code compareTo} returns the difference of the lengths of the     * strings -- that is, the value:     * 
     
           * this.length()-anotherString.length()     * 
     
     *     * @param   anotherString   the {
    @code String} to be compared.     * @return  the value {
    @code 0} if the argument string is equal to     *          this string; a value less than {
    @code 0} if this string     *          is lexicographically less than the string argument; and a     *          value greater than {
    @code 0} if this string is     *          lexicographically greater than the string argument.     */    public int compareTo(String anotherString) {        int len1 = value.length;        int len2 = anotherString.value.length;        int lim = Math.min(len1, len2);        char v1[] = value;        char v2[] = anotherString.value;        int k = 0;        while (k < lim) {            char c1 = v1[k];            char c2 = v2[k];            if (c1 != c2) {                return c1 - c2;            }            k++;        }        return len1 - len2;    }

　　第二种情况：定义一个Student类当做treeMap的key，Student类并未实现Comparable接口

public class Student{    private String name;    private String age;    public Student() {    }    public Student(String name, String age) {        this.name = name;        this.age = age;    }    @Override    public String toString() {        return "Student{" +                "name='" + name + '\'' +                ", age='" + age + '\'' +                '}';    }    public String getName() {        return name;    }    public void setName(String name) {        this.name = name;    }    public String getAge() {        return age;    }    public void setAge(String age) {        this.age = age;    }}

　　测试一下：

public class Test {    public static void main(String[] args) {
            TreeMap
     
       treeMap = new TreeMap<>();        Student student1 = new Student("zs", "10");        Student student2 = new Student("ls", "12");        Student student3 = new Student("ww", "11");        Student student4 = new Student("zl", "15");        treeMap.put(student1,"beijing");        treeMap.put(student2,"shenzhen");        treeMap.put(student3,"hangzhou");        treeMap.put(student4,"guangzhou");        Set
      
       
        > entries = treeMap.entrySet();        for(Map.Entry
        
          entry : entries) {            System.out.println(entry.getKey() + "==========" + entry.getValue());        }    }}

　　结果：

Exception in thread "main" java.lang.ClassCastException: com.dajia.test.Student cannot be cast to java.lang.Comparable    at java.util.TreeMap.compare(TreeMap.java:1294)    at java.util.TreeMap.put(TreeMap.java:538)    at com.dajia.test.Test.main(Test.java:23)

　　说明：可以看到，当key未实现Comparable接口时，在put元素的时候就会报错。

　　当Student类实现Comparable接口时：比较规则是按照age的大小进行比较

public class Student implements Comparable
     
      {    private String name;    private String age;    public Student() {    }    public Student(String name, String age) {        this.name = name;        this.age = age;    }    @Override    public String toString() {        return "Student{" +                "name='" + name + '\'' +                ", age='" + age + '\'' +                '}';    }    public String getName() {        return name;    }    public void setName(String name) {        this.name = name;    }    public String getAge() {        return age;    }    public void setAge(String age) {        this.age = age;    }    @Override    public int compareTo(Student o) {        return this.age.compareTo(o.age);    }}

　　相同的测试代码测试一下，结果：按照key（student）的排序规则进行了排序

Student{name='zs', age='10'}==========beijingStudent{name='ww', age='11'}==========hangzhouStudent{name='ls', age='12'}==========shenzhenStudent{name='zl', age='15'}==========guangzhou

　　2、TreeMap(Comparator<? super K> comparator)型

/**     * Constructs a new, empty tree map, ordered according to the given     * comparator.  All keys inserted into the map must be mutually     * comparable by the given comparator: {
    @code comparator.compare(k1,     * k2)} must not throw a {
    @code ClassCastException} for any keys     * {
    @code k1} and {
    @code k2} in the map.  If the user attempts to put     * a key into the map that violates this constraint, the {
    @code put(Object     * key, Object value)} call will throw a     * {
    @code ClassCastException}.     *     * @param comparator the comparator that will be used to order this map.     *        If {
    @code null}, the {
    @linkplain Comparable natural     *        ordering} of the keys will be used.     */    public TreeMap(Comparator
      comparator) {        this.comparator = comparator;    }

　　说明：定义一个新的，空的treeMap，参数是自定义的比较器，排序规则是该比较器的比较规则，这些key要可以互相比较，否则会抛ClassCastException，即类型转换异常。

　　举例：自定义一个比较器StudentComparator，比较student下的age大小

public class StudentComparator implements Comparator
     
      {    @Override    public int compare(Student o1, Student o2) {        return o1.getAge().compareTo(o2.getAge());    }}

　　测试一下：

public class Test {    public static void main(String[] args) {        StudentComparator studentComparator = new StudentComparator();        TreeMap
     
       treeMap = new TreeMap<>(studentComparator);        Student student1 = new Student("zs", "10");        Student student2 = new Student("ls", "12");        Student student3 = new Student("ww", "11");        Student student4 = new Student("zl", "15");        treeMap.put(student1,"beijing");        treeMap.put(student2,"shenzhen");        treeMap.put(student3,"hangzhou");        treeMap.put(student4,"guangzhou");        Set
      
       
        > entries = treeMap.entrySet();        for(Map.Entry
        
          entry : entries) {            System.out.println(entry.getKey() + "==========" + entry.getValue());        }    }}

　　结果：

Student{name='zs', age='10'}==========beijingStudent{name='ww', age='11'}==========hangzhouStudent{name='ls', age='12'}==========shenzhenStudent{name='zl', age='15'}==========guangzhou

　　3、TreeMap(Map<? extends K, ? extends V> m)型

/**     * Constructs a new tree map containing the same mappings as the given     * map, ordered according to the natural ordering of its keys.     * All keys inserted into the new map must implement the {
    @link     * Comparable} interface.  Furthermore, all such keys must be     * mutually comparable: {
    @code k1.compareTo(k2)} must not throw     * a {
    @code ClassCastException} for any keys {
    @code k1} and     * {
    @code k2} in the map.  This method runs in n*log(n) time.     *     * @param  m the map whose mappings are to be placed in this map     * @throws ClassCastException if the keys in m are not {
    @link Comparable},     *         or are not mutually comparable     * @throws NullPointerException if the specified map is null     */    public TreeMap(Map
      m) {        comparator = null;        putAll(m);    }

　　说明：定义一个新的treeMap，根据key的自然排序将参数中m的元素存储到treeMap中。

　　4、TreeMap(SortedMap<K, ? extends V> m)型

/**     * Constructs a new tree map containing the same mappings and     * using the same ordering as the specified sorted map.  This     * method runs in linear time.     *     * @param  m the sorted map whose mappings are to be placed in this map,     *         and whose comparator is to be used to sort this map     * @throws NullPointerException if the specified map is null     */    public TreeMap(SortedMap
     
       m) {        comparator = m.comparator();        try {            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);        } catch (java.io.IOException cannotHappen) {        } catch (ClassNotFoundException cannotHappen) {        }    }

　　说明：定义一个新的treeMap，根据sortedMap中比较器的排序规则将参数中m的元素存储到treeMap中。

四、treeMap源码分析-核心函数

　　4.1 增：put函数----存储元素

/**     * Associates the specified value with the specified key in this map.     * If the map previously contained a mapping for the key, the old     * value is replaced.     *     * @param key key with which the specified value is to be associated     * @param value value to be associated with the specified key     *     * @return the previous value associated with {
    @code key}, or     *         {
    @code null} if there was no mapping for {
    @code key}.     *         (A {
    @code null} return can also indicate that the map     *         previously associated {
    @code null} with {
    @code key}.)     * @throws ClassCastException if the specified key cannot be compared     *         with the keys currently in the map     * @throws NullPointerException if the specified key is null     *         and this map uses natural ordering, or its comparator     *         does not permit null keys     */    public V put(K key, V value) {        //将根节点赋值给t        Entry
     
       t = root;        if (t == null) {            //根节点为null，添加的是第一个元素，先check key的type            compare(key, key); // type (and possibly null) check            //将第一个元素赋值给根节点            root = new Entry<>(key, value, null);            size = 1;            modCount++;            return null;        }        int cmp;//定义比较结果        Entry
      
        parent;//定义put进来的元素的父节点        // split comparator and comparable paths        Comparator
        cpr = comparator;        if (cpr != null) {            do {                parent = t;//获取要存储元素的parent节点                //从root开始，比较两者key的大小                cmp = cpr.compare(key, t.key);                if (cmp < 0)                    //小于已存在节点的key，将t.left赋值给t，以便再次进行比较                    t = t.left;                else if (cmp > 0)                    //大于已存在节点的key，将t.right赋值给t,以便再次进行比较                    t = t.right;                else                    //为0，表示两者相等，用value替换原value值，并返回原value                    return t.setValue(value);            } while (t != null);//t != null，接着进行比较        }        else {            //The comparator used to maintain order in this tree map, or null if it uses the natural ordering of its keys.            if (key == null)                throw new NullPointerException();            @SuppressWarnings("unchecked")//获取key的compareTo方法            Comparable
        k = (Comparable
       ) key;            do {                parent = t;//获取要存储元素的parent节点                //从root开始，比较两者key的大小                cmp = k.compareTo(t.key);                if (cmp < 0)                    //小于已存在节点的key，将t.left赋值给t，以便再次进行比较                    t = t.left;                else if (cmp > 0)                    //大于已存在节点的key，将t.right赋值给t,以便再次进行比较                    t = t.right;                else                    //为0，表示两者相等，用value替换原value值，并返回原value                    return t.setValue(value);            } while (t != null);//t != null，接着进行比较        }        //构建要存储的新元素        Entry
       
         e = new Entry<>(key, value, parent);        if (cmp < 0)//小于0，位于parent的左边            parent.left = e;        else//大于0，位于parent元素的右边            parent.right = e;        //插入后进行修正        fixAfterInsertion(e);        size++;        modCount++;        return null;    }

　　说明：插入一个元素时，若用户自定义一个比较器，则会按照用户自定义比较器中的排序规则确定元素的插入位置，否则，将会使用key自身实现的比较器确定插入位置。该方法主要是通过key的比较寻找插入节点的parent节点，并将parent节点与插入节点联系起来。

　　4.2 删：remove和removeNode函数----删除元素

/**     * Removes the mapping for this key from this TreeMap if present.     *     * @param  key key for which mapping should be removed     * @return the previous value associated with {
    @code key}, or     *         {
    @code null} if there was no mapping for {
    @code key}.     *         (A {
    @code null} return can also indicate that the map     *         previously associated {
    @code null} with {
    @code key}.)     * @throws ClassCastException if the specified key cannot be compared     *         with the keys currently in the map     * @throws NullPointerException if the specified key is null     *         and this map uses natural ordering, or its comparator     *         does not permit null keys     */    public V remove(Object key) {        Entry
     
       p = getEntry(key);        if (p == null)            return null;        V oldValue = p.value;        deleteEntry(p);        return oldValue;    }

　　通过getEntry获取要删除的节点

/**     * Returns this map's entry for the given key, or {
    @code null} if the map     * does not contain an entry for the key.     *     * @return this map's entry for the given key, or {
    @code null} if the map     *         does not contain an entry for the key     * @throws ClassCastException if the specified key cannot be compared     *         with the keys currently in the map     * @throws NullPointerException if the specified key is null     *         and this map uses natural ordering, or its comparator     *         does not permit null keys     */    final Entry
     
       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
       k = (Comparable
      ) key;        Entry
      
        p = root;        //比较器为null，通过key的循环比较获取节点        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;    }

　　再通过deleteEntry将该节点进行删除，这个方法没看懂，先放着 o(╥﹏╥)o

/**     * Delete node p, and then rebalance the tree.     */    private void deleteEntry(Entry
     
       p) {        modCount++;        size--;        // If strictly internal, copy successor's element to p and then make p        // point to successor.        if (p.left != null && p.right != null) {            Entry
      
        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.        Entry
       
         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;            }        }    }

　　4.3 改：put函数----修改元素

　　参见4.1中的put函数，可以将相同key的value覆盖。

　　4.4 查：get和getEntry方法----查找元素

/**     * Returns the value to which the specified key is mapped,     * or {
    @code null} if this map contains no mapping for the key.     *     * More formally, if this map contains a mapping from a key     * {
    @code k} to a value {
    @code v} such that {
    @code key} compares     * equal to {
    @code k} according to the map's ordering, then this     * method returns {
    @code v}; otherwise it returns {
    @code null}.     * (There can be at most one such mapping.)     *     * 
A return value of {
    @code null} does not necessarily     * indicate that the map contains no mapping for the key; it's also     * possible that the map explicitly maps the key to {
    @code null}.     * The {
    @link #containsKey containsKey} operation may be used to     * distinguish these two cases.     *     * @throws ClassCastException if the specified key cannot be compared     *         with the keys currently in the map     * @throws NullPointerException if the specified key is null     *         and this map uses natural ordering, or its comparator     *         does not permit null keys     */    public V get(Object key) {        Entry
      
        p = getEntry(key);        return (p==null ? null : p.value);    }