Java TreeMap Sorting: Ordering Keys with Comparators

TreeMap is a Map implementation that keeps its keys in sorted order at all times. Java treemap sorting relies on a red-black tree that maintains an ordering invariant on every put and remove operation. Iterating over keySet(), values(), or entrySet() always yields entries in sorted key order. This is different from HashMap, which makes no ordering guarantee, and LinkedHashMap, which preserves insertion order rather than key order.

The default ordering is the natural ordering of the key type. The key class must implement Comparable for this to work. String, Integer, LocalDate, and most standard library types do. When you create a TreeMap without a comparator, the map calls compareTo() on the keys internally to decide where each entry belongs.

Natural Ordering vs Explicit Comparator

A TreeMap can be constructed in two modes: natural ordering or comparator-based ordering.

// Natural ordering: keys must implement Comparable
TreeMap<String, Integer> byName = new TreeMap<>();

// Explicit comparator: overrides natural ordering
TreeMap<String, Integer> byNameReversed = new TreeMap<>(Comparator.reverseOrder());

When a comparator is supplied, the map uses it for every comparison and ignores the Comparable interface entirely. This is useful when you want an ordering that differs from the natural one, or when the key class does not implement Comparable.

The comparator must be consistent with equals. If two keys compare as equal under the comparator, TreeMap treats them as the same key. A put with a key that compares equal to an existing key replaces the existing value, even if the two key objects are not equal according to equals(). This is a common source of subtle bugs when the comparator only considers a subset of the key's fields.

Custom Sorting with a Comparator

For a key type that does not implement Comparable, or when the natural ordering is not what you need, pass a Comparator to the constructor.

record Task(int priority, String name) {}

Comparator<Task> byPriority = Comparator.comparingInt(Task::priority);

TreeMap<Task, String> tasks = new TreeMap<>(byPriority);

tasks.put(new Task(3, "deploy"), "pending");
tasks.put(new Task(1, "build"), "running");
tasks.put(new Task(2, "test"), "queued");

for (Task task : tasks.keySet()) {
    System.out.println(task.priority() + " " + task.name());
}

The output is ordered by priority: 1 build, 2 test, 3 deploy. The comparator is invoked on every put, get, remove, and navigation operation, so it must be fast and side-effect free. A comparator that performs expensive computation or accesses mutable external state will slow down every map operation.

What Happens When Keys Cannot Be Compared

If a key class does not implement Comparable and no comparator is provided, the first put throws ClassCastException. The failure happens at runtime, not at compile time, because the generic type parameter does not enforce Comparable.

Mutable keys are a more dangerous failure mode. If a key's fields change after insertion, the tree structure no longer reflects the new ordering. The entry remains at its original position, but lookups and iteration may return incorrect results or miss entries entirely. The standard solution is to use immutable keys, or to remove the entry and reinsert it after the key changes.

// Dangerous: mutating a key after insertion
TreeMap<StringBuilder, Integer> map = new TreeMap<>();
StringBuilder key = new StringBuilder("a");
map.put(key, 1);
key.append("b"); // tree structure is now inconsistent

Performance Cost of Maintaining Sorted Order

Every TreeMap operation runs in O(log n) time because the red-black tree requires comparisons and rotations to maintain balance. This is slower than HashMap's average O(1) lookup and insertion. The cost is justified when sorted iteration is a core requirement.

If you only need sorted output occasionally, a HashMap plus a one-time sort may be cheaper:

List<String> keys = new ArrayList<>(hashMap.keySet());
keys.sort(null); // natural order

This costs O(n log n) once. For a workload with many writes and rare sorted reads, the HashMap approach avoids paying the tree maintenance cost on every write.

TreeMap also provides navigation methods that rely on the sorted structure: firstKey(), lastKey(), floorKey(), ceilingKey(), lowerKey(), and higherKey(). These are useful for range queries and nearest-key lookups, and they are the main reason to choose TreeMap over a sorted copy of a HashMap.

Choosing Between TreeMap and HashMap

The decision depends on whether sorted iteration and navigation are required.

Use TreeMap when you need sorted iteration, range queries, or nearest-key navigation. Use HashMap when order does not matter and you want the lowest average cost per operation.

Edge Cases That Break TreeMap Sorting

Null keys are rejected. The put method throws NullPointerException because the comparator cannot compare null against another key. HashMap, by contrast, allows a single null key.

An inconsistent comparator can corrupt the tree. The red-black tree assumes a total ordering: the comparator must be transitive, and it must return the same result for the same pair of keys across calls. A comparator that depends on mutable state, or one that violates transitivity, can cause entries to disappear during iteration or be stored in the wrong position.

// Inconsistent comparator: depends on mutable state
class MutableComparator implements Comparator<String> {
    boolean reversed = false;
    public int compare(String a, String b) {
        return reversed ? b.compareTo(a) : a.compareTo(b);
    }
}

If the comparator's behavior changes after entries have been inserted, the tree structure no longer matches the comparator's current ordering. The map will behave unpredictably. The same risk applies to any comparator that reads mutable external state during comparison. Keep comparators pure and deterministic, and prefer immutable key types, to keep the sorted structure reliable.