Why must a TreeMap's Comparator be consistent with equals, and what bugs appear when it is not?
answer
- TreeMap uses compare()==0 for key identity, never equals/hashCode
- Consistent with equals: compare==0 iff a.equals(b)
- Inconsistent comparator → overwrites, phantom containsKey, wrong size
- Fix: add identity-bearing tie-break for a total order
- BigDecimal is the classic 'not consistent with equals' JDK example
basics
~20 sTreeMap decides whether two keys are 'the same' using compare()/compareTo, not equals(). If your Comparator says two different objects compare as 0, TreeMap treats them as one key — so puts overwrite and lookups can 'miss' keys, breaking the Map contract.
solid answer
~50 sTreeMap determines key equality solely by comparison: two keys are the 'same' key when compare (or compareTo) returns 0 — it never calls equals/hashCode. The Map interface, however, defines equality via equals. A Comparator is 'consistent with equals' when compare(a,b)==0 exactly matches a.equals(b). When it is not — e.g. a comparator that sorts strings by length only — distinct keys ('cat' and 'dog') collide at compare 0, so the second put overwrites the first, size is wrong, and containsKey/get behave by comparison rather than equality. The map still works correctly as a Map, but it 'behaves strangely' and violates the general Map contract that is phrased in terms of equals. The fix is to make the comparator a total order that breaks ties by an identity-bearing field (e.g. by length then natural order), so compare==0 only for truly equal keys. This is the same rule TreeSet relies on.
go deeper
Aware that TreeMap sorts by a comparator/Comparable and that keys must be comparable.
Knows TreeMap compares keys rather than using equals, and that two keys comparing equal are treated as one.
States the 'consistent with equals' rule precisely, predicts the overwrite/phantom-key/size bugs, and fixes them with a total-order tie-break.
Anticipates contract violations across TreeSet/sorted operations, cites BigDecimal and IllegalArgumentfor non-transitive comparators, and sets team conventions for comparator design.
## Two different notions of 'equal' Most of Java's collections decide whether two objects are the same using **equals()** (and **hashCode()** for hashing). A **sorted** collection is different: TreeMap (and TreeSet) decide ordering *and* identity using **comparison** — either the key's `compareTo` (natural ordering, from `Comparable`) or the `Comparator` you supplied. **TreeMap never calls equals or hashCode on its keys.** ## The rule: consistent with equals The `Comparable`/`Comparator` documentation says an ordering is **'consistent with equals'** when: > compare(a, b) == 0 if and only if a.equals(b) That is, two keys compare as equal *exactly when* they are `.equals`-equal. The `SortedMap`/`SortedSet` contract **strongly recommends** this, because the Map interface itself is specified in terms of `equals`, while a sorted map's behaviour is specified in terms of `compare`. If they disagree, the sorted map 'behaves strangely' — it still obeys its own comparison-based contract but **violates the general Map contract**. ## What goes wrong concretely Suppose keys are Strings and you use a comparator that orders **by length only**: `Comparator.comparingInt(String::length)`. - `put("cat", 1)` then `put("dog", 2)`: both have length 3, so compare returns 0. TreeMap thinks they are the **same key** and the second `put` **overwrites** the first. Now the map has one entry, not two, even though `"cat".equals("dog")` is false. - `get("dog")` returns 2; `get("cat")` *also* returns 2 (any length-3 key maps to that slot). - `containsKey("car")` returns true though you never inserted 'car' — it has length 3. - `size()` undercounts; iteration is missing 'lost' keys. The map is internally consistent (it does exactly what compare tells it) but **surprising** to anyone expecting equals-based semantics. ## The fix: a total order with identity-bearing tie-break Make compare return 0 **only** for genuinely equal keys by adding a tie-breaker: `Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder())`. Now 'cat' and 'dog' compare nonzero (alphabetical tie-break), so both are kept and equals/compare agree. The principle: design the comparator as a **total order** whose zero result coincides with `.equals`. ## Where else this bites - **TreeSet** has the identical issue: 'duplicate' elements (by comparator) are silently dropped. - A comparator that is **not a total order** (e.g. returns 0 for incomparable pairs, or is not transitive) can corrupt the tree or throw `IllegalArgumentException: Comparator violates its general contract!` during sort-heavy operations. - Natural orderings of JDK types (Integer, String, BigDecimal is the famous *exception* — `compareTo` of `2.0` vs `2.00` is 0 but they are not equals) — so even built-ins can be inconsistent; document it when you rely on it. ## Takeaway In a TreeMap, **comparison defines key identity**. Keep your Comparator a total order consistent with equals, breaking ties on a field that distinguishes otherwise-equal-looking keys, or accept (and document) the deliberate collapsing of keys.
- Give a JDK type whose natural ordering is not consistent with equals.BigDecimal: new BigDecimal("2.0").compareTo(new BigDecimal("2.00")) is 0, but equals is false (different scale). So a TreeMap treats them as one key while a HashMap treats them as two.
- How do you keep distinct keys that share a primary sort value?Append a tie-breaker that distinguishes them, e.g. Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()), making compare==0 only for truly equal keys.
saying these in an interview costs you the question
- Believing TreeMap calls equals/hashCode on keys
- Writing a length-only or single-field comparator and expecting distinct keys to survive
- Thinking an inconsistent comparator throws (it usually silently misbehaves)
- Confusing 'breaks the Map contract' with 'throws an exception'