NavigableMap与NavigableSet

 

可导航的Map和集合 NavigableMap and NavigableSet

Java集合框架（Java Collections Framework）加入了一个新的NavigableMap和NavigableSet接口。分别的扩展了SortedMap和SortedSet接口，本质上添加了搜索选项到接口。

NavigableMap接口

对于NavigableMap，有3个方法的集合。其中一个方法集合用于获取子Map，另一个集合用于获取Map Entity，最后一个用于设置Map键关联的工作。

在 第一个集合中存在3个方法。首先，navigableHeadMap(toKey)返回一个包含所有的键的NavigableMap，但是不包括 toKey，有一个返回带有所有键的NavigableMap的方法navigableTailMap(fromKey)，从fromKey开始的，一直 到最后一个键的内容。最后，是一个naviagbleSubMap(fromKey,toKey)方法，返回一NavigableMap，从 fromKey开始，结束于toKey（这里是一个半开半闭区间[startKey,endKey)）。感官上，这些方法与SortedMap的 headMap()、tailMap()和subMap()方法相同，但是返回不一样的类型，而不是上面提到的NavigableMap。

这里的第二个方法的集合是和Map的键有关的。对于SortedMap，你有firstKey()和lastKey()来获取某个Map的边界键值。NavigableMap有一些获取键的其他方法：

• ceilingKey(key):用来获取大于或者等于给定的key的第一个键，如果没有的话就返回null。
• floorKey(key):用来获取小于或者等于给定的key的第一个键，如果没有的话就返回null。
• higherKey(key):用来获取大于给定的key的第一个键，如果没有的话就返回null。
• lowerKey(key):用来获取小于给定的key的第一个键，如果没有的话就返回null。

第三个方法的集合可能是最有用的。当需要使用到SortedMap或者Map实例的时候，一般来说，你将获得键和获得对应的值。最后的方法的集合一般都是返回Map。实体实例取代了键。因此，你不必要去进行第二次查找操作。所以，这里有6个方法来操控第二个集合：

• ceilingEntry(key):用于获取大于或等于给定key的第一个实体，如果没有则返回null。
• firstEntry():用于获取Map的第一个实体，如果没有则返回null。
• floorEntry(key):用于获取小于或等于给定的第一个实体key，如果没有则返回null。
• higherEntry():用于获取大于给定的key的第一个实体，如果没有则返回null。
• lastEntry():用于获取Map最后一个实体，如果没有则返回null。
• lowerEntry(key):用于获取小于给定key的第一个实体，如果没有则返回null。

这里有两个单步从Map获取和删除实体的方法。提供了一个简单的不用使用迭代器而遍历所有Map元素的方法。下面是具体的介绍：

• Map.Entry<K,V> pollFirstEntry():获取Map第一个键的实体并且从Map中移除该实体，如果Map为空则返回null。
• Map.Entry<K,V> pollLastEntry():获取Map最后一个键的实体并且从Map移除该实体，如果Map为空则返回null。

另外还有两个值得起到的NavigableMap方法：descendingKeySet()和descendingEntrySet()。keySet()和entrySet()返回的是升序的键的集合，而新的NavigableMap方法是以降序进行工作的。

在Java 6中，这里有两个NavigableMap接口的实现。旧的TreeMap被从NavigableMap中继承而不是原来的SortedMap。另外，一 个该接口的并发的版本现在可以在ConcurrentSkipListMap类中找到。可能你并不熟悉skiplist，它们是一种排序过的链接，使用了 并行链表提高了搜索的速度。但TreeMap的结构是平衡的，并且粗略的从链表中寻找一个键，ConcurrentSkipListMap一直都是从最前 面开始，但是由于副skip list的作用，搜索的效果很接近于二分查找。

下面是一个具体例子，仅供参考:

import java.util.NavigableMap;
import java.util.TreeMap;

public static void main(String[] args) {
NavigableMap<String, Integer> nav = new TreeMap<String, Integer>();
nav.put("aaa", 111);
nav.put("bbb", 222);
nav.put("eee", 333);
nav.put("ccc", 555);
nav.put("ddd", 444);
System.out.printf("Whole list:%s%n", nav);

System.out.printf("First key: %s/tFirst entry: %s%n",nav.firstKey(), nav.firstEntry());

System.out.printf("Last key: %s/tLast entry: %s%n",nav.lastKey(), nav.lastEntry());

System.out.printf("Key floor before bbb: %s%n",nav.floorKey("bbb"));

System.out.printf("Key lower before bbb: %s%n", nav.lowerKey("bbb"));

System.out.printf("Key ceiling after ccc: %s%n",nav.ceilingKey("ccc"));

System.out.printf("Key higher after ccc: %s%n",nav.higherKey("ccc"));
}

输出结果：

Whole list:{aaa=111, bbb=222, ccc=555, ddd=444, eee=333}

First key: aaa First entry: aaa=111

Last key: eee Last entry: eee=333

Key floor before: bbb: bbb

Key lower before: bbb: aaa

Key ceiling after: ccc: ccc

Key higher after: ccc: ddd

NavigableSet接口

NavigableSet 工作类似于NavigableMap，但是没有键值对。在NavigableMap中的3组方法，这里有其中的两组。你可以可以获取一个可导航的子集，带 有navigableHeadSet(toElement), navigableSubSet(fromElement, toElement),和 navigableTailSet(E fromElement)方法。或者你可以获得特定的元素，通过ceiling(element), floor(element), higher(element), 和lower（element)方法。你也可以获取或删除元素，通过pollFirst()和pollLast()方法，升序的迭代 descendingIterator()补充了iterator()。

在表面之下，CouncurrentSkipListSet使用ConcurrentSkipListSet来完成所有的工作。