TreeMap, TreeSet and sorted collections

TreeMap and TreeSet keep their elements sorted all the time and can answer range questions: the first key, the nearest key below or above a value, everything between two keys.

🔎 Unravel this example Prerequisites (2)

Learn these first

Comparable and Comparator Collections: List, Set, Map

At a glance

Mental model

A dictionary versus a pile of index cards: the dictionary is always in alphabetical order, so you can open it near "M" and find the next word after "monkey" without reading the entire book.

What happens, in order

1Order comes from Comparable keys or a Comparator passed to the constructorOperations (get, put, remove) cost O(log n), slower than a hash map but ordered.
2Navigation: floorKey(k) is the greatest key at most k, ceilingKey(k) the smallest at least k, lowerKey/higherKey are strict, firstKey/lastKey the ends, pollFirstEntry removes and returns the smallest
3Ranges: headMap(to), tailMap(from), subMap(from, to) return views of part of the mapdescendingMap() iterates in reverse.
4Typical uses: time-series lookups ("the rate valid on this date"), leaderboards, interval scheduling, sorted output

Remember

Sorted collections define "duplicate" through the comparator: two different objects that compare as 0 count as the same key, and one silently replaces the other
Keys must not be mutated while in the map
TreeMap is a red-black tree: a self-balancing binary search tree with a height of at most 2·log2(n+1)

Watch out

Using a comparator that is inconsistent with equals and losing entriesCalling firstKey() on an empty map (NoSuchElementException)Expecting headMap to be a copy

Example (highlighted lines explain it)

import java.util.*;public class Rates {  private final TreeMap<java.time.LocalDate, Double> byDate = new TreeMap<>();  void add(java.time.LocalDate from, double rate) { byDate.put(from, rate); }  double rateOn(java.time.LocalDate day) {    Map.Entry<java.time.LocalDate, Double> e = byDate.floorEntry(day);    return e == null ? 0.0 : e.getValue();  }  java.time.LocalDate earliest() { return byDate.firstKey(); }}

line 3 uses TreeMap, the core of TreeMap, TreeSet and sorted collections
line 6 uses floorEntry, the core of TreeMap, TreeSet and sorted collections
line 9 uses firstKey, the core of TreeMap, TreeSet and sorted collections

Read the full explanation (about 1 min)

TreeMap and TreeSet keep their elements sorted all the time and can answer range questions: the first key, the nearest key below or above a value, everything between two keys.

A mental model

A dictionary versus a pile of index cards: the dictionary is always in alphabetical order, so you can open it near "M" and find the next word after "monkey" without reading the entire book.

How it works

Order comes from Comparable keys or a Comparator passed to the constructor. Operations (get, put, remove) cost O(log n), slower than a hash map but ordered.

Navigation: floorKey(k) is the greatest key at most k, ceilingKey(k) the smallest at least k, lowerKey/higherKey are strict, firstKey/lastKey the ends, pollFirstEntry removes and returns the smallest.

Ranges: headMap(to), tailMap(from), subMap(from, to) return views of part of the map. descendingMap() iterates in reverse.

Typical uses: time-series lookups ("the rate valid on this date"), leaderboards, interval scheduling, sorted output.

Going deeper

Sorted collections define "duplicate" through the comparator: two different objects that compare as 0 count as the same key, and one silently replaces the other.

Keys must not be mutated while in the map. TreeMap does not allow null keys with natural ordering.

For concurrent access use ConcurrentSkipListMap. If you only need the smallest element repeatedly, a PriorityQueue is cheaper.

Under the hood

TreeMap is a red-black tree: a self-balancing binary search tree with a height of at most 2·log2(n+1). Each entry is a node with key, value, left, right, parent and a colour bit.

Common mistakes

Using a comparator that is inconsistent with equals and losing entries.
Calling firstKey() on an empty map (NoSuchElementException).
Expecting headMap to be a copy.

How Unravel recognises it

When you paste code, Unravel looks for these signs of treemap, treeset and sorted collections. Spotting them yourself is a good habit when you read unfamiliar code:

Types: TreeMap TreeSet SortedMap SortedSet NavigableMap NavigableSet
Method calls: firstKey() lastKey() floorKey() ceilingKey() headMap() tailMap() subMap() firstEntry() pollFirstEntry() descendingMap() higherKey() lowerKey() floorEntry() ceilingEntry()

Part of a learning path

Collections in depth · previous: Sets: HashSet, LinkedHashSet, EnumSet · next: Queue, Deque and Stack

Related concepts

Comparable and ComparatorJava language PriorityQueue and heapsJava language How HashMap worksJava language

Frequently asked questions

What is TreeMap, TreeSet and sorted collections?

TreeMap and TreeSet keep their elements sorted all the time and can answer range questions: the first key, the nearest key below or above a value, everything between two keys.

What are the most common mistakes with TreeMap, TreeSet and sorted collections?

Using a comparator that is inconsistent with equals and losing entries. Calling firstKey() on an empty map (NoSuchElementException). Expecting headMap to be a copy.

How can I see TreeMap, TreeSet and sorted collections in real code?

Paste your own Java into Unravel and it will point out where treemap, treeset and sorted collections appears, explain how it works at the detail level you choose, and draw the flow of the code around it.