
We have seen in the article Java Map: Preserve Insertion Order how to choose the right implementation of the Java Map interface to keep the order in which keys are inserted into the Map object. We saw that the right choice was LinkedHashMap. There are other common scenarios though in which we want the keys to be sorted in some order different from the sequence of insertions.
The TreeMap class is the answer in this case. A TreeMap object sort sorts its elements by the natural order by default, but can also use a specific ordering strategy by using a comparator, passed by one of its constructors.
You can find the code fragments used in this post in the following GitHub project: java miscellaneous tips.
Java Map: Sorted Keys with TreeMap
How TreeMap is Internally Implemented
As its name suggests a TreeMap uses a tree data structure internally, specifically a red-black tree. This data structure can provide a log(n) time cost performance for common operations such as inserting, removing, and searching. It can keep that performance by balancing the tree after each operation.
TreeMap Sorting by Natural Order
A TreeMap object’s default behavior is to sort its keys by their natural order. You can see an example below:
class TreeMapKeySorting {
public static void main(String args[]) {
TreeMap<String, String> treeMap = new TreeMap<>();
treeMap.put("z", "value1");
treeMap.put("c", "value2");
treeMap.put("a", "value3");
treeMap.put("b", "value4");
for (Map.Entry<String, String> mapEntry : treeMap.entrySet()) {
System.out.println(mapEntry.getKey() + " - " + mapEntry.getValue());
}
}
}
TreeMap Sorting by a Comparator
If we want a more specific ordering pattern we can pass a Comparator instance to the TreeMap constructor. In the example below, for sake of simplicity, we make use of a default implementation of the Comparator class that has just the effect of reversing the natural order:
class TreeMapKeyComparatorSorting {
public static void main(String args[]) {
TreeMap<String, String> treeMap = new TreeMap<>(Comparator.reverseOrder());
treeMap.put("z", "value1");
treeMap.put("c", "value2");
treeMap.put("a", "value3");
treeMap.put("b", "value4");
for (Map.Entry<String, String> mapEntry : treeMap.entrySet()) {
System.out.println(mapEntry.getKey() + " - " + mapEntry.getValue());
}
}
}
TreeMap is Not Synchronized
A TreeMap is not thread-safe. In a scenario in which multiple threads access the map and make modifications, we have to implement some synchronization mechanism outside the boundaries of the TreeMap instance.