参考阅读：
【小家java】HashMap原理、TreeMap、ConcurrentHashMap的原理、性能、安全方面大解析-----看这一篇就够了
SortedMap和NavigableMap
决定在讲解TreeMap的源码之前，先讲解这两个接口
SortedMap和SortedSet接口两个接口jdk1.2就已经提供，扩展的NavigableMap与NavigableSet接口jdk1.6才开始支持。
SortedMap：顾名思义，此接口应该与排序有关，以下是它的一些方法：
Comparator<? super K> comparator(); //可以自定义排序比较器 //按key升序排列，返回子映射，fromKey到toKey，包括fromKey，不包括toKey SortedMap<K,V> subMap(K fromKey, K toKey); //按key升序排列，返回子映射，开头到toKey，不包括toKey SortedMap<K,V> headMap(K toKey); //按key升序排列，返回子映射，fromKey到末尾，包括fromKey SortedMap<K,V> tailMap(K fromKey); //按key升序排列，返回第一个key K firstKey(); //按key升序排列，返回最后一个key K lastKey(); //返回key的集合，升序排列 Set<K> keySet(); //返回value的集合，按key升序排列， Collection<V> values(); //返回Entry的集合，按key升序排列 Set<Map.Entry<K, V>> entrySet();
再看NavigableMap，它继承了SortedMap：
public interface NavigableMap<K,V> extends SortedMap<K,V>
它自己又定义了一些导航方法
//返回第一个key小于参数的Entry Map.Entry<K,V> lowerEntry(K key); //返回第一个key小于参数的key K lowerKey(K key); //返回第一个key小于等于参数的Entry Map.Entry<K,V> floorEntry(K key); //返回第一个key小于等于参数的key K floorKey(K key); //返回第一个key大于等于参数的Entry Map.Entry<K,V> ceilingEntry(K key); //返回第一个key大于等于参数的key K ceilingKey(K key); //返回第一个key大于参数的Entry Map.Entry<K,V> higherEntry(K key); //返回第一个key大于参数的key K higherKey(K key); //返回key最小的Entry Map.Entry<K,V> firstEntry(); //返回key最大的Entry Map.Entry<K,V> lastEntry(); //删除并返回key最小的Entry Map.Entry<K,V> pollFirstEntry(); //删除并返回key最大的Entry Map.Entry<K,V> pollLastEntry(); //返回key降序排列的NavigableMap(视图) 注意是视图，所以对它进行一个remove操作，也会影响到原来的Map的 是同一个引用 NavigableMap<K,V> descendingMap(); //返回key升序排列的NavigableSet NavigableSet<K> navigableKeySet(); //返回key降序排列的NavigableSet NavigableSet<K> descendingKeySet(); //返回key升序排列的子映射，设置包含标志 NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive); //按key升序排列，返回子映射，开头到toKey，设置包含标志 NavigableMap<K,V> headMap(K toKey, boolean inclusive); //按key升序排列，返回子映射，fromKey到末尾，设置包含标志 NavigableMap<K,V> tailMap(K fromKey, boolean inclusive); //同时也继承了SortedMap的【不带包含标志】的子映射方法 SortedMap<K,V> subMap(K fromKey, K toKey); SortedMap<K,V> headMap(K toKey); SortedMap<K,V> tailMap(K fromKey);
NavigableMap所有已知实现类：ConcurrentSkipListMap（后面博文会有讲解）, TreeMap
NavigableMap扩展了 SortedMap，具有了针对给定搜索目标返回最接近匹配项的导航方法。
方法 lowerEntry、floorEntry、ceilingEntry 和 higherEntry 分别返回与小于、小于等于、大于等于、大于给定键的键关联的 Map.Entry 对象，如果不存在这样的键，则返回 null。
类似地，方法 lowerKey、floorKey、ceilingKey 和 higherKey 只返回关联的键。所有这些方法是为查找条目而不是遍历条目而设计的。
descendingMap 方法返回映射的一个视图，该视图表示的所有关系方法和方向方法都是逆向的。升序操作和视图的性能很可能比降序操作和视图的性能要好。
此接口还定义了 firstEntry、pollFirstEntry、lastEntry 和 pollLastEntry 方法，它们返回和/或移除最小和最大的映射关系（如果存在），否则返回 null。
public static void main(String[] args) { // NavigableMap多态接收TreeMap的实例 NavigableMap<String, Integer> navigatorTreeMap = new TreeMap<String, Integer>() {{ put("aa", 11); put("bb", 22); put("cc", 33); put("dd", 44); put("ee", 55); put("ff", 55); put("gg", 55); }}; System.out.println(navigatorTreeMap.size());// 7个元素：7 System.out.println(navigatorTreeMap.ceilingKey("cc"));// 返回大于等于cc的最小键：cc System.out.println(navigatorTreeMap.ceilingEntry("c"));// 返回一个键-值映射关系，它与大于等于cc的最小键关联：cc=33 System.out.println(navigatorTreeMap.firstKey());// 最小键:aa System.out.println(navigatorTreeMap.firstEntry());// 最小键对应的k-v键值对：aa=11 System.out.println(navigatorTreeMap.floorEntry("c"));// 返回一个键-值映射关系，它与小于等于给定键的最大键关联:bb=22 System.out.println(navigatorTreeMap.floorKey("cc"));// 返回小于等于cc的最大键:cc System.out.println(navigatorTreeMap.headMap("bb"));// 返回此映射的部分视图，其键值严格小于bb:{aa=11} System.out.println(navigatorTreeMap.headMap("bb", true));// 同上小于等于（true）:{aa=11, bb=22} System.out.println(navigatorTreeMap.higherEntry("c"));// 返回一个键-值映射关系，它与小于等于给定键的最大键关联:cc=33 System.out.println(navigatorTreeMap.higherKey("cc"));// 返回小于等于cc的最大键:dd System.out.println(navigatorTreeMap.lastEntry());// 返回一个键-值映射关系，它与小于等于给定键的最大键关联:gg=55 System.out.println(navigatorTreeMap.lastKey());// 返回小于等于cc的最大键:gg System.out.println(navigatorTreeMap.lowerEntry("c"));// 返回一个键-值映射关系，它与小于等于给定键的最大键关联:bb=22 System.out.println(navigatorTreeMap.lowerKey("cc"));// 返回严格小于cc的最大键:bb System.out.println(navigatorTreeMap.pollFirstEntry());// 移除并返回与此映射中的最小键关联的键-值映射关系:aa=11 System.out.println(navigatorTreeMap.pollLastEntry());// 移除并返回与此映射中的最大键关联的键-值映射关系:gg=55 System.out.println(navigatorTreeMap.navigableKeySet());// 返回此映射中所包含键的 // NavigableSet 视图。:[bb, cc, dd, ee, ff] System.out.println(navigatorTreeMap.subMap("aa", true, "dd", true));// 返回部分视图，true表示包括当前元素键值对:{bb=22, cc=33, dd=44} System.out.println(navigatorTreeMap.subMap("bb", "dd"));// 返回部分视图包括前面的元素，不包括后面的：{bb=22, cc=33} System.out.println(navigatorTreeMap.tailMap("cc"));// 返回元素大于cc的元素映射视图,包括cc：//{cc=33, dd=44, ee=55, ff=55} System.out.println(navigatorTreeMap.tailMap("cc", false));// 返回元素大于等于cc的元素映射视图:{dd=44, ee=55, ff=55} //逆序视图 NavigableMap<String, Integer> descendingMap = navigatorTreeMap.descendingMap(); System.out.println(navigatorTreeMap); //原来的Map： System.out.println(descendingMap);// 返回逆序视图:{gg=55, ff=55, ee=55, dd=44, cc=33, bb=22, aa=11} //执行一个移除操作后 再看看会不会影响到原来的Map descendingMap.remove("gg"); System.out.println(navigatorTreeMap); //原来的Map：{aa=11, bb=22, cc=33, dd=44, ee=55, ff=55} System.out.println(descendingMap);// 返回逆序视图:{ff=55, ee=55, dd=44, cc=33, bb=22, aa=11} }
之所以可以去到第一个最后一个元素，或者某个元素的前一个，后一个，是因为集合内部的元素是有序的。
