CodingBison - Sorted Map

A SortedMap interface is one of the widely used Collection interfaces. We highly recommended that you should go through its parent interface, Map Interface, before getting into the details of a SortedMap interface. As shown in the figure below, SortedMap interface extends Map interface. Accordingly, it inherits all the operations from Map interface. A SortedMap inherits all the basic/fundamental concepts from a Map, so in a SortedMap (like a Map) Each "key" in the Map object, can at most relates/maps/corresponds to one "value", a SortedMap cannot contain duplicate keys.

Figure: Map Interfaces and Classes

Things To Remember

All the "Keys" in a SortedMap are ordered using their natural ordering.

You might ask, how does a SortedMap compare with a Map then? Well, a SortedMap brings in the extra feature of sorting to the map. So, all the keys of a SortedMap are ordered using their natural ordering. Because all the keys of a SortedMap would be in a particular order, the keys should be comparable; a SortedMap cannot contain any "Keys" that cannot be comparable. Thus, if we have two keys (let us say, key1 and key2), then key1.compareTo(key2) or comparator.compare(key1, key2) must not throw "ClassCastException".

In order to get more information about the natural ordering, please go through the Comparable and Comparator interfaces. The ordering of the keys can be noticed when iterating over a SortedMap.

Methods defined in Sorted Map interface

The SortedMap interface inherits all the methods from the Map interface; these Map methods are put(), putIfAbsent(), putAll(), get(), entrySet(), keySet(), remove(), clear(), replace(), etc. These methods are defined in the method table for the Map: Map Interface Methods List. However, the SortedMap also defines its own properties that are added on top of the Map interface. The below table lists the methods that are additionally defined by the interface SortedMap. One can imagine this table to be an extension of the above-mentioned table.

Table: Methods defined by Sorted Map Interface
Method	Description
Comparator comparator()	Returns the comparator used to order the keys. Returns null if natural ordering is used.
<k key> firstKey()	Returns the first(lowest) key in the SortedMap
<k key> lastKey()	Returns the last(highest) key in the SortedMap
SortedMap headMap(k key)	Returns the view of the SortedMap, whose keys are less than the key passed as the parameter
SortedMap tailMap(k Key)	Returns the view of the SortedMap, whose keys are greater or equal to the key passed as the parameter
SortedMap subMap(k from, k to)	Returns the view of the SortedMap, whose keys are in the range "from" and "to" that are passed as parameters

Like shown in the figure at the beginning of this page, the NavigableMap interface extends the SortedMap interface and the class that implements these interfaces is "TreeMap" Class; more details about TreeMap class is available here understanding TreeMap. Here is an Example program that demonstrates the usage of the above mentioned operations. Since Sortedmap and NavigableMap are interfaces, we use the TreeMap class in our example and demonstrate the usage of the methods defined by the SortedMap interface.

 import java.util.TreeMap;

 public class SortedMapDemo {
     public static void main(String[] args) {
         TreeMap tmapObj1 = new TreeMap();

         tmapObj1.put(1237,"John");
         tmapObj1.put(2013,"Ray");
         tmapObj1.put(1024,"Mike");
         //tmapObj1.put("1","Chris");

         System.out.println(" Treemap1: " + tmapObj1);
         System.out.println(" First Key: " + tmapObj1.firstKey());
         System.out.println(" Last Key: " + tmapObj1.lastKey());
         System.out.println(" Sub map: " + tmapObj1.subMap(1024, 2013));
         System.out.println(" Tail map: " + tmapObj1.tailMap(1237));
         System.out.println(" Head map: " + tmapObj1.headMap(1237));
     }
 }

Things To Remember

All the keys in a SortedMap must be mutually comparable, which implies, key1.compareTo(key2) or comparator.compare(key1,key2) must not throw "ClassCastException".

The above program also demonstrates another important property of the SortedMap interface. If you notice, tmapObj1, the keys of the SortedMap (1237, 2013, and 1024) are mutually comparable -- they are all integers. This implies that key1.compareTo(key2) or comparator.compare(key1, key2) must not throw "ClassCastException". Uncomment the commented line "tmapObj1.add(1);" in the above program and try to run it. The example program throws "java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer" exception. In other works, the String('1') cannot be compared with Integer classes like "1237" or "1024".

Let us compile/run the program. If we look at the output (provided below), we can see that the keys of the map are in sorted order. This is the basic difference between a Map vs a SortedMap.

  Treemap1: {1024=Mike, 1237=John, 2013=Ray}
  First Key: 1024
  Last Key: 2013
  Sub map: {1024=Mike, 1237=John}
  Tail map: {1237=John, 2013=Ray}
  Head map: {1024=Mike}