Java Comparators and Ordered Collections

A typical version of this question: “You put five employees into a TreeSet sorted by salary and only three come out. What happened?” Another: “What does consistent with equals mean for a Comparator?” Interviewers ask because comparator bugs are silent. Nothing throws, the code compiles, and data quietly disappears from sorted collections or sorts in an order that changes between runs.

The question tests whether you know that sorted collections do not call equals at all, whether you can state the comparator contract, and whether you can build a safe comparator with the Comparator factory methods.

Before you start

You should know the Comparable and Comparator interfaces, lambdas and method references, and the difference between HashSet and TreeSet. Recall that compareTo and compare return a negative number, zero or a positive number. Only the sign matters, which is exactly why a comparator that returns zero for distinct objects is so dangerous.

The short answer

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.

How it works

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());          // 2

The Comparator Javadoc spells out the contract. For all x, y and z:

1. sgn(compare(x, y)) == -sgn(compare(y, x)) (antisymmetry).
2. If compare(x, y) > 0 and compare(y, z) > 0, then compare(x, z) > 0 (transitivity).
3. If compare(x, y) == 0, then x and y compare 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()); // 1

Step-by-step walkthrough

Step 1: Decide what “same element” means

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.

Step 2: Build the primary ordering with factory methods

Comparator<Employee> order = Comparator
        .comparingInt(Employee::salary)
        .reversed();                      // highest salary first

comparingInt 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.

Step 3: Add 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.

Step 4: Handle nulls explicitly

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()));

Worked scenario

A leaderboard service keeps players in a TreeSet so it can return the top ten quickly. The original 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));
}

Common mistake

• “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.x overflows for large or negative values. Use Integer.compare, Long.compare or comparingInt.
• Comparing doubles with casts. (int) (a.price - b.price) truncates 0.4 to 0 and declares different prices equal. Use Double.compare, which also orders NaN and -0.0 consistently.
• Mutating sort keys in place. Changing a field used by the comparator while the element sits in a TreeSet leaves it in the wrong branch, so contains and remove fail.
• Misplacing reversed(). comparing(A).thenComparing(B).reversed() reverses both keys, not just A.

Verify the behavior

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);
    }
}

Follow-up questions

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.

Interview exercise

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 and reasoning

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 map.keySet().equals(Set.of("apple")) to behave asymmetrically, because the HashSet-style equals uses string equality. Documenting that the map is case-insensitive is part of the answer.

Continue learning

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.