Java TreeMap Usage: Sorted Map Operations

TreeMap is the standard Map implementation in Java that keeps its keys in sorted order. When you iterate over a TreeMap, the entries come back ordered by key, not in insertion order and not in hash order. That single property drives most of the practical java treemap usage: any code that needs to process map entries in sorted key order, find the nearest key to a target, or produce a deterministic traversal can rely on TreeMap without an extra sorting step.

Creating a TreeMap and Understanding Its Ordering

The simplest way to create a TreeMap is with the no-argument constructor, which uses the natural ordering of the keys. The key type must implement Comparable; otherwise the constructor throws a ClassCastException at insertion time.

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

for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

The output is alice, bob, carol, in lexicographic order, because String implements Comparable. The iteration order of a TreeMap is the sorted order of its keys at the time of iteration. Inserting the same keys in a different order does not change the traversal order.

Custom Ordering with a Comparator

When natural ordering is not what you need, pass a Comparator to the constructor. This is common when keys are custom objects, or when you want descending order.

TreeMap<Integer, String> descending = new TreeMap<>(Comparator.reverseOrder());
descending.put(3, "three");
descending.put(1, "one");
descending.put(2, "two");

Iterating over this map yields 3, 2, 1. The comparator is applied consistently for every operation: insertion, lookup, and navigation all use the same comparator. That means a get() call locates the key using the comparator, so the comparator must be consistent with equals() for correct behavior. If the comparator treats two keys as equal but equals() does not, the map can hold duplicate logical keys and lookups become unpredictable.

Navigating the Sorted Key Space

The sorted structure enables methods that other Map implementations do not have. firstKey() and lastKey() return the smallest and largest keys. floorKey(k) returns the greatest key less than or equal to k, and ceilingKey(k) returns the smallest key greater than or equal to k. lowerKey(k) and higherKey(k) are the strict versions that exclude the key itself.

TreeMap<Integer, String> events = new TreeMap<>();
events.put(10, "start");
events.put(20, "checkpoint");
events.put(30, "end");

Integer before = events.floorKey(25);   // 20
Integer after = events.ceilingKey(25);  // 30

This pattern is useful for range queries, such as finding which event applies at a given time. The subMap(), headMap(), and tailMap() methods return views of the map restricted to a key range. These views are backed by the original map, so changes made through the view are reflected in the map, and vice versa.

Performance Characteristics and Runtime Behavior

TreeMap is backed by a red-black tree, so the cost of put, get, remove, and the navigation methods is O(log n). HashMap offers O(1) average cost for the basic operations but provides no ordering. The decision between them depends on whether sorted iteration or range queries are part of the workload.

If the map is large and the only operation is occasional lookup by exact key, HashMap is the better choice. If the map is iterated frequently in sorted order, or if range queries are common, TreeMap avoids the cost of sorting the entries on each traversal. The red-black tree also keeps the map balanced, so worst-case behavior stays logarithmic rather than degrading to linear.

Concurrency: What TreeMap Does and Does Not Guarantee

TreeMap is not thread-safe. Concurrent modification from multiple threads requires external synchronization. Collections.synchronizedMap(new TreeMap<>()) provides a synchronized wrapper, but iteration still needs manual synchronization because the iterator is fail-fast and throws ConcurrentModificationException if the map changes during traversal.

For concurrent access with sorted ordering, ConcurrentSkipListMap is the standard alternative. It provides sorted iteration and thread safety without locking the entire map. If the workload is read-heavy and writes are rare, a synchronized TreeMap may be acceptable; for general concurrent use, ConcurrentSkipListMap is usually the better fit.

Null Keys and Values: Where TreeMap Differs

TreeMap does not accept null keys. The natural ordering comparator throws NullPointerException when comparing a null key. A custom comparator that handles null can allow null keys, but this is rarely a good idea because the navigation methods then have ambiguous behavior. Null values are allowed, just as in other Map implementations.

Choosing Between TreeMap and Other Map Implementations

The choice comes down to ordering requirements. HashMap gives the best average performance for unordered access. LinkedHashMap preserves insertion order with O(1) operations. TreeMap provides sorted order and range navigation at O(log n) cost.

Use TreeMap when the keys must be traversed in sorted order, when you need floor, ceiling, lower, or higher queries, or when a deterministic iteration order matters for output or testing. Use HashMap when ordering is irrelevant and lookup speed dominates. Use LinkedHashMap when insertion order is the requirement.