Section 16.3. SortedMap and NavigableMap

16.3. SortedMap and NavigableMap

Like SortedSet, the subinterface SortedMap (see Figure 16.5) adds to its contract a guarantee that its iterators will traverse the map in ascending key order. Its definition is similar to that of SortedSet, with methods such as firstKey and headMap corresponding to the SortedSet methods first and headSet. Also like SortedSet, the SortedMap interface has been extended in Java 6 by the subinterface NavigableMap (see Figure 16.6). This section is structured like Section 13.2 for the same reasons: SortedMap has been made obsolete by NavigableMap, but it may be helpful for developers prevented for the moment from using Java 6 to have the two interfaces treated separately.

Figure 16-5. SortedMap

Figure 16-6. NavigableMap

A SortedMap imposes an ordering on its keys, either that of their natural ordering or of a Comparator; but in either case the compare method must be consistent with equals, as the SortedMap will use compare to determine when a key is already in the map.

The extra methods defined by the SortedMap interface fall into three groups:

Getting the First and Last Elements

 K firstKey() K lastKey() 

If the set is empty, these operations throw a NoSuchElementException.

Retrieving the Comparator

 Comparator<? super K> comparator() 

This method returns the map's key comparator if it has been given one, instead of relying on the natural ordering of the keys. Otherwise, it returns null.

Finding Subsequences

 SortedMap<K,V> subMap(K fromKey, K toKey) SortedMap<K,V> headMap(K toKey) SortedMap<K,V> tailMap(K fromKey) 

These operations work like the corresponding operations in SortedSet: the key arguments do not themselves have to be present in the map, and the sets returned include the fromKeyif, in fact, it is present in the mapand do not include the toKey.

16.3.1.

16.3.1.1. NavigableMap

NavigableMap (see Figure 16.6) extends and replaces SortedMap, in the same way as NavigableSet replaces SortedSet. Its methods correspond almost exactly to those of NavigableSet, regarding the map as a set of key-value associations represented by Map.Entry objects. So where a NavigableSet method returns an element of the set, the corresponding NavigableMap method return a result of type Map.Entry. Until now, objects of this type were only obtainable by iterating over the set returned by Map.entrySet, and were specified to become invalid in the face of concurrent modification of the map. This specification is not appropriate to Map.Entry objects returned by the new methods, and the contract for NavigableMap acknowledges this by specifying that the Map.Entry objects returned by its methods are snapshot objects reflecting the state of the map at the time they were produced, and do not support setValue.

The methods added by NavigableMap can be divided into four groups.

Getting the First and Last Elements

 Map.Entry<K,V> pollFirstEntry() Map.Entry<K,V> pollLastEntry() Map.Entry<K,V> firstEntry() Map.Entry<K,V> lastEntry() 

The first two methods are analogous to pollFirst and pollLast in NavigableSet. The last two were introduced because the emphasis in NavigableMap on making map entries available requires entry-returning methods corresponding to the key-returning methods first and last inherited from SortedMap.

Getting Range Views

 NavigableMap<K,V> subMap(             K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) NavigableMap<K,V> headMap(K toKey, boolean inclusive) NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) 

Like the NavigableSet methods, these provide more flexibility than the range-view methods of SortedMap. Instead of always returning a half-open interval, these methods accept boolean parameters that are used to determine whether to include the key or keys defining the interval.

Getting Closest Matches

 Map.Entry<K,V> ceilingEntry(K Key) K ceilingKey(K Key) Map.Entry<K,V> floorEntry(K Key) K floorKey(K Key) Map.Entry<K,V> higherEntry(K Key) K higherKey(K Key) Map.Entry<K,V> lowerEntry(K Key) K lowerKey(K Key) 

These are similar to the corresponding closest-match methods of NavigableSet, but they return Map.Entry objects. If you want the key belonging to one of these entries, use the corresponding convenience key-returning method, with the performance benefit of allowing the map to avoid the unnecessary creation of a Map.Entry object.

Navigating the Map

 NavigableMap<K,V> descendingMap()  // return a reverse-order view of the map NavigableSet<K> descendingKeySet() // return a reverse-order key set 

There is also a new method defined to obtain a NavigableSet of keys:

 NavigableSet<K> navigableKeySet()  // return a forward-order key set 

You might wonder why the method keySet, inherited from Map, could not simply be overridden using a covariant return type to return a NavigableSet. Indeed, the platform implementations of NavigableMap.keySet do return a NavigableMap. But there is a compatibility concern: if TReeMap.keySet were to have its return type changed from Set to NavigableSet, any existing treeMap subclasses which override that method would now fail to compile unless they too changed their return type. (This concern is similar to those discussed in Section 8.4.)

16.3.1. TreeMap

SortedMap is implemented in the Collections Framework by treeMap. We met trees as a data structure for storing elements in order when we discussed TReeSet (see Section 13.2.1). In fact, the internal representation of a treeSet is just a TReeMap in which every key is associated with the same standard value, so the explanation of the mechanism and performance of red-black trees given in Section 13.2.1 applies equally here.

The constructors for TReeMap include, besides the standard ones, one that allows you to supply a Comparator and one that allows you to create one from another SortedMap, using both the same comparator and the same mappings:

 public TreeMap(Comparator<? super K> comparator) public TreeMap(SortedMap<K, ? extends V> m) 

Notice that the second of these constructors suffer from a similar problem to the corresponding constructor of TReeSet (see Section 13.2.1), because the standard conversion constructor always uses the natural ordering of the keys, even when its argument is actually a SortedMap.

treeMap has similar performance characteristics to TReeSet: the basic operations (get, put, and remove) perform in O(log n) time). The collection view iterators are fail-fast.