一、SortedMap接口

1、SortedMap概述

SortedMap继承Map接口，是Collection框架的成员之一。

SortedMap提供有序的Map实现，是对Map集合中键进行总体排序后的映射。

Map的主要实现有HashMap,TreeMap,HashTable,LinkedHashMap。其中的TreeMap实现了SortedMap接口，保证了有序性。默认的排序是根据Key值进行生序排序，也可以重写comparator方法来根据value进行排序。

由于乱序的数据对查找不利，例如无法使用二分法等降低算法的时间复杂度，如果数据在插入时就排好顺序，查找的性能就会提升很多。SortedMap接口就是为这种有序数据服务的，和SortedSet有异曲同工之妙，都是根据键的自然顺序进行排序，或者由通常在排序映射创建时提供的比较器进行排序。这个顺序在遍历排序映射的集合视图(由entrySet、keySet和values方法返回)时可以被体现出来。

SortedMap的子接口：

SortedMap的实现类包括：ConcurrentSkipListMap, TreeMap。其中TreeMap是常用的实现类。

2、SortedMap接口使用原则：

SortedMap接口需要数据的键(key)需要支持Comparable接口，或者可以被指定的Comparator接受，即SortedMap使用需要遵守如下原则：

• 插入到排序映射中的所有键都必须实现Comparable接口(或被指定的比较器接受)。
• 此外，所有这些键必须是相互可比的，即可以执行k1. compareto (k2)或comparator.compare(k1, k2)操作。
• 不能对排序映射中的任何键k1和k2抛出ClassCastException。尝试违反此限制将导致违规的方法或构造函数调用抛出ClassCastException异常。

3、SortedMap接口的方法

（1）集于排序特征的方法

修饰符/类型	方法	说明
Comparator<? super K>	comparator()	返回排序数据所用的Comparator
Set<Map.Entry<K,V>>	entrySet()	返回此映射中包含的映射的集合视图。
Set	keySet()	返回此映射中包含的键的集合视图。
SortedMap<K,V>	subMap(K fromKey, K toKey)	返回在[fromKey, toKey)之间的数据
SortedMap<K,V>	headMap(K toKey)	返回从第一个元素到toKey之间的数据
SortedMap<K,V>	tailMap(K fromKey)	返回从fromKey到末尾之间的数据
K	firstKey()	返回第一个数据的key
K	lastKey()	返回最后一个数据的key

（2）继承自Map接口的方法

SortedMap还有一些继承自Map接口的方法：

clear, compute, computeIfAbsent, computeIfPresent, containsKey, containsValue, equals, forEach, get, getOrDefault, hashCode, isEmpty, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll, size

上述方法的详细描述请查看Map概述的Map方法部分内容。

⚠️注意，如果排序的映射要正确实现map接口，则排序映射(无论是否提供显式比较器)维护的顺序必须与equals一致。之所以如此，是因为映射接口是根据equals操作定义的，当使用compareTo(或compare)方法执行所有键比较时，方法视为相等的两个键，从排序映射的角度来看就是相等的。

3、排序映射实现类的“标准”构造函数

所有通用的排序映射实现类都应该提供四个“标准”构造函数：

• 一个void(无参数)构造函数：它创建一个空的排序映射，该映射按照其键的自然顺序排序。

• 具有一个比较器类型参数的构造函数：它创建一个空的排序映射，该映射根据指定的比较器排序。

• 有一个参数类型为Map的构造函数：它创建一个新映射，其中具有与其参数相同的键-值映射，并根据键的自然顺序排序。

• 有一个参数类型为SortedMap的构造函数：它创建一个新的排序映射，具有与输入排序映射相同的键-值映射和排序。

⚠️注意：有几个方法返回键范围受限的子映射。他们的范围是半开的，也就是说，它们是下包含上不包含的（左闭右开的）。如果需要一个上下都包含的范围，可以通过重写方法实现。

二、NavigableMap接口

1、NavigableMap接口概述

SortedMap提供了获取最大值与最小值的方法，但对于一个已经排序的数据集，除了最大值与最小值之外，我们可以对任何一个元素，找到比它小的值和比它大的值，还可以按照按照原有的顺序倒序排序等。

NavigableMap就为我们提供了这些功能，他在继承SortedMap接口的基础之上，扩展了一些返回了给定搜索目标的最接近匹配项的方法。从上下图可以看到，Navigable接口也是TreeMap类直接实现的接口。返回给定搜索目标的最近匹配项：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IP0yXYI7-1604992847730)(/Users/changchunlai/Desktop/pic/10 泛型与集合/Map接口的实现类.png)]

2、NavigableMap接口方法

（1）NavigableMap所有方法

修饰符/类型	方法	描述
Map.Entry<K,V>	ceilingEntry(K key)	返回与大于或等于给定键的最小键相关联的键-值映射，如果没有这样的键，则返回null。
K	ceilingKey(K key)	返回大于或等于给定键的最小键，或者如果没有这样的键，返回null。
NavigableSet	descendingKeySet()	返回一个颠倒顺序的NavigableSet 在这个映射中包含的键视图。
NavigableMap<K,V>	descendingMap()	返回此映射中包含的映射的逆序视图。
Map.Entry<K,V>	firstEntry()	返回与此映射中最小键关联的键-值映射，如果映射为空，则返回null。
Map.Entry<K,V>	floorEntry(K key)	返回与小于或等于给定键的最大键相关联的键-值映射，如果没有这样的键，则返回null。
K	floorKey(K key)	返回小于或等于给定键的最大键，或者如果没有这样的键，返回null。
SortedMap<K,V>	headMap(K toKey)	返回key严格小于toKey 的映射部分的视图。
NavigableMap<K,V>	headMap(K toKey, boolean inclusive)	返回此映射的键值小于(或等于)toKey部分的视图。
Map.Entry<K,V>	higherEntry(K key)	返回与严格大于给定键的最小键相关联的键-值映射，如果没有这样的键，则返回null。
K	higherKey(K key)	返回严格大于给定键的最小键，如果没有这样的键，则返回null。
Map.Entry<K,V>	lastEntry()	返回与此映射中最大键相关联的键值映射，如果映射为空，则返回null。
Map.Entry<K,V>	lowerEntry(K key)	返回与严格小于给定键的最大键相关联的键-值映射，如果没有这样的键，则返回null。
K	lowerKey(K key)	返回严格小于给定键的最大键，如果没有这样的键，返“null。
NavigableSet	navigableKeySet()	返回这个Map中包含的键的导航视图。
Map.Entry<K,V>	pollFirstEntry()	删除和返回与此映射中最小键关联的键-值映射，如果映射为空，则返回null。
Map.Entry<K,V>	pollLastEntry()	删除和返回与此映射中最大键相关联的键值映射，如果映射为空，则返回null。
NavigableMap<K,V>	subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)	返回键范围从 fromKey 到toKey 的映射部分的视图。
SortedMap<K,V>	subMap(K fromKey, K toKey)	返回该映射的键范围从[fromKey , toKey) 部分的视图。
SortedMap<K,V>	tailMap(K fromKey)	返回键值大于或等于fromKey 的那部分映射的视图。
NavigableMap<K,V>	tailMap(K fromKey, boolean inclusive)	返回此映射的键值大于或等于fromKey的部分的视图。

上述方法中，有部分是重新定义的SortedMap的方法：

• SortedMap<K,V> subMap(K fromKey, K toKey);

• SortedMap<K,V> headMap(K toKey);

• SortedMap<K,V> tailMap(K fromKey);

（2）从java.util.SortedMap中继承的方法

comparator, entrySet, firstKey, keySet, lastKey, values

上述的方法的详细描述可以在本篇内容的SortedMap部分内容中查看。

（3）从Map接口中继承的方法

clear, compute, computeIfAbsent, computeIfPresent, containsKey, containsValue, equals, forEach, get, getOrDefault, hashCode, isEmpty, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll, size

从Map中继承的方法，详细描述可以在Map接口详述查看，这里就过多的赘述了。