一、前言
二、TreeMap的继承关系
三、SortedMap接口源码解析
3.1 SortedMap接口
3.2 Comparable接口
3.3 Comparator接口
四、NavigableMap接口源码解析
五、总结
在前面两篇随笔中，我们提到过，当HashMap的桶过大的时候，会自动将链表转化成红黑树结构，当时一笔带过，因为我们将留在本章中，针对TreeMap进行详细的了解。
下面先让我们来看一下TreeMap的继承关系，对它有一个大致的了解：
可以看到，除了在之前HashMap里常见的继承类和接口以外，TreeMap实现了NavigableMap接口，而NavigableMap继承自SortedMap，由名字可以看出，只是一个用来实现排序的接口。而这也是为什么TreeMap能够实现排序的原因。由于篇幅关系，将TreeMap的源码解析分为三部分，本章将对接口NavigableMap以及SortedMap进行解析。
public interface SortedMap<K,V> extends Map<K,V> { //返回用于对键的进行排序的比较器，如果此映射使用其键的自然排序，则为null Comparator<? super K> comparator(); //返回从fromKey（包括）到toKey（不包括）之间的map SortedMap<K,V> subMap(K fromKey, K toKey); //返回小于toKey的map SortedMap<K,V> headMap(K toKey); //返回大于或等于fromKey的map SortedMap<K,V> tailMap(K fromKey); //返回map中第一个（最低）键 K firstKey(); //返回map中最后一个（最高）键 K lastKey(); Set<K> keySet(); Collection<V> values(); Set<Map.Entry<K, V>> entrySet(); }
SortedMap的接口比较简单，没有很特别的地方，唯一比较特别的就是返回Comparator这个接口，可以设想实现排序功能的秘密或许就藏在此处。下面让我们来看一下Comparator和Comparable接口，两者之间有点关联，可以理解为Comparable自带了比较功能，而Comparator是赋予没有比较能力的对象一种比较能力。举个简单例子：面对一道计算题，小明天生口算能力很强，看一眼就能算出来答案。而小李没有这种能力，需要借助计算器才能得出答案。
先让我们看下它的代码：
public interface Comparable<T> { //如果小于o，返回负数；等于o，返回0；大于o返回正数。 public int compareTo(T o); }
对，就是这么简单，里面传入一个泛型T的对象o，对o进行比较。如果小于o，返回负数；等于o，返回0；大于o返回正数。
我们熟悉的很多对象如String，Integer，Double等都实现了这个接口。可以来看一下简单的例子：
public class Item implements Comparable<Item> { private String name; private int price; public Item(String name, int price) { this.name = name; this.price = price; } public int getPrice() { return price; } public String getName() { return name; } @Override public String toString() { return "Item{" + "name=‘" + name + ‘\‘‘ + ", price=" + price + ‘}‘; } @Override public int compareTo(Item o) { if (this.name.compareTo(o.name) < 0) { return -1; } else if (this.name.compareTo(o.name) > 0) { return 1; } else { return 0; } } public static void main(String[] args) { List<Item> items = Arrays.asList(new Item("banana", 200), new Item("apple", 400)); System.out.println("before:" + items); Collections.sort(items); System.out.println("after:" + items); } }
上述main函数的输出：
before:[Item{name=‘banana‘, price=200}, Item{name=‘apple‘, price=400}]
after:[Item{name=‘apple‘, price=400}, Item{name=‘banana‘, price=200}]上面的例子中，我们自己实现了Comparable接口，比较了Item的name属性，然后通过Collections.sort对它进行了排序（值得注意的是：没有实现Comparable接口的对象不能使用该方法）。但是，如果我不想用name属性对它进行排序，想对price进行排序呢，或者先对name排序，相同的话在对price进行排序呢，用这个不就没法实现了吗。这就需要提到了下面的Comparator接口
照例先来看一下代码：
@FunctionalInterface public interface Comparator<T> { // 核心方法，用来比较两个对象，如果o1小于o2，返回负数；等于o2，返回0；大于o2返回正数 int compare(T o1, T o2); // 好像很少用到，一般都用对象自带的equals boolean equals(Object obj); /**-----------下面的都是JDK1.8新增的接口，挑几个放进去----------*/ //返回反向排序比较器 default Comparator<T> reversed() { return Collections.reverseOrder(this); } //根据名字知道，先进行compare比较后，再进行一次比较 default Comparator<T> thenComparing(Comparator<? super T> other) { Objects.requireNonNull(other); return (Comparator<T> & Serializable) (c1, c2) -> { int res = compare(c1, c2); return (res != 0) ? res : other.compare(c1, c2); }; } //对int类型的key进行比较 public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) { Objects.requireNonNull(keyExtractor); return (Comparator<T> & Serializable) (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2)); } //返回正常顺序的比较器 public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() { return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE; } }
一起来看一下如何使用，先来看一下JDK1.8以前的用法：
public class SimpleComparator implements Comparator<Item> { @Override public int compare(Item o1, Item o2) { return o1.price - o2.price; } public static void main(String[] args) { List<Item> items = Arrays.asList(new Item("banana", 200), new Item("apple", 400), new Item("Orange", 100)); Collections.sort(items, new SimpleComparator()); System.out.println(items); } }
上述main函数的输出是：
[Item{name=‘Orange‘, price=100}, Item{name=‘banana‘, price=200}, Item{name=‘apple‘, price=400}]JDK1.8以前的用法要自己手动实现Comparator接口，然后调用Collections.sort()，传入实现类来完成排序，非常麻烦，而JDK1.8则相对来说简单了很多：
public static void main(String[] args) { List<Item> items = Arrays.asList(new Item("banana", 200), new Item("apple", 400), new Item("Orange", 100)); Collections.sort(items, (Item a, Item b) -> a.price - b.price); System.out.println(items); }
甚至，我们可以不使用Collections.sort：
public static void main(String[] args) { List<Item> items = Arrays.asList(new Item("banana", 100), new Item("Orange", 100), new Item("apple", 400), new Item("Orange", 50)); items.sort((Item a, Item b) -> a.price - b.price); System.out.println(items); //使用上面的thenComparing items.sort(Comparator.comparing(Item::getName).thenComparing(Comparator.comparingInt(Item::getPrice))); System.out.println("after using thenComparing: " + items); }
上述main函数的输出：
[Item{name=‘orange‘, price=50}, Item{name=‘banana‘, price=100}, Item{name=‘orange‘, price=100}, Item{name=‘apple‘, price=400}]
after using thenComparing: [Item{name=‘apple‘, price=400}, Item{name=‘banana‘, price=100}, Item{name=‘orange‘, price=50}, Item{name=‘orange‘, price=100}]public interface NavigableMap<K,V> extends SortedMap<K,V> { //返回键小于且最接近Key（不包含等于）的键值对，没有返回null Map.Entry<K,V> lowerEntry(K key); //返回小于且最接近（不包含等于）Key的键，没有返回null K lowerKey(K key); //返回键小于且最接近（包含等于）Key的键值对，没有返回null Map.Entry<K,V> floorEntry(K key); //返回小于且最接近（包含等于）Key的键，没有返回null K floorKey(K key); //返回大于且最接近（包含等于）给定key的键值对，没有返回null Map.Entry<K,V> ceilingEntry(K key); //同上 K ceilingKey(K key); //返回大于且最接近（不包含等于）给定key的键值对 Map.Entry<K,V> higherEntry(K key); //同上 K higherKey(K key); //返回第一个Entry Map.Entry<K,V> firstEntry(); //返回最后一个Entry Map.Entry<K,V> lastEntry(); //移除并返回第一个Entry Map.Entry<K,V> pollFirstEntry(); //同上 Map.Entry<K,V> pollLastEntry(); //返回map中包含的映射关系的逆序视图 NavigableMap<K,V> descendingMap(); //返回map中包含的键的NavigableSet视图。 set的迭代器按key的升序 NavigableSet<K> navigableKeySet(); //逆序 NavigableSet<K> descendingKeySet(); //根据fromKey和toKey来返回子map，两个boolean参数用于是否包含该key NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive); //返回小于（或等于,根据inclusive）toKey的map NavigableMap<K,V> headMap(K toKey, boolean inclusive); //返回大于（或等于,根据inclusive）fromKey的map NavigableMap<K,V> tailMap(K fromKey, boolean inclusive); SortedMap<K,V> subMap(K fromKey, K toKey); SortedMap<K,V> headMap(K toKey); SortedMap<K,V> tailMap(K fromKey); }
注意：上述返回的map与原map是相互影响的。
本章分析了TreeMap的继承关系，给后面分析TreeMap作为铺垫。SortedMap和NavigableMap的接口中，包含了大量的返回Map的方法，这也是作为排序Map的一大特点吧。
【JDK1.8】JDK1.8集合源码阅读——TreeMap（一）
原文：https://www.cnblogs.com/lukelook/p/11094365.html