在Map集合框架中，除了 HashMap 以外，TreeMap 也是我们工作中常用到的集合对象之一。

与 HashMap 相比，TreeMap 是一个能比较元素大小的 Map 集合，会对传入的 key 进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序；

不同于 HashMap 的哈希映射，TreeMa 底层实现了树形结构，至于具体形态，你可以简单的理解为一颗倒过来的树—根在上叶在下。如果用计算机术语来说的话，TreeMap实现了红黑树的结构，形成了一颗二叉树

概述

TreeMap的Key按照自然顺序进行排序或者根据创建映射时提供的Comparator接口进行排序。

TreeMap为增、删、改、查这些操作提供了log(N)的时间开销，从存储角度而言，这比HashMap与LinkedHashMap的O(1)时间复杂度要差些。

但是在统计性能上，TreeMap同样可以保证log(N)的时间开销，这又比HashMap与LinkedHashMap的O(N)时间复杂度好不少。

类的继承图：

域

• Comparator<? super K> comparator: 比较器对象
• Entry<K,V> root： 根节点
• int size = 0：容器长度
• int modCount = 0：结构性修改次数
• EntrySet entrySet： 存储KV对，无顺序
• KeySet navigableKeySet：存储K
• NavigableMap<K,V> descendingMap： 有顺序的存储。

构造函数

• TreeMap()
• TreeMap(Comparator<? super K> comparator)
• TreeMap(Map<? extends K, ? extends V> m)
• TreeMap(SortedMap<K, ? extends V> m)
• 创建 TreeMap 对象，如果没有指定比较器，那么就是用自然排序。

成员方法

put

• 按照 comparator 对 key 进行排序，然后放到红黑二叉树指定的位置。
• key 不允许为 null， value 可以为空。
• oldValue 如果存在的话，会被替换；如果不存在的话，则新添一个节点，然后对做红黑树的平衡操作。

get

• 按照 comparator 对 key 进行排序，获取key的位置， 迭代红黑二叉树，取到节点对象。
• 时间复杂度是log(n)。

remove

• 先找到节点对象，删除，然后平衡红黑树。

总结

• 构造方法中传递了 Comparator 对象，那么就会以 Comparator 对象的方法进行比较。否则，则使用 Comparator 的compareTo(T o)方法来比较。
• key 不允许为 null。
• 如果只需要存储功能，使用HashMap与LinkedHashMap是一种更好的选择；如果需要保证统计性能或者需要对 key 按照一定规则进行排序，那么使用 TreeMap 是一种更好的选择。