Java TreeMap: The Complete Reference

TreeMap keeps its keys sorted, which costs O(log n) per operation against HashMap’s O(1). You do not pay that for the ordering alone: you pay it for the navigation methods, and if the code never calls floorKey, headMap or firstEntry, a HashMap plus a sort is usually the better trade.

Written against Java 17.

The basics

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("charlie", 3);
scores.put("alpha", 1);
scores.put("bravo", 2);

System.out.println(scores);           // {alpha=1, bravo=2, charlie=3}
System.out.println(scores.firstKey()); // alpha
System.out.println(scores.lastEntry()); // charlie=3

Iteration is in key order, always, regardless of insertion order. That is the guarantee LinkedHashMap (insertion order) and HashMap (no order) do not make.

Underneath is a red-black tree, a self-balancing binary search tree, so the height stays logarithmic and get, put and remove are all O(log n). The balancing happens on write, which is why inserting already-sorted data costs the same here as random data; a plain unbalanced BST would degenerate to a linked list on exactly that input.

The navigation methods, which are the point

NavigableMap<Integer, String> tiers = new TreeMap<>();
tiers.put(0,    "free");
tiers.put(100,  "basic");
tiers.put(500,  "pro");
tiers.put(2000, "enterprise");

tiers.floorEntry(750);      // 500=pro    — greatest key <= 750
tiers.ceilingEntry(750);    // 2000=...   — smallest key >= 750
tiers.lowerEntry(500);      // 100=basic  — strictly less than
tiers.higherEntry(500);     // 2000=...   — strictly greater than

floor and ceiling include the key itself; lower and higher exclude it. Getting that pair backwards is the most common bug with this class, and it only shows on an exact match.

This is the operation a HashMap cannot do at all. “Which pricing tier applies to 750 units”, “what was the last reading before this timestamp”, “which rate band does this salary fall in” are all one floorEntry call, and a linear scan otherwise.

All four have *Key variants returning just the key, and all return null when nothing qualifies — which is worth handling explicitly, since a TreeMap<Integer, String> legitimately containing null values makes the return ambiguous.

Range views

tiers.headMap(500);           // keys < 500
tiers.headMap(500, true);     // keys <= 500
tiers.tailMap(500);           // keys >= 500  (inclusive by default — note the asymmetry)
tiers.subMap(100, true, 2000, false);   // 100 inclusive, 2000 exclusive
tiers.descendingMap();

The default inclusivity is not symmetric: headMap excludes the bound and tailMap includes it. The explicit two-argument forms remove the guesswork and are worth using.

These are views, not copies. They are backed by the map, so changes flow both ways, and writing outside the view’s range throws IllegalArgumentException. The view costs nothing to create. It is not a filtered copy, which is what makes range queries cheap.

scores.subMap("b", "c").clear();     // removes the matching entries from the underlying map

Comparators, and agreement with equals

TreeMap<String, Integer> caseInsensitive = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.put("Alpha", 1);
caseInsensitive.put("ALPHA", 2);

caseInsensitive.size();          // 1 — the comparator says these are the same key

A TreeMap decides key identity with compareTo or the comparator, never with equals. That is the crucial difference from HashMap, and it means a comparator inconsistent with equals produces a map that violates the Map contract in ways that look like bugs elsewhere: containsKey returns true for a key that is not equals to any stored key.

Sometimes that is exactly the intent, as above. When it is not, make sure the comparator compares everything equals does.

A comparator that returns 0 for distinct objects loses data: the second put overwrites the first. A comparator on one field of an object is the usual way to hit this.

TreeMap<Person, String> byAge = new TreeMap<>(Comparator.comparingInt(Person::age));
// two people of the same age collapse into one entry

Add a tie-breaker on something unique, thenComparing(Person::id), and the collapse disappears.

Nulls throw

treeMap.put(null, "value");     // NullPointerException

Keys cannot be null, because sorting requires comparing them. HashMap allows one null key; the two classes differ here and swapping one for the other can surface a latent null.

Values may be null. That is what makes map.get(k) == null ambiguous between “absent” and “present and null”, use containsKey, or getOrDefault with a sentinel.

An interesting asymmetry: an empty TreeMap accepts put(null, v) on some JDK versions because nothing needs comparing yet, then throws on the second insert. Do not rely on either behaviour.

Iteration and the entry API

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

for (Map.Entry<String, Integer> entry : scores.descendingMap().entrySet()) { }

Map.Entry<String, Integer> first = scores.pollFirstEntry();   // reads AND removes

entrySet() is the loop to use when both key and value are needed. Iterating keySet() and calling get on each is a second O(log n) lookup per element.

pollFirstEntry and pollLastEntry remove as they read, which makes a TreeMap usable as a priority queue that also supports lookup and removal by key. Something PriorityQueue does only in linear time.

entry.setValue(v) writes through to the map and is the supported way to modify during iteration. Calling map.put inside the loop throws ConcurrentModificationException, and so does remove — use iterator.remove() or collect the keys first.

Java 21 added SequencedMap, which TreeMap implements, giving firstEntry, lastEntry, putFirst, putLast and reversed() as a common vocabulary shared with LinkedHashMap. On a TreeMap the positional put methods throw, because position is determined by the ordering rather than by the caller.

Building one

TreeMap<String, Integer> copy = new TreeMap<>(existingMap);          // sorts on construction
TreeMap<String, Integer> sorted = new TreeMap<>(Comparator.reverseOrder());

Map<String, Integer> collected = list.stream()
        .collect(Collectors.toMap(Item::name, Item::count, (a, b) -> a, TreeMap::new));

Constructing from an unsorted Map is O(n log n). Constructing from a SortedMap with the same ordering is O(n), because the tree can be built directly without comparisons, worth knowing when copying a large map defensively.

The four-argument toMap is the way to collect a stream into a TreeMap; the two-argument form gives a HashMap and the ordering is lost.

Not thread-safe

NavigableMap<String, Integer> safe = Collections.synchronizedNavigableMap(new TreeMap<>());
ConcurrentNavigableMap<String, Integer> better = new ConcurrentSkipListMap<>();

ConcurrentSkipListMap is the concurrent sorted map: a skip list rather than a tree, with the same NavigableMap API and O(log n) operations. Prefer it over a synchronised wrapper, which locks the whole map per call and gives no atomic compound operations.

Iterating a synchronised wrapper still needs manual synchronisation on the wrapper, or you get ConcurrentModificationException.

When to use it

Reach for TreeMap when the code needs at least one of:

• Nearest-match lookup, floorKey, ceilingKey. This is the strongest reason.
• Range queries, subMap, headMap, tailMap as live views.
• First and last: firstEntry, pollLastEntry, which make it a usable priority structure with removal by key.
• Always-sorted iteration where the map changes constantly, so re-sorting a list each time would cost more.

Use a HashMap when lookups are by exact key. The constant factor matters: HashMap is roughly two to three times faster on get at typical sizes, and it uses less memory per entry: a tree node carries two child pointers, a parent pointer and a colour bit.

If the data is loaded once and then only read in order, a sorted ArrayList with Collections.binarySearch beats both on memory and cache locality.

Compare with HashMap for the hash-based alternative and PriorityQueue when only the smallest element matters. More in the Java guides.

Frequently asked questions

What is the difference between TreeMap and HashMap?

TreeMap keeps keys sorted and offers navigation and range methods at O(log n); HashMap is unordered at O(1). Choose on whether you need the ordering.

What is the difference between floor and lower?

floorKey includes an exact match, lowerKey excludes it. Same for ceiling and higher in the other direction.

Are headMap and subMap copies?

No. They are live views backed by the map. Changes flow both ways and writing outside the range throws.

Why is tailMap inclusive but headMap exclusive?

That is the API’s default, and it is asymmetric. Use the two-argument forms that state inclusivity explicitly.

Does TreeMap use equals to compare keys?

No, compareTo or the comparator. A comparator inconsistent with equals makes the map violate the Map contract in confusing ways.

Why did two of my entries collapse into one?

The comparator returned 0 for them, so the map treats them as the same key and the second put overwrites. Add a tie-breaker on a unique field.

Can a TreeMap have a null key?

No, sorting requires comparison. HashMap allows one, so swapping the implementation can expose a latent null. Values may be null.

Is TreeMap thread-safe?

No. Use ConcurrentSkipListMap, which offers the same NavigableMap API concurrently, rather than a synchronised wrapper.

What is the time complexity?

O(log n) for get, put, remove and the navigation methods. size is O(1); building from a sorted source is O(n log n).

When is a sorted ArrayList better?

When the data is loaded once and only read. Binary search over a compact array beats a tree on memory and cache locality; a tree wins once the data changes.