Java TreeMap class

Java TreeMap class stores key-value pairs very similar to the HashMap class. The difference is that TreeMap provides an efficient way to store key/value pairs in sorted order. The TreeMap class is a red-black tree-based NavigableMap implementation.

This Java TreeMap tutorial will teach us about TreeMap class, methods, usecases, and other essential details.

1. TreeMap Hierarchy in Collection Framework

The TreeMap class extends the AbstractMap class and implements the NavigableMap interface. Here 'K' is the type of keys and 'V' is the type of mapped values to keys.

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {

  //  ...implementation...
}

2. Features of a TreeMap

The important points about the Java TreeMap class are:

• It stores key-value pairs similar to like HashMap.
• It allows only distinct keys. Duplicate keys are not possible.
• It cannot have null key but can have multiple null values.
• It stores the keys in sorted order (natural order) or by a Comparator provided at map creation time.
• It provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
• It is not synchronized. Use Collections.synchronizedSortedMap(new TreeMap()) to work in concurrent environment.
• The iterators returned by the iterator method are fail-fast.

3. Constructors

The TreeMap has five types of constructors:

• TreeMap(): creates a new, empty tree map, using the natural ordering of its keys.
• TreeMap(Comparator c): creates a new, empty tree map, ordered according to the given comparator.
• TreeMap(Map map): creates a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys.
• TreeMap(SortedMap map): creates a new tree map containing the same mappings and using the same ordering as the specified sorted map.

4. Methods

The essential methods we should learn about TreeMap are as follows:

• void clear(): It removes all the key-value pairs from the map.
• void size(): It returns the number of key-value pairs present in this map.
• void isEmpty(): It returns true if this map contains no key-value mappings..
• boolean containsKey(Object key): It returns 'true' if a specified key is present in the map.
• boolean containsValue(Object key): It returns 'true' if a specified value is mapped to at least one key in the map.
• Object get(Object key): It retrieves the value mapped by the specified key, or null if this map contains no mapping for the key.
• Object remove(Object key): It removes the key-value pair for the specified key from the map if present.
• Comparator comparator(): It returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.
• Object firstKey(): It returns the first (least) key currently in the tree map.
• Object lastKey(): It returns the last (greatest) key currently in the tree map.
• Object ceilingKey(Object key): It returns the least key greater than or equal to the given key, or null if there is no such key.
• Object higherKey(Object key): It returns the least key strictly greater than the specified key.
• NavigableMap descendingMap(): It returns a reverse order view of the mappings contained in this map.

5. TreeMap Examples

5.1. Sort Key-Value Pairs in Natural Ordering

Java program to demonstrate the usage of TreeMap storing the key-value pairs in natural ordering.

//Natual ordering by deafult
TreeMap<Integer, String> pairs = new TreeMap<>();

pairs.put(2,  "B");
pairs.put(1,  "A");
pairs.put(3,  "C");

String value = pairs.get(3);    //get method
System.out.println(value);

value = pairs.getOrDefault(5, "oops");  //getOrDefault method
System.out.println(value);

//Iteration example
Iterator<Integer> iterator =  pairs.keySet().iterator();

while(iterator.hasNext()) {
  Integer key = iterator.next();
  System.out.println("Key: " + key + ", Value: " + pairs.get(key));
}

//Remove example
pairs.remove(3);
System.out.println(pairs);
System.out.println(pairs.containsKey(1));    //containsKey method   
System.out.println(pairs.containsValue("B"));    //containsValue method   
System.out.println(pairs.ceilingKey(2));

Program Output.

C
oops
Key: 1, Value: A
Key: 2, Value: B
Key: 3, Value: C
{1=A, 2=B}
true
true
2

5.2. Custom Ordering using Comparator

TreeMap<Integer, String> pairs = new TreeMap<>(Collections.reverseOrder());
 
pairs.put(2,  "B" );
pairs.put(1,  "A");
pairs.put(3,  "C");
 
System.out.println(pairs);

Program Output.

{3=C, 2=B, 1=A}

 6. When to Use TreeMap?

Whether using default ordering or custom ordering using a comparator, TreeMap provides an efficient method to store and retrieve the information contained within in a sorted manner. This makes it an excellent tool for scenarios where information needs to be displayed in sorted order. For example, employees’ information based on their age or phone numbers in any mobile application.

Another helpful use case can be a dictionary where information is recorded and displayed in a sorted fashion.

In fact, they are useful anywhere information needs to be sorted and quick random access is necessary. If random access is not needed, then rather use a sorted set or list.

7. Performance of TreeMap

TreeMap provides the performance of log(n) for most operations, such as add(), remove(), and contains(). HashMap performs with constant-time performance O(1) for the same operations. In that way, HashMap performs much better than TreeMap.

TreeMap performs better in memory management as it does not maintain an array internally to store key-value pairs. In HashMap, the array size is determined while initialization or resizing, which is often more than needed at the time. It wastes memory. There is no such problem with TreeMap.

8. Concurrency

Both versions of Map, HashMap, and TreeMap aren’t synchronized, and the programmer needs to manage concurrent access to the maps.

We can get the synchronized view of the treemap explicitly using Collections.synchronizedSortedMap(new TreeMap()).

Map<Integer, String> syncTreeMap = Collections.synchronizedSortedMap(new TreeMap<Integer, String>());
 
syncTreeMap.put(1,  "A");
syncTreeMap.put(2,  "B" );
syncTreeMap.put(3,  "C");

9. Conclusion

In this tutorial, we learned about Java TreeMap class and it’s internals. We saw how it stores key-value pairs in sorted manner – either in natural ordering (default) or in some custom ordering of keys (using provided comparator).

We discussed how and when to use TreeMap in real-time applications and compared its performance with HashMap to better understand when to use which version of Map.

Drop me your questions related to working with TreeMap in Java in the comments section.

Happy Learning !!