Java SortedMap
Jakob Jenkov |
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.
| Tweet | |
Jakob Jenkov | |
