Ordered maps and sets

TreeMap<K, V> is a map whose keys are kept in sorted order. In the JDK it is a red-black tree, a self-balancing BST (the topic of the next chapter), so get, put and remove cost O(log n) even for sorted input. Iteration visits keys in increasing order. A HashMap is O(1) on average but has no order and no neighbour queries.

Use TreeMap when you need sorted iteration, nearest-key lookups, or range views. Keys must be comparable (or a Comparator must be given), and a null key throws NullPointerException with natural ordering.

1static void treeMapBasics() {
2    TreeMap<Integer, String> m = new TreeMap<>();
3    m.put(50, "fifty"); m.put(30, "thirty"); m.put(70, "seventy"); m.put(20, "twenty");
4    System.out.println(m);                       // {20=twenty, 30=thirty, 50=fifty, 70=seventy}: sorted by key
5    System.out.println(m.firstKey() + " " + m.lastKey());            // 20 70
6    for (Map.Entry<Integer, String> e : m.entrySet()) System.out.print(e.getKey() + " ");   // 20 30 50 70
7}

TreeSet<E> is a sorted set backed by a TreeMap: no duplicates (by the comparison), sorted iteration, O(log n) add, remove and contains. It is the structure to reach for with 'keep the elements ordered while inserting and removing', such as a sweep line's active set or a leaderboard.

first() and last() return the extremes, pollFirst() and pollLast() remove them, and the neighbour methods below find the closest elements to a value. Rule of thumb: a PriorityQueue if you only ever need the extreme; a TreeSet if you also need to delete arbitrary elements or find neighbours.

1static void treeSetBasics() {
2    TreeSet<Integer> s = new TreeSet<>(List.of(40, 10, 30, 20, 30));
3    System.out.println(s);                       // [10, 20, 30, 40]: sorted, the duplicate 30 is dropped
4    System.out.println(s.first() + " " + s.last());            // 10 40
5    System.out.println(s.pollFirst() + " " + s);               // 10 [20, 30, 40]: removes and returns the smallest
6}

NavigableMap (implemented by TreeMap) adds the neighbour queries of this chapter. floorKey(k) is the largest key at most k, ceilingKey(k) the smallest key at least k, lowerKey(k) the largest key strictly below and higherKey(k) the smallest strictly above, each returning null when none exists. The ...Entry forms return the entry, and firstEntry, lastEntry, pollFirstEntry and pollLastEntry handle the extremes. descendingMap() is a reversed view.

Every call is O(log n). The null return is the thing to remember: unbox a missing Integer and you get a NullPointerException.

1static void navigableMap() {
2    TreeMap<Integer, String> m = new TreeMap<>();
3    for (int k : new int[]{50, 30, 70, 20, 40, 60, 80}) m.put(k, "v" + k);
4    System.out.println(m.floorKey(65) + " " + m.ceilingKey(65));       // 60 70
5    System.out.println(m.lowerKey(50) + " " + m.higherKey(50));        // 40 60
6    System.out.println(m.floorKey(10));                                // null: nothing is <= 10
7    System.out.println(m.firstEntry() + " " + m.lastEntry());          // 20=v20 80=v80
8    System.out.println(m.descendingMap().firstKey());                  // 80
9}

NavigableSet (implemented by TreeSet) has the same four neighbour methods without the entries: floor, ceiling, lower, higher, all O(log n) and returning null for no answer, plus first, last, pollFirst, pollLast, headSet, tailSet, subSet and descendingSet.

A typical use: 'for each query value x find the closest stored value': take floor(x) and ceiling(x) and compare the two distances.

1static int closest(TreeSet<Integer> set, int x) {      // the stored value nearest to x; ties prefer the smaller
2    Integer lo = set.floor(x), hi = set.ceiling(x);
3    if (lo == null) return hi;
4    if (hi == null) return lo;
5    return x - lo <= hi - x ? lo : hi;
6}

Range queries come as **views** of the original collection, not copies, in O(log n) to create. headMap(to) holds keys below to (exclusive by default), tailMap(from) keys from from upward (inclusive by default), and subMap(from, to) the **half-open** range [from, to). Overloads take explicit inclusive flags. TreeSet has headSet, tailSet and subSet with the same conventions.

Views are **live**: writes to the view change the original, and the reverse. A view only accepts keys inside its range: put of a key outside throws IllegalArgumentException. Counting the elements in a view with size() costs O(k), not O(log n), because it iterates.

1static void views() {
2    TreeMap<Integer, String> m = new TreeMap<>();
3    for (int k = 10; k <= 50; k += 10) m.put(k, "v" + k);              // 10 20 30 40 50
4    System.out.println(m.subMap(20, 40).keySet());                      // [20, 30]: [20, 40) is half-open
5    System.out.println(m.subMap(20, true, 40, true).keySet());          // [20, 30, 40]
6    System.out.println(m.headMap(30).keySet() + " " + m.tailMap(30).keySet());   // [10, 20] [30, 40, 50]
7    m.subMap(20, 40).clear();                                           // removes 20 and 30 from the original map
8    System.out.println(m.keySet());                                     // [10, 40, 50]
9    try { m.subMap(20, 40).put(99, "x"); } catch (IllegalArgumentException e) { System.out.println("key out of range"); }
10}

A TreeMap or TreeSet decides everything by the comparator: two keys are **equal if compare returns 0**, whatever equals says. A TreeSet<String> with String.CASE_INSENSITIVE_ORDER treats "a" and "A" as the same element and keeps only the first; a comparator that orders strings by length would reject every second string of the same length.

A comparator must be consistent: antisymmetric, transitive and stable over time, otherwise the tree misbehaves silently. Avoid the subtraction trick (a, b) -> a - b for ints: it overflows, so compare(Integer.MAX_VALUE, -1) returns a negative number. Use Integer.compare or Comparator.comparingInt. For several fields, chain them with thenComparing, and make sure the comparator distinguishes elements that you want to keep apart.

1static void comparatorPitfalls() {
2    TreeSet<String> ci = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
3    ci.add("a"); ci.add("A"); ci.add("b");
4    System.out.println(ci);                                    // [a, b]: "A" compared equal to "a" and was dropped
5
6    TreeSet<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
7    byLength.add("aa"); byLength.add("bb"); byLength.add("c");
8    System.out.println(byLength);                              // [c, aa]: "bb" has the same length as "aa", so it is "equal"
9
10    Comparator<Integer> broken = (a, b) -> a - b;              // overflows near the limits
11    System.out.println(broken.compare(Integer.MAX_VALUE, -1) < 0);   // true: MAX_VALUE sorts BEFORE -1 (wrong)
12    System.out.println(Integer.compare(Integer.MAX_VALUE, -1) > 0);  // true: the correct answer
13}