Sách giáo khoa cấu trúc dữ liệu nói: mảng động truy cập nhanh nhưng chèn chậm; danh sách liên kết chèn nhanh nhưng truy cập chậm. Chọn theo nhu cầu.
Lời khuyên đó đúng về lý thuyết và sai về thực tế — ít nhất là với Java trên phần cứng hiện đại.
Tôi đo bốn thao tác trên 100.000 phần tử bằng JMH.
Truy cập ngẫu nhiên: chênh nhau năm chữ số
1000 lần get(i) ở các vị trí rải đều:
DanhSach.docNgauNhien_ArrayList 100000 avgt 0.813 ± 0.490 us/op
DanhSach.docNgauNhien_LinkedList 100000 avgt 40267.512 ± 6729.062 us/op
Nhanh hơn khoảng 49.500 lần.
ArrayList tính địa chỉ bằng một phép nhân — get(i) là O(1). LinkedList phải đi từng nút một từ đầu (hoặc từ cuối, nó chọn đầu gần hơn) — O(n) cho mỗi lần gọi, và ta gọi 1000 lần.
Con số này lớn tới mức đáng ngờ, nhưng nó có lý: mỗi get trung bình đi qua 25.000 nút, nhân 1000 lần là 25 triệu lần nhảy con trỏ. Và mỗi lần nhảy là một lần truy cập bộ nhớ ngẫu nhiên — chuyện mà CPU hiện đại ghét nhất.
Hệ quả thực dụng: đừng bao giờ dùng vòng lặp chỉ số trên LinkedList.
for (int i = 0; i < ds.size(); i++) ds.get(i); // O(n²) trên LinkedList
Đoạn này chạy êm với 100 phần tử và treo máy với 100.000.
Duyệt tuần tự: vẫn thua ba lần
DanhSach.duyet_ArrayList 100000 avgt 59.003 ± 27.917 us/op
DanhSach.duyet_LinkedList 100000 avgt 168.452 ± 14.268 us/op
Đây mới là kết quả đáng nói. Duyệt bằng for-each thì cả hai đều O(n) — về lý thuyết phải ngang nhau. Thực tế LinkedList chậm hơn gần ba lần.
Nguyên nhân là cục bộ bộ nhớ. ArrayList giữ một mảng liền khối; đọc phần tử thứ i thì CPU đã nạp sẵn cả một dòng cache chứa i+1, i+2… LinkedList rải các nút khắp heap, mỗi nút là một lần nhảy tới địa chỉ ngẫu nhiên, và cache gần như luôn trượt.
Thêm nữa, mỗi nút LinkedList mang hai con trỏ và một tham chiếu — tốn khoảng 40 byte cho một phần tử, so với 4–8 byte trong ArrayList.
Đây là lý do phân tích big-O không đủ để dự đoán hiệu năng. Hai thuật toán cùng O(n) có thể chênh nhau nhiều lần vì cách chúng dùng bộ nhớ.
Thêm vào cuối: ArrayList vẫn thắng
DanhSach.themCuoi_ArrayList avgt 202.208 ± 12.809 us/op
DanhSach.themCuoi_LinkedList avgt 348.928 ± 78.296 us/op
Kết quả này gây bất ngờ cho nhiều người, vì ArrayList phải cấp phát lại mảng khi đầy.
Nhưng nó chỉ tăng gấp rưỡi mỗi lần đầy, nên với 100.000 phần tử chỉ có khoảng 25 lần cấp phát lại. Và mỗi lần là một System.arraycopy — thao tác chép khối liền, cực nhanh ở mức phần cứng.
Còn LinkedList phải tạo một đối tượng nút mới cho mỗi phần tử — 100.000 lần cấp phát, 100.000 đối tượng cho GC dọn sau này.
Nếu biết trước kích thước thì khai sẵn để bỏ hẳn phần cấp phát lại:
new ArrayList<>(100_000);
Thêm vào đầu: chỗ LinkedList thắng
DanhSach.themDau_ArrayList avgt 10496.586 ± 215.996 us/op
DanhSach.themDau_LinkedList avgt 65.505 ± 9.098 us/op
LinkedList nhanh hơn 160 lần.
Đây là chỗ lý thuyết đúng: add(0, x) trên ArrayList phải dịch toàn bộ phần tử sang phải — O(n) cho mỗi lần thêm, O(n²) cho cả vòng lặp. LinkedList chỉ nối lại hai con trỏ.
Vậy là có một trường hợp LinkedList thắng thật. Nhưng khoan mừng.
Nhưng ArrayDeque còn thắng hơn
Cùng bài toán thêm 20.000 phần tử vào đầu, ba cách:
ThemDau.arrayDeque avgt 44.710 ± 1.943 us/op
ThemDau.arrayListRoiDao avgt 59.541 ± 4.181 us/op
ThemDau.linkedList avgt 73.212 ± 39.116 us/op
ArrayDeque — mảng vòng — nhanh hơn LinkedList khoảng 1,6 lần, dù cả hai đều O(1). Lại là chuyện cục bộ bộ nhớ.
Và cách thứ ba đáng chú ý: cứ thêm vào cuối rồi đảo ngược một lần cũng nhanh hơn LinkedList. Đây là mẹo đáng nhớ khi bạn xây một danh sách theo thứ tự ngược.
Chú ý sai số của LinkedList rất lớn (±39 trên 73) — dấu hiệu của việc GC phải làm việc nhiều vì hàng chục nghìn đối tượng nút.
Vậy khi nào dùng LinkedList
Câu trả lời thành thật: gần như không bao giờ.
Trường hợp duy nhất tôi thấy hợp lý là khi bạn cần một List mà thêm/xoá ở cả hai đầu và cũng cần List API (chỉ số, subList). Nếu chỉ cần hai đầu thì ArrayDeque tốt hơn.
Còn "xoá ở giữa nhanh" — lý do hay được viện dẫn — là một hiểu lầm. LinkedList.remove(i) phải đi tới vị trí i trước đã, nên vẫn O(n). Nó chỉ nhanh khi bạn đã có sẵn ListIterator đứng đúng chỗ:
var it = ds.listIterator();
while (it.hasNext()) {
if (canXoa(it.next())) it.remove(); // đây mới là O(1) thật
}
Nhưng cùng đoạn đó trên ArrayList cũng chạy tốt, và với dữ liệu vừa phải thì vẫn nhanh hơn nhờ cache. Còn cách gọn nhất vẫn là ds.removeIf(this::canXoa).
ArrayList lớn lên thế nào
Vài chi tiết đáng biết:
Mảng bên trong bắt đầu rỗng, và lần add đầu tiên cấp phát 10 phần tử.
Khi đầy, mảng mới có kích thước gấp rưỡi, rồi System.arraycopy chép sang.
remove không thu nhỏ mảng. Một ArrayList từng chứa một triệu phần tử rồi bị xoá hết vẫn giữ mảng một triệu ô. Gọi trimToSize() nếu cần trả bộ nhớ lại.
clear() cũng vậy — nó gán null cho từng ô nhưng giữ nguyên mảng.
Với dữ liệu lớn và biết trước kích thước, khai sẵn dung lượng là cách tối ưu rẻ nhất mà nhiều người bỏ qua.
Vài chỗ hay sai khác
list.remove(1) xoá theo chỉ số, không phải theo giá trị — cái bẫy nạp chồng ở bài phương thức.
subList là khung nhìn, không phải bản sao. Sửa nó thì danh sách gốc đổi theo, và sửa danh sách gốc thì khung nhìn ném ConcurrentModificationException.
Xoá phần tử trong lúc for-each cũng ném ConcurrentModificationException — chuyện của bài về Iterator.
Arrays.asList cho danh sách kích thước cố định, đã nói ở bài bản đồ.
Rút lại thành một câu
Dùng ArrayList cho mọi danh sách. Cần thêm/xoá ở hai đầu thì ArrayDeque. LinkedList để dành cho bài giảng về danh sách liên kết.
Và bài học rộng hơn, đáng nhớ hơn cả các con số cụ thể: big-O cho biết xu hướng khi n lớn, không cho biết cái nào nhanh hơn ở kích thước thật của bạn. Hai cấu trúc cùng O(n) chênh nhau ba lần chỉ vì cách sắp xếp trong bộ nhớ. Muốn biết cái nào nhanh hơn thì phải đo.
Thử ba mươi giây
Viết vòng lặp for (int i = 0; i < ds.size(); i++) ds.get(i); trên một LinkedList 100.000 phần tử, bấm giờ.
Rồi đổi sang for-each và bấm lại. Cùng một cấu trúc dữ liệu, cùng một công việc, chênh nhau tới mức bạn sẽ nhớ mãi.
Ngày mai ta mở HashMap ra xem bên trong: bảng băm, va chạm, ngưỡng chuyển sang cây đỏ đen, và chuyện gì xảy ra trong một lần rehash.
