Chọn một cấu trúc chứa dữ liệu cũng giống chọn đúng món nội thất để cất đồ, theo cách bạn sẽ lấy ra. Cần tìm nhanh theo tên thì dùng tủ hồ sơ có nhãn (Map — tra theo khoá). Cần lấy "món thứ ba" thì dùng kệ đánh số (List — theo vị trí). Cần một danh sách hội viên không ai trùng ai thì dùng Set. Cần lấy ra theo thứ tự đến thì dùng hàng đợi. Điều quan trọng là chọn theo thao tác bạn cần làm, không theo thói quen gõ ArrayList cho mọi thứ. Mở đầu chặng Collections — mười bốn bài, và đây là chặng có tác động trực tiếp nhất tới mã bạn viết hằng ngày. Bài này là tấm bản đồ. Không đi sâu vào cái nào, mà trả lời câu hỏi bạn gặp mười lần mỗi ngày: cần một chỗ chứa dữ liệu, chọn cái gì?

Hai nhánh, không phải một

Điều đầu tiên cần nhớ: Map không phải Collection.

Collection là "một đám phần tử". Map là "các cặp khoá – giá trị". Chúng không kế thừa nhau, và đó là lý do Map không có add(), không duyệt trực tiếp bằng for-each được.

Muốn duyệt Map thì đi qua ba khung nhìn của nó: keySet(), values(), entrySet() — cái thứ ba là cái bạn nên dùng nhất, vì nó cho cả khoá lẫn giá trị trong một lượt.

Nhánh Collection chia làm ba:

List — có thứ tự, cho phép trùng lặp, truy cập theo chỉ số.

Set — không trùng lặp, và "trùng" nghĩa là gì thì do equals/hashCode hoặc comparator quyết định — đúng cái bẫy BigDecimal ở bài Comparable.

Queue và Deque — thêm và lấy ra theo quy tắc, thường ở hai đầu.

Ai cài đặt cái gì

Chạy thật để xem, thay vì tin bảng vẽ:

  ArrayList        -> List RandomAccess
  LinkedList       -> List Deque
  ArrayDeque       -> Deque
  HashSet          -> Set
  LinkedHashSet    -> SequencedSet
  TreeSet          -> NavigableSet
  HashMap          -> Map
  LinkedHashMap    -> SequencedMap
  TreeMap          -> NavigableMap

Ba điều đáng chú ý trong danh sách này.

ArrayList cài thêm RandomAccess — một giao diện đánh dấu, không có phương thức nào. Nó nói với các thuật toán rằng truy cập theo chỉ số ở đây là rẻ. Collections.binarySearch đọc dấu này để chọn chiến lược khác nhau cho ArrayList và LinkedList.

LinkedList vừa là List vừa là Deque — nên nó dùng được như ngăn xếp hoặc hàng đợi. Nhưng ArrayDeque gần như luôn nhanh hơn cho việc đó, chuyện của bài về Deque.

LinkedHashSet và LinkedHashMap cài SequencedSet và SequencedMap — hai giao diện mới toanh.

Sequenced Collections: bổ sung của Java 21

Trước Java 21, lấy phần tử cuối của một LinkedHashSet phải duyệt hết cả tập. Không có API nào cho việc đơn giản đó, dù thứ tự rõ ràng là có.

Java 21 thêm ba giao diện — SequencedCollection, SequencedSet, SequencedMap — với các phương thức thống nhất:

seq.getFirst();      seq.getLast();
seq.addFirst(x);     seq.addLast(x);
seq.removeFirst();   seq.removeLast();
seq.reversed();      // khung nhìn đảo ngược, không sao chép

Nhờ đó List, Deque, LinkedHashSet, LinkedHashMap, SortedSet giờ có chung một bộ từ vựng. Nếu bạn từng viết list.get(list.size() - 1) thì giờ có list.getLast().

reversed() là khung nhìn, không sao chép — sửa bản đảo thì bản gốc cũng đổi.

Thứ tự duyệt: ba loại Set cho ba kết quả

var vao = List.of("chuoi", "banh", "an", "dua");

  HashSet       : [dua, banh, an, chuoi]
  LinkedHashSet : [chuoi, banh, an, dua]
  TreeSet       : [an, banh, chuoi, dua]

HashSet — thứ tự không xác định, phụ thuộc mã băm. Chú ý nó không phải ngẫu nhiên: cùng dữ liệu thì cùng thứ tự, nên rất dễ viết một test dựa vào thứ tự đó rồi hỏng khi dữ liệu đổi. Đừng bao giờ phụ thuộc vào thứ tự của HashSet.

LinkedHashSet — theo thứ tự chèn. Trả về đúng cái người dùng đưa vào, hợp cho mọi thứ hiển thị ra giao diện.

TreeSet — theo thứ tự sắp xếp.

Cùng quy luật đó áp dụng cho HashMap, LinkedHashMap, TreeMap.

Cái nào chứa được null

Đây là bảng tôi phải tra lại nhiều lần trước khi thuộc, nên đo hẳn cho chắc:

  HashMap khoá null    -> được
  TreeMap khoá null    -> NullPointerException
  HashSet phần tử null -> được
  ArrayList null       -> được
  List.of null         -> NullPointerException

Quy luật: các bản cài đặt cũ (HashMap, ArrayList, HashSet) cho phép null; các bản có sắp xếp (TreeMap, TreeSet) và các bản bất biến mới (List.of, Map.of, Set.of) thì không.

TreeMap từ chối null vì nó phải so sánh khoá, mà null.compareTo(...) là NPE.

Các API bất biến từ chối null vì đó là lựa chọn thiết kế có chủ ý — nhóm phát triển JDK cho rằng null trong collection gây nhiều lỗi hơn là tiện lợi. Đây cũng là lý do Map.of(...) an toàn hơn khi trả dữ liệu ra ngoài.

"Bất biến" cũng có nhiều mức

  List.of().add        -> UnsupportedOperationException
  Arrays.asList().add  -> UnsupportedOperationException
  Arrays.asList().set  -> được

Ba dòng này làm rõ một chỗ rất hay nhầm:

List.of(...) — bất biến hoàn toàn. Không thêm, không xoá, không sửa.

Arrays.asList(...) — kích thước cố định, nhưng phần tử sửa được. Nó là một khung nhìn gắn với mảng gốc, nên set được, và sửa mảng thì list cũng đổi theo.

Collections.unmodifiableList(ds) — khung nhìn chỉ đọc lên một danh sách sửa được. Người cầm khung nhìn không sửa được, nhưng ai còn giữ ds gốc thì vẫn sửa được, và người kia thấy thay đổi đó.

Với sao chép phòng vệ như bài hôm qua, List.copyOf(...) là lựa chọn đúng — nó sao chép thật và bất biến thật.

Bảng chọn nhanh

Đây là phần đáng in ra dán cạnh màn hình:

Cần gì Dùng
Danh sách thường, truy cập theo chỉ số ArrayList
Danh sách chỉ đọc, cố định List.of(...)
Bỏ trùng lặp, không cần thứ tự HashSet
Bỏ trùng lặp, giữ thứ tự chèn LinkedHashSet
Bỏ trùng lặp, cần sắp xếp TreeSet
Tra cứu theo khoá HashMap
Tra cứu, giữ thứ tự chèn LinkedHashMap
Tra cứu, cần sắp xếp hoặc truy vấn theo khoảng TreeMap
Ngăn xếp hoặc hàng đợi ArrayDeque
Lấy ra theo mức ưu tiên PriorityQueue
Nhiều luồng cùng ghi ConcurrentHashMap

Vài lựa chọn không nên dùng, dù bạn sẽ gặp trong mã cũ:

Vector và Hashtable — đồng bộ hoá trên mọi phương thức, chậm và vẫn không an toàn cho thao tác ghép đôi. Thay bằng ArrayList/HashMap, hoặc ConcurrentHashMap nếu thật sự cần nhiều luồng.

Stack — kế thừa Vector, và tệ hơn: nó đánh chỉ số ngược đời, push thêm vào cuối nhưng get(0) lại là phần tử dưới đáy. Dùng ArrayDeque.

LinkedList — hiếm khi thắng ArrayList, kể cả ở những chỗ lý thuyết bảo nó nhanh hơn. Bài về ArrayList và LinkedList sẽ đo cụ thể.

Khai kiểu ở mức giao diện

Một thói quen nhỏ mà lợi lâu dài:

List<String> ds = new ArrayList<>();          // tốt
ArrayList<String> ds = new ArrayList<>();     // ràng buộc không cần thiết

Khai bằng giao diện thì đổi bản cài đặt sau này chỉ sửa một chỗ. Tương tự với tham số và kiểu trả về: nhận Collection<String> nếu chỉ cần duyệt, nhận List<String> nếu cần thứ tự.

Ngoại lệ: khi bạn cố tình cần đặc tính của một bản cài đặt cụ thể — ví dụ khai ArrayDeque vì mã sau đó dùng push/pop — thì khai kiểu cụ thể lại rõ ràng hơn.

Mẫu số chung

Tấm bản đồ này thoạt nhìn là chuyện riêng của Java, nhưng nó phản chiếu một sự thật đúng ở mọi thư viện chuẩn trưởng thành: tất cả đều hội tụ về đúng vài trừu tượng chứa dữ liệu, phân biệt nhau bằng hợp đồng truy cập — dãy theo chỉ số, tập không trùng, ánh xạ theo khoá, hàng đợi hai đầu — và bằng bảo đảm thứ tự: không có, theo thứ tự chèn, hay theo thứ tự sắp xếp. Bạn chọn theo thao tác cần làm, và viết code dựa vào trừu tượng chứ không vào lớp cụ thể — vì lớp cụ thể thay được, còn hợp đồng mới là thứ code của bạn thật sự dựa vào.

Đổi ngăn xếp thì tên đổi, khung thì y hệt:

  • C++ STL là bản gốc của ý tưởng này: vector, set, map, unordered_map — và cả một trường phái "viết thuật toán theo iterator/concept" để cùng một thuật toán chạy trên mọi container.
  • Python có list, dict, set, tuple, cộng collections.deque và Counter; và dict giờ giữ thứ tự chèn — đúng cái LinkedHashMap cho bạn.
  • Go cố ý giữ tối giản với slice và map dựng sẵn — và đáng chú ý, nó cố tình ngẫu nhiên hoá thứ tự duyệt map để không lập trình viên nào lỡ phụ thuộc vào một thứ tự mà bảng băm không hề hứa. Đó chính là bài học "đừng bao giờ tin thứ tự của HashSet", được ép thẳng vào ngôn ngữ.

Nên câu hỏi đúng khi cần một chỗ chứa dữ liệu không phải "gõ cái nào quen tay" mà là "tôi sẽ lấy ra kiểu gì (theo khoá, theo vị trí, theo thứ tự?) và tôi có cần chặn trùng không" — trả lời hai câu đó là bảng chọn nhanh ở trên tự điền. Muốn tự thấy cái bẫy thứ tự: chạy đoạn ba loại Set ở trên với dữ liệu của bạn, rồi đổi thứ tự các phần tử đầu vào và chạy lại.

LinkedHashSet và TreeSet cho kết quả đoán trước được. HashSet thì đổi — và nếu trong dự án của bạn có test nào đang so sánh chuỗi kết quả duyệt một HashSet, nó là một test sẽ hỏng vào một ngày không báo trước.

Ngày mai: ArrayList và LinkedList — chi phí thật của thêm, xoá, truy cập, đo bằng JMH để thấy vì sao LinkedList hiếm khi thắng.