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.
TreeMap<String, Integer> byName = new TreeMap<>(); TreeMap<String, Integer> descending = new TreeMap<>(Comparator.reverseOrder());
Try it
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.
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
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)forget,put,remove,containsKeyand navigation;containsValueisO(n). - Comparator defines identity:
get()uses the comparator, notequals(). A comparator that is inconsistent withequals()makes the map violate the generalMapcontract (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()throwsUnsupportedOperationException. Entries fromentrySet()iteration do allowsetValue(). - 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
TreeMapoverHashMap. - Not synchronized. For concurrent sorted maps use
ConcurrentSkipListMap. - Do not mutate keys in ways that change their ordering.
Related
- Map, HashMap, LinkedHashMap, TreeSet, Comparable
- Lessons: TreeMap and TreeSet, Choosing a collection