All topics
4 / 101
collections
beginner

Comparable vs Comparator

Define an object's natural order once (Comparable) or supply an alternate ordering on demand (Comparator).

Both tell Java how to put objects in order. The difference is where that instruction lives.

Comparable is your default ranking on a leaderboard. Comparator is "sort the same list by name instead" for a different view.

Key Concepts

1
Comparable goes inside the class. The class itself defines its natural order, and there can be only one.
Comparable
2
Comparator is a separate object you pass to the sort. You can write as many as you like, and you can sort classes you did not write.
Comparator
3
    users.sort(null);                                   // uses Comparable
    users.sort(Comparator.comparing(User::getName));    // uses a Comparator
4
Building comparators is easy now.
    Comparator.comparing(User::getLastName)
              .thenComparing(User::getFirstName)
              .thenComparingInt(User::getAge)
              .reversed();
5
One warning: reversed() reverses everything built so far, not just the last step.
reversed()
6
Never compare by subtracting. This looks fine and is wrong:
7
    return a.getValue() - b.getValue();
8
If a is a very large negative number and b is positive, the subtraction overflows and wraps around to a positive result. Your comparator then claims the smaller value is larger.
ab
9
    Integer.MIN_VALUE - 1  =  2147483647    // positive!
    Integer.compare(a, b)                    // correct, and free
10
Returning 0 means "these are the same", and sorted collections believe you. TreeSet and TreeMap decide whether two things are duplicates by asking the comparator, not by calling equals.
TreeSetTreeMapequals
11
So a comparator that returns 0 for two objects that are not equal makes a TreeSet silently drop the second one. The classic example is BigDecimal: 2.0 and 2.00 compare as equal but are not equals, so a TreeSet keeps one and a HashSet keeps both.
TreeSetBigDecimal2.02.00equals
12
"Comparison method violates its general contract" is not a JDK bug. Java's sort checks your comparator as it works, and throws this when the answers are inconsistent — usually overflow from subtraction, or logic where a beats b, b beats c, but c beats a.
abc
13
It often appears months after release, the first time the data is shaped in a way that exposes it.
14
The rules a comparator must follow.
  If compare(a,b) is positive, compare(b,a) must be negative.
  If a beats b, and b beats c, then a must beat c.
  If compare(a,b) is 0, then a and b must compare the same
    way against every other element.
  Strongly recommended: compare(a,b) == 0 only when a.equals(b).
15
What the interviewer is probing.1. "What is the difference?" Probing: where the ordering lives. Stalls: "One is an interface on the class." Moves up: one natural order inside the class, versus many orders outside it, including for classes you cannot change.
16
2. "Sort by name, then age, descending." Probing: fluency. Stalls: an anonymous class. Moves up: comparing().thenComparing().reversed(), and knowing what reversed() applies to.
comparing().thenComparing().reversed()reversed()
17
3. "What is wrong with a.value - b.value?" Probing: overflow. Stalls: "Nothing." Moves up: it wraps for large opposite-signed values; use Integer.compare.
a.value - b.valueInteger.compare
18
4. "What does consistent with equals mean?" Probing: sorted collections. Stalls: "They should agree." Moves up: TreeSet uses the comparator to decide duplicates, so returning 0 drops elements.
TreeSet
19
5. "Why does sorting throw that contract exception?" Probing: the cause. Stalls: "A JDK bug." Moves up: the sort detected an inconsistent comparator, usually overflow or intransitive logic.
20
                     Comparable              Comparator
  ------------------------------------------------------------------
  Lives               inside the class        outside, as an object
  Method              compareTo(T o)          compare(T a, T b)
  How many orders     one (natural)           any number
  Types you own?      must own the class      works on any type
  Used by default by  sort(), TreeMap,        only when passed
                      TreeSet
  Package             java.lang               java.util
21
  The modern Comparator API
22
    Comparator.comparing(User::getLastName)
              .thenComparing(User::getFirstName)
              .thenComparingInt(User::getAge)
              .reversed();                  // reverses the WHOLE chain
23
    Comparator.comparing(User::getEmail,
                         Comparator.nullsLast(String::compareTo));
24
    Comparator.comparingInt(...)   // avoids boxing the key
25
  The contract, in full
    1. sgn(compare(a,b)) == -sgn(compare(b,a))     for all a,b
    2. transitive: compare(a,b)>0 and compare(b,c)>0
       implies compare(a,c)>0
    3. compare(a,b)==0 implies sgn(compare(a,z)) ==
       sgn(compare(b,z)) for every z
    4. strongly recommended: compare(a,b)==0 iff a.equals(b)
26
  Overflow, concretely
    a = Integer.MIN_VALUE, b = 1
    a - b   = 2147483647   (positive!)  -> claims a > b
    Integer.compare(a, b) = -1          -> correct
Use cases:SortingTreeMapAPI Design