TreeMap, SortedMap and NavigableMap in Java

Swap new HashMap<>() for new TreeMap<>() to get keys printed in alphabetical order, and code that has worked for years suddenly fails on map.put(null, 0) with a NullPointerException. A HashMap simply puts the null key into bucket 0, while a TreeMap has to compare every key with compareTo(), and null cannot be compared. That is not the only difference: a sorted map has its own rules, its own exceptions and a set of search methods that HashMap does not have at all.

TreeMap is a Map implementation backed by a red-black tree that keeps key–value pairs sorted by key: in natural ordering (Comparable) or by a Comparator you pass in. TreeMap implements SortedMap (Java 1.2: first and last key, key ranges) and NavigableMap (Java 6: nearest-key lookups — floorKey(), ceilingKey(), lowerKey(), higherKey()). The get(), put(), remove() and containsKey() operations run in O(log n).

The TreeMap class: how it works and how to create one

A TreeMap in Java stores its entries in the nodes of a red-black tree — a self-balancing binary search tree whose height always stays around log n. That is why lookup, insertion and removal by key take O(log n), and iteration always goes in ascending key order, no matter in which order the entries were added.

Keys are compared not with equals() and hashCode(), but with compareTo() or the comparator's compare(): if the comparison returns 0, the keys are treated as the same key. The hierarchy looks like this:

Map<K,V>
└── SortedMap<K,V>        (Java 1.2; extends SequencedMap since Java 21)
    └── NavigableMap<K,V>  (Java 6)
        ├── TreeMap<K,V>
        └── ConcurrentSkipListMap<K,V>  (thread-safe)

The basic put(), get() and entrySet() methods and the ways to iterate are shared by all maps — they are covered in Map Interface in Java. Example: salaries added in random order come out of a TreeMap sorted by last name:

import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, Double> salaries = new TreeMap<>();

        salaries.put("Smith", 123.22);
        salaries.put("Taylor", 1378.00);
        salaries.put("Brown", 3434.34);

        salaries.forEach((key, value) -> System.out.println(key + ": " + value));
    }
}

Output:

Brown: 3434.34
Smith: 123.22
Taylor: 1378.0

Strings are compared by character code, so all uppercase letters come before lowercase ones: a key "adams" would be printed after "Taylor" (details in How compareTo compares strings).

TreeMap constructors

TreeMap has four constructors: an empty map with natural ordering, an empty map with a comparator, and a copy of another map — a plain one or a sorted one.

TreeMap with a Comparator

To sort a TreeMap in an order other than the natural one, pass a Comparator to the constructor: for example Comparator.reverseOrder() for descending keys or String.CASE_INSENSITIVE_ORDER for strings that ignore case. The comparator decides not only the iteration order but also which keys the map considers the same.

NavigableMap<Integer, String> desc = new TreeMap<>(Comparator.reverseOrder());
desc.put(1, "a");
desc.put(5, "e");
desc.put(3, "c");
System.out.println(desc);            // Output: {5=e, 3=c, 1=a}
System.out.println(desc.firstKey()); // Output: 5 - "first" according to the comparator

What does this code print?

import java.util.TreeMap;

public class CaseInsensitiveKeys {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
        map.put("Java", 1);
        map.put("JAVA", 2);
        map.put("python", 3);

        System.out.println(map);
        System.out.println(map.get("jAvA"));
        System.out.println(map.containsKey("PYTHON"));
    }
}

Output:

{Java=2, python=3}
2
true

The comparator returned 0 for “Java” and “JAVA”, so the second put() did not add a new entry — it replaced the value of the existing one. The key itself stayed “Java”, not “JAVA”. For dictionaries, logins and HTTP headers that is exactly what you want; for data where case matters it is a way to lose entries silently. Why this happens and how to write a comparator that is consistent with equals() is explained in Comparable and Comparator.

The SortedMap interface and its methods

SortedMap is the interface of a sorted map: it guarantees iteration in ascending key order and adds to Map methods for the first and last key and for cutting out a key range (headMap(), subMap(), tailMap()). The lower bound of a range is included, the upper bound is not.

Example: the keys are added in random order, and the SortedMap methods treat them as the sorted sequence 1, 2, 3, 4, 5, 100:

import java.util.SortedMap;
import java.util.TreeMap;

public class SortedMapExample {
    public static void main(String[] args) {
        SortedMap<Integer, Double> treeMap = new TreeMap<>();

        treeMap.put(3, 3434.34);
        treeMap.put(2, 1378.00);
        treeMap.put(1, 123.22);
        treeMap.put(4, 444.00);
        treeMap.put(5, 555.00);
        treeMap.put(100, 123.22);

        System.out.println("treeMap: " + treeMap);
        System.out.println("firstKey: " + treeMap.firstKey());
        System.out.println("lastKey: " + treeMap.lastKey());
        System.out.println("headMap(3): " + treeMap.headMap(3));
        System.out.println("subMap(3, 5): " + treeMap.subMap(3, 5));
        System.out.println("tailMap(4): " + treeMap.tailMap(4));
    }
}

Output:

treeMap: {1=123.22, 2=1378.0, 3=3434.34, 4=444.0, 5=555.0, 100=123.22}
firstKey: 1
lastKey: 100
headMap(3): {1=123.22, 2=1378.0}
subMap(3, 5): {3=3434.34, 4=444.0}
tailMap(4): {4=444.0, 5=555.0, 100=123.22}

headMap(3) cuts off the beginning of the map up to key 3, without including it. subMap(3, 5) takes the middle: key 3 is in, key 5 is out. tailMap(4) returns the “tail” from key 4 inclusive to the end. The same bound rules apply to sets — headSet(), subSet() and tailSet() in the lesson SortedSet, NavigableSet and TreeSet.

headMap, subMap and tailMap are live views

The range methods do not copy data: they return a view of the original map. Changes to the original map show up in the view immediately and vice versa, and you cannot put a key outside the view's range into it.

TreeMap<Integer, String> map = new TreeMap<>(Map.of(10, "ten", 20, "twenty", 30, "thirty"));
SortedMap<Integer, String> head = map.headMap(25);   // keys less than 25

map.put(15, "fifteen");      // added to the original map
System.out.println(head);

head.remove(10);             // removed through the view
System.out.println(map);

head.put(40, "forty");       // 40 is outside the range < 25

Output:

{10=ten, 15=fifteen, 20=twenty}
{15=fifteen, 20=twenty, 30=thirty}
Exception in thread "main" java.lang.IllegalArgumentException: key out of range

If you need an independent copy of a range, wrap the view: new TreeMap<>(map.headMap(25)). The same view behavior applies to keySet(), values() and entrySet() of any map.

NavigableMap in Java: finding the nearest key

NavigableMap in Java is an interface that extends SortedMap with navigation methods: find the nearest key that is less than, at most, at least or greater than a given key, take and remove the first or last entry, view the map in reverse order, and get ranges with explicit flags for including each bound. It was added in Java 6 and is implemented by TreeMap and ConcurrentSkipListMap.

The key difference from get(): navigation methods do not need an exact key match. If there is no key 35, floorKey(35) returns the nearest key below it instead of null.

The entries returned by firstEntry(), floorEntry() and the other *Entry methods of TreeMap are immutable snapshots: calling entry.setValue(...) throws UnsupportedOperationException. To change the value, use map.put(entry.getKey(), newValue).

The example below runs all four lookup methods on one map, including key 35, which is not in the map, and the keys at both ends:

import java.util.NavigableMap;
import java.util.TreeMap;

public class NavigableMapExample {
    public static void main(String[] args) {
        NavigableMap<Integer, String> map = new TreeMap<>();
        map.put(30, "c");
        map.put(10, "a");
        map.put(50, "e");
        map.put(20, "b");
        map.put(40, "d");

        System.out.println("lowerKey(30) = " + map.lowerKey(30));
        System.out.println("floorKey(30) = " + map.floorKey(30));
        System.out.println("ceilingKey(30) = " + map.ceilingKey(30));
        System.out.println("higherKey(30) = " + map.higherKey(30));

        System.out.println("floorKey(35) = " + map.floorKey(35));
        System.out.println("ceilingKey(35) = " + map.ceilingKey(35));
        System.out.println("lowerKey(10) = " + map.lowerKey(10));
        System.out.println("higherKey(50) = " + map.higherKey(50));
        System.out.println("floorEntry(35) = " + map.floorEntry(35));
    }
}

Output:

lowerKey(30) = 20
floorKey(30) = 30
ceilingKey(30) = 30
higherKey(30) = 40
floorKey(35) = 30
ceilingKey(35) = 40
lowerKey(10) = null
higherKey(50) = null
floorEntry(35) = 30=c

When the key is in the map, floorKey() and ceilingKey() return the key itself, while lowerKey() and higherKey() return its neighbors. When the key is missing, the strict and non-strict methods give the same result. Beyond the ends of the map all four return null, so check the result before using it. The set versions of these methods are called lower(), floor(), ceiling() and higher() — see SortedSet, NavigableSet and TreeSet.

Ranges and reverse order in NavigableMap

In NavigableMap, headMap(), tailMap() and subMap() have overloads with inclusive flags: true includes the bound in the result, false excludes it. This removes the main inconvenience of SortedMap, where the upper bound is always excluded. To iterate from the largest key to the smallest, use descendingMap().

For the same map {10=a, 20=b, 30=c, 40=d, 50=e}:

System.out.println(map.headMap(30));                    // {10=a, 20=b}
System.out.println(map.headMap(30, true));              // {10=a, 20=b, 30=c}
System.out.println(map.tailMap(30, false));             // {40=d, 50=e}
System.out.println(map.subMap(20, false, 40, true));    // {30=c, 40=d}
System.out.println(map.descendingMap());                // {50=e, 40=d, 30=c, 20=b, 10=a}
System.out.println(map.descendingKeySet());             // [50, 40, 30, 20, 10]

The pollFirstEntry() and pollLastEntry() methods turn the map into a queue sorted by key: each call returns the entry at one end and removes it.

NavigableMap<Integer, String> queue = new TreeMap<>(map);

System.out.println("firstEntry: " + queue.firstEntry());
System.out.println("pollFirstEntry: " + queue.pollFirstEntry());
System.out.println("lastEntry: " + queue.lastEntry());
System.out.println("pollLastEntry: " + queue.pollLastEntry());
System.out.println("queue: " + queue);

Output:

firstEntry: 10=a
pollFirstEntry: 10=a
lastEntry: 50=e
pollLastEntry: 50=e
queue: {20=b, 30=c, 40=d}

firstEntry() and lastEntry() only read the end entries, while the poll methods return the same entries and remove them, so keys 10 and 50 are gone from the final map.

NavigableMap examples from real code

A NavigableMap fits any task where a value depends on the range a key falls into: grade scales and discount tiers, rates by weight or amount, time schedules. The key is the lower bound of each range, and floorEntry() finds the right range in O(log n) instead of a chain of if-else statements.

A grade scale with floorEntry

import java.util.NavigableMap;
import java.util.TreeMap;

public class GradeScale {
    public static void main(String[] args) {
        NavigableMap<Integer, String> grades = new TreeMap<>();
        grades.put(0, "F");
        grades.put(60, "D");
        grades.put(70, "C");
        grades.put(80, "B");
        grades.put(90, "A");

        for (int score : new int[]{95, 80, 79, 12}) {
            System.out.println(score + " -> " + grades.floorEntry(score).getValue());
        }
    }
}

Output:

95 -> A
80 -> B
79 -> C
12 -> F

For 80, floorEntry() finds an exact match; for 79, the nearest bound below it, 70. But for a negative score such as -5 there is no key ≤ -5 in the map: floorEntry(-5) returns null, and getValue() throws a NullPointerException. So the scale must start at the lowest possible value, or the result must be checked for null.

A schedule: events in a time window

import java.time.LocalTime;
import java.util.NavigableMap;
import java.util.TreeMap;

public class Schedule {
    public static void main(String[] args) {
        NavigableMap<LocalTime, String> schedule = new TreeMap<>();
        schedule.put(LocalTime.of(9, 0), "Stand-up");
        schedule.put(LocalTime.of(10, 30), "Code review");
        schedule.put(LocalTime.of(13, 0), "Lunch");
        schedule.put(LocalTime.of(15, 0), "Demo");
        schedule.put(LocalTime.of(17, 30), "Retro");

        LocalTime now = LocalTime.of(12, 0);
        System.out.println("From 10:00 to 15:00: "
                + schedule.subMap(LocalTime.of(10, 0), true, LocalTime.of(15, 0), true));
        System.out.println("Next: " + schedule.ceilingEntry(now));
        System.out.println("Previous: " + schedule.lowerEntry(now));
    }
}

Output:

From 10:00 to 15:00: {10:30=Code review, 13:00=Lunch, 15:00=Demo}
Next: 13:00=Lunch
Previous: 10:30=Code review

LocalTime implements Comparable, so no comparator is needed. The true flag on the upper bound included the event at exactly 15:00 — with subMap(from, to) from SortedMap, “Demo” would have been left out.

TreeMap vs HashMap: which one to choose

HashMap is the default choice: its operations take O(1) on average, but key order is not guaranteed. TreeMap is slower — O(log n) per operation — but it keeps keys sorted, can find the nearest key and can cut out key ranges. If you only need insertion order rather than sorting, use LinkedHashMap. And if you searched for “TreeHashMap”: there is no such class in Java — it is either TreeMap or HashMap.

Why HashMap runs in O(1) and what happens on collisions is covered in How HashMap Works Internally, and a summary table of all Map implementations is in Map Interface in Java. If O(1) and O(log n) are new to you, see Big O notation. A common pattern: collect data in a HashMap and sort it once before output with new TreeMap<>(hashMap).

Common TreeMap mistakes

Most TreeMap bugs come from two things: keys are compared with compareTo()/compare() rather than equals(), and range bounds are included differently depending on the method. Here are the usual mistakes and their fixes: