Java TreeMap

TreeMap<K, V> is the Map that keeps its keys sorted. Internally it's a red-black tree — the same self-balancing binary search tree that backs TreeSet — and every operation is O(log n): put, get, remove, the first key, the last key, range queries. The pay-off for the log cost is the navigation API on NavigableMap<K, V>: floor, ceiling, lower, higher, sub-map, head-map, tail-map, descending views. None of those are possible on a hash table without a full sort first.

If you ever find yourself doing new TreeMap<>(hashMap) at the end of a function to "sort the entries," that's the signal TreeMap should have been the type all along.

Two ways to define key order

A TreeMap needs to compare keys somehow. As with TreeSet:

1. Natural ordering — the key type implements Comparable<K>. Strings, numeric wrappers, dates, and your own record types that implement Comparable all qualify.
2. A Comparator<K> passed to the constructor — use it when natural order doesn't exist or doesn't match what you want.

Map<String, Integer> byName    = new TreeMap<>();                        // case-sensitive natural
Map<String, Integer> byNameCi  = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
Map<String, Integer> reverse   = new TreeMap<>(Comparator.reverseOrder());

As with TreeSet, equality is by compareTo returning 0, not by equals. Two keys that the comparator says are equal collapse into one entry — the second put overwrites the first. With String.CASE_INSENSITIVE_ORDER keying, putting \"Java\" and then \"JAVA\" leaves you with one entry whose key is the original \"Java\" and whose value is the second put's value. That's almost never what you want by accident.

The NavigableMap API

The interface a TreeMap implements gives you a lot of operations a plain Map doesn't:

TreeMap<Integer, String> t = new TreeMap<>();
t.put(10, \"a\"); t.put(20, \"b\"); t.put(30, \"c\"); t.put(40, \"d\");

t.firstKey();        // 10
t.lastKey();         // 40
t.firstEntry();      // 10=a
t.pollFirstEntry();  // 10=a, removes
t.lowerKey(30);      // 20 — strictly less
t.floorKey(30);      // 30 — ≤
t.higherKey(30);     // 40 — strictly greater
t.ceilingKey(30);    // 30 — ≥
t.headMap(30);       // {20=b}        — keys strictly < 30
t.tailMap(30);       // {30=c, 40=d}  — keys ≥ 30
t.subMap(20, 40);    // {20=b, 30=c}  — [20, 40)
t.descendingMap();   // reverse-order view

These are why TreeMap exists. "Find the closest event before 9 a.m." is headMap(9am).lastEntry() — one log-time lookup. The same operation on a HashMap would have to scan every key.

Sub-map views are live

subMap, headMap, and tailMap return views into the original map — not copies. Changes made through the view propagate back, and changes to the original that fall within the view's range show up in the view. The views also enforce the range: trying to put a key outside the range through the view throws IllegalArgumentException. That's how range-bounded iteration stays safe even when you mutate during the walk.

TreeMap<Integer, String> t = new TreeMap<>();
t.put(10, \"a\"); t.put(20, \"b\"); t.put(30, \"c\");
NavigableMap<Integer, String> mid = t.subMap(15, true, 25, true);
mid.put(20, \"updated\");   // OK — 20 is in range
// mid.put(40, \"x\");      // would throw — 40 is out of range
System.out.println(t);     // {10=a, 20=updated, 30=c}

Null is rejected (for keys)

You can't have a null key in a TreeMap for the same reason TreeSet rejects them: there's no sensible way to call compareTo on null. The first put(null, ...) throws NullPointerException. Null values are fine.

When to pick TreeMap

Decision flow:

• You need sorted iteration by key or range queries on keys → TreeMap. Only choice.
• You need fast lookup and order doesn't matter → HashMap. O(1) wins.
• You need fast lookup and insertion-order iteration → LinkedHashMap.
• The key type is an enum → EnumMap. Faster than TreeMap and naturally ordered.

A useful pattern: use a HashMap to build the map fast, then new TreeMap<>(hashMap) once to present a sorted view at the end. Build fast, present sorted.

A worked example: schedule lookup, range queries, comparator keying

The program below uses a TreeMap to model a small "event schedule" keyed by minutes-since-midnight. It demonstrates the navigation API for "what's the next event after X" and "everything before Y," shows the live sub-map view, and reveals the comparator-equality trap with a case-insensitive map.

What to take from the run:

• The schedule prints in chronological order without any explicit sort. Adding \"coffee\" at 11:30 slotted it into the right place automatically.
• ceilingEntry(11*60) returned the design review at 10:30... no — at 11:00 we asked, and the next entry at-or-after 11:00 is 13:00's lunch. lowerEntry(11*60) returned 10:30's design review. Both are O(log n).
• The morning sub-map is a live view — coffee showed up in it after we put it into the original map. If we'd put \"midnight snack\" at 23:00, the view would have ignored it (out of range).
• pollFirstEntry repeatedly drained the next-up event. That's a poor-person's priority queue when you also want lookups by key, which a real PriorityQueue can't give you.
• The case-insensitive map collapsed \"Java\" and \"JAVA\" into one entry — keyed by the original \"Java\" but with the second put's value 2. Comparator equality, not equals-equality.

What's next

The four modern map implementations — HashMap, LinkedHashMap, TreeMap, and ConcurrentHashMap — are the ones to reach for in new code. There's one more in the JDK that predates them all and you'll still see it occasionally in old code: Hashtable. It's worth knowing why it exists, why it's almost always the wrong choice today, and how to replace it.

Practice