Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java TreeMap Comparator: Custom Ordering and Null Handling

Learn how to control Java TreeMap ordering by supplying a custom Comparator. This article covers natural ordering, custom comparators, sorting keys by values, comparator consistency, and null-key handling.

~4 min readJava
#TreeMap#Comparator#Java Collections#Sorting
Java TreeMap comparator concept with a balanced tree structure and ordering arrows

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. A custom Comparator provides explicit control over that ordering, which is necessary when keys do not have a natural order, when you need a different sort order, 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.

java
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. To avoid surprising behavior, the comparator should be consistent with equals: compare(a, b) == 0 should have the same boolean result as a.equals(b). If compare(a, b) == 0 while a.equals(b) is false, the map treats distinct keys as the same key and silently overwrites one value.

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.

java
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.

java
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.

java
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.

java
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.

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

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

java
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 order depends on a value that requires a lookup or calculation, compute that value 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 depends on external mutable state can also cause inconsistencies because the same two keys can compare differently at different times. Prefer comparators that depend only on the keys themselves.

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.

Try matching browser tools

All tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.