Serguey Asael Shinder: TreeMap decides key equality with compareTo, and that quietly breaks the Map contract
There is a paragraph in the javadoc for java.util.TreeMap that deserves to be read slowly, because it describes a class of bug that never throws.
The ordering maintained by a tree map, with or without an explicit comparator, must be consistent with equals if the map is to correctly implement the Map interface. The reason is given in the same breath: Map is defined in terms of the equals operation, but a sorted map performs all key comparisons using compareTo or compare, so two keys that method deems equal are, from the standpoint of the sorted map, equal.
Then the sentence that matters most: the behaviour of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of Map.
Well-defined is the trap. Nothing breaks. The map does exactly what the comparator told it to do. put returns the previous value for a key your equals would have called different; containsKey answers true for an object that is not in the map by any definition your domain would recognise; size is smaller than the number of distinct things you inserted, and stays that way.
The comparator most likely to do this is the one that looks most reasonable. Sorting people by surname, jobs by scheduled time, orders by amount — each of those compares on one field of an object whose identity is more than one field. Drop such a comparator into a TreeMap and it silently becomes the definition of key equality.
I have twice seen this arrive as a report of missing records. In both cases the insertion loop was correct, the source data was correct, and the collection was simply holding fewer entries than had been put into it, because two distinct objects compared to zero. Neither case produced a stack trace, and both were found by counting.
The fix is boring: when a comparator exists only for display order, sort a list with it and keep the map keyed on something that matches equals. The javadoc's own phrasing is the check worth remembering — if two objects your code treats as different can make your comparator return zero, that comparator does not belong in a sorted map.