[Java Masterclass] Giải ngố Collections Framework: List, Set, Map và những cú lừa "Under The Hood"

Chào anh em, nếu anh em đi phỏng vấn vị trí Backend Java (hoặc bất kỳ ngôn ngữ OOP nào tương tự), câu hỏi: "Sự khác nhau giữa ArrayList và LinkedList?" hay "HashMap hoạt động như thế nào?" là những câu hỏi kinh điển đến mức... nhàm chán.

Nhưng đằng sau những câu hỏi nhàm chán đó là cách đánh giá xem bạn có thực sự hiểu về Memory Management (Quản lý bộ nhớ) và Time Complexity (Độ phức tạp thuật toán) hay không. Cùng bóc tách từng gia tộc trong thế giới Collections nhé.

1. Bức tranh toàn cảnh

Java Collections Framework được chia làm 2 nhánh chính:

1. Interface Collection: Gốc gác của những cấu trúc lưu trữ 1 tập hợp các phần tử đơn lẻ. Dưới nó là List, Set, Queue.
2. Interface Map: Kẻ ngoại đạo. Nó không kế thừa Collection vì nó lưu trữ theo cặp Key-Value (Giống Object trong JS hay Dictionary trong C#).

2. Gia tộc List: Những kẻ thích xếp hàng ngang

Đặc điểm nhận dạng của List là: Có thứ tự (Ordered), cho phép trùng lặp (Duplicate) và truy cập qua Index (chỉ mục). Hai gương mặt cộm cán nhất là ArrayList và LinkedList.

2.1. ArrayList - Con cưng của mọi nhà

• Bản chất: Nó là một mảng (Array) có khả năng tự co giãn (Dynamic Array).
• Sự thật ngã ngửa: Khi bạn khởi tạo new ArrayList(), Java tạo ra một mảng trống. Khi add phần tử đầu tiên, nó phình ra kích thước mặc định là 10.
• Lúc hết chỗ thì sao? Nếu bạn add phần tử thứ 11, mảng hiện tại đã đầy. ArrayList sẽ làm một việc cực kỳ tốn kém: Nó tạo ra một mảng mới bự gấp rưỡi (1.5 lần) mảng cũ (kích thước 15), rồi copy toàn bộ data từ mảng cũ sang mảng mới.

Kinh nghiệm xương máu: Khúc copy mảng này (độ phức tạp O(n)) chính là thủ phạm gây giật lag (GC Pause) nếu bạn nạp data quá lớn. Nếu biết trước cần chứa khoảng 100,000 phần tử, hãy khởi tạo ngay từ đầu: List<String> list = new ArrayList<>(100000); để tránh việc nó phải resize và copy chục lần.

2.2. LinkedList - Cú lừa thế kỷ

• Bản chất: Nó là Danh sách liên kết kép (Doubly Linked List). Các phần tử nằm rải rác trên RAM, nối với nhau bằng các "sợi dây" (con trỏ next và prev).
• Sách giáo khoa bảo: LinkedList thêm/xóa (add/remove) ở giữa danh sách nhanh hơn ArrayList vì O(1), không phải dịch chuyển các phần tử.
• Thực tế vả vào mặt: Để tìm được vị trí ở giữa mà thêm/xóa, nó phải duyệt từ đầu (hoặc cuối) tới vị trí đó mất O(n). Tệ hơn nữa, vì các phần tử nằm rải rác trên RAM, nó làm hỏng hoàn toàn cơ chế CPU Caching (không có tính Cache Locality như mảng). 👉 Kết luận: 99% trường hợp thực tế, ArrayList đập chết LinkedList về mặt hiệu năng. Hãy quên LinkedList đi trừ khi bạn làm việc với Queue/Deque.

3. Gia tộc Set: Hội những người cuồng sự độc nhất

Đặc điểm của Set là: Không cho phép trùng lặp (No Duplicates).

3.1. HashSet - Kẻ mượn hoa hiến Phật

Bạn có bao giờ thắc mắc HashSet làm sao để biết một phần tử đã tồn tại cực nhanh để chặn trùng lặp không?

Sự thật: Khi bạn soi source code của Java, HashSet thực chất chỉ là một lớp bọc (wrapper) của HashMap.

// Trích xuất source code Java (java.util.HashSet)
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

public boolean add(E e) {
    // Nó nhét data của bạn vào làm KEY của HashMap, 
    // còn VALUE là một object rỗng vô thưởng vô phạt (PRESENT)
    return map.put(e, PRESENT)==null; 
}

Vì nó dựa trên HashMap, thao tác thêm, xóa, tìm kiếm của nó chớp nhoáng với tốc độ O(1). Nhược điểm? Dữ liệu của bạn đưa vào sẽ bị sắp xếp lộn xộn, không theo thứ tự bạn add vào đâu.

3.2. TreeSet - Chậm mà chắc

Nếu bạn muốn một tập hợp không trùng lặp, nhưng data phải được sắp xếp tăng dần/giảm dần, hãy dùng TreeSet.

Nó được build trên cấu trúc cây Đỏ-Đen (Red-Black Tree). Tốc độ tìm kiếm/thêm/xóa sẽ chậm hơn HashSet, rơi vào khoảng O(log n).

4. Cuốn từ điển vạn năng: Map

Lưu trữ theo cặp Key -> Value. Đây là cấu trúc dữ liệu được xài nhiều nhất trong Backend để làm bộ nhớ đệm (Cache), đếm tần số, mapping data,...

4.1. HashMap - Ma thuật của hàm Băm (Hash Function)

Cách nó hoạt động:

1. Bạn đưa vào Key là "viblo". HashMap chạy hàm băm hash("viblo") ra một con số nguyên (VD: 12345).
2. Nó ép con số này về một index của mảng nội bộ (VD: index = 5).
3. Nó ném Value của bạn vào ngăn kéo số 5. Khi cần lấy ra, nó tính toán lại index cực nhanh và bốc data ra. Tốc độ là O(1).

Nhưng... chuyện gì xảy ra nếu "viblo" và "hello" cùng băm ra index số 5? (Hash Collision) Trước Java 8, tại ngăn kéo số 5, nó sẽ nối các Value thành một cái LinkedList. Nếu có 1000 Key cùng đụng độ tại số 5, tốc độ truy xuất từ O(1) biến thành O(n) (phải lội qua 1000 cái node). Hackers từng dùng trò này để tạo ra hàng vạn request có Key đụng độ nhau, ép CPU server xỉu ngang (Hash Collision DoS attack).

Từ Java 8 trở đi: Đội ngũ Java đã fix cực kì thông minh. Khi ngăn kéo số 5 có từ 8 phần tử trở lên, nó tự động biến cái LinkedList lề mề kia thành một Cây Đỏ Đen (Red-Black Tree), kéo tốc độ tệ nhất từ O(n) xuống O(log n). Server thoát chết!

4.2. ConcurrentHashMap - Vua của Multithreading

HashMap thông thường không Thread-safe (an toàn trong môi trường đa luồng). Nếu 2 worker cùng put() data vào một HashMap cùng lúc, cấu trúc bên trong nó sẽ bị nát bét (thậm chí dính Infinite Loop trong các phiên bản cũ).

Người ta thường nghĩ đến HashTable hoặc Collections.synchronizedMap(), nhưng bọn này quá ngu ngốc: Nó khóa (Lock) toàn bộ cái Map lại. Luồng A đang ghi, luồng B, C, D phải đứng chờ. Cực kì nghẽn cổ chai!

ConcurrentHashMap xịn hơn nhiều: Nó dùng cơ chế Lock Stripping (Khóa phân đoạn). Mảng băm chia làm 16 khúc. Luồng A ghi vào khúc số 1 thì nó chỉ khóa khúc 1. Luồng B ghi vào khúc số 5 thì vẫn cứ ghi thoải mái không ai chờ ai. Tuyệt đỉnh tối ưu!

5. Bỏ túi bí kíp (Cheat sheet) cho anh em

• Cần truy xuất nhanh, thay đổi kích thước ít: ArrayList (90% case).
• Chỉ thêm/xóa ở 2 đầu liên tục: ArrayDeque (Ngon hơn LinkedList).
• Chỉ cần kiểm tra tồn tại, không cho trùng: HashSet.
• Map bình thường: HashMap.
• Map đa luồng (Multi-threading): ConcurrentHashMap.
• Cần sort tự động: TreeSet / TreeMap.

Tổng kết & Next step

Hiểu được cấu trúc dữ liệu không giúp bạn code nhanh hơn, nhưng nó giúp ứng dụng của bạn không bị "đột tử" lúc scale lên hàng chục triệu bản ghi.

Nói đến ConcurrentHashMap, chúng ta đã chạm một chân vào thế giới của Đa luồng (Multithreading). Một thế giới cực kì quyến rũ nhưng cũng đầy rẫy những bug "hôm nay chạy, ngày mai lỗi không biết đường mò".

Anh em có tò mò về cách các luồng (Thread) trong Java tranh giành nhau CPU như thế nào, và keyword volatile thần thánh thực chất làm cái trò gì dưới tầng Hardware không? Để lại comment nhé, mình sẽ lên tiếp: 👉 Bài sau: Giải ngố Java Multithreading - Từ Memory Visibility đến tuyệt kĩ ThreadPool.

Nếu bài viết gãi đúng chỗ ngứa của anh em, tiếc gì 1 Upvote và Bookmark đúng không nào? Hẹn anh em ở bài sau!