99 Ngày Java — Ngày 31: Collections tổng quan

Giai đoạn 4 bắt đầu! Trong mini project Ngày 30, ta đã dùng HashMap cho repository và ArrayList cho phiếu mượn — theo trực giác. Mười ngày tới biến trực giác đó thành hiểu biết có hệ thống về Collections Framework — bộ đồ nghề quan trọng nhất của java.util. Bài mở màn hôm nay vẽ bức tranh toàn cảnh: cây phân cấp Collection/Map, lời hứa riêng của từng loài List–Set–Queue–Map, cây quyết định chọn cấu trúc, và bảng Big-O — thứ phân biệt code chạy 1 giây với code chạy 1 giờ.

Bức tranh toàn cảnh — hai cây họ hàng

// Bản đồ java.util — hai cây họ hàng, KHÔNG chung gốc:
//
//                    Iterable            (duyệt được bằng for-each)
//                       │
//                   Collection           (nhóm phần tử)
//          ┌────────────┼────────────┐
//        List          Set         Queue / Deque
//     "danh sách"   "duy nhất"     "hàng đợi"
//          │            │               │
//     ArrayList     HashSet         ArrayDeque
//     LinkedList    LinkedHashSet   PriorityQueue
//                   TreeSet
//
//                      Map                (cặp key → value — cây RIÊNG,
//          ┌────────────┼──────────┐       không phải Collection!)
//       HashMap    LinkedHashMap  TreeMap
//
// Nhớ theo cặp "lời hứa → cái giá":
List<String>  ds  = new ArrayList<>();   // giữ THỨ TỰ chèn, cho phép trùng
Set<String>   tap = new HashSet<>();     // KHÔNG trùng — không hứa thứ tự
Queue<String> hd  = new ArrayDeque<>();  // vào trước ra trước (FIFO)
Map<String, Integer> bd = new HashMap<>(); // tra theo KEY — key không trùng

// Cùng dữ liệu, khác lời hứa:
List.of("a", "b", "a").size();           // 3 — List chấp nhận trùng
Set.of("a", "b").contains("a");          // true — Set sinh ra để hỏi câu này
new HashSet<>(List.of("a", "b", "a")).size();  // 2 — đổ List vào Set là khử trùng

• Đỉnh cây là Iterable (duyệt được bằng for-each) → Collection (nhóm phần tử) → ba nhánh List/Set/Queue. Map là cây riêng — lưu cặp key→value chứ không phải nhóm phần tử, nên không extends Collection; câu hỏi phỏng vấn nhập môn kinh điển.

• Cách nhớ bền nhất là theo lời hứa: List hứa thứ tự (và chấp nhận trùng), Set hứa duy nhất (và mặc định không hứa thứ tự), Queue hứa trước–sau, Map hứa tra theo key. Chọn sai loài nghĩa là tự viết lại lời hứa bằng tay — như đoạn khử trùng lặp bằng List.contains ở phần Big-O bên dưới.

• Mỗi interface có 2–3 implementation quen mặt: họ Hash* nhanh nhất nhưng không thứ tự, họ Linked* giữ thứ tự chèn, họ Tree* luôn sắp xếp — quy luật đặt tên lặp lại ở cả Set lẫn Map, học một lần dùng hai nơi.

Cây quyết định — chọn cấu trúc trong 4 câu hỏi

// Cây quyết định 4 câu hỏi — phủ 90% lựa chọn hằng ngày

// 1. Tra cứu theo KEY?                    → Map
Map<String, TaiKhoan> theoUsername = new HashMap<>();
theoUsername.get("mars");                  // O(1) — không phải duyệt tìm

// 2. Cần loại TRÙNG LẶP?                  → Set
Set<String> daXem = new HashSet<>();
if (!daXem.add(videoId)) { /* đã xem rồi — add trả false khi trùng */ }

// 3. Xử lý theo LƯỢT (trước-sau)?         → Queue / Deque
Deque<String> hoanTac = new ArrayDeque<>();
hoanTac.push(hanhDong);                    // stack undo — LIFO
hoanTac.pop();

// 4. Còn lại — danh sách có thứ tự?       → List (mặc định: ArrayList)
List<DonHang> donTrongNgay = new ArrayList<>();

// Câu hỏi phụ: cần SẮP XẾP theo khóa tự nhiên mọi lúc?
TreeMap<LocalDate, BigDecimal> doanhThu = new TreeMap<>();
doanhThu.firstKey();                       // ngày sớm nhất — Tree* luôn có thứ tự
// cần giữ THỨ TỰ CHÈN cho Set/Map? → LinkedHashSet / LinkedHashMap

// Quy tắc vàng: khai báo bằng INTERFACE, khởi tạo bằng implementation
List<String> xs = new ArrayList<>();       // ✅ đổi sang LinkedList: sửa 1 chỗ
ArrayList<String> ys = new ArrayList<>();  // ❌ khóa cứng — tham số method cũng lộ chi tiết
// (đúng bài Ngày 30: service phụ thuộc interface BookRepository, không phụ thuộc InMemory)

• Thứ tự hỏi có chủ đích: tra theo key? → Map; cần khử trùng? → Set (mẹo: add trả false khi trùng — vừa thêm vừa kiểm tra một phát); xử lý theo lượt? → Queue/Deque; còn lại → List với mặc định ArrayList.

• Hai câu hỏi phụ tinh chỉnh: cần sắp xếp thường trực theo khóa → TreeMap/TreeSet (trả giá O(log n)); cần Set/Map giữ thứ tự chèn (in ra ổn định, làm cache) → LinkedHashSet/LinkedHashMap.

• Quy tắc vàng khai báo bằng interface chính là bài Dependency Inversion của Ngày 30 thu nhỏ: đổi implementation là sửa đúng một chữ sau new, và chữ ký method nhận List dùng được với mọi loại danh sách.

Big-O tổng quan — giá niêm yết của từng thao tác

// Big-O — "giá niêm yết" của từng thao tác (n = số phần tử)
//
//                 get(i)   add cuối   add giữa   contains   remove
// ArrayList        O(1)     O(1)*      O(n)       O(n)      O(n)
// LinkedList       O(n)     O(1)       O(n)**     O(n)      O(n)
// HashSet           —        —          —         O(1)      O(1)
// TreeSet           —        —          —       O(log n)  O(log n)
// HashMap        get: O(1)  put: O(1)             —       O(1)
// TreeMap        get: O(log n)  put: O(log n)     —       O(log n)
//
//  *  amortized — thi thoảng phải nhân đôi mảng, tính trung bình vẫn O(1)
//  ** tìm đến vị trí đã O(n) — "chèn giữa nhanh" là hiểu lầm phổ biến nhất
//
// Big-O không phải lý thuyết suông — nó là bug hiệu năng ngoài đời:
List<String> daCo = new ArrayList<>();     // 100.000 phần tử
for (String email : danhSachMoi) {
    if (!daCo.contains(email)) { ... }     // O(n) MỖI lần → tổng O(n²): ~10 TỶ phép so
}
Set<String> daCoSet = new HashSet<>(daCo);
danhSachMoi.stream().filter(e -> !daCoSet.contains(e));  // O(1) mỗi lần — nhanh gấp vạn lần

// Lời hứa O(1) của HashSet/HashMap đứng trên vai equals + hashCode (Ngày 24)
// — cài sai hashCode là O(1) sụp về O(n) không báo trước

• Đọc bảng theo cột thao tác bạn làm nhiều nhất: truy cập theo chỉ số → ArrayList O(1); hỏi "có chứa không" → HashSet O(1) thay vì O(n) của List.contains — khác biệt giữa mili giây và phút khi n lên trăm nghìn.

• Ví dụ O(n²) trong code là bug hiệu năng phổ biến nhất sự nghiệp: vòng lặp ngoài O(n) nhân contains O(n) bên trong — thay một dòng new HashSet<>(...) là 10 tỷ phép so sánh còn 100 nghìn.

• Nhớ hai dấu sao: add cuối của ArrayList là amortized O(1) (thi thoảng nhân đôi mảng — Ngày 32 mổ xẻ), và "LinkedList chèn giữa nhanh" là hiểu lầm — tìm đến vị trí đã tốn O(n) rồi. Và lời hứa O(1) của họ Hash đứng trên equals/hashCode cài đúng (Ngày 24).

Đồ nghề đi kèm — of, copyOf, Collections và các bẫy

// Đồ nghề đi kèm — dùng hằng ngày

// Khởi tạo nhanh, BẤT BIẾN (Ngày 29): of / copyOf
List<String> thu = List.of("T2", "T3", "T4");
Map<String, Integer> diem = Map.of("toan", 9, "van", 8);
List<String> anToan = List.copyOf(nguonBenNgoai);      // defensive copy khi vào

// Lớp tiện ích Collections:
Collections.sort(ds);                       // sắp xếp tại chỗ (List mutable)
Collections.max(ds);  Collections.min(ds);
Collections.shuffle(ds);                    // xáo trộn — demo, chọn ngẫu nhiên
Collections.frequency(ds, "a");             // đếm số lần xuất hiện
Collections.emptyList();                    // trả về thay cho null (Ngày 30!)

// Chuyển đổi qua lại — bộ ba hay dùng:
String[] mang = ds.toArray(new String[0]);  // List → mảng
List<String> tuMang = List.of(mang);        //  mảng → List bất biến
List<String> suaDuoc = new ArrayList<>(tap); // Set → List (để sort chẳng hạn)

// Bẫy kinh điển: Arrays.asList — "nửa nạc nửa mỡ"
List<Integer> nua = Arrays.asList(1, 2, 3);
nua.set(0, 99);                             // ✅ sửa phần tử được
nua.add(4);                                 // 💥 UnsupportedOperationException
// → List.of (bất biến hẳn) hoặc new ArrayList<>(...) (mutable hẳn) — đừng lửng lơ

// for-each đến từ Iterable — mọi Collection đều duyệt được:
for (var entry : diem.entrySet())           // Map duyệt qua entrySet
    System.out.println(entry.getKey() + " = " + entry.getValue());

• Họ of/copyOf (Ngày 29) là lựa chọn mặc định cho dữ liệu cố định và defensive copy; Collections góp sort/max/shuffle/frequency và đặc biệt emptyList — trả rỗng thay cho null để người gọi khỏi phải if-null.

• Arrays.asList là bẫy "nửa nạc nửa mỡ": view cỡ cố định trên mảng — set được nhưng add là nổ UnsupportedOperationException. Quy tắc: cần bất biến → List.of, cần sửa → new ArrayList<>(...), đừng đứng giữa.

• Chuyển đổi qua lại tự do giữa các loài qua constructor nhận Collection: new ArrayList<>(set) để sort kết quả Set, new HashSet<>(list) để khử trùng — thiết kế "mọi loài nói chuyện được với nhau" là điểm ăn tiền nhất của framework.

Bài tập nhỏ

• Với mỗi tình huống, chọn cấu trúc và giải thích bằng lời hứa: giỏ hàng, danh bạ tra theo SĐT, tập từ đã học (không trùng), lịch sử undo, bảng xếp hạng cập nhật liên tục.

• Đo thật O(n²): tạo List 100.000 email, khử trùng bằng contains rồi bằng HashSet — in thời gian hai cách bằng System.nanoTime().

• Chứng minh Map không phải Collection: thử gán Collection<?> c = new HashMap<>() và đọc lỗi compile; rồi duyệt Map đúng cách qua entrySet.

• Tái hiện bẫy Arrays.asList: gọi set rồi add — sửa bằng cả hai hướng (bất biến hẳn / mutable hẳn).

• Lấy mini project Ngày 30: thay List<Loan> trong Member bằng cấu trúc trả lời nhanh câu "đã mượn cuốn ISBN này chưa?" — cần đổi gì ở equals/hashCode?

Kết luận

Bốn ý mang về: Collection và Map là hai cây riêng — List/Set/Queue nhóm phần tử, Map tra theo key; chọn cấu trúc bằng lời hứa qua 4 câu hỏi, họ Hash–Linked–Tree tinh chỉnh thứ tự; bảng Big-O là la bàn hiệu năng — cảnh giác contains trên List và tin vào O(1) của Hash khi hashCode chuẩn; khai báo bằng interface và né bẫy Arrays.asList. Ngày 32 ta mổ xẻ loài dùng nhiều nhất: ArrayList vs LinkedList — mảng động lớn lên thế nào, vì sao LinkedList hiếm khi thắng, và cách duyệt–xóa an toàn. Hẹn gặp lại!