Comparator và Comparable — thứ tự sắp xếp và hợp đồng so sánh

TL;DR: Java phân tách việc sắp xếp thành hai interface rõ rệt: Comparable<T> định nghĩa "thứ tự tự nhiên" (natural ordering) duy nhất gắn liền bên trong class thông qua compareTo(), trong khi Comparator<T> đóng vai trò chiến lược so sánh bên ngoài độc lập (external strategy) qua compare(). Bất kỳ hàm so sánh nào cũng phải tuân thủ nghiêm ngặt 4 quy tắc toán học (phản đối xứng, bắc cầu, bảo toàn dấu và nhất quán với equals). Vi phạm hợp đồng so sánh—chẳng hạn như dùng phép trừ a - b gây tràn số nguyên hoặc bỏ qua tính nhất quán với equals()—sẽ khiến TreeSet âm thầm nuốt mất phần tử hoặc làm thuật toán TimSort ném ngoại lệ ở runtime.

1. Vì sao TreeSet lại nuốt mất ấn phẩm khi chỉ so sánh theo năm xuất bản?

Xét tình huống thực tế trong hệ thống thư viện: Bạn cần lưu trữ danh mục sách vào một TreeSet để tự động sắp xếp theo năm xuất bản. Nhà phát triển tạo lớp CatalogBook cài đặt Comparable<CatalogBook>:

public class CatalogBook implements Comparable<CatalogBook> {
    private final String isbn;
    private final String title;
    private final int publishYear;

    public CatalogBook(String isbn, String title, int publishYear) {
        this.isbn = isbn;
        this.title = title;
        this.publishYear = publishYear;
    }

    @Override
    public int compareTo(CatalogBook other) {
        return Integer.compare(this.publishYear, other.publishYear);
    }
}

Mọi bài kiểm thử đơn lẻ đều vượt qua. Nhưng khi đưa vào vận hành thực tế, khi nạp 1.000 cuốn sách vào TreeSet<CatalogBook>, tập hợp chỉ còn lại chưa tới 50 cuốn! Tất cả các cuốn sách xuất bản trong cùng một năm đều bị loại bỏ chỉ còn giữ lại đúng 1 cuốn duy nhất.

Nguyên nhân: TreeSet định vị và kiểm tra sự tồn tại của phần tử chỉ thông qua compareTo(). Khi compareTo() trả về 0, TreeSet kết luận rằng phần tử này đã có sẵn trong cây và từ chối thêm vào (add() trả về false). Trên toàn bộ quá trình, phương thức equals() không hề được gọi tới.

2. Khi nào nên cài đặt thứ tự tự nhiên với Comparable?

Interface java.lang.Comparable<T> được thiết kế cho các lớp có một trật tự hiển nhiên duy nhất (Natural Ordering):

public interface Comparable<T> {
    int compareTo(T o);
}

Hợp đồng quy ước giá trị trả về của compareTo(o):

• Số âm (< 0): Đối tượng hiện tại nhỏ hơn o.
• Số 0 (== 0): Hai đối tượng tương đương nhau về thứ tự sắp xếp.
• Số dương (> 0): Đối tượng hiện tại lớn hơn o.

Hầu hết các lớp cơ bản trong JDK như String (theo bảng chữ cái), Integer (theo độ lớn số học), LocalDate (theo trình tự thời gian) đều cài đặt Comparable. Với ấn phẩm thư viện, mã tiêu chuẩn quốc tế ISBN là ứng viên lý tưởng cho thứ tự tự nhiên:

@Override
public int compareTo(CatalogBook other) {
    return this.isbn.compareTo(other.isbn);
}

3. Khi nào nên linh hoạt định nghĩa thứ tự ngoài với Comparator?

Trong thực tế quản lý kho sách, thủ thư không chỉ tìm kiếm theo ISBN mà còn cần sắp xếp theo nhiều góc độ khác nhau: theo số lượt mượn giảm dần, theo độ dày sách, hoặc theo tên tác giả. java.util.Comparator<T> cho phép tách biệt logic so sánh ra khỏi cấu trúc đối tượng:

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
}

Bởi vì Comparator là một @FunctionalInterface, ta có thể truyền nó linh hoạt dưới dạng Lambda hoặc Method Reference:

List<CatalogBook> books = getCatalogList();

// Sort by checkout frequency descending:
books.sort((b1, b2) -> Integer.compare(b2.getCheckoutCount(), b1.getCheckoutCount()));

// Initialize TreeSet with safe composite Comparator:
Comparator<CatalogBook> byYearThenIsbn = Comparator
    .comparingInt(CatalogBook::getPublishYear)
    .thenComparing(CatalogBook::getIsbn);

Set<CatalogBook> sortedShelf = new TreeSet<>(byYearThenIsbn);

4. Bốn quy tắc trong hợp đồng toán học của phép so sánh là gì?

Cả compareTo() lẫn compare() đều phải thỏa mãn 4 quy tắc toán học khắt khe để bảo đảm thuật toán sắp xếp (như TimSort của Java) không bị sụp đổ:

1. Quy tắc dấu đối xứng: sgn(compare(x, y)) == -sgn(compare(y, x)).
2. Quy tắc bắc cầu (Transitivity): Nếu $x > y$ và $y > z$ thì bắt buộc $x > z$.
3. Quy tắc nhất quán tương đương: Nếu $compare(x, y) == 0$, thì sgn(compare(x, z)) == sgn(compare(y, z)) với mọi $z$.
4. Tính nhất quán với equals() (Consistency with Equals): Khuyến nghị mạnh mẽ rằng $(compare(x, y) == 0) \iff (x.equals(y))$.

Nếu vi phạm quy tắc bắc cầu hoặc phản đối xứng, Arrays.sort() hoặc Collections.sort() sẽ ném ra lỗi IllegalArgumentException: Comparison method violates its general contract!.

5. Vì sao phép trừ a - b lại là cạm bẫy gây tràn số kinh điển?

Nhiều lập trình viên có thói quen viết tắt:

// Dangerous anti-pattern:
@Override
public int compareTo(CatalogBook other) {
    return this.publishYear - other.publishYear; // Never use subtraction here!
}

Phép trừ số nguyên 32-bit trong Java có thể gặp hiện tượng Tràn số (Integer Overflow):

• Giả sử this.publishYear = Integer.MIN_VALUE ($-2.147.483.648$) và other.publishYear = 1.
• Kết quả phép toán: $-2.147.483.648 - 1 = +2.147.483.647$ (giá trị bị đảo sang số dương cực lớn do tràn bit).
• Hàm so sánh báo rằng số cực âm lại "lớn hơn" số dương! Thứ tự sắp xếp sẽ bị phá hủy hoàn toàn.

✅ Giải pháp chuẩn: Luôn dùng phương thức tiện ích tĩnh của kiểu đóng gói:

return Integer.compare(this.publishYear, other.publishYear);

6. Xử lý giá trị Double.NaN và tính nhất quán với equals() ra sao?

Khi so sánh trọng lượng hoặc phí phạt quá hạn (double/float), toán tử so sánh thông thường < hoặc > sẽ sụp đổ khi gặp giá trị Double.NaN:

• Theo chuẩn IEEE 754, Double.NaN < x, Double.NaN > x, và Double.NaN == x đều trả về false.
• Hàm so sánh tự viết sẽ vi phạm quy tắc phản đối xứng vì compare(NaN, NaN) không trả về 0.

✅ Giải pháp: Sử dụng Double.compare(d1, d2) để bảo đảm Total Ordering chuẩn IEEE 754 (coi NaN là giá trị lớn nhất và bằng chính nó).

Khác biệt giữa BigDecimal trong HashSet và TreeSet

Một ví dụ kinh điển về việc không nhất quán với equals() trong chính JDK là BigDecimal:

• new BigDecimal("1.0").equals(new BigDecimal("1.00")) trả về false (vì khác độ chính xác scale: 1 so với 2).
• new BigDecimal("1.0").compareTo(new BigDecimal("1.00")) trả về 0 (vì bằng nhau về giá trị toán học).

Hệ quả: HashSet sẽ chứa cả 2 phần tử, trong khi TreeSet sẽ coi chúng là một và chỉ giữ lại 1 phần tử!

7. Xây dựng chuỗi so sánh phức tạp bằng Java 8 Fluent Comparator như thế nào?

Từ Java 8, interface Comparator bổ sung bộ công cụ Fluent API giúp viết các tiêu chí sắp xếp phức hợp vô cùng thanh lịch:

Comparator<CatalogBook> complexComparator = Comparator
    // Criteria 1: Publication year descending
    .comparingInt(CatalogBook::getPublishYear).reversed()
    // Criteria 2: Title ascending (case-insensitive)
    .thenComparing(CatalogBook::getTitle, String.CASE_INSENSITIVE_ORDER)
    // Criteria 3: Unique ISBN tie-breaker
    .thenComparing(CatalogBook::getIsbn);

Xử lý phần tử null an toàn

Khi danh sách có thể chứa các giá trị null:

// Place null elements at the end of sorted list
Comparator<CatalogBook> nullSafeComparator = Comparator.nullsLast(
    Comparator.comparing(CatalogBook::getTitle)
);

[!TIP] Sử dụng các hàm chuyên biệt cho kiểu nguyên thủy như comparingInt(), comparingLong(), comparingDouble() thay vì comparing() để ngăn ngừa chi phí đóng gói tự động (Autoboxing) khi sắp xếp danh sách lớn.

8. Đọc thêm từ tài liệu Oracle và các liên kết liên quan

9. Tóm tắt các điểm mấu chốt

• Comparable định hình thứ tự tự nhiên của đối tượng; Comparator định nghĩa chiến lược so sánh tùy biến bên ngoài.
• TreeSet và TreeMap xác định tính duy nhất dựa hoàn toàn vào compareTo() hoặc compare(), không dùng equals().
• Tránh xa phép trừ a - b khi so sánh số; luôn dùng Integer.compare(), Long.compare(), hoặc Double.compare().
• Với các tập hợp sắp xếp, luôn bảo đảm tính nhất quán giữa compareTo() và equals(), hoặc bổ sung tie-breaker để không làm thất lạc dữ liệu.
• Tận dụng Comparator.comparingInt() và .thenComparing() để xây dựng các chuỗi so sánh đa tầng không tốn chi phí autoboxing.

10. Câu hỏi tự kiểm tra

Bài tiếp theo: Immutable Collections — List.of, Set.of và unmodifiableList