Java TreeMap with Example

Java TreeMap is an ordered Java Map. It has the special property that it keeps the entries sorted (in ascending order) either by the natural order of its keys or using the Comparator provided to constructor. TreeMap uses a balanced tree internally to keep the keys ordered. Oracle’s JDK implementation uses Red-Black  Trees (a kind of balanced binary tree). Because TreeMap uses balanced trees, all major Map operations has logarithmic complexity.

Constructors of TreeMap

Like all other classes in the Collections Framework, TreeMap is also defined as a generic.

As described in the introductory lesson on Maps, TreeMap has a no-args and copy constructor. And pretty much like HashMap, also has four constructors in total.

1. TreeMap() -> Default no-args constructor. Sorts keys based on their ‘natural’ order.
2. TreeMap(Map<? extends K,? extends V> m) -> Copy constructor. Copies all the entries from Map provided as argument to the newly constructed TreeMap.
3. TreeMap(Comparator<? super K> comparator) –> Used to provide a Comparator object that can override the ‘natural’ order of keys.
4. TreeMap(SortedMap<K,? extends V> m) -> A special kind of copy constructor which not only copies the entries from the Map provided as argument but also retains their order.

Note that there is no constructor that takes in initial capacity or load factor as arguments, the way we have for HashMap. The reason is that TreeMap implementation uses some kind of balanced tree (usually Red-Black). There is a possible re-ordering of elements as soon as an entry is inserted. Therefore, it makes no sense to start out with initial capacity or load factor. For more on why these constructors make sense for HashMap, read the internal implementation detail of HashMap.

Important Methods of TreeMap

TreeMap has a lot of useful methods. TreeMap is richer than other Maps primarily because there are a lot of methods to utilize the sorted nature of entries in addition to the usual Map methods. Here is a partial list of important methods in a TreeMap.

1. V put(K key, V value) -> associates value with key in the map.
2. V remove(Object key) -> removes association of value with key in the map.
3. V get(Object key) -> Returns value corresponding to specified key, null if the key is not present.
4. boolean containsKey(Object key) –> checks if key is present.
5. boolean containsValue(Object value) -> checks if there is any key in the map with specified value.
6. Set<Map.Entry<K,V>> entrySet() -> Returns all entries of the Map as a Set.
7. Set<K> keySet() -> Returns all the keys as a Set.
8. NavigableSet<K> navigableKeySet() -> Returns all the keys as a NavigableSet.
9. NavigableMap<K,V> descendingMap() -> Returns a new Map having the entries in reverse order.
10. SortedMap<K,V> headMap(K key) -> Returns a part of the Map where keys are smaller than the key specified as argument.
11. SortedMap<K,V> tailMap(K key) -> Returns a part of the Map where keys are greater than the key specified as argument.
12. Map.Entry<K,V> pollFirstEntry() -> Removes and returns a key-value mapping associated with the least key in this Map, or null if the Map is empty.
13. Map.Entry<K,V> pollLastEntry() -> Removes and returns a key-value mapping associated with the greatest key in this Map, or null if the Map is empty.
14. Map.Entry<K,V> firstEntry() -> Returns a key-value mapping associated with the least key in this Map, or null if the map is empty.
15. Map.Entry<K,V> lastEntry() -> Returns a key-value mapping associated with the greatest key in this Map, or null if the Map is empty.
16. Map.Entry<K,V> floorEntry(K key) -> Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
17. Map.Entry<K,V> ceilingEntry(K key) -> Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
18. K ceilingKey(K key) -> Returns the least key greater than or equal to the given key, or null  if there is no such key.
19. K floorKey(K key) -> Returns the greatest key less than or equal to the given key, or null if there is no such key.

Salient Features of TreeMap

The list below summarizes the salient features of TreeMap. TreeMap

1. Is an ordered Map
2. Does not allow any key to be null. Meaning null cannot be inserted as a key.
3. Allows multiple values to be null. Any number of keys can be associated with a null value.
4. Is not synchronized. Therefore, not suitable in multi-threaded environment.
5. Has fail-fast iterators. Meaning iterators of TreeMap may through ConcurrentModificationException if the Map is structurally altered by a different while an iteration is underway.
6. Uses Balanced Trees as the underlying data structure. Therefore, all major operations have logarithmic i.e. Ο(log(n)) time complexity.

Internal Implementation of TreeMap

We examined internal implementation of HashMap in great details. Internal implementation of TreeMap is equally if not more interesting. But the details are too intricate to be done justice with in a small section. Therefore, we will only cover important points regarding the implementation of TreeMap.

TreeMap uses an Red-Black tree to maintain the keys in sorted order.

Red-Black Tree

A Red-Black tree is a self-balancing search tree where every node stores an extra bit of information. This bit is referred to as the color of the node and by tradition is either red or black. The color of the nodes and the rules of insertion/deletion in Red-Black trees make these trees self-balancing.

There are exactly five properties of red-black trees –

1. Each node is either red or black
2. Root of the tree is by convention black. It could have been red as well and not changed anything else, but something had to be chosen initially. The original algorists seem to have darker tastes.
3. All leaves are black.
4. If a node is red both its children must be black.
5. Sorry for the caps – EVERY PATH FROM ANY NODE TO ITS DESCENDANT LEAVES CONTAINS SAME NUMBER OF BLACK NODES.

These properties ensure that red-black trees are self-balancing and are not skewed to impact the time complexity of critical operations.

TreeMap Example

Now that we have looked at TreeMap, its constructors, important methods and internal implementation details, let’s look at a quick example.

We will use TreeMap to store a mapping of dictators to the nations that they ruled over. Since we are using String as key and value, we will be able to print the names of dictators with their countries in alphabetical order.

The output of the above code is –

We have looked at HashMap and TreeMap. Next, we will examine LinkedHashMap and EnumMap.