Hiệu năng và so sánh

Hai bài trước đã đi qua từng cấu trúc. Bài này khép lại bằng cách trả lời câu hỏi quan trọng nhất: với một bài toán cụ thể thì chọn cấu trúc nào. Câu trả lời nằm ở thao tác chiếm đa số và ở hai hợp đồng làm nền cho bảng băm và cây sắp xếp.

Hãy đặt vấn đề bằng một tình huống thật. Một chương trình đọc một triệu dòng nhật ký và cần đếm mỗi mã người dùng xuất hiện bao nhiêu lần. Viết bằng List rồi mỗi lần lại contains để xem mã đã có chưa: mỗi lần tìm quét cả danh sách, tổng chi phí O(n²), chạy hàng chục phút. Đổi sang HashMap: mỗi lần tra trung bình O(1), tổng chi phí O(n), xong trong vài giây. Cùng thuật toán, cùng máy, chỉ khác cấu trúc dữ liệu.

Hợp đồng equals và hashCode

Bảng băm chỉ chạy đúng nếu khoá cài đúng cặp equals và hashCode. equals quyết định hai đối tượng có được coi là bằng nhau hay không; hashCode cho biết đối tượng thuộc ngăn nào. Quy tắc bắt buộc: nếu a.equals(b) đúng thì a.hashCode() phải bằng b.hashCode(). Chiều ngược lại không bắt buộc, hai đối tượng cùng mã băm vẫn có thể khác nhau.

Luôn ghi đè cả hai cùng lúc

Nếu chỉ ghi đè equals mà quên hashCode, hai đối tượng bằng nhau sẽ có mã băm khác nhau, rơi vào hai ngăn khác nhau, và HashSet sẽ chứa cả hai như thể chúng khác nhau.

public final class Diem {
    private final int x, y;
    public Diem(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;                 // same reference
        if (!(o instanceof Diem d)) return false;   // type check + pattern
        return x == d.x && y == d.y;                // compare same fields
    }
    @Override
    public int hashCode() {
        return Objects.hash(x, y);   // must use the same fields as equals
    }
}

Java 16 có record

Từ Java 16, lớp record sinh sẵn equals, hashCode và toString theo các trường thành phần, nên hiếm khi phải tự viết. Dù vậy hiểu hợp đồng vẫn cần thiết để biết khi nào tự cài là an toàn.

Sắp xếp với Comparable và Comparator

Để TreeSet, TreeMap hay Collections.sort biết cách sắp xếp, phần tử phải có một thứ tự. Có hai con đường:

• Comparable là thứ tự tự nhiên gắn vào chính lớp qua phương thức compareTo; mỗi lớp chỉ có một thứ tự tự nhiên.
• Comparator là một đối tượng so sánh bên ngoài, cho phép định nghĩa nhiều tiêu chí khác nhau mà không sửa lớp gốc.

Phương thức so sánh trả số âm nếu phần tử này đứng trước, số dương nếu đứng sau, và không nếu coi là tương đương. Từ Java 8, Comparator có các phương thức tiện lợi như comparing, thenComparing, reversed để ghép nhiều tiêu chí gọn gàng.

public class SinhVien implements Comparable<SinhVien> {
    String ten; double diem;
    SinhVien(String t, double d) { ten = t; diem = d; }

    @Override
    public int compareTo(SinhVien o) {     // natural order: by name
        return this.ten.compareTo(o.ten);
    }
}
// Custom multi-key order: by score descending, then by name ascending
List<SinhVien> ds = new ArrayList<>();
ds.sort(Comparator.comparingDouble((SinhVien s) -> s.diem).reversed()
                  .thenComparing(s -> s.ten));

Khi nào dùng cái nào

Dùng Comparable cho thứ tự duy nhất và hiển nhiên của một lớp. Dùng Comparator khi cần nhiều cách sắp, khi không sửa được lớp gốc, hoặc khi muốn sắp khác với thứ tự tự nhiên.

Chọn cấu trúc nào: tổng kết hiệu năng

Quyết định chọn cấu trúc nên dựa trên thao tác chiếm đa số trong bài toán. Bảng sau so sánh độ phức tạp trung bình của các thao tác chính.

Cấu trúc	Truy cập	Tìm	Thêm	Xoá	Đặc điểm
ArrayList	O(1)	O(n)	O(1)*	O(n)	có chỉ số, duyệt nhanh
LinkedList	O(n)	O(n)	O(1)†	O(1)†	thêm xoá ở hai đầu
ArrayDeque	n/a	n/a	O(1)	O(1)	hàng đợi, ngăn xếp
PriorityQueue	n/a	n/a	O(log n)	O(log n)	lấy nhỏ nhất trước
HashSet	n/a	O(1)	O(1)	O(1)	không thứ tự, loại trùng
LinkedHashSet	n/a	O(1)	O(1)	O(1)	giữ thứ tự chèn
TreeSet	n/a	O(log n)	O(log n)	O(log n)	luôn được sắp
HashMap	n/a	O(1)	O(1)	O(1)	tra khoá nhanh
LinkedHashMap	n/a	O(1)	O(1)	O(1)	giữ thứ tự chèn
TreeMap	n/a	O(log n)	O(log n)	O(log n)	khoá luôn được sắp

(*) Thêm vào cuối ArrayList là O(1) khấu hao (amortized); thỉnh thoảng tốn O(n) khi tăng dung lượng.

(†) Với LinkedList, O(1) chỉ đúng khi thao tác ở hai đầu (addFirst, addLast, removeFirst, removeLast) hoặc khi đã cầm sẵn Iterator đứng đúng chỗ. Thêm hay xoá theo chỉ số ở giữa bằng add(i, x) và remove(i) vẫn là O(n), vì phải đi i bước tới vị trí đó trước đã. Mục "Đọc bảng độ phức tạp cho đúng" nói kỹ chuyện này.

Thao tác chiếm đa số thì chọn gì: bấm để xem

Đọc bảng độ phức tạp cho đúng

Bảng trên chỉ có ích nếu hiểu con số đến từ đâu. ArrayList là một mảng liên tục nên get(i) chỉ là một phép tính địa chỉ, tức O(1); nhưng chèn hay xoá ở giữa buộc phải dịch mọi phần tử phía sau, tức O(n). LinkedList ngược lại: không có chỉ số nên get(i) phải đi từng nút, bù lại khi đã đứng ở đúng vị trí thì nối lại con trỏ chỉ tốn O(1).

Điểm dễ hiểu nhầm nhất nằm ở chữ "khi đã đứng ở đúng vị trí". Chèn vào giữa LinkedList bằng add(i, x) không phải O(1), vì máy vẫn phải đi i bước để tới chỗ đó. Chỉ khi thao tác ở hai đầu, LinkedList mới thật sự thắng.

List<Integer> a = new ArrayList<>();
List<Integer> b = new LinkedList<>();

a.add(0, 5);     // O(n): every element shifts right
b.add(0, 5);     // O(1): index 0 IS the head, only pointers are relinked

a.add(500, 5);   // O(n): shift the tail right
b.add(500, 5);   // O(n) TOO: must walk 500 nodes before relinking

a.get(500);      // O(1): direct address computation
b.get(500);      // O(n): walk 500 nodes from the head

Đọc kỹ bốn dòng giữa: LinkedList chỉ thắng ở dòng add(0, 5), nơi vị trí cần chèn đúng là đầu danh sách nên không phải đi đâu cả. Sang add(500, 5) thì cả hai đều O(n), chỉ khác nguyên nhân: ArrayList tốn vì phải dịch phần đuôi, LinkedList tốn vì phải đi tới nơi.

Trong thực tế, ArrayList thắng thường xuyên hơn bảng gợi ý, vì các phần tử nằm liền nhau nên bộ đệm của CPU nạp được cả cụm một lần, còn LinkedList rải các nút khắp bộ nhớ động. Cứ mặc định ArrayList, chỉ đổi khi có bằng chứng đo được.

Cái bảng đại lượng lớn giấu đi một sự thật của phần cứng: không phải phép truy cập bộ nhớ nào cũng tốn như nhau. Bộ xử lý đọc bộ nhớ theo từng khối liền gọi là dòng đệm (cache line), nên khi duyệt một ArrayList, phần tử kế tiếp thường đã nằm sẵn trong đệm nhờ được nạp cùng khối với phần tử vừa đọc. LinkedList thì mỗi nút là một đối tượng cấp phát riêng, rải rác khắp heap, nên đi từ nút này sang nút kia dễ thành một lần trượt đệm phải chờ bộ nhớ chính. Khoảng cách tốc độ giữa đệm và bộ nhớ chính lớn tới mức một thuật toán O(n) duyệt liền mạch có khi thắng một thuật toán cùng bậc nhưng nhảy lung tung. Đây là lý do sâu xa vì sao lời khuyên mặc định ArrayList đứng vững ngoài đời chứ không chỉ trên giấy.

Vậy có khi nào nên chọn LinkedList? Có, nhưng hẹp. Nó hợp khi mã liên tục thêm và xoá ở hai đầu một hàng đợi hai chiều, hoặc khi đang duyệt bằng Iterator và cần xoá ngay phần tử hiện tại mà không phải dịch mảng. Ngay cả hai ca này, ArrayDeque thường vẫn nhanh hơn cho vai hàng đợi nhờ nằm liền trong bộ nhớ. Nói cách khác, LinkedList là một cấu trúc có lý thuyết đẹp nhưng ít khi là lựa chọn tốt nhất trong thực tế; hãy coi nó là ngoại lệ cần biện minh bằng số đo, không phải mặc định.

Chi phí băm và va chạm

HashMap được ghi là O(1), nhưng đó là trung bình chứ không phải luôn luôn. Một lần put gồm ba việc: tính hashCode() của khoá, rút gọn về chỉ số ngăn, rồi so khoá bằng equals với những gì đã nằm trong ngăn đó. Nếu hàm băm phân tán tốt, mỗi ngăn chỉ giữ vài phần tử và bước cuối gần như tức thời.

Khi hàm băm phân tán kém, nhiều khoá cùng rơi vào một ngăn, gọi là va chạm. Chuỗi trong ngăn dài ra, mỗi lần tra phải quét cả chuỗi, và O(1) xấu dần về O(n). Cực đoan nhất là hashCode trả về hằng số: mọi khoá vào chung một ngăn và HashMap biến thành một danh sách liên kết. Từ Java 8, ngăn quá dài được chuyển thành cây cân bằng nên cái xấu nhất được kìm ở O(log n), nhưng đó là vá lỗi chứ không phải giải pháp.

Khoá của HashMap phải bất biến

Nếu đặt một đối tượng làm khoá rồi sửa chính trường mà hashCode dựa vào, mã băm đổi theo. HashMap vẫn giữ đối tượng ở ngăn cũ nhưng lần tra sau lại tính ra ngăn mới, nên get trả về null dù cặp vẫn nằm trong bảng. Hãy dùng khoá bất biến: String, số bọc, record, hoặc lớp chỉ có trường final.

Chi phí mở rộng mảng

Bên trong ArrayList là một mảng cố định. Khi mảng đầy, nó cấp một mảng mới lớn hơn và sao chép toàn bộ phần tử sang, một thao tác O(n). Vì việc này thưa dần theo cấp số nhân, chi phí trung bình của mỗi lần add cuối vẫn là O(1) khấu hao. Dù vậy, nếu biết trước số phần tử thì nên báo trước dung lượng để tránh hẳn các lần sao chép.

List<Integer> a = new ArrayList<>(1_000_000);  // capacity given up front
for (int i = 0; i < 1_000_000; i++) a.add(i);  // no resize, no copying

HashMap cũng vậy: khi số cặp vượt hệ số tải (mặc định 0.75 của số ngăn), bảng phải tăng gấp đôi số ngăn và băm lại toàn bộ khoá.

Ở đây có một cái bẫy. Nếu định bỏ vào n cặp mà chỉ viết new HashMap<>(n), bảng vẫn phải băm lại, vì ngưỡng mở rộng là 0.75 × n chứ không phải n. Muốn tránh hẳn, dung lượng ban đầu phải chia cho hệ số tải.

int n = 1_000_000;
Map<String, Integer> m1 = new HashMap<>(n);   // still rehashes: threshold is only 0.75 x capacity
Map<String, Integer> m2 = new HashMap<>((int) (n / 0.75) + 1);  // room for n entries, no rehash

Con số 0.75 không phải tùy tiện mà là một điểm cân bằng. Hệ số tải thấp nghĩa là bảng còn nhiều ngăn trống, va chạm ít, tra nhanh, nhưng tốn bộ nhớ và phải băm lại sớm hơn; hệ số tải cao thì tiết kiệm bộ nhớ nhưng chuỗi trong ngăn dài ra, kéo mỗi lần tra chậm lại. Mức 0.75 mặc định của Java là chỗ đổi chác được cho là hợp lý giữa hai thái cực đó cho phần lớn tình huống. Chỉnh nó chỉ đáng làm khi đã đo và biết rõ mình đang tối ưu cho bộ nhớ hay cho tốc độ, chứ không phải theo cảm tính.

Tập hợp chỉ chứa đối tượng, số nguyên thủy bị bọc lại

Nguyên nhân gốc là generic của Java làm việc trên kiểu tham chiếu, nên List<Integer> không giữ int mà giữ Integer. Mỗi lần add(i) một int, Java lặng lẽ bọc nó thành Integer (autoboxing), và mỗi lần đọc ra lại tháo bọc. Với vòng lặp hàng triệu phần tử, chi phí bọc và tháo cùng đống đối tượng rác sinh ra là thật, đôi khi lấn át cả khác biệt độ phức tạp. Khi cần nhồi số nguyên thủy với số lượng lớn và nhạy hiệu năng, một mảng int[] phẳng hay một thư viện tập hợp nguyên thủy chuyên dụng thường nhanh hơn hẳn.

Đo thực tế thay vì đoán

Độ phức tạp chỉ nói về xu hướng khi n lớn, không nói về hằng số. Với n nhỏ, một thuật toán O(n) hằng số nhỏ có thể nhanh hơn một thuật toán O(1) hằng số lớn. Đừng đoán, hãy đo.

long t0 = System.nanoTime();
// the operation being measured, repeated many times
long ms = (System.nanoTime() - t0) / 1_000_000;
System.out.println(ms + " ms");

Phép đo tay như trên đủ để thấy khác biệt lớn, nhưng dễ sai lệch vì máy ảo còn phải khởi động và biên dịch nóng. Muốn số liệu nghiêm túc, hãy chạy phần cần đo vài nghìn lần cho máy ảo kịp tối ưu rồi mới tính giờ, hoặc dùng JMH.

Bài tập thực hành

Bài tập 1: chọn đúng cấu trúc

Với mỗi tình huống sau, chọn cấu trúc phù hợp nhất và giải thích ngắn gọn: (a) lưu danh sách số điện thoại không trùng và in theo thứ tự tăng dần; (b) hàng chờ xử lý công việc theo thứ tự đến; (c) bảng tra điểm theo mã sinh viên cần truy xuất nhanh; (d) ngăn xếp hoàn tác của một trình soạn thảo.

Lời giải chi tiết

(a) TreeSet vừa loại trùng vừa giữ phần tử luôn được sắp, nên duyệt ra đúng thứ tự tăng dần mà không cần sắp lại; mỗi thao tác O(log n).

(b) ArrayDeque dùng như hàng đợi FIFO: offer ở đuôi, poll ở đầu, đều O(1). Đây là lựa chọn được khuyến nghị thay cho LinkedList khi làm hàng đợi.

(c) HashMap với khoá là mã sinh viên cho tra cứu trung bình O(1). Nếu cần duyệt theo thứ tự mã thì đổi sang TreeMap, nhưng ở đây yêu cầu chỉ là truy xuất nhanh.

(d) ArrayDeque dùng như ngăn xếp LIFO: push và pop ở cùng một đầu, đều O(1). Tài liệu Java khuyến nghị dùng nó thay cho lớp Stack cũ.

Bài tập 2: quên hashCode

Một lập trình viên ghi đè equals cho lớp Diem nhưng quên hashCode. Mô tả chính xác điều gì xảy ra khi đặt hai đối tượng Diem bằng nhau vào một HashSet, và vì sao.

Lời giải chi tiết

Vì không ghi đè hashCode, hai đối tượng dùng mã băm mặc định của Object, vốn dựa trên địa chỉ, nên gần như chắc chắn khác nhau. Hai mã băm khác nhau dẫn tới hai ngăn khác nhau, nên HashSet không bao giờ so chúng bằng equals để phát hiện trùng. Kết quả: HashSet chứa cả hai như thể chúng khác nhau, vi phạm ý nghĩa của tập hợp. Đây chính là lý do phải ghi đè cả hai theo cùng tập trường.

Bài tập 3: sắp xếp nhiều tiêu chí

Cho lớp SanPham có trường ten, gia, soLuongBan. Viết chương trình sắp một List<SanPham> theo soLuongBan giảm dần, nếu bằng nhau thì theo gia tăng dần, nếu vẫn bằng thì theo ten tăng dần, dùng Comparator ghép bằng thenComparing.

Lời giải chi tiết

Ghép ba tiêu chí bằng chuỗi Comparator: bắt đầu bằng comparingInt trên soLuongBan rồi reversed để thành giảm dần, sau đó thenComparing lần lượt cho gia và ten ở thứ tự tăng dần.

List<SanPham> ds = new ArrayList<>(/* ... */);
ds.sort(
    Comparator.comparingInt((SanPham s) -> s.soLuongBan).reversed()  // most sold first
              .thenComparingDouble(s -> s.gia)                       // then cheaper first
              .thenComparing(s -> s.ten)                             // then by name
);

Ý chính: mỗi thenComparing chỉ được dùng để phân định khi các tiêu chí trước đó coi hai phần tử là bằng nhau, nhờ đó diễn đạt được quy tắc sắp nhiều tầng một cách gọn gàng.

Bài tập 4: vì sao chương trình chậm

Một chương trình gom n mã sinh viên vào List<String>, trước mỗi lần thêm lại gọi ds.contains(ma) để loại trùng. Với n bằng 200000 nó chạy rất lâu. Hãy chỉ ra độ phức tạp thực tế và cách sửa.

Lời giải chi tiết

contains trên List là tìm tuyến tính O(n). Gọi nó n lần cho tổng chi phí O(n²), tức hàng chục tỉ phép so sánh khi n bằng 200000.

Cách sửa là dùng HashSet để loại trùng, vì contains và add của nó trung bình O(1), đưa tổng chi phí về O(n). Nếu vẫn cần giữ thứ tự xuất hiện thì dùng LinkedHashSet.

Set<String> daCo = new LinkedHashSet<>();  // O(1) lookup, keeps insertion order
for (String ma : nguon) {
    daCo.add(ma);                          // duplicates are ignored automatically
}

Điều kiện đi kèm: khoá phải cài đúng equals và hashCode. Ở đây khoá là String nên Java đã lo sẵn.

Câu hỏi tự kiểm

Kiểm tra nhanh: hiệu năng và hợp đồng0/4 đúngchưa trả lời

1. 1Khi mảng bên trong đầy, ArrayList cấp mảng mới lớn hơn theo hệ số nào?
2. 2Hệ số tải (load factor) mặc định của HashMap là bao nhiêu?
3. 3Muốn nhồi đúng n cặp vào HashMap mà không phải băm lại lần nào, nên khởi tạo thế nào?
4. 4Theo hợp đồng, nếu a.equals(b) trả về true thì điều gì bắt buộc đúng?

Tóm tắt

• Chọn cấu trúc theo thao tác chiếm đa số, không theo thói quen.
• ArrayList truy cập chỉ số O(1) nhưng chèn giữa O(n); LinkedList ngược lại và chỉ thật sự thắng khi thao tác ở hai đầu.
• HashMap và HashSet cho O(1) trung bình, với điều kiện hashCode phân tán tốt và khoá bất biến.
• Cấu trúc Tree đổi O(1) lấy O(log n) để có thứ tự; chỉ trả giá đó khi thật cần.
• Báo trước dung lượng khi biết số phần tử, để tránh sao chép và băm lại.
• Đo trước khi kết luận: độ phức tạp không nói gì về hằng số.

Ghi nhớ

Lập trình theo giao tiếp (List, Set, Map), rồi chọn lớp cài đặt theo thao tác chiếm đa số: cần chỉ số thì ArrayList, cần loại trùng và tra nhanh thì HashSet/HashMap, cần luôn được sắp thì thêm tiền tố Tree, cần giữ thứ tự chèn thì thêm tiền tố Linked.