The SortedMap interface in Java is part of the java.util package and is a specialized version of the Map interface. As the name suggests, the SortedMap interface ensures that the entries (key-value pairs) are maintained in a sorted order based on the natural ordering of the keys or by a custom comparator provided during map construction.
In this tutorial, we will cover:
Overview of the SortedMap interface.
Common methods in SortedMap.
Implementations of SortedMap (TreeMap).
Code examples demonstrating common SortedMap operations.
Table of Contents
1. SortedMap Interface Overview
A SortedMap sorts its keys either by their natural ordering (which requires the keys to implement Comparable) or by a custom Comparator.
The keys must be unique, and the sorting is done in ascending order by default.
Common Implementations of SortedMap
TreeMap: This is the most common implementation of SortedMap. It stores key-value pairs in a tree structure (Red-Black Tree), ensuring that the keys are sorted.
2. Common Methods in SortedMap
Apart from the usual Map interface methods, SortedMap provides some additional methods related to the sorting of keys:
Comparator<? super K> comparator(): Returns the comparator used to order the keys, or null if natural ordering is used.
K firstKey(): Returns the first (lowest) key in the map.
K lastKey(): Returns the last (highest) key in the map.
SortedMap<K, V> headMap(K toKey): Returns a view of the portion of the map whose keys are strictly less than toKey.
SortedMap<K, V> tailMap(K fromKey): Returns a view of the portion of the map whose keys are greater than or equal to fromKey.
SortedMap<K, V> subMap(K fromKey, K toKey): Returns a view of the portion of the map whose keys range from fromKey (inclusive) to toKey (exclusive).
3. TreeMap Implementation of SortedMap
The TreeMap class is the most commonly used implementation of the SortedMap interface. It maintains the entries in a sorted order based on the natural ordering of the keys or a custom comparator.
Example 1: Basic TreeMap Operations
import java.util.SortedMap;
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
// Creating a TreeMap (SortedMap) of strings to integers
SortedMap<String, Integer> treeMap = new TreeMap<>();
// Adding key-value pairs using put()
treeMap.put("Apple", 5);
treeMap.put("Banana", 2);
treeMap.put("Orange", 7);
treeMap.put("Mango", 3);
// Displaying the TreeMap (sorted by key)
System.out.println("SortedMap: " + treeMap); // {Apple=5, Banana=2, Mango=3, Orange=7}
// Accessing the first and last keys
System.out.println("First key: " + treeMap.firstKey()); // Apple
System.out.println("Last key: " + treeMap.lastKey()); // Orange
// Getting a subMap (from Banana to Mango)
SortedMap<String, Integer> subMap = treeMap.subMap("Banana", "Orange");
System.out.println("SubMap (Banana to Orange): " + subMap); // {Banana=2, Mango=3}
}
}
Explanation:
TreeMap: Maintains a sorted order of keys.
firstKey() and lastKey(): Return the lowest and highest keys, respectively.
subMap(): Returns a portion of the map between two specified keys (fromKey inclusive and toKey exclusive).
Example 2: Working with HeadMap and TailMap
import java.util.SortedMap;
import java.util.TreeMap;
public class HeadTailMapExample {
public static void main(String[] args) {
// Creating a TreeMap of string keys and integer values
SortedMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Apple", 5);
treeMap.put("Banana", 2);
treeMap.put("Mango", 3);
treeMap.put("Orange", 7);
treeMap.put("Grapes", 8);
// Getting a headMap (keys less than Mango)
SortedMap<String, Integer> headMap = treeMap.headMap("Mango");
System.out.println("HeadMap (keys less than Mango): " + headMap); // {Apple=5, Banana=2}
// Getting a tailMap (keys greater than or equal to Mango)
SortedMap<String, Integer> tailMap = treeMap.tailMap("Mango");
System.out.println("TailMap (keys greater than or equal to Mango): " + tailMap); // {Mango=3, Orange=7}
}
}
Explanation:
headMap(toKey): Returns a view of the portion of the map with keys less than toKey.
tailMap(fromKey): Returns a view of the portion of the map with keys greater than or equal to fromKey.
4. Custom Comparator in TreeMap
By default, TreeMap uses the natural ordering of the keys (e.g., alphabetical for String). You can provide a custom comparator when creating a TreeMap to change the ordering.
Example 3: TreeMap with Custom Comparator (Reverse Order)
import java.util.Comparator;
import java.util.SortedMap;
import java.util.TreeMap;
public class CustomComparatorExample {
public static void main(String[] args) {
// Creating a TreeMap with a custom comparator (reverse order)
SortedMap<String, Integer> treeMap = new TreeMap<>(Comparator.reverseOrder());
// Adding key-value pairs
treeMap.put("Apple", 5);
treeMap.put("Banana", 2);
treeMap.put("Orange", 7);
treeMap.put("Mango", 3);
// Displaying the TreeMap (sorted by keys in reverse order)
System.out.println("SortedMap with custom comparator: " + treeMap); // {Orange=7, Mango=3, Banana=2, Apple=5}
}
}
Explanation:
Comparator.reverseOrder(): A built-in comparator that sorts keys in reverse (descending) order.
The keys in the TreeMap are now sorted from highest to lowest.
5. Navigating a SortedMap
SortedMap provides methods like firstKey(), lastKey(), headMap(), and tailMap() to allow navigation through the map. Let's explore more navigation techniques.
Example 4: Using Navigation Methods in SortedMap
import java.util.SortedMap;
import java.util.TreeMap;
public class SortedMapNavigation {
public static void main(String[] args) {
SortedMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Apple", 5);
treeMap.put("Banana", 2);
treeMap.put("Orange", 7);
treeMap.put("Mango", 3);
treeMap.put("Grapes", 8);
// Accessing the first and last keys
System.out.println("First key: " + treeMap.firstKey()); // Apple
System.out.println("Last key: " + treeMap.lastKey()); // Orange
// Accessing a subMap (between Apple and Orange)
SortedMap<String, Integer> subMap = treeMap.subMap("Apple", "Orange");
System.out.println("SubMap (Apple to Orange): " + subMap); // {Apple=5, Banana=2, Grapes=8, Mango=3}
// Accessing headMap (keys less than Mango)
SortedMap<String, Integer> headMap = treeMap.headMap("Mango");
System.out.println("HeadMap (keys less than Mango): " + headMap); // {Apple=5, Banana=2, Grapes=8}
}
}
Explanation:
subMap() gives you a range view of the map between two specified keys.
headMap() and tailMap() give you parts of the map based on the specified keys.
6. Example of TreeMap with Custom Object Keys
You can use custom objects as keys in a TreeMap. However, the custom object must either implement the Comparable interface or you must provide a Comparator to define the sorting order.
Example 5: Using Custom Object as Keys in TreeMap
import java.util.SortedMap;
import java.util.TreeMap;
class Person implements Comparable {
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person other) {
return Integer.compare(this.age, other.age); // Sorting by age
}
@Override
public String toString() {
return name + " (" + age + ")";
}
}
public class TreeMapCustomObjectExample {
public static void main(String[] args) {
// Creating a TreeMap where keys are Person objects
SortedMap<Person, String> personMap = new TreeMap<>();
personMap.put(new Person("Alice", 30), "HR");
personMap.put(new Person("Bob", 25), "Finance");
personMap.put(new Person("Charlie", 35), "IT");
// Displaying the TreeMap (sorted by age, which is defined in compareTo)
for (Map.Entry<Person, String> entry : personMap.entrySet()) {
System.out.println(entry.getKey() + " works in " + entry.getValue());
}
}
}
Explanation:
The Person class implements Comparable, and the compareTo() method sorts Person objects by age.
The TreeMap stores Person objects as keys and sorts them based on their age.
7. Key Considerations for SortedMap
Sorted by keys: SortedMap implementations (like TreeMap) always maintain the order of the keys.
Performance: In a TreeMap, the time complexity for basic operations like put(), get(), remove(), and containsKey() is O(log n) because the keys are stored in a tree structure.
Custom comparators: You can easily change the sorting order of a SortedMap by providing a custom comparator.
Conclusion
In this tutorial, we explored the SortedMap interface in Java, focusing on its common implementation TreeMap. We discussed key operations such as:
Basic operations (put(), get(), remove()).
Navigating the map using headMap(), tailMap(), and subMap().
Custom sorting with comparators and custom objects as keys.
The SortedMap interface is a powerful tool when you need to maintain a sorted collection of key-value pairs, making it highly useful for scenarios like scheduling, range queries, and more.