java treemap comparator

When you create a TreeMap in Java without specifying a comparator, it relies on the natural ordering of its keys. The class must implement Comparable, or the map throws a ClassCastException at insertion time. The java treemap comparator pattern provides explicit control over that ordering, which becomes necessary when keys do not have a natural order, when you need a custom sort, or when you want to control how equal keys are recognized.

The Role of the Comparator in TreeMap

A TreeMap is a red-black tree implementation. Every insertion and lookup determines the position of a key by comparing it with existing keys. The comparator you supply defines the total ordering for the map. If no comparator is given, the map casts the key to Comparable and uses its compareTo method.

import java.util.*;

TreeMap<Integer, String> byNaturalOrder = new TreeMap<>();
byNaturalOrder.put(3, "three");
byNaturalOrder.put(1, "one");
byNaturalOrder.put(2, "two");
System.out.println(byNaturalOrder.keySet()); // [1, 2, 3]

When you pass a comparator, the map uses it instead. The comparator must be consistent with equals to avoid surprising behavior: if compare(a, b) == 0, then a.equals(b) should be true. Violating this rule makes the map treat distinct keys as the same key, silently dropping values.

Creating a Custom Comparator

Comparators can be written as lambda expressions, anonymous classes, or separate Comparator implementations. A lambda works well when the logic is short.

TreeMap<Integer, String> reverseOrder = new TreeMap<>(Comparator.reverseOrder());
reverseOrder.put(1, "one");
reverseOrder.put(2, "two");
System.out.println(reverseOrder.keySet()); // [2, 1]

For a more specific case, suppose you have a Person class and you want to order by lastName, then firstName. The comparator should handle nulls if they are possible.

class Person {
    String firstName;
    String lastName;
    // constructor, getters, toString
}

Comparator<Person> byName = Comparator
    .comparing(Person::getLastName, Comparator.nullsFirst(String::compareTo))
    .thenComparing(Person::getFirstName, Comparator.nullsFirst(String::compareTo));

TreeMap<Person, String> directory = new TreeMap<>(byName);

Using Comparator.comparing and thenComparing avoids manual null checks and keeps the chaining readable. The nullsFirst wrapper defines an ordering for null keys; otherwise the comparator throws a NullPointerException when it encounters one.

Comparing Keys Versus Sorting by Values

A TreeMap can only be sorted by its keys. The comparator receives two keys and decides their order. If you want to order by the map's values, you need a different approach: extract entries into a list and sort it, or create a custom comparator that looks up the value for each key.

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("alice", 90);
scores.put("bob", 85);
scores.put("carol", 95);

// Comparator that sorts keys by their associated value (descending)
Comparator<String> byValueDesc = (a, b) -> {
    int compare = Integer.compare(scores.get(b), scores.get(a));
    return compare != 0 ? compare : a.compareTo(b);
};

List<String> sortedKeys = new ArrayList<>(scores.keySet());
sortedKeys.sort(byValueDesc);
System.out.println(sortedKeys); // [carol, alice, bob]

Because the comparator reads the map during comparison, changing the map while the comparator is in use can produce inconsistent results. This pattern works for a snapshot, but it is not safe for a live view used in a TreeMap itself.

Comparator Consistency and Its Effects

The contract between Comparator and equals is critical in TreeMap. The map uses the comparator to decide whether two keys are duplicates. If compare(a, b) == 0 but !a.equals(b), the second key is treated as the same entry and replaces the value. This can cause silent data loss.

TreeMap<String, String> caseInsensitiveMap = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitiveMap.put("hello", "first");
caseInsensitiveMap.put("HELLO", "second");
System.out.println(caseInsensitiveMap); // {hello=second}

The comparator considers "hello" and "HELLO" equal, so the second put overwrites the first. That behavior is expected, but it must match the application's requirement. If case-insensitive keys are not desired, use a case-sensitive comparator.

Handling Null Keys and Null Values

TreeMap allows null values freely. Null keys are only allowed if the comparator handles them. With natural ordering, a null key throws NullPointerException on the first comparison.

TreeMap<String, String> map = new TreeMap<>();
map.put(null, "value"); // throws NullPointerException

To allow null keys, pass a comparator that deals with nulls.

Comparator<String> nullSafe = Comparator.nullsFirst(String::compareTo);
TreeMap<String, String> safeMap = new TreeMap<>(nullSafe);
safeMap.put(null, "null value");
safeMap.put("key", "normal");
System.out.println(safeMap); // {null=null value, key=normal}

When nulls are first, the map places the null key at the beginning. If you want nulls last, use nullsLast. Be careful with nullsFirst and nullsLast when the comparator chain includes multiple fields; the null handling must be consistent across the entire chain.

Performance Characteristics

All operations in a TreeMap — get, put, remove, and containsKey — run in O(log n) time. The comparator you supply does not change that complexity, but it affects constant factors. Each comparison may involve multiple field accesses or even method calls. A comparator that computes an expensive value every time it runs can dominate the map's performance, especially for large maps.

Consider caching computed sort keys when they are expensive to derive. For example, if the natural sort depends on the length of a string, compute that length once and store it in the key object, rather than recalculating it during each comparison.

Thread safety is another concern. TreeMap is not thread-safe. If multiple threads access the map concurrently and at least one mutates it, external synchronization is required. A comparator that reads mutable state shared across threads can cause inconsistencies even with synchronization.

Conclusion

The comparator is the controlling element of a TreeMap's ordering. It determines not only the iteration order but also key equality and null handling. Design it carefully to match the application's semantics, keep it consistent with equals, and be aware of its impact on runtime performance and thread safety.