Java TreeMap is a Red-Black tree based implementation of Java’s NavigableMap and SortedMap interfaces.
The TreeMap class is part of Java’s collection framework in java.util package. It implements the NavigableMap interface, which in turn extends the SortedMap interface. Following is the class hierarchy of TreeMap.
The map is sorted according to the natural ordering of its keys. The SortedMap interface provides functionalities to maintain the ordering of keys. And the NavigableMap interface provides functionalities to navigate through the map. For example, finding the element which just greater than or just less than the given key, finding the first and last element in the TreeMap etc.
Since a TreeMap implements NavigableMap interface, it has the functionalities of both the NavigableMap as well as the SortedMap.
Following are key points to note about TreeMap in Java
- The underlying data structure is RED-BLACK Tree.
- Duplicate keys are not allowed but values can be duplicated.
- Insertion order of entry is not preserved and all entries will be inserted according to some sorting order of keys.
- If we are depending on default natural sorting order, keys should be homogeneous (same type) and Comparable (Key type should be child of Comparable interface) otherwise we will get ClassCastException.
- If we are defining our own sorting order by Comparator then keys can be heterogeneous (in a non generic TreeMap) and non Comparable.
- There are no restrictions on values they can be heterogeneous (can be different types in a non generic TreeMap) and non Comparable.
- null key is not allowed, if we are trying to insert we will get NullPointerException.
- There are no restrictions for null values.
- Java TreeMap implementation is not synchronized.
By default, TreeMap sorts all its entries according to their natural ordering. For an integer, this would mean ascending order and for strings, alphabetical order.
If we’re not satisfied with the natural ordering of TreeMap, we can also define our own rule for ordering by means of a Comparator during construction of a TreeMap. This way is old fashion, its before Java 8.
- Create a java class and implement Comparable interface
- Override compare(Object o1, Object o2) method and use compareTo(Object 0) method of java.lang.Comparable interface to sort the order.
In Java 8 there are several utility methods introduced in Comparator functional interface. Lets see in this example how we customize sorting order in TreeMap. Also we can use java.util.Collections class to reverse the order of entries.