Tech and Media Labs
This site uses cookies to improve the user experience.




Java Collections - NavigableMap

Jakob Jenkov
Last update: 2015-02-01

The java.util.NavigableMap interface is a subtype of the java.util.SortedMap interface. It has a few extensions to the SortedSet which makes it possible to navigate the map. I will take a closer look at these navigation methods in this text.

The java.util package only has one implementation of the NavigableMap interface: java.util.TreeMap. There is an implementation in the java.util.concurrent package but that is outside the scope of this trail.

Here is a list of the topics covered in this text:

  1. descendingKeySet() and descendingMap()
  2. headMap(), tailMap() and subMap()
  3. ceilingKey(), floorKey(), higherKey() and lowerKey()
  4. ceilingEntry(), floorEntry(), higherEntry() and lowerEntry()
  5. pollFirstEntry() and pollLastEntry()
  6. More detail in the JavaDoc

descendingKeySet() and descendingMap()

The first interesting navigation methods are the descendingKeySet() and descendingMap() methods.

The descendingKeySet() method returns a NavigableSet in which the order of the elements is reversed compared to the original key set. The returned "view" is backed by the original NavigableSet ket set, so changes to the descending set are also reflected in the original set. However, you should not remove elements directly from the key set. Use the Map.remove() method instead.

Here is a simple example:

NavigableSet reverse = map.descendingKeySet();

The descendingMap() method returns a NavigableMap which is a view of the original Map. The order of the elements in this view map is reverse of the order of the original map. Being a view of the original map, any changes to this view is also reflected in the original map.

Here is a simple example:

NavigableMap descending = map.descendingMap();

headMap(), tailMap() and subMap()

The headMap() method returns a view of the original NavigableMap which only contains elements that are "less than" the given element. Here is an example:

NavigableMap original = new TreeMap();
original.put("1", "1");
original.put("2", "2");
original.put("3", "3");

//this headmap1 will contain "1" and "2"
SortedMap headmap1 = original.headMap("3");

//this headmap2 will contain "1", "2", and "3" because "inclusive"=true
NavigableMap headmap2 = original.headMap("3", true);

The tailMap() method works the same way, except it returns all elements that are higher than the given parameter element.

The subMap() allows you to pass two parameters demarcating the boundaries of the view map to return. Here is an example:

NavigableMap original = new TreeMap();
original.put("1", "1");
original.put("2", "2");
original.put("3", "3");
original.put("4", "4");
original.put("5", "5");

//this submap1 will contain "3", "3"
SortedMap    submap1  = original.subMap("2", "4");

//this submap2 will contain ("2", "2") ("3", "3") and ("4", "4") because
//    fromInclusive=true, and toInclusive=true
NavigableMap submap2 = original.subMap("2", true, "4", true);

ceilingKey(), floorKey(), higherKey() and lowerKey()

The ceilingKey() method returns the least (smallest) key in this map that is greater than or equal to the element passed as parameter to the ceilingKey() method. Here is an example:

NavigableMap original = new TreeMap();
original.put("1", "1");
original.put("2", "2");
original.put("3", "3");


//ceilingKey will be "2".
Object ceilingKey = original.ceilingKey("2");

//floorKey will be "2".
Object floorKey = original.floorKey("2");

The floorKey() method does the opposite of ceilingKey()

The higherKey() method returns the least (smallest) element in this map that is greater than (not equal too) the element passed as parameter to the higherKey() method. Here is an example:

NavigableMap original = new TreeMap();
original.put("1", "1");
original.put("2", "2");
original.put("3", "3");


//higherKey will be "3".
Object higherKey = original.higherKey("2");

//lowerKey will be "1"
Object lowerKey = original.lowerKey("2");

The lowerKey() method does the opposite of the higherKey() method.


celingEntry(), floorEntry(), higherEntry(), lowerEntry()

The NavigableMap also has methods to get the entry for a given key, rather than the key itself. These methods behave like the ceilingKey() etc. methods, except they return an Map.Entry instead of the key object itself.

A Map.Entry maps a single key to a single value.

Here is a simple example. For more details, check out the JavaDoc.

NavigableMap original = new TreeMap();
original.put("1", "1");
original.put("2", "2");
original.put("3", "3");


//higherEntry will be ("3", "3").
Map.Entry higherEntry = original.higherEntry("2");

//lowerEntry will be ("1", "1")
Map.Entry lowerEntry = original.lowerEntry("2");

pollFirstEntry() and pollLastEntry()

The pollFirstEntry() method returns and removes the "first" entry (key + value) in the NavigableMap or null if the map is empty. The pollLastEntry() returns and removes the "last" element in the map or null if the map is empty. "First" means smallest element according to the sort order of the keys. "Last" means largest key according to the element sorting order of the map.

Here are two examples:

NavigableMap original = new TreeMap();
original.put("1", "1");
original.put("2", "2");
original.put("3", "3");


//first is ("1", "1")
Map.Entry first = original.pollFirstEntry();

//last is ("3", "3")
Map.Entry last = original.pollLastEntry();

More Detail in the JavaDoc

There are still a few interesting methods left in the NavigableMap interface that I have not covered here. For instance, the firstEntry() and lastEntry() methods. You can check out these last methods in the official JavaDoc.

Jakob Jenkov




Copyright  Jenkov Aps
Close TOC