Put five employees into a TreeSet sorted by salary and only three come out. Nothing throws, the code compiles, and two records are simply gone. Comparator bugs fail this quietly: data disappears from sorted collections, or a sort produces an order that changes between runs.
Explaining the missing employees takes three pieces of knowledge: sorted collections never call equals, the comparator contract has specific rules, and the Comparator factory methods build safe comparators for you. The same knowledge answers the related question of what “consistent with equals” means. Only the sign of compare matters, and a zero returned for two distinct objects is where the data loss starts.
Zero from compare means the same key, whatever equals says
TreeSet and TreeMap place and look up elements purely by compare (or compareTo). If the comparator returns zero for two objects, the collection treats them as the same key, so a set keeps only the first and a map overwrites the value, even when equals says they differ. A correct comparator must be antisymmetric, transitive and consistent, and in practice you should add tie-breaking fields until zero means “same element”. Build comparators with Comparator.comparing(...).thenComparing(...) rather than subtracting numbers.
The tree walk, the contract and the BigDecimal trap
A TreeMap is a red-black tree. Every put walks down from the root, calling compare(newKey, nodeKey) at each node: negative goes left, positive goes right, zero means “found it” and replaces the value. There is no fallback to equals or hashCode. TreeSet is a thin wrapper over a TreeMap, so the same rule decides membership.
record Employee(String name, int salary) {}
Comparator<Employee> bySalary = Comparator.comparingInt(Employee::salary);
Set<Employee> set = new TreeSet<>(bySalary);
set.add(new Employee("Asha", 90_000));
set.add(new Employee("Ben", 90_000)); // compare returns 0: rejected
set.add(new Employee("Chen", 75_000));
System.out.println(set.size()); // 2The Comparator Javadoc spells out the contract. For all x, y and z:
sgn(compare(x, y)) == -sgn(compare(y, x))(antisymmetry).- If
compare(x, y) > 0andcompare(y, z) > 0, thencompare(x, z) > 0(transitivity). - If
compare(x, y) == 0, thenxandycompare the same way against every z.
Separately, a comparator is “consistent with equals” when compare(a, b) == 0 exactly when a.equals(b). That property is strongly recommended, not required, but the Javadoc warns that sorted sets and maps behave “strangely” without it: they obey their own ordering instead of the general Set and Map contracts, which are defined in terms of equals.
A famous example from the JDK itself is BigDecimal, whose compareTo ignores scale while equals does not:
Set<BigDecimal> hash = new HashSet<>(List.of(new BigDecimal("1.0"), new BigDecimal("1.00")));
Set<BigDecimal> tree = new TreeSet<>(List.of(new BigDecimal("1.0"), new BigDecimal("1.00")));
System.out.println(hash.size()); // 2
System.out.println(tree.size()); // 1Building a comparator that returns zero only for equal elements
Decide which fields identify an element
Before writing the comparator, decide which fields identify an element. For employees, the name alone is probably not unique, but an employee id is. That decision drives the tie-breakers: the comparator should return zero only when the identifying fields match.
Primary order with comparingInt and reversed()
Comparator<Employee> order = Comparator
.comparingInt(Employee::salary)
.reversed(); // highest salary firstcomparingInt uses Integer.compare internally, which avoids overflow and boxing. reversed() flips the whole comparator built so far, so place it carefully: calling it at the end of a chain reverses the tie-breakers too.
Tie-breakers until zero means identical
record Employee(long id, String name, int salary) {}
Comparator<Employee> order = Comparator
.comparingInt(Employee::salary).reversed()
.thenComparing(Employee::name)
.thenComparingLong(Employee::id);Now two employees with the same salary sort by name, and two with the same salary and name sort by id. Because a record’s equals compares all three components, this comparator is consistent with equals, so a TreeSet<Employee> behaves like a proper set.
Null keys with nullsLast
If a field can be null, Comparator.comparing(Employee::department) throws NullPointerException on the first null. Wrap the key comparator:
Comparator<Employee> byDept = Comparator.comparing(
Employee::department,
Comparator.nullsLast(Comparator.naturalOrder()));A leaderboard that hides tied players
Picture a leaderboard service that keeps players in a TreeSet so it can return the top ten quickly, with this comparator:
Comparator<Player> byScore = (a, b) -> b.score() - a.score();
NavigableSet<Player> board = new TreeSet<>(byScore);Two bugs hide here. First, players with equal scores collapse into one entry, so a newly joined player with the same score as an existing one simply never appears. Second, subtraction overflows: if scores can be large or negative, b.score() - a.score() can wrap around and return the wrong sign. With a.score() = -2_000_000_000 and b.score() = 2_000_000_000, the difference overflows to a negative number and the ordering inverts. Once transitivity breaks, Collections.sort and List.sort may throw IllegalArgumentException: Comparison method violates its general contract! from TimSort, and tree collections end up with elements they cannot find again.
The fix uses safe comparison and a unique tie-breaker:
Comparator<Player> byScore = Comparator
.comparingInt(Player::score).reversed()
.thenComparing(Player::id);
NavigableSet<Player> board = new TreeSet<>(byScore);Updating a player’s score also needs care. Sorted collections assume the sort key does not change while the element is inside, so the update must remove the old entry, then insert the new one:
void updateScore(Player oldEntry, int newScore) {
board.remove(oldEntry);
board.add(oldEntry.withScore(newScore));
}JUnit tests for ties, tie-breakers and overflow
This JUnit 5 test pins down both the lost-element bug and the fix:
import static org.junit.jupiter.api.Assertions.*;
import java.util.*;
import org.junit.jupiter.api.Test;
class ComparatorTest {
record Player(String id, int score) {}
@Test
void scoreOnlyComparatorDropsTies() {
var set = new TreeSet<Player>(Comparator.comparingInt(Player::score));
set.add(new Player("a", 10));
set.add(new Player("b", 10));
assertEquals(1, set.size());
}
@Test
void tieBreakerKeepsDistinctPlayers() {
var set = new TreeSet<Player>(Comparator.comparingInt(Player::score)
.reversed().thenComparing(Player::id));
set.add(new Player("a", 10));
set.add(new Player("b", 10));
set.add(new Player("c", 20));
assertEquals(List.of("c", "a", "b"), set.stream().map(Player::id).toList());
}
@Test
void subtractionOverflows() {
Comparator<Integer> bad = (x, y) -> x - y;
assertTrue(bad.compare(Integer.MIN_VALUE, 1) > 0); // wrong sign
assertTrue(Integer.compare(Integer.MIN_VALUE, 1) < 0);
}
}Five comparator bugs that compile cleanly
- “TreeSet uses equals to detect duplicates.” It does not. It uses only the comparator, which is why inconsistent comparators lose data.
- Subtraction comparators.
(a, b) -> a.x - b.xoverflows for large or negative values. UseInteger.compare,Long.compareorcomparingInt. - Comparing doubles with casts.
(int) (a.price - b.price)truncates 0.4 to 0 and declares different prices equal. UseDouble.compare, which also ordersNaNand-0.0consistently. - Mutating sort keys in place. Changing a field used by the comparator while the element sits in a
TreeSetleaves it in the wrong branch, socontainsandremovefail. - Misplacing reversed().
comparing(A).thenComparing(B).reversed()reverses both keys, not just A.
Practice question: a case-insensitive TreeMap
You need a TreeMap<String, Integer> that treats keys case-insensitively, so “Apple” and “apple” are the same key. Is String.CASE_INSENSITIVE_ORDER a correct choice, and what behaviour should callers expect?
Answer
It is a correct and deliberate choice. String.CASE_INSENSITIVE_ORDER satisfies the comparator contract: it is antisymmetric, transitive and consistent. It is not consistent with String.equals, and that is precisely the goal. Callers should expect put("apple", 2) after put("Apple", 1) to replace the value while keeping the original key spelling “Apple”, because TreeMap.put updates the value of the existing node rather than replacing the key. They should also expect set equality to become one-sided. map.keySet().equals(Set.of("apple")) returns true, because the key set checks membership with the map’s comparator. Set.of("apple").equals(map.keySet()) returns false, because Set.of checks membership with String.equals and the stored key is “Apple”. Documenting that the map is case-insensitive is part of the answer.
Follow-ups on Comparable, HashMap and TimSort
What is the difference between Comparable and Comparator? Comparable defines a class’s natural ordering through compareTo on the class itself. Comparator is an external strategy, so one class can have many orderings.
Does HashMap ever use compareTo? Yes, indirectly. When a bucket turns into a tree, HashMap uses compareTo as a tie-breaker for keys that implement Comparable, but equals still decides key identity.
Why does Collections.sort sometimes throw “Comparison method violates its general contract”? TimSort detects some contract violations, such as non-transitive results, while merging runs. The comparator is broken; the exception is the symptom.
Is it ever acceptable for a comparator to be inconsistent with equals? Yes, for sorting a List where duplicates are fine, such as ordering search results by relevance. It becomes a problem only when the comparator backs a sorted set or map.
Where to go next on ordering and equality
Review more ordering questions in the Java interview questions and the Java MCQs. Pair this with equals and hashCode contracts and HashMap collisions. The full contract, including the consistent-with-equals warning, is in the Comparator API documentation.