Lesson 6. Comparable and Comparator

Mission link: Ordering is where a contract violation stops being theoretical: an inconsistent comparator makes a TreeSet drop elements and makes sort throw, and both failures name something other than the comparator.
Primary source: Comparator, Java SE 25 API
Prerequisites: Lesson 3, Lesson 5

Warm-up

1. ▢ What is the difference between Collections.unmodifiableList(source) and List.copyOf(source)?

2. ▢ Why must equal objects have equal hash codes?

Know this

There are two ways to order things, and they answer different questions.

Comparable is implemented by the type itself and defines its natural ordering. String, the numeric wrappers and LocalDate all have one.

Comparator is a separate object that imposes an ordering from outside. Use it when the type has no natural order, when you need a second order, or when the type is not yours to change.

Both return a negative number, zero, or a positive number. Only the sign matters.

records.sort(Comparator.comparing(Order::createdAt));
records.sort(Comparator.comparing(Order::customer)
                       .thenComparing(Order::createdAt)
                       .reversed());

comparing, thenComparing, reversed, nullsFirst and nullsLast compose, which is how a multi-key ordering stays readable. comparingInt, comparingLong and comparingDouble avoid boxing in the key extractor.

The contract

For any x, y, z:

• Antisymmetric in sign: sgn(compare(x, y)) == -sgn(compare(y, x)).
• Transitive: if compare(x, y) > 0 and compare(y, z) > 0, then compare(x, z) > 0.
• Consistent on ties: if compare(x, y) == 0, then x and y compare the same way against every z.
• Deterministic: the same pair gives the same answer while nothing relevant changes.

And a fifth, which is strongly recommended rather than required: consistency with equals, meaning compare(x, y) == 0 exactly when x.equals(y).

Why that last one matters more than "recommended" suggests

A sorted collection uses the ordering and never calls equals:

record Task(String name, int priority) {}

Set<Task> set = new TreeSet<>(Comparator.comparingInt(Task::priority));
set.add(new Task("write", 1));
set.add(new Task("review", 1));
System.out.println(set.size());     // 1

Two answers exist, and only one of them goes anywhere. The equality answer is drawn with nothing leaving it because nothing consults it.

Two tasks that are not equals compared as zero, so the TreeSet treated the second as a duplicate and discarded it. Nothing was thrown, and size() is the only evidence.

The fix is to make the ordering a total order over distinct elements, by adding a tie-breaker that ends in something unique:

Comparator.comparingInt(Task::priority).thenComparing(Task::name)

TreeMap behaves the same way with keys, and binarySearch gives meaningless results on a list sorted by a different comparator than the one it is passed.

The subtraction bug

Comparator<Item> byId = (a, b) -> a.id() - b.id();      // BROKEN
Comparator<Item> ok   = Comparator.comparingInt(Item::id);

Subtraction overflows. With a.id() at Integer.MIN_VALUE and b.id() positive, the difference wraps to a positive number and the comparator claims the smaller value is larger. It also breaks transitivity, which is what actually corrupts a sort.

Use Integer.compare, Long.compare, Double.compare, or the comparingInt family. Never subtract. For double, Double.compare also handles NaN and the two zeros consistently, which a subtraction cannot.

What a broken comparator does to sort

List.sort and Collections.sort use a merge sort that detects some contract violations and throws:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

That message names the sort, not the comparator, and it appears only for some violations and some inputs, which is why it usually arrives long after the comparator was written.

Two ordering properties worth knowing while you are here: sorting a List or an object array is stable, so equal elements keep their relative order, and sorting a primitive array is not, because a different algorithm is used and stability is unobservable for primitives anyway.

Practice

1. ▢ Predict the size, and explain it.

   record Task(String name, int priority) {}
   Set<Task> set = new TreeSet<>(Comparator.comparingInt(Task::priority));
   set.add(new Task("a", 1));
   set.add(new Task("b", 1));
   set.add(new Task("c", 2));
   System.out.println(set.size());
   

2. ▢ This comparator passes its tests. Name the input that breaks it and the property it violates.

   Comparator<Item> byId = (a, b) -> a.id() - b.id();
   

3. ▢ Which comparator is safe to hand to a TreeSet<Person> where Person is record Person(String last, String first)?

   • a) Comparator.comparing(Person::last)
   • b) Comparator.comparing(Person::last).thenComparing(Person::first)
   • c) (a, b) -> a.last().length() - b.last().length()
   • d) Comparator.comparing(Person::last).reversed()

4. ▢ You need to sort orders by customer name, then by date descending, with orders that have no date last. Write it.

orders.sort(Comparator.comparing(Order::customer)
        .thenComparing(Order::createdAt,
                       Comparator.nullsLast(Comparator.reverseOrder())));

5. ▢ A class implements Comparable with an ordering that is deliberately inconsistent with equals, and a reviewer says that is acceptable. When are they right, and what must the class do about it?

Real-world reps

• [ ] Build the TreeSet from practice 1, watch the size come out at 2, then add the tie-breaker and watch it become 3.
• [ ] Write the subtraction comparator, sort a list containing Integer.MIN_VALUE, and see what comes out. Then swap in comparingInt.
• [ ] Tomorrow: find a Comparator in code you know. Check whether it is a total order over distinct elements, and whether anything sorted by it ever lands in a TreeSet or TreeMap.

Going further

• Comparator: the contract, and every composing factory method
• Comparable: natural ordering, and the wording for documenting an inconsistent one
• Arrays: which sorts are stable, stated per overload
• Equality, hashing and ordering: the reference sheet for this stage
• Resources

Not landing? Reread the primary source at the top, since this lesson compresses it and compression is where understanding leaks. Check the glossary for any term that felt slippery.

If the lesson itself is unclear rather than the material, that is a defect: open an issue.