绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
Java集合源码分析之Map(二):SortedMap与NavigableMap
2020-04-29 09:37:44

SortedMap

由于乱序的数据对查找不利,例如无法使用二分法等降低算法的时间复杂度,如果数据在插入时就排好顺序,查找的性能就会提升很多。SortedMap接口就是为这种有序数据服务的。

SortedMap接口需要数据的key支持Comparable,或者可以被指定的Comparator接受。SortedMap主要提供了以下方法:

// 返回排序数据所用的Comparator
Comparator<? super K> comparator();

// 返回在[fromKey, toKey)之间的数据
SortedMap<K,V> subMap(K fromKey, K toKey);

// 返回从第一个元素到toKey之间的数据
SortedMap<K,V> headMap(K toKey);

// 返回从fromKey到末尾之间的数据
SortedMap<K,V> tailMap(K fromKey);

//返回第一个数据的key
firstKey();

//返回最后一个数据的key
lastKey();

SortedMap主要提供了获取子集,以及获取最大值(最后一个值)和最小值(第一个值)的方法。

NavigableMap

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

NavigableMap主要有以下方法:

// 找到第一个比指定的key小的值
Map.Entry<K,V> lowerEntry(K key);

// 找到第一个比指定的key小的key
lowerKey(K key);

// 找到第一个小于或等于指定key的值
Map.Entry<K,V> floorEntry(K key);

// 找到第一个小于或等于指定key的key
floorKey(K key);

//  找到第一个大于或等于指定key的值
Map.Entry<K,V> ceilingEntry(K key);

ceilingKey(K key);

// 找到第一个大于指定key的值
Map.Entry<K,V> higherEntry(K key);

higherKey(K key);

// 获取最小值
Map.Entry<K,V> firstEntry();

// 获取最大值
Map.Entry<K,V> lastEntry();

// 删除最小的元素
Map.Entry<K,V> pollFirstEntry();

// 删除最大的元素
Map.Entry<K,V> pollLastEntry();

//返回一个倒序的Map
NavigableMap<K,V> descendingMap();

// 返回一个Navigable的key的集合,NavigableSet和NavigableMap类似
NavigableSet<K> navigableKeySet();

// 对上述集合倒序
NavigableSet<K> descendingKeySet();


现在,我们对Map的继承结构有了一定的了解,接下来就看看TreeMap,HashMap是如何实现这些方法的吧。接下来的知识依赖于红黑树,如果你已经忘了红黑树,就翻看前面的文章,先补补课哈。



分享好友

分享这个小栈给你的朋友们,一起进步吧。

飞机酱的IT之旅
创建时间:2020-04-28 18:20:39
飞机酱是一个Android开发攻城狮,除了要攻陷Android外,还会进攻数据结构、算法、网络、计算机系统等方面的知识。关注我,一起学IT吧。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 大大纸飞机
    栈主

小栈成员

查看更多
  • ☀️
  • 小雨滴
  • 人工智能频道
  • 栈栈
戳我,来吐槽~