Explain the Comparable/Comparator contract requirements (transitivity, consistency with equals) and what breaks when compareTo is inconsistent with equals in a TreeSet/TreeMap.
answer
- Total order: antisymmetry + transitivity + transitive equality
- Tree containers use compareTo, NOT equals/hashCode
- compareTo==0 but not equals -> element silently dropped
- equals but compareTo!=0 -> duplicate kept, Set contract broken
- Broken transitivity -> TimSort 'violates general contract' or silent corruption
basics
~20 sAn ordering must be consistent: if a<b and b<c then a<c, and comparisons can't contradict each other. Sorted sets and maps decide equality by compareTo, not equals, so if those disagree, elements can vanish or duplicate unexpectedly.
solid answer
~40 sA correct Comparable/Comparator must satisfy: antisymmetry (sign of compareTo(a,b) is the negation of compareTo(b,a)), transitivity (a<b and b<c implies a<c), and transitivity of equality (compareTo==0 is transitive). It should ideally be *consistent with equals*: compareTo(a,b)==0 exactly when a.equals(b). TreeSet and TreeMap use compareTo (or the supplied Comparator) — NOT equals/hashCode — to test membership and key identity. If compareTo returns 0 for objects that are equals-unequal, the TreeSet treats them as the same element and silently drops one; conversely if equals says equal but compareTo never returns 0, both are kept, breaking the Set contract. Violating transitivity can corrupt the red-black tree, causing lost elements or wrong contains() results. The same applies to sortedMapOf and binarySearch, which assume a total, consistent order.
code
kotlin · 8 linesdata class Item(val id: Int, val score: Int)
// Consistent-with-equals: tie-break by id so distinct items never compare 0
val cmp = compareByDescending<Item> { it.score }.thenBy { it.id }
val set = java.util.TreeSet(cmp)
set.add(Item(1, 50)); set.add(Item(2, 50))
println(set.size) // 2 -> both kept, because id breaks the score tiego deeper
Aware that ordering should be consistent and that a broken comparator can sort wrongly.
States the consistency-with-equals guideline and that compareTo==0 means 'equal in order'.
Explains precisely how TreeSet/TreeMap use compareTo over equals and predicts dropped/duplicate elements; knows TimSort's contract exception.
Sets a team rule that ordering keys must be a superset of identity (or include a unique tiebreaker), and audits comparators for total-order correctness.
## The formal contract For a comparator/`compareTo` to be valid it must define a **total order** over the elements: 1. **Antisymmetry / sign symmetry**: `sgn(compare(a, b)) == -sgn(compare(b, a))` for all a, b. 2. **Transitivity**: if `compare(a, b) > 0` and `compare(b, c) > 0` then `compare(a, c) > 0`. 3. **Transitive equality**: if `compare(a, b) == 0` then `sgn(compare(a, c)) == sgn(compare(b, c))` for every c. A *recommended* (not mandatory) extra rule is **consistency with equals**: `compare(a, b) == 0` if and only if `a.equals(b)`. ## Why sorted containers care `TreeSet<T>` and `TreeMap<K, V>` are backed by a balanced (red-black) tree and locate elements **using the ordering only** — they never call `equals` or `hashCode` for lookup. Two consequences: - If `compareTo` returns `0` for two objects that are **not** `equals`, the tree considers them the *same* node. Adding the second is a no-op; one is effectively dropped. This breaks the `Set` invariant that distinct (non-equal) elements coexist. - If `equals` says two objects are equal but `compareTo` never returns `0`, a `TreeSet` will store **both**, even though a `HashSet` would store one. ```kotlin data class P(val id: Int, val name: String) : Comparable<P> { // BUG: orders by name only, but equals (data class) uses id + name override fun compareTo(other: P): Int = name.compareTo(other.name) } val s = sortedSetOf(P(1, "ann"), P(2, "ann")) println(s.size) // 1 -> second 'ann' silently dropped println(s.contains(P(99, "ann"))) // true -> matched by order, ignoring id ``` The `data class` `equals` distinguishes them, but the `TreeSet` collapsed them because `compareTo` tied. ## Breaking transitivity A non-transitive comparator (a classic example: subtracting fields that can overflow, or ad-hoc "a is special" rules) can corrupt internal tree/array invariants. On the JVM, `Collections.sort`/`Arrays.sort` may even throw `IllegalArgumentException: Comparator violates its general contract!` when TimSort detects inconsistency. With trees you instead get *silently wrong* `contains`/iteration. ## How to stay safe - Build comparators with `compareBy` / `compareValuesBy` so each key uses a correct, overflow-safe comparison. - Make the comparison keys cover **the same fields** that `equals` uses (or at least a unique key) so ties only happen for truly-equal objects. - Never write `compareTo` as `this.x - other.x` for unbounded numbers. - Remember `binarySearch` and `sorted*` assume the list is already ordered by a *consistent* comparator; a broken one yields undefined results, not an exception. ## Comparator-supplied trees `TreeSet(comparator)` / `TreeMap(comparator)` follow the **comparator**, not natural order or equals — the same consistency rules apply to that comparator.
- Why does a TreeSet drop an element that a HashSet keeps?TreeSet locates elements by compareTo; if compareTo returns 0 it considers them identical and won't add the second. HashSet uses equals/hashCode, which may distinguish them.
- When does the JVM throw 'Comparator violates its general contract'?When TimSort (Collections.sort/sortedWith on a List) detects intransitive/inconsistent comparisons during merging; it fails fast rather than producing garbage.
saying these in an interview costs you the question
- Believing TreeSet/TreeMap use equals/hashCode for membership
- Writing compareTo over a strict subset of equals fields without realizing it ties
- Using a - b subtraction and dismissing overflow as theoretical
- Assuming an inconsistent comparator just sorts slightly wrong rather than dropping elements
- Not knowing TimSort can throw on contract violations