skip to content

Why must a TreeMap's Comparator be consistent with equals, and what bugs appear when it is not?

level: seniorimportance: should knowfreq 42%

answer

  1. Key identity is compare()==0, not equals/hashCode
  2. Consistent with equals: compare==0 iff a.equals(b)
  3. Inconsistent comparator → overwrites, phantom containsKey, wrong size
  4. Fix: add identity-bearing tie-break for a total order
  5. BigDecimal is the classic 'not consistent with equals' JDK example

basics

~20 s

TreeMap 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 s

TreeMap 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

for a junior

Aware that TreeMap sorts by a comparator/Comparable and that keys must be comparable.

for a middle

Knows TreeMap compares keys rather than using equals, and that two keys comparing equal are treated as one.

for a senior

States the 'consistent with equals' rule precisely, predicts the overwrite/phantom-key/size bugs, and fixes them with a total-order tie-break.

for a principal

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