hen I heard about the two new navigable interfaces, NavigableSet and NavigableMap, that were going to be released with the collections framework in Java SE 6, I wondered how I would have used them in my previous Java implementations. If the navigable interfaces sounded like some GPS library classes to you, you’re not alone?I thought the same thing. Actually, navigable interfaces provide methods to retrieve a view of either a map based on a range of keys or a subset of a set based on a range of entries.

ConcurrentSkipListMap and TreeMap implement the NavigableMap interface, while ConcurrentSkipListSet and TreeSet implement the NavigableSet interface. TreeSet is implemented on top of TreeMap and ConcurrentSkipListSet using ConcurrentSkipListMap.

So the question then is, as a Java application developer, where in a real development scenario would I use a NavigableSet or a NavigableMap? This article provides the answer, which I found somewhat disappointing.

Navigable Interfaces in the Real World
Suppose you want to look up a range of employees from 564566 to 606000 using a map with EmployeeId as the key and an EmployeeInfo object as the value. Listing 1 shows the code for this task using the TreeMap implementation of NavigableMap.

The key methods I want to emphasize here are subSet and subMap. As you can see in Listing 1, you do not have to iterate when you use the subMap method, which results in a faster implementation. You also can use the subMap method to look up an employee list based on an employee range or in a page wise display sorted by EmployeeIds.

For a more sophisticated development scenario in which you would use a NavigableMap, suppose you are developing a configuration UI that displays in a tabbed view database and networking parameters. Say you use the Properties class (which is an implementation of the thread safe HashTable) and a thread safe ConcurrentSkipListMap class, and then compare their performances (see Listing 2).

The code to obtain the map containing only network parameters is very simple:

map.subMap(paramType, new String("" + (char)(paramType.charAt(0)+1))) 

It is equivalent to map.subMap(“Network_Params, “O”).

On the other hand, you have to iterate through the Properties object to obtain all the parameters starting with “Network Params”.

Not only are keys in ConcurrentSkipListMap sorted alphabetically, but ConcurrentSkipListMap also is on the order of two to three times faster than the Properties class. You can see the performance for yourself by executing the code.

The disadvantage with NavigableMap is that the subMap method has no provision for returning a map based on a range of values rather than on keys. Therefore, implementing something similar to database views is laborious. I find this limiting, as most of the time I want a view of a map based on the attribute of values rather than keys. For example, if I am implementing a scheduler that maintains a map of JobId to JobInfo objects consisting of status and priority of job, there is no direct way to fetch a map of JobIds whose status is complete. So, instead of NavigableMap, I was forced to use a NavigableSet of Jobs with a custom Comparator implementation.

Listing 3 shows an example of an in-memory NavigableSet that holds jobs.

There are two classes, PriorityComparator and StatusComparator, for fetching result sets sorted by priority and status, respectively. For example, the following statement:

list.subSet(Job.INPROGESS_JOB, Job.FAILED_JOB)

Is the same as this:

list.subSet(list.floor(Job.INPROGESS_JOB), false, list.floor(Job.FAILED_JOB), true)

I wish there was a simple method to look up a set matching a specific pattern. All I have are the tailSet(key) and headSet(key) methods, which are not very useful in this scenario.

NavigableMap and NavigableSet expect the custom Comparator to be passed to the constructor. It would be handy if the subMap or subSet methods took Comparator as a parameter instead. That way, I wouldn’t have to create a new NavigableMap/NavigableSet instance.

Not Quite Enough to Sell Me
In short, the new navigable interfaces are useful wherever you have in-memory cached data and you want to perform range-based queries upon keys of a map or entries of a set. However, I don’t think that’s a compelling enough functionality to use them. I would be more excited about the new interfaces if both sets and lists implemented them (currently, only sets implement them). I also would be a more eager navigables interface user if they featured a simple associative lookup method to fetch a map or set based on key/entry patterns.

To their credit, however, you can take advantage of algorithmic enhancements such as the added thread safe versions, the ConcurrentSkipListMap and ConcurrentSkipListSet classes. ConcurrentSkipListMap is based on an efficient Skip list data structure.