[Advanced Java] Comparable vs Comparator trong Java: Natural Ordering và Sắp Xếp Tùy Chỉnh

Sort trong Java tách thành hai câu hỏi trông rất giống nhau nhưng không phải một. Câu thứ nhất: type này có thứ tự nào khi không ai nói gì thêm? Đó là Comparable, nằm bên trong class, và mỗi class chỉ được đúng một cái. Câu thứ hai: lần gọi này muốn thứ tự nào? Đó là Comparator, nằm bên ngoài class, và bạn muốn bao nhiêu cũng được.

Mọi thứ khó trong custom sorting đều bắt nguồn từ chỗ tách đó, cộng thêm một điều mà không interface nào ép được. Method so sánh có một contract, compiler không kiểm tra được nó, và khi bạn phá vỡ contract thì JDK lúc thì throw, lúc thì lặng lẽ trả về kết quả sai.

Mọi listing, error message, stack trace và con số bên dưới đều được tạo ra bằng cách compile và chạy code trên OpenJDK 21.0.6 (arm64). Chi phí luôn được biểu diễn bằng số lần gọi compare() đã được instrument, không bao giờ bằng thời gian chạy — một biến đếm cho ra cùng một con số trên mọi máy, còn đồng hồ bấm giây thì không.

Comparable: ordering thuộc về chính type

Comparable<T> có đúng một method, int compareTo(T o), và implement nó nghĩa là khai báo natural ordering của type. Giá trị trả về mang dấu chứ không mang độ lớn: âm nghĩa là "cái này đứng trước", 0 nghĩa là "hai cái ngang nhau", dương nghĩa là "cái này đứng sau".

Version number là ví dụ kinh điển, vì sort version dưới dạng text nổi tiếng là sai:

import java.util.*;

class Version implements Comparable<Version> {
    final int major, minor, patch;

    Version(int major, int minor, int patch) {
        this.major = major; this.minor = minor; this.patch = patch;
    }

    @Override
    public int compareTo(Version o) {
        int c = Integer.compare(major, o.major);
        if (c != 0) return c;
        c = Integer.compare(minor, o.minor);
        if (c != 0) return c;
        return Integer.compare(patch, o.patch);
    }

    @Override public boolean equals(Object o) {
        return o instanceof Version v && major == v.major && minor == v.minor && patch == v.patch;
    }
    @Override public int hashCode() { return Objects.hash(major, minor, patch); }
    @Override public String toString() { return major + "." + minor + "." + patch; }
}

public class NaturalOrder {
    public static void main(String[] args) {
        List<Version> vs = new ArrayList<>(List.of(
            new Version(1, 10, 0), new Version(1, 2, 3),
            new Version(2, 0, 0), new Version(1, 2, 10)));
        System.out.println("before = " + vs);
        Collections.sort(vs);
        System.out.println("after  = " + vs);

        System.out.println("compareTo sign  = " + new Version(1,2,3).compareTo(new Version(1,10,0)));
        System.out.println("as strings sort = " + new TreeSet<>(List.of("1.10.0","1.2.3","2.0.0","1.2.10")));
    }
}

before = [1.10.0, 1.2.3, 2.0.0, 1.2.10]
after  = [1.2.3, 1.2.10, 1.10.0, 2.0.0]
compareTo sign  = -1
as strings sort = [1.10.0, 1.2.10, 1.2.3, 2.0.0]

Dòng cuối là lý do class này tồn tại. So sánh như text thì 1.10.0 đứng trước 1.2.3, vì ký tự 1 nhỏ hơn ký tự 2. So sánh theo natural ordering do type định nghĩa thì không.

Một type không có natural ordering thì không sort được nếu không cung cấp thêm gì. Collections.sort được khai báo là <T extends Comparable<? super T>>, nên lỗi xuất hiện ngay lúc compile chứ không phải lúc chạy:

NotComparable.java:9: error: no suitable method found for sort(List<Point>)
        Collections.sort(pts);
                   ^
    method Collections.<T#1>sort(List<T#1>) is not applicable
      (inference variable T#1 has incompatible bounds
        equality constraints: Point
        upper bounds: Comparable<? super T#1>)

List.sort là cánh cửa lỏng hơn. Nó chấp nhận null với nghĩa "dùng natural ordering", parameter chỉ là Comparator<? super E> không kèm bound Comparable, nên list.sort(null) trên một type không Comparable vẫn compile được và nổ lúc runtime:

Exception in thread "main" java.lang.ClassCastException: class Point cannot be cast to class java.lang.Comparable (Point is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
	at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
	at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
	at java.base/java.util.Arrays.sort(Arrays.java:1108)
	at java.base/java.util.Arrays.sort(Arrays.java:1302)
	at java.base/java.util.ArrayList.sort(ArrayList.java:1804)
	at RawSort.main(RawSort.java:9)

Mỗi class chỉ có một natural ordering, và compiler bắt buộc điều đó

"Một cái cho mỗi class" không phải quy ước phong cách. Vì generic type argument bị erase, một class không thể implement Comparable hai lần với hai type argument khác nhau, và javac từ chối thẳng:

class Money implements Comparable<Money>, Comparable<String> {
    public int compareTo(Money o) { return 0; }
    public int compareTo(String o) { return 0; }
}

TwoNatural.java:1: error: repeated interface
class Money implements Comparable<Money>, Comparable<String> {
                                                    ^
TwoNatural.java:1: error: Comparable cannot be inherited with different arguments: <Money> and <java.lang.String>
class Money implements Comparable<Money>, Comparable<String> {
^
2 errors

Vậy nên ngay khi bạn cần ordering thứ hai, Comparable hết vai trò và Comparator bắt đầu.

Contract của compareTo

compareTo là method mà JDK gọi thay bạn bên trong các sorted collection và các thuật toán sort, và những thuật toán đó giả định nó hành xử như một quan hệ thứ tự thật sự. Contract trong javadoc có bốn phần, và chỉ phần cuối là tùy chọn.

compareTo còn phải throw NullPointerException khi argument là null và ClassCastException khi gặp type không so sánh được. Cả hai là hành vi sẵn có của JDK, không phải thứ bạn phải tự thêm.

Ba quy tắc đầu có thể kiểm tra trên một mẫu nhỏ, và viết sẵn cái checker này rất đáng, vì nó biến "comparator này thấy sai sai" thành một bộ ba cụ thể:

import java.util.*;

public class ContractCheck {
    static final Comparator<Integer> TOLERANT =
        (a, b) -> Math.abs(a - b) <= 10 ? 0 : Integer.compare(a, b);

    static <T> String check(Comparator<T> c, List<T> xs) {
        for (T a : xs) for (T b : xs) {
            if (Integer.signum(c.compare(a, b)) != -Integer.signum(c.compare(b, a)))
                return "sign symmetry fails at (" + a + ", " + b + ")";
        }
        for (T a : xs) for (T b : xs) for (T d : xs) {
            if (c.compare(a, b) > 0 && c.compare(b, d) > 0 && !(c.compare(a, d) > 0))
                return "transitivity fails at (" + a + ", " + b + ", " + d + ")";
            if (c.compare(a, b) == 0
                && Integer.signum(c.compare(a, d)) != Integer.signum(c.compare(b, d)))
                return "equality transitivity fails at (" + a + ", " + b + ", " + d + ")";
        }
        return "holds on this sample";
    }

    public static void main(String[] args) {
        List<Integer> xs = List.of(0, 5, 8, 12, 16, 25, 40);
        System.out.println("naturalOrder : " + check(Comparator.<Integer>naturalOrder(), xs));
        System.out.println("TOLERANT     : " + check(TOLERANT, xs));

        System.out.println();
        System.out.println("String.compareTo returns a magnitude, not just -1/0/1:");
        System.out.println("  \"apple\".compareTo(\"banana\") = " + "apple".compareTo("banana"));
        System.out.println("  \"a\".compareTo(\"z\")          = " + "a".compareTo("z"));
        System.out.println("  \"abc\".compareTo(\"ab\")       = " + "abc".compareTo("ab"));
        System.out.println("  Integer.compare(3, 99)      = " + Integer.compare(3, 99));

        System.out.println();
        try { "a".compareTo(null); } catch (Exception e) { System.out.println("  compareTo(null) -> " + e); }
    }
}

naturalOrder : holds on this sample
TOLERANT     : equality transitivity fails at (0, 5, 12)

String.compareTo returns a magnitude, not just -1/0/1:
  "apple".compareTo("banana") = -1
  "a".compareTo("z")          = -25
  "abc".compareTo("ab")       = 1
  Integer.compare(3, 99)      = -1

  compareTo(null) -> java.lang.NullPointerException: Cannot read field "value" because "anotherString" is null

Kết quả đó cho hai điều. Thứ nhất, comparator kiểu "chênh nhau dưới 10 thì coi như bằng nhau" — đọc lên rất hợp lý — đã hỏng ngay trên mẫu bảy phần tử. Thứ hai, String.compareTo trả về -25 chứ không phải -1: độ lớn là chi tiết cài đặt không ai cam kết, nên đừng bao giờ test kết quả so sánh bằng == -1 hay == 1. Chỉ xét dấu.

Consistent với equals là khuyến nghị, không phải bắt buộc

Quy tắc thứ tư là quy tắc lạ. Javadoc nói natural ordering consistent với equals là điều rất được khuyến khích nhưng không bắt buộc, và JDK không ngăn bạn viết một cái không consistent — BigDecimal chính là ví dụ có sẵn, vì 2.0 và 2.00 bằng nhau theo compareTo nhưng khác nhau theo equals.

Chỗ mà "không bắt buộc" biến thành mất dữ liệu là các sorted collection, vốn quyết định trùng lặp bằng compareTo chứ không bằng equals; một bài khác trong series này dựng lại đúng tình huống đó và đếm số phần tử biến mất. Với việc sort một list bình thường thì sự không nhất quán này vô hại, và đó chính là toàn bộ ranh giới.

Comparator: ordering thuộc về phía gọi

Comparator<T> khai báo int compare(T a, T b) với cùng quy ước về dấu, nhưng nhận cả hai toán hạng làm argument thay vì dùng this. Khác biệt duy nhất đó là toàn bộ thiết kế: comparator là một giá trị, nên nó có thể nằm trong field, truyền vào method, trả về từ factory, và được chọn ngay tại call site.

Nó chỉ có một abstract method, nên một lambda hay method reference chính là một Comparator — bài này chỉ cần đúng bấy nhiêu từ functional interface. Điểm quan trọng là không có gì ở đây đụng vào class đang được sort:

import java.util.*;
import static java.util.Comparator.*;

record Employee(String name, String dept, int salary) {
    @Override public String toString() { return name + "/" + dept + "/" + salary; }
}

public class ThreeOrderings {
    static final List<Employee> STAFF = List.of(
        new Employee("Ana",  "Eng",   120),
        new Employee("Bo",   "Sales", 120),
        new Employee("Cy",   "Eng",   140),
        new Employee("Dee",  "Sales", 110));

    public static void main(String[] args) {
        Comparator<Employee> byName    = comparing(Employee::name);
        Comparator<Employee> byPay     = comparingInt(Employee::salary).reversed();
        Comparator<Employee> byDeptPay = comparing(Employee::dept).thenComparingInt(Employee::salary);

        for (Comparator<Employee> c : List.of(byName, byPay, byDeptPay)) {
            List<Employee> l = new ArrayList<>(STAFF);
            l.sort(c);
            System.out.println(l);
        }
    }
}

[Ana/Eng/120, Bo/Sales/120, Cy/Eng/140, Dee/Sales/110]
[Cy/Eng/140, Ana/Eng/120, Bo/Sales/120, Dee/Sales/110]
[Ana/Eng/120, Cy/Eng/140, Dee/Sales/110, Bo/Sales/120]

Ba ordering, một record, và Employee không hề biết cái nào tồn tại.

API factory và combinator

Gần như không ai còn viết new Comparator<Employee>() { ... } nữa, và cũng gần như không nên viết lambda hai tham số trần. Các static factory dựng comparator từ một key, còn các default method compose comparator lại thành comparator lớn hơn.

Hai tính chất của danh sách này quan trọng hơn bản thân danh sách. Mỗi lời gọi đều trả về một comparator mới và không thay đổi gì cả, và mỗi combinator bọc lấy comparator mà nó được gọi trên đó, chứ không phải bọc lấy key cuối cùng bạn vừa nhắc tới.

Vì sao có comparingInt, comparingLong và comparingDouble

comparing nhận Function<T, U extends Comparable<? super U>>, mà int thì không phải Comparable. Nên một key extractor trả về int sẽ bị autobox ở mỗi lần gọi, rồi phần cài đặt của JDK gọi compareTo trên cái box đó:

public static <T, U extends Comparable<? super U>> Comparator<T> comparing(
        Function<? super T, ? extends U> keyExtractor)
{
    Objects.requireNonNull(keyExtractor);
    return (Comparator<T> & Serializable)
        (c1, c2) -> keyExtractor.apply(c1).compareTo(keyExtractor.apply(c2));
}

public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
    Objects.requireNonNull(keyExtractor);
    return (Comparator<T> & Serializable)
        (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
}

comparingInt nhận ToIntFunction, nên key không bao giờ trở thành object. Khác biệt này nhìn thấy được ngay trong bytecode của hai lambda, chứ không chỉ ở signature:

import java.util.*;

record Employee(String name, String dept, int salary) {}

public class Boxing {
    public static void main(String[] args) {
        List<Employee> l = new ArrayList<>();
        l.sort(Comparator.comparing((Employee e) -> e.salary()));
        l.sort(Comparator.comparingInt((Employee e) -> e.salary()));
    }
}

javap -p -c Boxing

  private static int lambda$main$1(Employee);
    Code:
       0: aload_0
       1: invokevirtual #34                 // Method Employee.salary:()I
       4: ireturn

  private static java.lang.Integer lambda$main$0(Employee);
    Code:
       0: aload_0
       1: invokevirtual #34                 // Method Employee.salary:()I
       4: invokestatic  #40                 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
       7: areturn

Cùng một biểu thức trong source, hai return type khác nhau. Bản comparing kết thúc bằng Integer.valueOf; bản comparingInt kết thúc bằng ireturn. Lương trên 127 nằm ngoài Integer cache, nên mỗi lần valueOf đó thật sự cấp phát bộ nhớ.

Key extractor chạy hai lần cho mỗi comparison

Chuyện đó xảy ra bao nhiêu lần? Một lần cho mỗi toán hạng của mỗi comparison, và đây là con số đếm được chứ không phải đoán:

import java.util.*;
import java.util.concurrent.atomic.AtomicLong;

record Employee(String name, String dept, int salary) {}

public class BoxCount {
    public static void main(String[] args) {
        Random r = new Random(7);
        List<Employee> base = new ArrayList<>();
        for (int i = 0; i < 1000; i++) base.add(new Employee("e" + i, "d", r.nextInt(1_000_000)));

        AtomicLong k1 = new AtomicLong(), k2 = new AtomicLong();
        List<Employee> a = new ArrayList<>(base);
        a.sort(Comparator.comparing((Employee e) -> { k1.incrementAndGet(); return e.salary(); }));
        List<Employee> b = new ArrayList<>(base);
        b.sort(Comparator.comparingInt((Employee e) -> { k2.incrementAndGet(); return e.salary(); }));

        System.out.printf("comparing    : %,d key-extractor calls, %,d Integer boxes%n", k1.get(), k1.get());
        System.out.printf("comparingInt : %,d key-extractor calls, 0 Integer boxes%n", k2.get());
        System.out.println("same order   : " + a.equals(b));
    }
}

comparing    : 17,346 key-extractor calls, 17,346 Integer boxes
comparingInt : 17,346 key-extractor calls, 0 Integer boxes
same order   : true

Sort một nghìn record cần 8,673 comparison, nên key extractor chạy 17,346 lần trong cả hai trường hợp. Với comparing, đó là 17,346 lần cấp phát vô ích. Cũng chính phép tính đó là lập luận thật sự chống lại một key extractor đắt tiền: comparing(e -> e.name().toLowerCase()) tạo ra mười bảy nghìn string chỉ để sort một nghìn record, và cách sửa là lưu sẵn key đã chuẩn hóa trên object thay vì tính nó bên trong comparator.

Bẫy type inference khi lambda nằm trong chain

Có một chi tiết của API này khiến ai cũng dính ít nhất một lần. Lambda với parameter type suy diễn cần một target type, mà phần nhận của một chained call thì không có target type:

import java.util.*;

record Employee(String name, String dept, int salary) {}

public class Infer {
    public static void main(String[] args) {
        List<Employee> l = new ArrayList<>();
        l.sort(Comparator.comparing(e -> e.dept()).thenComparing(e -> e.name()));
    }
}

Infer.java:8: error: cannot find symbol
        l.sort(Comparator.comparing(e -> e.dept()).thenComparing(e -> e.name()));
                                          ^
  symbol:   method dept()
  location: variable e of type Object
Infer.java:8: error: cannot find symbol
        l.sort(Comparator.comparing(e -> e.dept()).thenComparing(e -> e.name()));
                                                                       ^
  symbol:   method name()
  location: variable e of type Object
2 errors

e bị suy ra là Object. Nếu bỏ phần chain đi thì đúng lambda đó compile bình thường, vì l.sort(...) cung cấp target type. Cách sửa: ghi rõ type của parameter một lần, hoặc dùng method reference:

l.sort(Comparator.comparing((Employee e) -> e.dept()).thenComparing(e -> e.name()));
l.sort(Comparator.comparing(Employee::dept).thenComparing(Employee::name));

Chaining, và reversed() thực sự đảo cái gì

thenComparing dựng một composite: chạy comparator thứ nhất, nếu nó trả 0 thì chạy comparator thứ hai. reversed() đảo một comparator. Cái bẫy là khi bạn gọi reversed() trên một chain, thứ bị đảo là toàn bộ chain đó.

Bốn ordering trên cùng năm record, tất cả đều là output thật:

import java.util.*;
import static java.util.Comparator.*;

record Employee(String name, String dept, int salary) {
    @Override public String toString() { return name + "/" + dept + "/" + salary; }
}

public class Chaining {
    static final List<Employee> STAFF = List.of(
        new Employee("Ana",  "Eng",   120),
        new Employee("Bo",   "Sales", 120),
        new Employee("Cy",   "Eng",   140),
        new Employee("Dee",  "Sales", 110),
        new Employee("Eli",  "Eng",   120));

    static void show(String label, Comparator<Employee> c) {
        List<Employee> l = new ArrayList<>(STAFF);
        l.sort(c);
        System.out.println(label);
        l.forEach(e -> System.out.println("    " + e));
    }

    public static void main(String[] args) {
        show("A  comparing(dept).thenComparing(salary)",
             comparing(Employee::dept).thenComparing(Employee::salary));

        show("B  comparing(dept).thenComparing(salary).reversed()",
             comparing(Employee::dept).thenComparing(Employee::salary).reversed());

        show("C  comparing(dept).thenComparing(comparing(salary).reversed())",
             comparing(Employee::dept).thenComparing(comparing(Employee::salary).reversed()));

        show("D  comparing(dept).thenComparing(salary, reverseOrder())",
             comparing(Employee::dept).thenComparing(Employee::salary, reverseOrder()));
    }
}

A  comparing(dept).thenComparing(salary)
    Ana/Eng/120
    Eli/Eng/120
    Cy/Eng/140
    Dee/Sales/110
    Bo/Sales/120
B  comparing(dept).thenComparing(salary).reversed()
    Bo/Sales/120
    Dee/Sales/110
    Cy/Eng/140
    Ana/Eng/120
    Eli/Eng/120
C  comparing(dept).thenComparing(comparing(salary).reversed())
    Cy/Eng/140
    Ana/Eng/120
    Eli/Eng/120
    Bo/Sales/120
    Dee/Sales/110
D  comparing(dept).thenComparing(salary, reverseOrder())
    Cy/Eng/140
    Ana/Eng/120
    Eli/Eng/120
    Bo/Sales/120
    Dee/Sales/110

Hãy đọc B cạnh D. Gần như ai viết B cũng đang muốn D: department theo thứ tự bình thường, lương cao nhất lên đầu trong từng department. Còn B cho ra Sales trước Eng — key department cũng bị đảo, vì reversed() được áp lên cái composite chứ không phải lên key được nhắc sau cùng. C và D là hai cách chỉ đảo key cuối, và D ngắn hơn.

Quy tắc thuần máy móc: reversed() đảo comparator mà nó được gọi trên đó, và method chaining nghĩa là comparator đó bao gồm tất cả những gì nằm bên trái.

reversed() không giống với sort tăng dần rồi lật ngược list

Còn một khác biệt thứ hai, âm thầm hơn. Đảo comparator không đảo thứ tự của các phần tử ngang nhau, vì sort vẫn stable trong cả hai trường hợp — nhưng lật ngược list đã sort thì có:

import java.util.*;
import static java.util.Comparator.*;

record Employee(String name, String dept, int salary) {
    @Override public String toString() { return name + "/" + dept + "/" + salary; }
}

public class ReversedStable {
    static final List<Employee> STAFF = List.of(
        new Employee("Ana", "Eng",   120),
        new Employee("Bo",  "Sales", 120),
        new Employee("Cy",  "Eng",   140),
        new Employee("Dee", "Sales", 110),
        new Employee("Eli", "Eng",   120));

    public static void main(String[] args) {
        List<Employee> a = new ArrayList<>(STAFF);
        a.sort(comparingInt(Employee::salary).reversed());
        System.out.println("sort with reversed()      = " + a);

        List<Employee> b = new ArrayList<>(STAFF);
        b.sort(comparingInt(Employee::salary));
        System.out.println("sort ascending then flip  = " + b.reversed());
    }
}

sort with reversed()      = [Cy/Eng/140, Ana/Eng/120, Bo/Sales/120, Eli/Eng/120, Dee/Sales/110]
sort ascending then flip  = [Cy/Eng/140, Eli/Eng/120, Bo/Sales/120, Ana/Eng/120, Dee/Sales/110]

Ba người có lương 120. Sort bằng reversed() giữ họ ở thứ tự Ana, Bo, Eli — đúng thứ tự ban đầu. Sort tăng dần rồi lật ngược cả list cho ra Eli, Bo, Ana. Nếu list của bạn đến từ một lần sort trước đó hoặc từ một câu ORDER BY của database thì hai cách này không thay thế cho nhau được. (List.reversed() dùng ở trên là view của SequencedCollection thêm vào từ Java 21; nó trả về một view đảo ngược nên dựng ra không tốn gì.)

Bug trừ hai số int

Comparator lâu đời nhất trong Java là (a, b) -> a.value - b.value, và nó sai. Phép trừ hai giá trị int bị overflow một cách lặng lẽ, và khi overflow thì dấu của kết quả ngược hẳn với sự thật:

import java.util.*;

record Account(String id, int balance) {
    @Override public String toString() { return id + "=" + balance; }
}

public class Overflow {
    public static void main(String[] args) {
        List<Account> accounts = new ArrayList<>(List.of(
            new Account("a", 2_000_000_000),
            new Account("b", -2_000_000_000),
            new Account("c", 0)));

        List<Account> broken = new ArrayList<>(accounts);
        broken.sort((x, y) -> x.balance() - y.balance());
        System.out.println("subtraction     = " + broken);

        List<Account> fixed = new ArrayList<>(accounts);
        fixed.sort(Comparator.comparingInt(Account::balance));
        System.out.println("Integer.compare = " + fixed);

        int a = 2_000_000_000, b = -2_000_000_000;
        System.out.println();
        System.out.println("  a - b           = " + (a - b));
        System.out.println("  Integer.compare = " + Integer.compare(a, b));
        System.out.println("  a > b           = " + (a > b));
    }
}

subtraction     = [a=2000000000, b=-2000000000, c=0]
Integer.compare = [b=-2000000000, c=0, a=2000000000]

  a - b           = -294967296
  Integer.compare = 1
  a > b           = true

2000000000 - (-2000000000) là 4.000.000.000, con số không lọt vào một int; nó wrap thành -294967296, nên comparator báo rằng hai tỉ nhỏ hơn âm hai tỉ. List trả về đúng thứ tự ban đầu và không có gì báo lỗi.

Cách viết này chỉ an toàn khi cả hai toán hạng chắc chắn không âm và hiệu của chúng không vượt Integer.MAX_VALUE — size, count, index. Điều kiện đó dễ phát biểu và cũng rất dễ mất trong một lần refactor, còn Integer.compare(x, y) thì không tốn thêm gì, nên không có lý do gì giữ lại phép trừ. Lập luận tương tự áp dụng cho Long.compare, Double.compare và Character.compare; riêng Double.compare còn xử lý đúng NaN và -0.0, thứ mà không biểu thức số học nào làm được.

Comparison method violates its general contract

Đây mới là lỗi mà cả bài này thật sự nói về. Một comparator không có tính bắc cầu có thể sống sót qua mọi test bạn viết rồi hạ gục một request trên production, vì JDK chỉ phát hiện ra nó với input đủ lớn để đi vào một nhánh code nhất định.

Comparator không bắc cầu kinh điển nhất là kiểu tolerance: hai giá trị chênh nhau dưới một ngưỡng thì coi như bằng nhau.

import java.util.*;

public class Tolerant {
    // "within 10 counts as equal" -- reads sensible, is not transitive
    static final Comparator<Integer> TOLERANT =
        (a, b) -> Math.abs(a - b) <= 10 ? 0 : Integer.compare(a, b);

    public static void main(String[] args) {
        System.out.println("cmp(0, 8)   = " + TOLERANT.compare(0, 8));
        System.out.println("cmp(8, 16)  = " + TOLERANT.compare(8, 16));
        System.out.println("cmp(0, 16)  = " + TOLERANT.compare(0, 16));
    }
}

cmp(0, 8)   = 0
cmp(8, 16)  = 0
cmp(0, 16)  = -1

0 bằng 8, 8 bằng 16, và 0 nhỏ hơn 16. Không có thứ gì suy luận về thứ tự mà sống nổi với chuyện đó, vì "bằng nhau" đã không còn là một quan hệ tương đương.

Check nằm ở đâu, và vì sao con số là 32

List.sort trên một ArrayList đi tới java.util.TimSort, và TimSort có hai chế độ khác nhau. Dưới MIN_MERGE nó chạy một lượt binary insertion sort rồi dừng. Chỉ khi vượt ngưỡng đó nó mới dựng các run và merge chúng, mà contract check thì nằm bên trong các lần merge:

private static final int MIN_MERGE = 32;

// ...

int nRemaining  = hi - lo;
if (nRemaining < 2)
    return;  // Arrays of size 0 and 1 are always sorted

// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
    int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
    binarySort(a, lo, hi, lo + initRunLen, c);
    return;
}

Exception được ném từ mergeLo và mergeHi, đúng chỗ mà một trong hai run đang được merge bị phát hiện là đã hết trong khi thuật toán vẫn tin rằng còn phần tử. Trạng thái đó không thể xảy ra với một comparator đàng hoàng, nên TimSort kết luận — hoàn toàn chính xác — rằng lỗi nằm ở comparator, và báo ra thay vì làm hỏng mảng.

Cùng một comparator, thêm đúng một phần tử

Hệ quả là cùng một comparator hỏng lại hành xử hoàn toàn khác nhau tùy vào lượng dữ liệu bạn đưa vào. Chương trình dưới đây nhận kích thước từ command line và dựng input từ một seed cố định, nên mọi lần chạy bên dưới đều lặp lại được:

import java.util.*;

public class ContractViolation {
    static final Comparator<Integer> TOLERANT =
        (a, b) -> Math.abs(a - b) <= 10 ? 0 : Integer.compare(a, b);

    static List<Integer> sample(int n) {
        Random rnd = new Random(42);
        List<Integer> l = new ArrayList<>();
        for (int i = 0; i < n; i++) l.add(rnd.nextInt(200));
        return l;
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        List<Integer> l = sample(n);
        l.sort(TOLERANT);
        System.out.println("n=" + n + " sorted without throwing");
        System.out.println("ascending? " + ascending(l));
        System.out.println("first 20  = " + l.subList(0, Math.min(20, l.size())));
    }

    static boolean ascending(List<Integer> l) {
        for (int i = 1; i < l.size(); i++) if (l.get(i - 1) > l.get(i)) return false;
        return true;
    }
}

Với n = 32 không có exception nào, mà cũng không có list nào được sort:

n=32 sorted without throwing
ascending? false
first 20  = [9, 0, 32, 26, 30, 48, 43, 41, 56, 46, 63, 58, 84, 76, 76, 93, 105, 102, 92, 118]

9 trước 0, 32 trước 26, 48 trước 43. Đây chính là kết quả mà một unit test với vài fixture nhận được: gần như đã sort, nhìn thoáng qua thì hợp lý, và sai.

Với n = 122 — cùng comparator đó, cùng generator đó, nhiều hơn n = 121 đúng một phần tử, mà n = 121 thì vẫn im lặng trả về — lần sort từ chối làm việc:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.base/java.util.TimSort.mergeHi(TimSort.java:903)
	at java.base/java.util.TimSort.mergeAt(TimSort.java:520)
	at java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
	at java.base/java.util.TimSort.sort(TimSort.java:254)
	at java.base/java.util.Arrays.sort(Arrays.java:1308)
	at java.base/java.util.ArrayList.sort(ArrayList.java:1804)
	at ContractViolation.main(ContractViolation.java:17)

Chạy mọi kích thước từ 2 tới 1000 qua generator đó rồi ghi lại kích thước nào bị throw sẽ thấy được hình dạng của vấn đề:

⚠️ Bug không nặng thêm khi n tăng. Nó hiện diện y hệt ở n = 4. Thứ tăng lên là xác suất pha merge của TimSort vô tình đi trúng chỗ không nhất quán và nói cho bạn biết — và đó chính là lý do lỗi này đến dưới dạng sự cố production chứ không phải một test đỏ.

Exception cũng không hề gọi tên comparator của bạn. Khi thấy stack trace này, method có lỗi là bất cứ comparator nào được truyền vào lời gọi sort đó, và tìm ra nó nghĩa là đọc lại mọi hàm compare trên đường đi.

System property giúp che giấu lỗi

Arrays vẫn giữ bản merge sort trước Java 7 sau một system property, và bản cài đặt đó không có check nào:

java -Djava.util.Arrays.useLegacyMergeSort=true ContractViolation 500

n=500 sorted without throwing
ascending? false
first 20  = [9, 0, 1, 0, 3, 2, 3, 0, 6, 6, 17, 12, 7, 10, 3, 7, 6, 6, 19, 10]

Exception biến mất và dữ liệu vẫn sai. Flag này tồn tại để code viết từ thời Java 6 vẫn khởi động được; dùng nó để làm một IllegalArgumentException biến mất là đổi một lỗi ồn ào lấy một lỗi im lặng.

Cách sửa: làm cho "bằng nhau" trở thành quan hệ tương đương

Cách sửa không phải nới lỏng comparator, mà là làm cho quan hệ bằng nhau thật sự bắc cầu. Thay vì hỏi "hai giá trị này có gần nhau không", hãy hỏi "hai giá trị này có rơi vào cùng một bucket không", câu hỏi chỉ có một đáp án cho mỗi giá trị:

import java.util.*;

public class Bucketed {
    // transitive: two values are equal iff they land in the same bucket
    static final Comparator<Integer> BUCKETED = Comparator.comparingInt(v -> v / 10);

    public static void main(String[] args) {
        System.out.println("cmp(0, 8)  = " + BUCKETED.compare(0, 8));
        System.out.println("cmp(8, 16) = " + BUCKETED.compare(8, 16));
        System.out.println("cmp(0, 16) = " + BUCKETED.compare(0, 16));

        for (int n : new int[]{122, 500, 1000, 100000}) {
            Random rnd = new Random(42);
            List<Integer> l = new ArrayList<>();
            for (int i = 0; i < n; i++) l.add(rnd.nextInt(200));
            l.sort(BUCKETED);
            boolean ok = true;
            for (int i = 1; i < l.size(); i++) if (l.get(i-1) / 10 > l.get(i) / 10) ok = false;
            System.out.println("n=" + n + " sorted, buckets ascending = " + ok);
        }
    }
}

cmp(0, 8)  = 0
cmp(8, 16) = -1
cmp(0, 16) = -1
n=122 sorted, buckets ascending = true
n=500 sorted, buckets ascending = true
n=1000 sorted, buckets ascending = true
n=100000 sorted, buckets ascending = true

Giờ 8 và 16 khác nhau, khắt khe hơn bản tolerance, và đó là cái giá của một ordering thật sự tồn tại. Dạng tổng quát của cách sửa: rút ra một key từ mỗi phần tử, rồi so sánh các key. Mọi comparator dựng từ comparing, comparingInt và thenComparing trên các key extractor thuần đều bắc cầu theo cấu trúc, và đó là lý do rất tốt để ưu tiên chúng hơn là tự viết thân hàm compare.

Key null: nullsFirst và nullsLast

comparing gọi compareTo trên bất cứ thứ gì key extractor trả về, nên một key null là một NullPointerException ngay bên trong lần sort:

import java.util.*;
import static java.util.Comparator.*;

record Contact(String name, String nickname) {
    @Override public String toString() { return name + "(" + nickname + ")"; }
}

public class Nulls {
    public static void main(String[] args) {
        List<Contact> cs = new ArrayList<>(List.of(
            new Contact("Ana", "ana"), new Contact("Bo", "bo")));
        cs.add(new Contact("Cy", null));

        try {
            List<Contact> l = new ArrayList<>(cs);
            l.sort(comparing(Contact::nickname));
        } catch (Exception e) {
            System.out.println("comparing(nickname)                 -> " + e);
        }

        List<Contact> a = new ArrayList<>(cs);
        a.sort(comparing(Contact::nickname, nullsFirst(naturalOrder())));
        System.out.println("nullsFirst(naturalOrder())          -> " + a);

        List<Contact> b = new ArrayList<>(cs);
        b.sort(comparing(Contact::nickname, nullsLast(naturalOrder())));
        System.out.println("nullsLast(naturalOrder())           -> " + b);

        List<String> raw = new ArrayList<>(Arrays.asList("b", null, "a", null, "c"));
        raw.sort(nullsFirst(naturalOrder()));
        System.out.println("List<String> nullsFirst             -> " + raw);
        raw.sort(nullsLast(reverseOrder()));
        System.out.println("List<String> nullsLast(reverseOrder)-> " + raw);
    }
}

comparing(nickname)                 -> java.lang.NullPointerException: Cannot invoke "java.lang.Comparable.compareTo(Object)" because the return value of "java.util.function.Function.apply(Object)" is null
nullsFirst(naturalOrder())          -> [Cy(null), Ana(ana), Bo(bo)]
nullsLast(naturalOrder())           -> [Ana(ana), Bo(bo), Cy(null)]
List<String> nullsFirst             -> [null, null, a, b, c]
List<String> nullsLast(reverseOrder)-> [c, b, a, null, null]

Hai điều đáng chú ý. Bản comparing(keyExtractor, keyComparator) hai tham số mới là chỗ đặt comparator chịu được null — bọc comparator bên ngoài bằng nullsFirst chỉ bảo vệ trước phần tử null, không bảo vệ trước key null. Và nullsFirst/nullsLast chỉ quyết định null nằm ở đâu; comparator bạn truyền vào vẫn quyết định mọi thứ còn lại, nên nullsLast(reverseOrder()) đặt null sau a dù phần còn lại của list đang giảm dần.

Tính stable, và nó mang lại điều gì

Một lần sort là stable khi các phần tử so sánh ngang nhau giữ nguyên thứ tự tương đối vốn có. List.sort và Arrays.sort(Object[], Comparator) đều stable — cả hai chạy TimSort, và javadoc cam kết điều đó. Đó là thứ làm cho sort hai lượt hoạt động được:

import java.util.*;
import static java.util.Comparator.*;

record Ticket(String title, String assignee, int priority) {
    @Override public String toString() { return priority + " " + assignee + " " + title; }
}

public class Stability {
    public static void main(String[] args) {
        List<Ticket> t = new ArrayList<>(List.of(
            new Ticket("crash on save", "bo",  1),
            new Ticket("slow startup",  "ana", 2),
            new Ticket("typo in menu",  "cy",  2),
            new Ticket("data loss",     "ana", 1),
            new Ticket("bad icon",      "bo",  2)));

        t.sort(comparing(Ticket::title));
        System.out.println("after pass 1 (title):");
        t.forEach(x -> System.out.println("    " + x));

        t.sort(comparingInt(Ticket::priority));
        System.out.println("after pass 2 (priority):");
        t.forEach(x -> System.out.println("    " + x));
    }
}

after pass 1 (title):
    2 bo bad icon
    1 bo crash on save
    1 ana data loss
    2 ana slow startup
    2 cy typo in menu
after pass 2 (priority):
    1 bo crash on save
    1 ana data loss
    2 bo bad icon
    2 ana slow startup
    2 cy typo in menu

Lượt thứ hai chỉ nhắc tới priority, mà title bên trong từng nhóm priority vẫn theo thứ tự chữ cái. Đó là tính stable đang làm việc: sort theo key ít quan trọng nhất trước, rồi sort theo key quan trọng nhất, và bạn có một ordering nhiều key mà không cần compose comparator. thenComparing thường rõ ràng hơn và luôn rẻ hơn — một lượt thay vì hai — nhưng dạng hai lượt là thứ bạn cần khi hai lượt nằm ở hai chỗ khác nhau, chẳng hạn database trả rows theo một thứ tự còn UI gom nhóm lại theo thứ tự khác.

Mảng primitive không nhận comparator

Arrays.sort trên mảng primitive là dual-pivot quicksort và không stable, nhưng đó không phải giới hạn bạn có thể vấp phải, vì không có overload nào cho bạn quan sát điều đó:

int[] a = {5, 1, 4};
Arrays.sort(a, Comparator.reverseOrder());

PrimSort.java:5: error: no suitable method found for sort(int[],Comparator<T#1>)
        Arrays.sort(a, Comparator.reverseOrder());
              ^
    method Arrays.<T#2>sort(T#2[],Comparator<? super T#2>) is not applicable
      (inference variable T#2 has incompatible bounds
        equality constraints: int
        upper bounds: Object)

Hai giá trị int bằng nhau là cùng một giá trị; không chương trình nào phân biệt được cái nào đã bị di chuyển. Tính stable chỉ có ý nghĩa khi các phần tử ngang nhau phân biệt được với nhau, và điều đó đòi hỏi object. Muốn sort primitive theo thứ tự tùy chỉnh thì phải box trước — Arrays.stream(a).boxed().toArray(Integer[]::new) rồi Arrays.sort(boxed, cmp) — và trả giá cho phần boxing đó.

Đếm comparison thay vì đo thời gian

TimSort có tính adaptive: nó tìm những run vốn đã đúng thứ tự rồi merge chúng lại thay vì sort lại từ đầu. Đếm số lần gọi compare() cho thấy điều đó rõ hơn hẳn một cái đồng hồ bấm giây, và cho cùng đáp án trên mọi máy:

import java.util.*;
import java.util.concurrent.atomic.AtomicLong;

public class Counts {
    static AtomicLong compares = new AtomicLong();

    static Comparator<Integer> counting(Comparator<Integer> c) {
        return (a, b) -> { compares.incrementAndGet(); return c.compare(a, b); };
    }

    public static void main(String[] args) {
        int n = 1000;
        for (String kind : List.of("sorted", "reverse", "random", "nearly", "equal")) {
            List<Integer> l = new ArrayList<>(gen(n, kind));
            compares.set(0);
            l.sort(counting(Comparator.naturalOrder()));
            System.out.printf("  %-10s %,d%n", kind, compares.get());
        }
    }

    static List<Integer> gen(int n, String kind) {
        List<Integer> l = new ArrayList<>();
        Random r = new Random(7);
        switch (kind) {
            case "sorted" -> { for (int i = 0; i < n; i++) l.add(i); }
            case "reverse" -> { for (int i = n; i > 0; i--) l.add(i); }
            case "random" -> { for (int i = 0; i < n; i++) l.add(r.nextInt(1_000_000)); }
            case "equal" -> { for (int i = 0; i < n; i++) l.add(5); }
            case "nearly" -> {
                for (int i = 0; i < n; i++) l.add(i);
                for (int k = 0; k < 10; k++) Collections.swap(l, r.nextInt(n), r.nextInt(n));
            }
        }
        return l;
    }
}

  sorted     999
  reverse    999
  random     8,673
  nearly     2,084
  equal      999

Một list đã sort sẵn tốn đúng n - 1 comparison: một lượt duyệt tìm ra một run tăng dần duy nhất và không còn gì để merge. List sort ngược cũng tốn đúng bằng đó, vì TimSort nhận ra một run giảm dần chặt và đảo nó tại chỗ. Mười lần swap trong một list nghìn phần tử đã sort chỉ tốn khoảng một phần tư so với dữ liệu ngẫu nhiên hoàn toàn. Đây là lý do sort lại một list vốn đã gần đúng thứ tự thì rẻ, và cũng là lý do một comparator đắt tiền gây hại ít hơn vẻ ngoài của nó trên dữ liệu thực tế — và nhiều hơn hẳn trên dữ liệu ngẫu nhiên.

Nên viết cái nào?

Implement Comparable là một cam kết: nó tuyên bố ordering này là thuộc tính của type, sẽ không đổi, và mọi sorted collection trong chương trình sẽ dùng nó một cách âm thầm. Nếu bạn còn ngần ngại khi phát biểu câu đó về ordering của mình thì nó là một Comparator.

Hai thói quen thực tế. Hãy làm comparator của bạn total — thêm một bước phá hòa trên một field duy nhất, để những phần tử trông ngang nhau vẫn có thứ tự xác định, nếu không thì kết quả phụ thuộc vào thứ tự input và diff sẽ nhảy loạn. Và hãy dựng comparator từ comparing/thenComparing trên các key extractor thay vì tự viết compare, vì dạng đó không thể mất tính bắc cầu.

FAQ

Comparable và Comparator trong Java khác nhau thế nào?

Comparable được implement bởi chính class được sort và định nghĩa natural ordering duy nhất của nó qua int compareTo(T o). Comparator là một object riêng implement int compare(T a, T b), định nghĩa bên ngoài class, và bạn muốn bao nhiêu cũng được. Collections.sort(list) dùng cái thứ nhất; list.sort(comparator) dùng cái thứ hai.

Một class có thể có nhiều hơn một Comparable không?

Không. Generic type argument bị erase, nên implements Comparable<A>, Comparable<B> là lỗi compile: "Comparable cannot be inherited with different arguments". Ordering thứ hai bắt buộc phải là một Comparator.

Vì sao lần sort của tôi throw "Comparison method violates its general contract!"?

Comparator của bạn không phải một ordering hợp lệ — thường gặp nhất là nó không bắc cầu, hoặc nó trả 0 cho những cặp không thể hoán đổi cho nhau. TimSort phát hiện sự không nhất quán trong lúc merge hai run và throw IllegalArgumentException thay vì làm hỏng mảng. Nó chỉ phát hiện được với input từ 32 phần tử trở lên, và ngay cả khi đó cũng chỉ đôi lúc, nên bug này mới lọt ra production.

Vì sao trừ hai số int trong comparator lại không dùng được?

a - b overflow khi hiệu vượt khỏi miền int, và kết quả bị wrap mang dấu sai — 2000000000 - (-2000000000) cho ra -294967296. Hãy dùng Integer.compare(a, b), hoặc comparingInt, cả hai đều đúng với mọi cặp giá trị int.

reversed() có chỉ đảo key cuối cùng không?

Không. reversed() đảo comparator mà nó được gọi trên đó, và trong một chain thì đó là tất cả những gì nằm bên trái. comparing(dept).thenComparing(salary).reversed() sort department giảm dần và salary giảm dần. Muốn chỉ đảo key cuối, hãy viết thenComparing(Employee::salary, Comparator.reverseOrder()).

Làm sao sort một list có chứa null?

Bọc comparator lại: list.sort(Comparator.nullsFirst(Comparator.naturalOrder())) cho phần tử null. Với key null bên trong các phần tử không null, hãy truyền cái bọc đó làm argument thứ hai của comparing: comparing(Contact::nickname, nullsLast(naturalOrder())).

List.sort có stable không?

Có. List.sort và Arrays.sort(Object[], Comparator) đều chạy TimSort, thứ mà javadoc cam kết là stable. Arrays.sort trên mảng primitive là dual-pivot quicksort và không stable, nhưng không có overload nhận comparator cho primitive và hai giá trị int bằng nhau thì không phân biệt được, nên không có gì quan sát được phụ thuộc vào điều đó.

Vì sao có comparingInt bên cạnh comparing?

comparing cần một key là Comparable, nên key int bị autobox hai lần cho mỗi comparison rồi được so sánh qua Integer.compareTo. comparingInt nhận ToIntFunction và gọi Integer.compare trên giá trị thô. Sort một nghìn record chạy key extractor 17,346 lần, tức là tiết kiệm 17,346 lần cấp phát chỉ bằng cách đổi một từ.

Kết luận

Comparable trả lời "type này có thứ tự gì", Comparator trả lời "lần gọi này muốn thứ tự gì", và các factory method — comparing, comparingInt, thenComparing, reversed, nullsFirst — bao phủ gần như mọi ordering bạn sẽ cần mà không phải tự viết thân hàm compare. Điều đó quan trọng vì tính đúng đắn chứ không chỉ vì ngắn gọn: comparator ghép từ các key extractor thì bắc cầu theo cấu trúc, và hai lỗi trong bài này — overflow khi trừ int và tolerance không bắc cầu — đều là những thứ mà các factory method khiến bạn khó viết ra.

Nhớ ba điều. So sánh bằng Integer.compare, đừng bao giờ bằng phép trừ. Nhớ rằng reversed() đảo cả chain. Và khi một lần sort throw IllegalArgumentException với message đó, đừng với tay tới flag legacy merge sort — comparator thật sự hỏng, và nó đã hỏng ngay trên bộ dữ liệu test nhỏ của bạn rồi.

Bài tiếp theo trong series: class tiện ích Collections — sort, reverse, shuffle, binarySearch, cùng các wrapper unmodifiable và synchronized ẩn sau cùng một class đó.