Java SortedMap

Jakob Jenkov
Last update: 2019-10-17

The Java SortedMap interface, java.util.SortedMap, is a subtype of the java.util.Map interface, with the addition that the elements stored in a Java SortedMap map are sorted internally. This means you can iterate the elements stored in a SortedMap in the sort order.

The TreeMap SortedMap Implementation

Java comes with a built-in implementation of the Java SortedMap interface called TreeMap (java.util.TreeMap).

Create a TreeMap

You instantiate a TreeMap instance via its constructor. Here is an example of creating a Java TreeMap instance, which implements the SortedMap interface:

SortedMap sortedMap = new TreeMap();

Create a TreeMap With Comparator

It is possible to pass a Comparator implementation to the TreeMap constructor. This Comparator will then be used to sort the keys of the key, value pairs stored in the SortedMap. Here is an example of creating a Java TreeMap with a Comparator:

Comparator comparator = new MyComparatorImpl();

SortedMap sortedMap = new TreeMap(comparator);

Sort Order

The order of the sorting in a Java SortedMap is either the natural sorting order of the elements (if they implement java.lang.Comparable), or the order determined by a Comparator that you can give to the SortedSet.

Ascending vs. Descending Sort Order

By default the elements are iterated in ascending order, starting with the "smallest" and moving towards the "largest". But it is also possible to iterate the elements in descending order using the method TreeMap.descendingKeySet().

Iterate a SortedMap

You iterate a Java SortedMap just like you iterate a normal Java Map. Since the keys of a SortedMap are sorted, you will most likely want to iterate the keys in their sorted order. You iterate the keys of a SortedMap by calling its keySet() method, like this:

SortedMap sortedMap = new TreeMap();

sortedMap.put("a", "one");
sortedMap.put("b", "two");
sortedMap.put("c", "three");

Iterator iterator = sortedMap.keySet().iterator();

while(iterator.hasNext()) {
    String key   = (String) iterator.next();

    String value = (String) sortedMap.get(key);
}

Remember, if you want to iterate the keys in descending order rather than ascending order, use the sortedMap.descendingKeySet().iterator() method, like this:

SortedMap sortedMap = new TreeMap();

sortedMap.put("a", "one");
sortedMap.put("b", "two");
sortedMap.put("c", "three");

Iterator iterator = sortedMap.descendingKeySet().iterator();

while(iterator.hasNext()) {
    String key   = (String) iterator.next();

    String value = (String) sortedMap.get(key);
}

Get Comparator Used

If your Java SortedMap was created using a Comparator, you can obtain the Comparator used via the SortedMap comparator() method. Here is an example of obtaining the Comparator used by a SortedMap via its comparator() method:

Comparator comparator = sortedMap.comparator();

Get First Key

The SortedMap interface has a shortcut method to obtain the first (lowest) key in the key set of the SortedMap. This method is named firstKey(). Here is an example of obtaining the first key of a SortedMap via its firstKey() method:

String firstKey = (String) sortedMap.firstKey();

Get Last Key

The SortedMap interface has a shortcut method to obtain the last (highest) key in the key set of the SortedMap. This method is named lastKey(). Here is an example of obtaining the last key of a SortedMap via its lastKey() method:

String lastKey = (String) sortedMap.lastKey();

Head Map

The SortedMap interface has a method named headMap() which returns a new Map which contains the first elements of the SortedMap according to the sort order used. The headMap() method takes a parameter that acts as a delimiter for what elements gets included in the returned head map. All elements with a key that is smaller than / earlier than the parameter passed to the headMap() method. Here is an example of obtaining a head map from a SortedMap via its headMap() method:

SortedMap sortedMap = new TreeMap();

sortedMap.put("a", "1");
sortedMap.put("c", "3");
sortedMap.put("e", "5");
sortedMap.put("d", "4");
sortedMap.put("b", "2");

SortedMap headMap = sortedMap.headMap("c");

System.out.println(headMap);

The head map returned will contain the key, value pairs ("a", "1") and ("b", "2"), since the keys "a" and "b" are smaller than / earlier than "c" in the sort order (natural order) used by this SortedMap .

Tail Map

The SortedMap interface has a method named tailMap() which returns a new Map which contains the last elements of the SortedMap according to the sort order used. The tailMap() method takes a parameter that acts as a delimiter for what elements gets included in the returned tail map. All elements with a key that is equal to or larger than the parameter passed to the tailMap() method. Here is an example of obtaining a tail map from a SortedMap via its tailMap() method:

SortedMap sortedMap = new TreeMap();

sortedMap.put("a", "1");
sortedMap.put("c", "3");
sortedMap.put("e", "5");
sortedMap.put("d", "4");
sortedMap.put("b", "2");

SortedMap tailMap = sortedMap.tailMap("c");

System.out.println(tailMap);

The tail map returned will contain the key, value pairs ("c", "3"), ("d", "4") and ("e", "5"), since "c", "d" and "e" are larger than or equal to the "c" passed as parameter to tailMap() .

Submap

The Java SortedMap also has a method named subMap() which can return a new Map which is a submap of the SortedMap. The subMap() method takes two parameters which act as delimiters for what elements are included in the returned submap. The submap will include all elements which have a key that is equal to or larger than the first parameter, and smaller than the second parameter. Here is an example of obtaining a submap from a Java SortedMap via its subMap() method:

SortedMap sortedMap = new TreeMap();

sortedMap.put("a", "1");
sortedMap.put("c", "3");
sortedMap.put("e", "5");
sortedMap.put("d", "4");
sortedMap.put("b", "2");

SortedMap subMap = sortedMap.subMap("b", "e");

System.out.println(subMap);

The returned submap will contain the key, value pairs ("b", "2), ("c", "3") and ("d", "4") since the keys "b", "c" and "d" are equal to or larger than "b", and smaller than "e".

More Details in the JavaDoc

There is actually a lot more you can do with a TreeMap that is not part of the SortedMap interface, like getting a descending key set etc. Check out the JavaDoc's for more detail about these features.

Jakob Jenkov

Featured Videos

Java Generics

Java ForkJoinPool

P2P Networks Introduction



















Close TOC
All Tutorial Trails
All Trails
Table of contents (TOC) for this tutorial trail
Trail TOC
Table of contents (TOC) for this tutorial
Page TOC
Previous tutorial in this tutorial trail
Previous
Next tutorial in this tutorial trail
Next