Why must a TreeMap's Comparator be consistent with equals, and what bugs appear when it is not?
answer
- Key identity is compare()==0, not 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 a Comparator returns 0 for two different objects, TreeMap treats them as one key — so puts overwrite and lookups match keys never inserted, 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 — key lookups and updates never call equals or 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 replaces the value while 'cat' stays as the key, size is low, and containsKey/get behave by comparison rather than equality. The map's behaviour stays well-defined, but it 'behaves strangely' and fails the general Map contract. 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 the sort's IllegalArgumentException for contract-breaking 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. **To find or match a key, TreeMap never calls `equals` or `hashCode` on it.** (Entry-level methods do: `TreeMap.hashCode()` hashes each key through its entries, and `Map.Entry.equals` compares keys with `equals`.) ## 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. `Comparable`'s documentation calls this **strongly recommended (though not required)** for natural orderings. `SortedMap`'s says the ordering **must** be consistent with equals *if the sorted map is to correctly implement the `Map` interface*, because `Map` is specified in terms of `equals` while a sorted map compares with `compare`. If they disagree, the behaviour is still **well-defined**, but the map 'behaves strangely': it obeys its own comparison-based contract and **fails 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**, so the second `put` **replaces the value** and keeps the first key: the map prints `{cat=2}`. 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. A tie-break on `hashCode` is not enough: `"Aa"` and `"BB"` have the same length and the same hash. 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 breaks its own contract (say, one that never returns 0 or is not transitive) is a different bug. `TreeMap` does not check for it, so a later lookup can miss a key that is there. `List.sort` and `Arrays.sort` may detect it instead and throw `IllegalArgumentException: Comparison method violates its general contract!`. - Natural orderings of JDK types are virtually all consistent with equals (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.
- Believing TreeMap uses equals/hashCode to find 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'
- TreeMap
- Java 1.2
- Comparator
- Java 1.2
- Comparator.comparingInt and thenComparing
- Java 1.8
context
- TreeMap (Java SE 27 & JDK 27)docs.oracle.com
- Comparable (Java SE 27 & JDK 27)docs.oracle.com
- Comparator (Java SE 27 & JDK 27)docs.oracle.com