TreeMap

TreeMap是基于红黑树（一种自平衡的二叉查找树）实现的一个保证有序性的Map，在继承关系结构图中可以得知TreeMap实现了NavigableMap接口，而该接口又继承了SortedMap接口，我们先来看看这两个接口定义了一些什么功能。

SortedMap

首先是SortedMap接口，实现该接口的实现类应当按照自然排序保证key的有序性，所谓自然排序即是根据key的compareTo()函数（需要实现Comparable接口）或者在构造函数中传入的Comparator实现类来进行排序，集合视图遍历元素的顺序也应当与key的顺序一致。SortedMap接口还定义了以下几个有效利用有序性的函数：

package java.util;
public interface SortedMap<K,V> extends Map<K,V> {
    /**
     * 用于在此Map中对key进行排序的比较器，如果为null，则使用key的compareTo()函数进行比较。
     */
    Comparator<? super K> comparator();
    /**
     * 返回一个key的范围为从fromKey到toKey的局部视图（包括fromKey，不包括toKey，包左不包右），
     * 如果fromKey和toKey是相等的，则返回一个空视图。
     * 返回的局部视图同样是此Map的集合视图，所以对它的操作是会与Map互相影响的。
     */
    SortedMap<K,V> subMap(K fromKey, K toKey);
    /**
     * 返回一个严格地小于toKey的局部视图。
     */
    SortedMap<K,V> headMap(K toKey);
    /**
     * 返回一个大于或等于fromKey的局部视图。
     */
    SortedMap<K,V> tailMap(K fromKey);
    /**
     * 返回当前Map中的第一个key（最小）。
     */
    K firstKey();
    /**
     * 返回当前Map中的最后一个key（最大）。
     */
    K lastKey();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}

NavigableMap

然后是SortedMap的子接口NavigableMap，该接口扩展了一些用于导航（Navigation）的方法，像函数lowerEntry(key)会根据传入的参数key返回一个小于key的最大的一对键值对，例如，我们如下调用lowerEntry(6)，那么将返回key为5的键值对，如果没有key为5，则会返回key为4的键值对，以此类推，直到返回null（实在找不到的情况下）。

public static void main(String[] args) {
    NavigableMap<Integer, Integer> map = new TreeMap<>();
    for (int i = 0; i < 10; i++)
        map.put(i, i);

    assert map.lowerEntry(6).getKey() == 5;
    assert map.lowerEntry(5).getKey() == 4;
    assert map.lowerEntry(0).getKey() == null;
}

NavigableMap定义的都是一些类似于lowerEntry(key)的方法和以逆序、升序排序的集合视图，这些方法利用有序性实现了相比SortedMap接口更加灵活的操作。