Java TreeMap

In this guide, we will learn the usage of TreeMap class methods/APIs with examples.

Important Key Points about TreeMap

Ordering: 

The TreeMap class in Java is a Red-Black tree-based implementation of the Map interface, which provides a guaranteed log(n) time complexity for the put, get, and remove operations. It stores its elements in a tree and they are automatically arranged in a natural ascending order. 

Null Keys and Values: 

Unlike HashMap and LinkedHashMap, a TreeMap in Java does not allow null keys but it can have null values. If you try to insert a null key, it will throw a NullPointerException. 

Non-synchronized:

TreeMap is not synchronized, which means it is not suitable for thread-safe operations unless synchronized explicitly. 

Comparator Interface: 

We can construct an empty TreeMap that will be sorted by using the natural order of its keys or by a custom Comparator at the time of creation. 

Performance: 

TreeMap offers a performance of O(log(n)) for most operations like add, remove, and contains tasks. 

Fail-Fast Iterator: 

The iterator provided by TreeMap is fail-fast, which means if the map is structurally modified at any time after the iterator is created, the iterator will throw a ConcurrentModificationException. 

Implements NavigableMap: 

TreeMap is the only class that implements the NavigableMap interface, which means it supports a number of navigation methods. For example, it can be used to return the greatest key less than or equal to the given key, or the first or last key in the map. 

Java 8 Enhancements: 

Java 8 introduced new methods in TreeMap like newKeySet(), descendingKeySet(), etc. These methods provide more functionality and make it easier to use TreeMap. 

Use-cases: 

TreeMap is an excellent choice when you need to keep your entries sorted according to natural ordering or custom ordering. It is commonly used in applications where data needs to be displayed in a sorted manner or when you need to search for elements within a range.

Create TreeMap 

Here is the syntax to create an object of the TreeMap class:
// Creating a TreeMap
TreeMap<String, String> fileExtensions  = new TreeMap<>();
We can use put() method to add an entry to the TreeMap:
// Creating a TreeMap
TreeMap<String, String> fileExtensions  = new TreeMap<>();

// Adding new key-value pairs to a TreeMap
fileExtensions.put("python", ".py");
fileExtensions.put("c++", ".cpp");
fileExtensions.put("kotlin", ".kt");
fileExtensions.put("golang", ".go");
fileExtensions.put("java", ".java");

// Printing the TreeMap (Output will be sorted based on keys)
System.out.println(fileExtensions);
Output:
{c++=.cpp, golang=.go, java=.java, kotlin=.kt, python=.py}

TreeMap Sorting Order Example(Ascending Order)

In this example, the TreeMap elements are sorted in natural ordering.
public class MapInterfaceTreeSetImpl {
    public static void main(String[] args) {
    treeMapDemo();
 }

 // maintain keys in ascending order.
 private static void treeMapDemo() {
     // Constructs a new, empty tree map, using the natural ordering of its
     // keys
      Map<String, String> treeMap = new TreeMap<>();
      treeMap.put("key1", "value1");
      treeMap.put("key3", "value3");
      treeMap.put("key2", "value2");
      treeMap.put("key0", "value0");

      // loop linkedHahMap using java 8 forEach method
      treeMap.forEach((k, v) -> {
      System.out.println(k);
      System.out.println(v);
  });

     // loop linkedHahMap using before java 8 forEach method
     for (Entry pair : treeMap.entrySet()) {
         System.out.println(pair.getKey());
         System.out.println(pair.getValue());
     }
   }
}
Output:
key0
value0
key1
value1
key2
value2
key3
value3

TreeMap with a custom Comparator (Descending Order)

This example demonstrates how to create a TreeMap with a custom comparator that orders the TreeMap entries in the descending order of keys -
// Creating a TreeMap with a Custom comparator (Descending order)
SortedMap<String, Integer> numberWordMapping = new TreeMap<>(Comparator.reverseOrder());
// Adding new key-value pairs to a TreeMap
numberWordMapping.put("one", 1);
numberWordMapping.put("two", 2);
numberWordMapping.put("three", 3);
numberWordMapping.put("five", 5);
numberWordMapping.put("four", 4);

// Printing the TreeMap (The keys will be sorted based on the supplied
// comparator)
System.out.println(numberWordMapping);
Output:
{two=2, three=3, one=1, four=4, five=5}
Note that the keys are sorted in descending order.

Accessing the entries of a TreeMap

Find the size of a TreeMap.
TreeMap<Integer, String> users = new TreeMap<>();
users.put(1, "Ramesh");
// Finding the size of a TreeMap
System.out.println("Total number of users: " + users.size());
Check if a given key exists in a TreeMap.
TreeMap<Integer, String> users = new TreeMap<>();

users.put(1003, "A");
users.put(1001, "B");
users.put(1002, "C");
users.put(1004, "D");
// Check if a given key exists in a TreeMap
Integer id = 1004;
if(users.containsKey(id)) {
    // Get the value associated with a given key in a TreeMap
    String name = users.get(id);
    System.out.println("user with id " + id + " : " + name);
} else {
    System.out.println("user does not exist with id : " + id);
}
Retrieve the first entry in the TreeMap.
TreeMap<Integer, String> users = new TreeMap<>();

users.put(1003, "A");
users.put(1001, "B");
users.put(1002, "C");
users.put(1004, "D");
// Find the first entry
System.out.println("First entry in users map : " + users.firstEntry());
Retrieve the last entry in the TreeMap.
TreeMap<Integer, String> users = new TreeMap<>();

users.put(1003, "A");
users.put(1001, "B");
users.put(1002, "C");
users.put(1004, "D");
// Find the last entry
System.out.println("Last entry in users map : " + users.lastEntry());
Retrieve the entry whose key is just lower than the given key.
TreeMap<Integer, String> users = new TreeMap<>();

users.put(1003, "A");
users.put(1001, "B");
users.put(1002, "C");
users.put(1004, "D");
// Find the entry whose key is just less than the given key
Map.Entry<Integer, String> users = users.lowerEntry(1002);
Retrieve the entry whose key is just higher than the given key.
TreeMap<Integer, String> users = new TreeMap<>();

users.put(1003, "A");
users.put(1001, "B");
users.put(1002, "C");
users.put(1004, "D");
// Find the entry whose key is just higher than the given key
Map.Entry<Integer, String> usersEx = users.higherEntry(1002);

Removing Elements from TreeMap

To remove entries from a TreeMap, you can use the remove(Object key) method. This method removes the mapping for the specified key from this TreeMap if present. 

Here's an example:
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        // Create a TreeMap
        TreeMap<Integer, String> treeMap = new TreeMap<>();

        // Add key-value pairs to the TreeMap
        treeMap.put(3, "Three");
        treeMap.put(2, "Two");
        treeMap.put(1, "One");

        System.out.println("Original TreeMap: " + treeMap);

        // Remove the entry with key 2
        treeMap.remove(2);

        System.out.println("TreeMap after removing entry: " + treeMap);
    }
}

Output:

Original TreeMap: {1=One, 2=Two, 3=Three}
TreeMap after removing entry: {1=One, 3=Three}
In this example, the remove method is called with the key 2 as the parameter, which removes the entry {2=Two} from the TreeMap.

Searching Elements in TreeMap

Searching for an element in a TreeMap can be done through the containsKey(Object key) or containsValue(Object value) methods. These methods return a boolean indicating if the TreeMap contains the specified key or value. 

Here's an example:
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        // Create a TreeMap
        TreeMap<Integer, String> treeMap = new TreeMap<>();

        // Add key-value pairs to the TreeMap
        treeMap.put(3, "Three");
        treeMap.put(2, "Two");
        treeMap.put(1, "One");

        // Search for a key in the TreeMap
        boolean hasKey = treeMap.containsKey(2);
        System.out.println("TreeMap contains key 2: " + hasKey);

        // Search for a value in the TreeMap
        boolean hasValue = treeMap.containsValue("Four");
        System.out.println("TreeMap contains value 'Four': " + hasValue);
    }
}

Output:

TreeMap contains key 2: true
TreeMap contains value 'Four': false

Iterate over TreeMap

You can iterate over a TreeMap in Java in several ways, which mainly includes using the entrySet or keySet along with the for-each loop, iterator, or Java 8 methods like forEach and streams. 

Using the for-each loop and the entrySet method:

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Three");
        treeMap.put(2, "Two");
        treeMap.put(1, "One");

        for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }
    }
}

Output:

1 => One
2 => Two
3 => Three

Using an Iterator:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Three");
        treeMap.put(2, "Two");
        treeMap.put(1, "One");

        Iterator<Map.Entry<Integer, String>> iterator = treeMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, String> entry = iterator.next();
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }
    }
}

Output:

1 => One
2 => Two
3 => Three

Using Java 8's forEach:

import java.util.*;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Three");
        treeMap.put(2, "Two");
        treeMap.put(1, "One");

        Stream<Map.Entry<Integer, String>> stream = treeMap.entrySet().stream();
        stream.forEach(entry -> System.out.println(entry.getKey() + " => " + entry.getValue()));
    }
}

Output:

1 => One
2 => Two
3 => Three

Using Java 8's Stream API:

import java.util.*;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Three");
        treeMap.put(2, "Two");
        treeMap.put(1, "One");

        Stream<Map.Entry<Integer, String>> stream = treeMap.entrySet().stream();
        stream.forEach(entry -> System.out.println(entry.getKey() + " => " + entry.getValue()));
    }
}

Output:

1 => One
2 => Two
3 => Three

Conclusion

In this article, you learned what is a TreeMap, how to create a TreeMap, how to use a custom Comparator to alter the sorting order of a TreeMap, how to access the entries from a TreeMap, how to search entries in a TreeMap, how to remove entries from a TreeMap and how to iterate over a TreeMap.

Comments