TreeMap 是一种基于红黑树实现的 Key-Value 结构。在使用集合视图在 HashMap 中迭代时，是不能保证迭代顺序的； LinkedHashMap 使用了双向链表，保证按照插入顺序或者访问顺序进行迭代。但是有些时候，我们可能需要按照键的大小进行按序迭代，或者在使用哈希表的同时希望按键值进行排序，这个时候 TreeMap 就有其用武之地了。 TreeMap 支持按键值进行升序访问，或者由传入的比较器（Comparator）来控制。
下面基于 JDK 8 的源码对 TreeMap 进行一个简单的分析。
1
2
3
| public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
|
同 HashMap 一样， TreeMap 也继承了 AbstractMap，并实现了 Cloneable， Serializable 接口。不同的是， TreeMap 还实现 NavigableMap 接口。
NavigableMap 接口和 SortedMapSortedMap 是一个扩展自 Map 的一个接口，对该接口的实现要保证所有的 Key 是完全有序的。
这个顺序一般是指 Key 的自然序（实现 Comparable 接口）或在创建 SortedMap 时指定一个比较器（Comparator）。当我们使用集合的视角（Collection View，由 entrySet、keySet 与 values 方法提供）来迭代时，就可以按序访问其中的元素。
插入 SortedMap 中的所有 Key 的类都必须实现 Comparable 接口（或者可以作为指定的 Comparator 的参数）。在比较两个 Key 时通过调用 k1.compareTo(k2) (or comparator.compare(k1, k2))，因而所有的 Key 都必须能够相互比较，否则会抛出 ClassCastException的异常。
SortedMap 中 Key 的顺序必须和 equals 保持一致（consistent with equals），
即 k1.compareTo(k2) == 0 (or comparator.compare(k1, k2)) 和 k1.equals(k2)要有相同的布尔值。（Comparable 接口的实现不强制要求这一点，但通常都会遵守。）这是因为 Map 接口的定义中，比较 Key 是通过 equals 方法，而在 SortedMap 中比较 Key 则是通过 compareTo (or compare) 方法。如果不一致的，就破坏了 Map 接口的约定。
通过 SortedMap 可以获取其中的一段数据，如 subMap(K fromKey, K toKey), headMap(K toKey), tailMap(K fromKey) 等，所有的区间操作都是左闭右开的。也可以通过 firstKey() 和 lastKey() 来获取第一个和最后一个键。
是 JDK 1.6 之后新增的接口，扩展了 SortedMap 接口，提供了一些导航方法（navigation methods）来返回最接近搜索目标的匹配结果。
- lowerEntry(K key) (or lowerKey(K key))，小于给定 Key 的 Entry (or Key)
- floorEntry(K key) (or floorKey(K key))，小于等于给定 Key 的 Entry (or Key)
- higherEntry(K key) (or higherKey(K key))，大于给定 Key 的 Entry (or Key)
- ceilingEntry(K key) (or ceilingKey(K key))，大于等于给定 Key 的 Entry (or Key)
这些方法都有重载的版本，来控制是否包含端点。subMap(K fromKey, K toKey), headMap(K toKey), tailMap(K fromKey) 等方法也是如此。
NavigableMap 可以按照 Key 的升序或降序进行访问和遍历。 descendingMap() 和 descendingKeySet() 则会获取和原来的顺序相反的集合，集合中的元素则是同样的引用，在该视图上的修改会影响到原始的数据。
底层结构TreeMap 是基于红黑树来实现的，排序时按照键的自然序（要求实现 Comparable 接口）或者提供一个 Comparator 用于排序。
1
2
3
4
5
6
7
8
9
10
11
| //比较器，没有指定的话默认使用Key的自然序
private final Comparator<? super K> comparator;
//红黑树根节点
private transient Entry<K,V> root;
//树中节点的数量
private transient int size = 0;
//结构化修改的次数
private transient int modCount = 0;
|
TreeMap 同样不是线程安全的，基于结构化修改的次数来实现 fail-fast 机制。因而要在多线程环境下使用时，可能需要手动进行同步，或者使用 Collections.synchronizedSortedMap 进行包装。 |
