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接口越发机动的操纵。

package java.util;
public interface NavigableMap<K,V> extends SortedMap<K,V> {
    /**
     * 返回一个小于指定key的最大的一对键值对，假如找不到则返回null。
     */
    Map.Entry<K,V> lowerEntry(K key);
    /**
     * 返回一个小于指定key的最大的一个key，假如找不到则返回null。
     */
    K lowerKey(K key);
    /**
     * 返回一个小于或便是指定key的最大的一对键值对，假如找不到则返回null。
     */
    Map.Entry<K,V> floorEntry(K key);
    /**
     * 返回一个小于或便是指定key的最大的一个key，假如找不到则返回null。
     */
    K floorKey(K key);
    /**
     * 返回一个大于或便是指定key的最小的一对键值对，昆山软件公司，假如找不到则返回null。
     */
    Map.Entry<K,V> ceilingEntry(K key);
    /**
     * 返回一个大于或便是指定key的最小的一个key，假如找不到则返回null。
     */
    K ceilingKey(K key);
    /**
     * 返回一个大于指定key的最小的一对键值对，假如找不到则返回null。
     */
    Map.Entry<K,V> higherEntry(K key);
    /**
     * 返回一个大于指定key的最小的一个key，假如找不到则返回null。
     */
    K higherKey(K key);
    /**
     * 返回该Map中最小的键值对，假如Map为空则返回null。
     */
    Map.Entry<K,V> firstEntry();
    /**
     * 返回该Map中最大的键值对，假如Map为空则返回null。
     */
    Map.Entry<K,V> lastEntry();
    /**
     * 返回并删除该Map中最小的键值对，假如Map为空则返回null。
     */
    Map.Entry<K,V> pollFirstEntry();
    /**
     * 返回并删除该Map中最大的键值对，假如Map为空则返回null。
     */
    Map.Entry<K,V> pollLastEntry();
    /**
     * 返回一个以当前Map降序（逆序）排序的荟萃视图
     */
    NavigableMap<K,V> descendingMap();
    /**
     * 返回一个包括当前Map中所有key的荟萃视图，该视图中的key以升序（正序）排序。
     */
    NavigableSet<K> navigableKeySet();
    /**
     * 返回一个包括当前Map中所有key的荟萃视图，该视图中的key以降序（逆序）排序。
     */
    NavigableSet<K> descendingKeySet();
    /**
     * 与SortedMap.subMap根基一致，区别在于多的两个参数fromInclusive和toInclusive，
     * 它们代表是否包括from和to，假如fromKey与toKey相等，而且fromInclusive与toInclusive
     * 都为true，那么不会返回空荟萃。
     */
    NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                             K toKey,   boolean toInclusive);
    /**
     * 返回一个小于或便是（inclusive为true的环境下）toKey的局部视图。
     */
    NavigableMap<K,V> headMap(K toKey, boolean inclusive);
    /**
     * 返回一个大于或便是（inclusive为true的环境下）fromKey的局部视图。
     */
    NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
    /**
     * 等价于subMap(fromKey, true, toKey, false)。
     */
    SortedMap<K,V> subMap(K fromKey, K toKey);
    /**
     * 等价于headMap(toKey, false)。
     */
    SortedMap<K,V> headMap(K toKey);
    /**
     * 等价于tailMap(fromKey, true)。
     */
    SortedMap<K,V> tailMap(K fromKey);
}