99 Ngày Java — Ngày 38: Comparable & Comparator

Ngày 33 TreeSet và Ngày 35 TreeMap đều đòi phần tử phải "so sánh được", và ta đã hứa sẽ quay lại. Hôm nay trả nợ: Comparable là thứ tự tự nhiên gắn liền với lớp, còn Comparator là thứ tự tháo rời ra ngoài — một lớp, vô số cách sắp. Kèm theo là ba thứ khiến việc sắp xếp hay sai trong thực tế: cái bẫy reversed() đặt nhầm chỗ, chuyện trừ hai số bị tràn, và tính ổn định của thuật toán sắp xếp.

Comparable — thứ tự tự nhiên của lớp

Comparable trả lời câu hỏi: "nếu chỉ được chọn MỘT cách sắp cho lớp này, thì đó là cách nào?". Với số, ngày tháng hay tiền thì câu trả lời hiển nhiên. Với một lớp nghiệp vụ như nhân viên thì thường không hiển nhiên — và đó là dấu hiệu bạn nên dùng Comparator thay vì ép một thứ tự vào lớp.

// Ngày 33 TreeSet và Ngày 35 TreeMap đều đòi key "so sánh được".
// Đây chính là thứ chúng đòi: Comparable — THỨ TỰ TỰ NHIÊN của một lớp.

record Nhanvien(String ten, int tuoi, long luong) implements Comparable<Nhanvien> {
    @Override public int compareTo(Nhanvien khac) {
        return Integer.compare(this.tuoi, khac.tuoi);   // trẻ trước, già sau
    }
}
Collections.sort(ds);          // dùng thứ tự tự nhiên
ds.sort(null);                 // y hệt — null nghĩa là "dùng Comparable"

// HỢP ĐỒNG của compareTo — trả về int, và chỉ DẤU mới có nghĩa:
//   âm  → this đứng TRƯỚC khac
//   0   → hai phần tử NGANG NHAU về thứ tự
//   dương → this đứng SAU khac

// LUÔN dùng Integer.compare / Long.compare, ĐỪNG tự trừ:
return this.luong - khac.luong;        // SAI: long trừ nhau tràn int
return (int)(this.luong - khac.luong); // SAI: 3 tỷ - (-3 tỷ) tràn → dấu ngược
return Long.compare(this.luong, khac.luong);  // ĐÚNG, luôn luôn

// Chỉ cài Comparable khi lớp có ĐÚNG MỘT thứ tự hiển nhiên
// (số, ngày, tiền). Nhân viên "tự nhiên" sắp theo gì? Không rõ → đừng cài.

• Chỉ dấu của số trả về mới có nghĩa — trả -1, -7 hay -9999 là như nhau.

• Đừng bao giờ trừ tay: a - b tràn số với long hoặc với int ở hai đầu miền giá trị, và khi tràn thì dấu lật ngược — sắp sai mà không hề báo lỗi. Luôn dùng Integer.compare / Long.compare.

• Cài Comparable là một lời tuyên bố: từ nay TreeSet, TreeMap, Collections.sort đều mặc định đi theo thứ tự này.

Comparator — tháo thứ tự ra khỏi lớp

Đây mới là thứ bạn dùng hằng ngày. Từ Java 8, Comparator có cả một bộ hàm dựng sẵn cho phép ghép thứ tự lại như xếp hình, và gần như không còn lý do gì để tự viết tay compare() nữa.

// Comparator = thứ tự ĐỂ RỜI khỏi lớp. Một lớp, vô số cách sắp.
// Từ Java 8 gần như không ai còn viết tay compare() nữa:

ds.sort(comparing(Nhanvien::luong));                    // theo lương tăng dần
ds.sort(comparing(Nhanvien::luong).reversed());         // giảm dần
ds.sort(comparing(Nhanvien::tuoi)
        .thenComparing(Nhanvien::ten));                 // cùng tuổi → theo tên

// Tránh autoboxing khi so số nguyên thủy — có bản chuyên dụng:
ds.sort(comparingInt(Nhanvien::tuoi));      // không sinh Integer rác
ds.sort(comparingLong(Nhanvien::luong));

// BẪY reversed() đặt sai chỗ:
comparing(Nhanvien::tuoi).thenComparing(Nhanvien::ten).reversed();
// → đảo NGƯỢC CẢ HAI tiêu chí, không phải chỉ tiêu chí đầu!
comparing(Nhanvien::tuoi, reverseOrder()).thenComparing(Nhanvien::ten);
// → chỉ tuổi giảm dần, tên vẫn tăng dần — đây mới là điều bạn muốn

// Xử lý null tường minh thay vì để NullPointerException:
comparing(Nhanvien::ten, nullsLast(naturalOrder()));

• comparing + thenComparing diễn đạt "sắp theo A, cùng A thì theo B" đúng như cách bạn nói thành lời.

• Bẫy hay gặp nhất: reversed() đặt ở cuối chuỗi sẽ đảo toàn bộ chuỗi, không phải chỉ tiêu chí đầu. Muốn đảo riêng một tiêu chí thì truyền reverseOrder() vào đúng tiêu chí đó.

• Dùng comparingInt / comparingLong cho số nguyên thủy để khỏi sinh Integer rác — đây là bài học autoboxing của Ngày 22 quay lại.

• nullsFirst / nullsLast xử lý null tường minh, thay vì để NullPointerException nổ giữa lúc sắp.

Tính ổn định và hợp đồng phải giữ

Có một tính chất của sort mà ít người để ý nhưng lại quyết định kết quả: tính ổn định. Java sắp object bằng TimSort, và TimSort giữ nguyên thứ tự cũ của những phần tử bằng nhau — nhờ đó danh sách đã sắp theo tên vẫn giữ được trật tự tên sau khi sắp lại theo tuổi.

// Java dùng TimSort cho object — và TimSort ỔN ĐỊNH.
// Ổn định = hai phần tử BẰNG NHAU về tiêu chí sắp thì GIỮ NGUYÊN thứ tự cũ.

// Nhờ vậy, sắp nhiều tiêu chí có thể làm bằng cách SẮP NHIỀU LẦN, từ phụ tới chính:
ds.sort(comparing(Nhanvien::ten));      // sắp phụ trước
ds.sort(comparing(Nhanvien::tuoi));     // rồi sắp chính — tên vẫn giữ trật tự
// (thực tế nên dùng thenComparing cho rõ ý, nhưng hiểu tính ổn định thì
//  bạn giải thích được vì sao cách này chạy đúng)

// Mảng NGUYÊN THỦY thì dùng dual-pivot quicksort — KHÔNG ổn định.
// Không sao: hai số 5 giống hệt nhau thì đổi chỗ cũng chẳng ai phân biệt được.

// Vi phạm hợp đồng = nổ giữa lúc chạy, không phải sai âm thầm:
//   "Comparison method violates its general contract!"
// Thường do compareTo không nhất quán (a<b, b<c nhưng a>c), hoặc do
// so sánh trên field MUTABLE bị đổi giữa chừng khi đang sắp.

// equals và compareTo NÊN nhất quán: compareTo trả 0 thì equals nên true.
// Không nhất quán thì TreeSet coi hai phần tử là một, còn HashSet coi là hai —
// cùng một dữ liệu, hai kết quả khác nhau (đúng cái bẫy BigDecimal Ngày 33).

• Object thì ổn định (TimSort), mảng nguyên thủy thì không (quicksort hai chốt) — và điều đó hoàn toàn hợp lý.

• Thông báo Comparison method violates its general contract! gần như luôn là do so sánh không nhất quán, hoặc so sánh trên field thay đổi được ngay trong lúc đang sắp.

• compareTo trả 0 thì equals nên trả true. Không nhất quán thì TreeSet và HashSet cho hai kết quả khác nhau trên cùng dữ liệu — đúng cái bẫy BigDecimal của Ngày 33.

Dùng trong thực tế

Vài thói quen nhỏ làm code sắp xếp đọc dễ hơn hẳn: đặt tên cho Comparator dùng lại nhiều lần, dùng stream().sorted() khi không được phép đụng vào danh sách gốc, và nhớ rằng không phải lúc nào cũng cần sắp toàn bộ.

// Sắp xếp bằng Stream khi cần giữ nguyên danh sách gốc:
List<Nhanvien> daSap = ds.stream()
        .sorted(comparing(Nhanvien::luong).reversed())
        .toList();                       // ds KHÔNG bị đổi

// Cần top-K chứ không cần sắp hết? PriorityQueue của Ngày 36 rẻ hơn nhiều:
// sort toàn bộ là O(n log n), heap k phần tử chỉ O(n log k).

// Comparator dùng lại được thì đặt tên và đưa vào chính lớp đó:
record Nhanvien(...) {
    static final Comparator<Nhanvien> THEO_LUONG_GIAM =
            comparing(Nhanvien::luong).reversed().thenComparing(Nhanvien::ten);
}
ds.sort(Nhanvien.THEO_LUONG_GIAM);       // đọc ra ý định ngay tại chỗ gọi

// TreeMap/TreeSet nhận Comparator trong constructor — và từ đó
// thứ tự ĐÓ quyết định luôn cả tính "trùng nhau" bên trong chúng:
new TreeSet<>(comparing(Nhanvien::ten));  // hai người trùng tên = MỘT phần tử!

• list.sort(...) sửa tại chỗ, còn stream().sorted(...) trả bản mới — chọn theo việc bạn có được phép đổi danh sách gốc hay không.

• Chỉ cần top 10 trong một triệu dòng thì đừng sắp cả triệu: PriorityQueue của Ngày 36 cho O(n log k).

• Nhớ kỹ khi đưa Comparator vào TreeSet: thứ tự đó định nghĩa luôn tính trùng lặp — sắp theo tên thì hai người trùng tên bị coi là một.

Bài tập nhỏ

• Viết compareTo bằng phép trừ trên hai giá trị long cỡ vài tỷ, rồi in kết quả sắp xếp ra — nhìn tận mắt thứ tự bị lật vì tràn số.

• Sắp danh sách nhân viên theo tuổi tăng, cùng tuổi thì tên tăng; rồi thêm reversed() ở cuối và giải thích vì sao tên cũng bị đảo theo.

• Chứng minh tính ổn định: sắp theo tên trước, rồi sắp theo tuổi, và kiểm tra những người cùng tuổi vẫn đứng theo thứ tự tên.

• Đưa comparing(Nhanvien::ten) vào một TreeSet rồi thêm hai nhân viên trùng tên khác tuổi — đếm size() và giải thích.

• So thời gian giữa sắp toàn bộ một triệu phần tử và lấy top 10 bằng PriorityQueue.

Kết lại

Bốn ý gói lại hôm nay: Comparable là một thứ tự tự nhiên gắn vào lớp, chỉ cài khi thứ tự đó hiển nhiên, và luôn dùng Integer.compare thay vì trừ tay; Comparator là thứ tự tháo rời, ghép bằng comparing và thenComparing — nhớ rằng reversed() đảo cả chuỗi; sắp object thì ổn định, nên sắp nhiều lần vẫn ra kết quả đúng; và compareTo phải nhất quán với equals kẻo cùng dữ liệu mà TreeSet với HashSet trả lời khác nhau. Ngày 39 ta bước vào phần khiến nhiều người ngại nhất của Java: Generics — vì sao List<String> an toàn hơn List, và type erasure thực chất là gì. Hẹn gặp lại!