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));
  }
}