java集合----TreeMap

一.前言

对于 Map 接口常见的或者常用的一般都是 HashMap 或者 LinkedHashMap 等，对于 TreeMap 的话在日常开发中使用的较少，但是作为 Map 体系中一个实现类，还是有必要去深入了解的，否则面试的你可能就会栽在这上面。

二.深入分析

1.简介

以下内容引用自源码的中的注释

TreeMap 是基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

此实现为 containsKey、get、put 和 remove 操作提供受保证的 log(n) 时间开销。

注意，如果要正确实现 Map 接口，则有序映射所保持的顺序（无论是否明确提供了比较器）都必须与 equals 一致。（关于与 equals 一致的精确定义，请参阅 Comparable 或 Comparator）。这是因为 Map 接口是按照 equals 操作定义的，但有序映射使用它的 compareTo（或 compare）方法对所有键进行比较，因此从有序映射的观点来看，此方法认为相等的两个键就是相等的。即使排序与 equals 不一致，有序映射的行为仍然是定义良好的，只不过没有遵守 Map 接口的常规协定。

注意，此实现不是同步的。如果多个线程同时访问一个映射，并且其中至少一个线程从结构上修改了该映射，则其必须外部同步。（结构上的修改是指添加或删除一个或多个映射关系的操作；仅改变与现有键关联的值不是结构上的修改。）这一般是通过对自然封装该映射的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSortedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的不同步访问，如下所示：
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(…));

collection（由此类所有的“collection 视图方法”返回）的 iterator 方法返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器自身的 remove 方法，否则在其他任何时间以任何方式进行修改都将导致迭代器抛出 ConcurrentModificationException。因此，对于并发的修改，迭代器很快就完全失败，而不会冒着在将来不确定的时间发生不确定行为的风险。

注意，迭代器的快速失败行为无法得到保证，一般来说，当存在不同步的并发修改时，不可能作出任何肯定的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测 bug。

此类及其视图中的方法返回的所有 Map.Entry 对都表示生成它们时的映射关系的快照。它们不支持 Entry.setValue 方法。（不过要注意的是，使用 put 更改相关映射中的映射关系是有可能的。）

总结几个点如下：

TreeMap 是基于红黑树的实现的一个 Map , 会根据 key 节点的值进行排序，默认是key 的自然排序
因为是基于红黑树的，所以增删改查都是基于红黑树的增删改查，因此时间复杂度都是一个 log(n) 级的
对于 key 的判断也是通过 key 的 equals 方法进行判断的。
TreeMap 不是线程安全的，在多线程并发的情况下需要同步，可以使用 Collections 的同步包装方法。
对于 TreeMap 返回的迭代器后，对 TreeMap 的修改都会导致迭代器失效，除了迭代器自身的 remove 方法。

2.变量

 //排序的比较器
 private final Comparator<? super K> comparator;

//TreeMap 的红黑树的根节点
 private transient Entry<K,V> root;

//集合的元素数量
 private transient int size = 0;

//快速失败机制的 修改数
//可以根据这个变量判断是否集合被修改
 private transient int modCount = 0;

从上面的几个变量中，可以看出 TreeMap 的内部结构就是保存着一棵红黑树的根节点，不像 HashMap 那样是个数组。

3.构造方法

// 默认 对 key 的自然排序
 public TreeMap() {
     comparator = null;
 }

 //指定比较器的排序
 public TreeMap(Comparator<? super K> comparator) {
     this.comparator = comparator;
 }

//给定 map 集合元素的排序
 public TreeMap(Map<? extends K, ? extends V> m) {
     comparator = null;
     putAll(m);
 }


 //给定一个比较器和 map 集合元素的排序
 //这个就是将有序的 map 集合转换为红黑树实现
 
 public TreeMap(SortedMap<K, ? extends V> m) {
     comparator = m.comparator();
     try {
         buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
     } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
     }
 }

4.插入

public V put(K key, V value) {
    //根节点
    Entry<K,V> t = root;
    //如果根节点 为 null 
    //就将插入的节点作为根节点
    //然后返回
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    //往红黑树中去插入
    int cmp;
    Entry<K,V> parent;
    
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    //如果有指定的 comparator 就使用指定的
    // 比较器去比较
    if (cpr != null) {
        do {
            parent = t;
            //注意这里的方法是通过比较器的
            // compare 方法
            //而不是 key 的 hashCode 或者 equals
            //因为要排序
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                //找到值就更新，
                //说明如果 TreeMap 对于 元素
                //是通过 compare 比较并保证不重复的
                return t.setValue(value);
        } while (t != null);
    }
    else {
    //如果没有指定的 comparator 就使用 key 的
    //compareTo 方法。
    //这里也表明这 TreeMap 不允许元素为空值
        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);
    }
    //如果有没有找到这个节点，或者说这个新的节点
    //就创建一个节点插入，然后进行红黑树的调整。
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

5.查找

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    
    //如果有指定的比较器
    //就调用下面这个方法
    if (comparator != null)
        return getEntryUsingComparator(key);
    //不允许 key 为 空 
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    
    //从红黑树中去查找
    
    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;
}

  
final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
        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;
}

对于 TreeMap 的插入和查找过程总结如下

TreeMap 不允许 key 为 null
不存在两个元素的 compare 或者 compareTo 返回 0 的情况。
因为每次都是从树中去查找，所以时间复杂度为 O(log n)

6.和 HashMap 的区别

TreeMap 是红黑树，有一个根节点的变量，HashMap 是通过数组+链表/红黑树实现
TreeMap 没有涉及到 equals/hashCode 方法，排序是通过 compare/compareTo 方法进行比较大小， HashMap 涉及到了 hashCode /equals 方法。
增删改查性能比较，TreeMap 为 O(logn) , HashMap 为 O(1) -> O(logn)
总和来说，HashMap 比较快。