Java TreeMap

The Java TreeMap Class

The TreeMap class is an implementation of the Map interface that uses a tree structure (specifically, a Red-Black Tree) for storage.

The most important feature of a TreeMap is that it stores its entries in sorted order based on the keys.

Key Characteristics of TreeMap

• Key-Value Pairs: It stores items in key/value pairs.
• Unique Keys: Keys must be unique.
• Sorted by Key: It automatically sorts the entries based on their keys. By default, it uses the "natural ordering" of the keys. You can also provide a custom sorting logic using a Comparator.
• No null Keys: TreeMap does not allow null keys, as it cannot compare null to other keys for sorting. It does, however, allow null values.
• Slower Performance: Because it has to maintain the sorted order, its performance for get, put, and remove operations is O(log n), which is slower than HashMap's O(1).
• NavigableMap: TreeMap implements the NavigableMap interface, which provides useful methods for finding entries relative to others in the sorted map (e.g., floorEntry(), ceilingEntry(), higherKey(), lowerKey()).

How TreeMap Works

When you add a key-value pair, the key is used to position the entry within the underlying tree structure. This comparison is done using either the key's compareTo() method (if the key's class implements Comparable) or a Comparator provided to the TreeMap's constructor.

This tree structure is always kept balanced, which guarantees the O(log n) performance for operations.

When to Use TreeMap

TreeMap is the perfect choice when you need to map keys to values and:

1. You require the entries to be always stored in a sorted order based on the key.
2. You need to perform "range searches" or find the closest matches to a given key.

If you don't need sorting, HashMap or LinkedHashMap will provide better performance.

TreeMap Example

Here is an example demonstrating the sorting behavior of a TreeMap.

import java.util.TreeMap;

public class Main {
  public static void main(String[] args) {
    // Create a TreeMap of Integers and Strings
    TreeMap<Integer, String> courses = new TreeMap<>();
    // Add items
    courses.put(103, "Data Structures");
    courses.put(101, "Intro to Programming");
    courses.put(201, "Web Development");
    // The entries are automatically sorted by key
    System.out.println("Sorted TreeMap: " + courses);
    // NavigableMap methods
    System.out.println("First entry: " + courses.firstEntry());
    System.out.println("Last entry: " + courses.lastEntry());
    System.out.println("Entry with key higher than 101: " + courses.higherEntry(101));
  }
}

Advanced: Custom Sorting with a Comparator

Just like TreeSet, a TreeMap can sort its keys based on a custom Comparator rather than their natural ordering. This is incredibly powerful if you want to, for example, sort a map with string keys in a case-insensitive manner, or in descending order.

import java.util.TreeMap;
import java.util.Comparator;

public class Main {
  public static void main(String[] args) {
    // Sort keys in reverse (descending) order
    TreeMap<Integer, String> rankMap = new TreeMap<>(Comparator.reverseOrder());
    rankMap.put(1, "Gold");
    rankMap.put(3, "Bronze");
    rankMap.put(2, "Silver");
    // Outputs: {3=Bronze, 2=Silver, 1=Gold}
    System.out.println("Reverse Order Map: " + rankMap);
  }
}

Advanced: Polling Entries

Because TreeMap implements NavigableMap, it provides methods to not only view but also simultaneously remove the lowest or highest entries. This is useful for processing priorities.

import java.util.TreeMap;
import java.util.Map;

public class Main {
  public static void main(String[] args) {
    TreeMap<Integer, String> tasks = new TreeMap<>();
    tasks.put(10, "Low Priority Task");
    tasks.put(1, "URGENT Task");
    tasks.put(5, "Medium Priority Task");
    // pollFirstEntry retrieves and removes the entry with the lowest key
    Map.Entry<Integer, String> urgent = tasks.pollFirstEntry();
    System.out.println("Processing: " + urgent.getValue());
    System.out.println("Remaining tasks: " + tasks);
  }
}