Java TreeMap guide with examples

In this article we will see what is Java TreeMap, main features of Java TreeMap, how it works in java, how it sorts elements by default, how we do the custom sorting order in TreeMap, how do we create TreeMap and methods of TreeMap with simple examples.

1. What is Java TreeMap

Java TreeMap is a Red-Black tree based implementation of Java’s NavigableMap and SortedMap interfaces. The map is sorted by default according to the natural ordering of its keys. 

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.

Since a TreeMap implements NavigableMap interface, it has the functionalities of both the NavigableMap as well as the SortedMap.

2. TreeMap key points

1. The underlying data structure is RED-BLACK Tree.
2. Duplicate keys are not allowed but values can be duplicated.
3.  Insertion order of entry is not preserved and all entries will be inserted according to some sorting order of keys.
4.  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.
5.  If we are defining our own sorting order by Comparator then keys can be heterogeneous (in a non generic TreeMap) and non Comparable.
6. There are no restrictions on values they can be heterogeneous (can be different types in a non generic TreeMap) and non Comparable.
7.  null key is not allowed, if we are trying to insert we will get NullPointerException.
8. There are no restrictions for null values.
9. Java TreeMap implementation is not synchronized.

3. How to create TreeMap

TreeMap provides following constructors to create instances in Java.

1. TreeMap() – Creates a new empty tree map using the natural sorting order of its keys.
2. TreeMap(Comparator comparator) – Creates a new, empty tree map, the sorting order depends on the given comparator.
3. TreeMap(Map<K,V> m) – Creates a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys, this is useful to convert other map implementation types like HashMap, Hashtable etc to TreeMap structure.
4. TreeMap(SortedMap<K, V> m) – Creates a new tree map containing the same mappings and using the same ordering as the specified sorted map.

4. Default Sorting in TreeMap

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.

Following code demonstrates how to create and add key values to TreeMap in Java, and also how default sorting in TreeMap.

public class TreeMapNaturalSortingDemo {

	public static void main(String[] args) {
		TreeMap<Integer, String> employeeMap = new TreeMap<Integer, String>();
		employeeMap.put(5, "Peter");
		employeeMap.put(1, "Gerhard");
		employeeMap.put(3, "Christina");
		employeeMap.put(4, "Martin");
		employeeMap.put(2, "Agasthya");
		
		System.out.println("TreeMap sorted in natural order by its keys: \n"+employeeMap);
	}
}

Output :

TreeMap sorted in natural order by its keys: 
{1=Gerhard, 2=Agasthya, 3=Christina, 4=Martin, 5=Peter}

5. Custom sorting order in Java TreeMap

5.1. Sort Method 1 :

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.

1. Create a java class and implement Comparable interface
2. Override compare(Object o1, Object o2) method and use compareTo(Object o) method of java.lang.Comparable interface to sort the order.

Following example demonstrates how to sort TreeMap using Comparator.

public class MyComparator implements Comparator<Integer> {

	@Override
	public int compare(Integer o1, Integer o2) {
		
		return o2.compareTo(o1); //For reverse order
		//return o1.compareTo(o2); //For natural order
	}
}

public class CustomSortingTreeMapDemo {
	
	public static void main(String[] args) {
		TreeMap<Integer, String> employeeMap = new TreeMap<Integer, String>(new MyComparator());
		employeeMap.put(5, "Peter");
		employeeMap.put(1, "Gerhard");
		employeeMap.put(3, "Christina");
		employeeMap.put(4, "Martin");
		employeeMap.put(2, "Agasthya");
		System.out.println("TreeMap sorted in reverse order by its keys: \n"+employeeMap+ "\n");	
	}
}

Output :

TreeMap sorted in reverse order by its keys: 
{5=Peter, 4=Martin, 3=Christina, 2=Agasthya, 1=Gerhard}

5.2. Sort Method 2 :

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.

Following Example shows you how to sort TreeMap using Collections class in Java 8.

public class CostomSortingTreeMapDemo2 {

public static void main(String[] args) {
		
		TreeMap<Integer, String> employeeMap = new TreeMap<Integer, String>(Comparator.reverseOrder());
		employeeMap.put(5, "Peter");
		employeeMap.put(1, "Gerhard");
		employeeMap.put(3, "Christina");
		employeeMap.put(4, "Martin");
		employeeMap.put(2, "Agasthya");
		
		System.out.println("TreeMap sorted in reverse order by its keys using Comparator.reverseOrder() : \n"+employeeMap+ "\n");
		
		TreeMap<Integer, String> employeeMap2 = new TreeMap<Integer, String>(Collections.reverseOrder());
		employeeMap2.put(5, "Peter");
		employeeMap2.put(1, "Gerhard");
		employeeMap2.put(3, "Christina");
		employeeMap2.put(4, "Martin");
		employeeMap2.put(2, "Agasthya");
		
		System.out.println("TreeMap sorted in reverse order by its keys using Collections.reverseOrder() : \n"+employeeMap);
	}
}

Output :

TreeMap sorted in reverse order by its keys using Comparator.reverseOrder() : 
{5=Peter, 4=Martin, 3=Christina, 2=Agasthya, 1=Gerhard}

TreeMap sorted in reverse order by its keys using Collections.reverseOrder() : 
{5=Peter, 4=Martin, 3=Christina, 2=Agasthya, 1=Gerhard}