Java TreeMap
›Short versionOpen if you only have a minute.
- TreeMap keeps keys sorted. get, put, and remove are O(log n).
- Identity is comparison. compare or compareTo returning 0 replaces the entry.
- The comparator must be consistent with equals, or the map silently violates the Map contract.
- A one-field comparator collapses keys that differ in every other field.
- floorKey, ceilingKey, and the range views are the operations you pay log n to get.
- Natural ordering rejects a null key. HashMap is the map that allows one.
A is a map you can walk in key order, and a map that can name the neighbor of a key. Both come from the tree, and both cost .
The is doing two jobs at once: it sorts, and it decides which keys are the same key. is what keeps the second job aligned with the rest of the collections framework.
Comparison is identity
SortedMap documents this directly. The map remains well-defined when the ordering disagrees with equals. It just stops obeying Map. put replaces a value whenever comparison returns 0, and containsKey follows the same test. Two keys that equals would separate become one entry.
Tie-break the comparator with enough fields that zero means the same key you would accept from equals. For a record, comparing the sort field and then the remaining components usually gets there. Comparing only the sort field is the bug.
A uses that same order. So does every navigable query. A has no place in natural order. If the design needs null keys, use a HashMap and give up sorted iteration, or write a comparator that places null on purpose.
Last name is not a key
record Person(String last, String first) {}
Map<Person, String> byLast = new TreeMap<>(Comparator.comparing(Person::last));
byLast.put(new Person("Lovelace", "Ada"), "analyst");
byLast.put(new Person("Lovelace", "Grace"), "replaced");
byLast.size(); // 1 — compare returned 0
NavigableMap<Integer, String> ranks = new TreeMap<>();
ranks.put(2, "silver");
ranks.put(1, "gold");
ranks.firstKey(); // 1
ranks.ceilingKey(2); // 2Two Person keys compare equal on last name only, and their equals method also compares first name. After both puts, what does size return, and which contract broke?
size is 1. The second put replaced the first because the comparator returned 0. The Map contract, which treats keys as the same only when equals says so, is the contract that broke. A comparator that continues with first name keeps both entries and stays consistent with the record’s equals.