TreeMap, SortedMap and NavigableMap in Java - Quiz

TreeMap stores its entries in the nodes of a red-black tree, a self-balancing binary search tree whose height stays around log n. That is why get(), put(), remove() and containsKey() take O(log n), and iteration always goes in ascending key order.

Keys are compared not with equals() and hashCode() but with compareTo() (natural ordering, the key must be Comparable) or with a Comparator passed to the constructor. If the comparison returns 0, the keys are treated as the same: put() replaces the value and keeps the original key.

Two consequences follow: put(null, ...) with natural ordering throws NullPointerException, and a key that is neither Comparable nor covered by a comparator throws ClassCastException on the first put(). TreeMap implements the SortedMap and NavigableMap interfaces.

SortedMap (Java 1.2) guarantees ascending key order and adds firstKey(), lastKey(), comparator() and the ranges headMap(to), subMap(from, to), tailMap(from): the lower bound is included, the upper bound is not. The ranges are live views of the original map; putting a key outside the range throws IllegalArgumentException: key out of range.

NavigableMap (Java 6) extends SortedMap with navigation methods: lowerKey(), floorKey(), ceilingKey(), higherKey() and their Entry versions, firstEntry()/lastEntry(), pollFirstEntry()/pollLastEntry(), descendingMap(), plus headMap(), tailMap() and subMap() with an inclusive flag for each bound. Its implementations are TreeMap and the thread-safe ConcurrentSkipListMap.

All four find the nearest key and do not need an exact match: lowerKey(k) is the greatest key strictly less than k (<), floorKey(k) is the greatest key less than or equal to k (≤), ceilingKey(k) is the least key greater than or equal to k (≥), and higherKey(k) is the least key strictly greater than k (>). If there is no such key, they return null.

For a map with keys 10, 20, 30, 40, 50: lowerKey(30) = 20, floorKey(30) = 30, ceilingKey(30) = 30, higherKey(30) = 40; for the missing key 35, floorKey = 30 and ceilingKey = 40; lowerKey(10) and higherKey(50) return null. The methods lowerEntry(), floorEntry(), ceilingEntry() and higherEntry() return the whole pair as an immutable snapshot whose setValue() throws UnsupportedOperationException.

Use the lower bound of each range as the map key and look the range up with floorEntry(value), which returns the greatest key not exceeding the value. That is O(log n) instead of an if-else chain:

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");
grades.floorEntry(79).getValue(); // C

If the value is below the lowest bound (for example, -5), floorEntry() returns null and getValue() throws NullPointerException, so the scale must start at the lowest possible value or the result must be checked. The same approach works for shipping rates by weight, discounts by order total and schedules: subMap(from, true, to, true) for a time window, ceilingEntry(now) for the next event.

HashMap is the default choice: get() and put() are O(1) on average, but key order is not guaranteed; keys need correct equals() and hashCode(), and one null key is allowed.

TreeMap is slower, O(log n) per operation, but keeps keys sorted in ascending order or by a Comparator, finds the nearest key (floorKey(), ceilingEntry()), gives the minimum and maximum and cuts out ranges (subMap()). Keys must be Comparable or handled by a comparator; a null key is not allowed with natural ordering.

A common trick is to collect data in a HashMap and sort it once before output: new TreeMap<>(hashMap). Neither map is thread-safe: the concurrent replacement for HashMap is ConcurrentHashMap, and for TreeMap it is ConcurrentSkipListMap.