Skip to content
Tutorials Center
My learning

Topics

Java Reference ยท Collections

The TreeMap class

Reference for java.util.TreeMap: a map sorted by key using a red-black tree, Comparator ordering, floorKey and ceilingKey, and live range views.

TreeMap<K, V> keeps its entries sorted by key. It is implemented as a red-black tree, so get, put and remove take O(log n), and iteration visits keys in ascending order. It also implements NavigableMap, which adds methods such as "the greatest key not above this value" and live sub-map views.

The ordering comes from the keys' natural order (Comparable) or from a Comparator given to the constructor. As with TreeSet, that ordering also defines key equality: keys that compare as 0 are the same key.

Java
TreeMap<String, Integer> byName = new TreeMap<>();
TreeMap<String, Integer> descending = new TreeMap<>(Comparator.reverseOrder());

Try it

Java Sorted keys and navigation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Java Comparators and live views

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Syntax

Java
public class TreeMap<K, V> extends AbstractMap<K, V>
        implements NavigableMap<K, V>, Cloneable, java.io.Serializable
Constructor Description
TreeMap() Natural ordering of keys.
TreeMap(Comparator<? super K> c) Ordering from the comparator.
TreeMap(Map<? extends K, ? extends V> m) Natural ordering, filled from m.
TreeMap(SortedMap<K, ? extends V> m) Same entries and same comparator as m.
Member Description
firstKey(), lastKey() Throw NoSuchElementException if empty.
firstEntry(), lastEntry(), pollFirstEntry(), pollLastEntry() Return null if empty.
lowerKey, floorKey, ceilingKey, higherKey (and ...Entry forms) Neighbor lookups; null when none.
headMap(to), tailMap(from), subMap(from, to) Live range views; overloads take inclusive flags.
descendingMap(), navigableKeySet(), descendingKeySet() Reverse and key views.

Usage notes

  • Complexity: O(log n) for get, put, remove, containsKey and navigation; containsValue is O(n).
  • Comparator defines identity: get() uses the comparator, not equals(). A comparator that is inconsistent with equals() makes the map violate the general Map contract (though it stays well-defined).
  • Null keys are rejected with natural ordering (NullPointerException); null values are allowed.
  • Entries from firstEntry() and friends are immutable snapshots; setValue() throws UnsupportedOperationException. Entries from entrySet() iteration do allow setValue().
  • Views are live, and inserting outside a view's range throws IllegalArgumentException.
  • Range queries such as "all keys between a and b" are the main reason to choose TreeMap over HashMap.
  • Not synchronized. For concurrent sorted maps use ConcurrentSkipListMap.
  • Do not mutate keys in ways that change their ordering.