Collections framework — List, Set, Map và cách chọn implementation

Java có một khung cấu trúc dữ liệu phong phú — Collections Framework. Mỗi interface (List, Set, Map) có 2–4 implementation khác nhau, tối ưu cho use case khác nhau. Chọn đúng implementation quyết định performance — ArrayList vs LinkedList cho cùng logic có thể chênh 10x tốc độ.

Bài này vẽ bản đồ framework, phân biệt các interface, so sánh implementation cụ thể qua bảng Big-O, và đưa rule chọn theo use case thực tế.

1. Cây interface — bức tranh tổng

flowchart TD
    Iterable --> Collection
    Collection --> List
    Collection --> Set
    Collection --> Queue
    Set --> SortedSet
    SortedSet --> NavigableSet
    Queue --> Deque
    Map[Map - khong extends Collection]
    Map --> SortedMap
    SortedMap --> NavigableMap

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

Điểm chính:

• Iterable — gốc, duy nhất có iterator(). Cho phép for-each.
• Collection — extends Iterable, thêm add, remove, size, contains.
• List — có thứ tự + index, cho phép trùng.
• Set — không trùng, thường không có thứ tự.
• Queue — FIFO. Deque — double-ended (stack + queue).
• Map — không extends Collection! Key-value.

2. List — thứ tự và index

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.get(1);         // "b"
list.indexOf("c");   // 2

2.1 ArrayList vs LinkedList

Rule thực tế: dùng ArrayList 99% trường hợp. LinkedList chỉ tốt khi:

• Add/remove ở 2 đầu liên tục — dùng ArrayDeque còn tốt hơn.
• Không bao giờ cần get(i) ngẫu nhiên.

Josh Bloch (thiết kế Collections) nói thẳng: "I don't think anyone has ever used LinkedList correctly in 20+ years of Java".

2.2 ArrayList bên dưới

public class ArrayList<E> {
    private Object[] elementData;   // mang noi bo
    private int size;

    public void add(E e) {
        if (size == elementData.length) {
            grow();   // resize voi factor 1.5x
        }
        elementData[size++] = e;
    }
}

• add amortized O(1) — thỉnh thoảng resize tốn O(n), trung bình O(1).
• ensureCapacity(n) nếu biết trước size — tránh resize nhiều lần.

3. Set — không trùng

Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("a");    // khong add, da ton tai
set.size();      // 2
set.contains("a");   // true

3.1 HashSet vs LinkedHashSet vs TreeSet

Rule:

• HashSet — mặc định, nhanh nhất, không cần order.
• LinkedHashSet — cần giữ thứ tự insert (vd hiển thị cho user).
• TreeSet — cần sorted, hoặc query range (subSet, headSet, tailSet).

3.2 HashSet yêu cầu equals + hashCode đúng

class Book {
    String title;
    // khong override equals, hashCode
}

Set<Book> set = new HashSet<>();
set.add(new Book("Java"));
set.contains(new Book("Java"));   // false!

Module 5 bài 5 đã nói — Set/Map dựa vào equals/hashCode của element. Nếu không override, mặc định so địa chỉ → 2 object cùng nội dung vẫn khác nhau.

4. Map — key-value

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
ages.put("Bob", 25);
ages.get("Alice");        // 30
ages.getOrDefault("Eve", 0);   // 0
ages.containsKey("Bob");  // true

4.1 HashMap vs LinkedHashMap vs TreeMap

Song song với Set:

LinkedHashMap(accessOrder=true) làm LRU cache đơn giản:

Map<String, Data> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Data> eldest) {
        return size() > 100;   // giu toi da 100 entry
    }
};

4.2 HashMap bên dưới (Java 8+)

• Bảng Node<K,V>[] table — array of bucket.
• Hash key → chỉ số bucket.
• Va chạm: linked list trong bucket. Java 8+ treeify thành red-black tree nếu bucket > 8 entry → lookup worst-case O(log n) thay vì O(n).

Load factor mặc định 0.75 — khi size / capacity > 0.75, table resize double + rehash toàn bộ. Nếu biết trước size, init capacity đủ:

Map<String, Integer> m = new HashMap<>(1024);   // tranh resize nhieu lan

5. Queue và Deque

5.1 Queue — FIFO

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);    // add tail
queue.offer(2);
queue.poll();       // remove head — tra 1
queue.peek();       // xem head — 2, khong remove

5.2 Deque — 2 đầu

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.pollFirst();   // 1
deque.pollLast();    // 2

// Dung lam stack:
deque.push(1);
deque.push(2);
deque.pop();   // 2

ArrayDeque nhanh hơn LinkedList và Stack cổ điển cho mọi stack/queue use case. Rule: cần stack/queue → ArrayDeque.

5.3 PriorityQueue — heap

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
pq.poll();   // 1 — min heap mac dinh

Truy xuất min/max O(1), add/remove O(log n). Dùng cho top-K, scheduling, Dijkstra.

6. Immutable collection (Java 9+)

List<Integer> list = List.of(1, 2, 3);
Set<String> set = Set.of("a", "b", "c");
Map<String, Integer> map = Map.of("a", 1, "b", 2);

• Immutable — add/remove ném UnsupportedOperationException.
• Không cho phép null.
• Thread-safe (không đổi được).
• Thường tiết kiệm memory hơn ArrayList tương ứng.

Dùng cho constants, config, test data. Khác Collections.unmodifiableList(mutable) — cái sau là view, mutable list gốc vẫn thay đổi được và view phản ánh.

6.1 List.copyOf, Set.copyOf, Map.copyOf — snapshot

List<Integer> mutable = new ArrayList<>(List.of(1, 2, 3));
List<Integer> snapshot = List.copyOf(mutable);

mutable.add(4);
// snapshot van la [1, 2, 3]

Pattern defensive copy — bảo vệ internal state khỏi mutation từ caller.

7. Bảng chọn — theo use case

8. Pitfall tổng hợp

❌ Nhầm 1: Dùng LinkedList vì "đọc trên internet nói insert nhanh". ✅ Hầu như luôn ArrayList. Nếu cần queue/stack → ArrayDeque.

❌ Nhầm 2: Không override equals/hashCode cho class dùng làm key HashMap / element HashSet. ✅ Module 5 bài 5. Luôn override cả 2 với cùng bộ field.

❌ Nhầm 3: Modify collection đang iterate → ConcurrentModificationException.

for (String s : list) { if (bad(s)) list.remove(s); }   // CME

✅ list.removeIf(...) hoặc Iterator.remove().

❌ Nhầm 4: List.of(...) rồi list.add(...).

List<Integer> list = List.of(1, 2, 3);
list.add(4);   // UnsupportedOperationException

✅ new ArrayList<>(List.of(1, 2, 3)) nếu cần mutable.

❌ Nhầm 5: new HashMap() với size lớn biết trước mà không init capacity.

Map<K, V> m = new HashMap<>();
for (int i = 0; i < 1_000_000; i++) m.put(keys[i], values[i]);   // resize nhieu lan

✅ new HashMap<>(1_500_000) — tránh resize.

9. 📚 Deep Dive Oracle

10. Tóm tắt

• Cây interface: Iterable → Collection → List/Set/Queue; Map tách riêng.
• ArrayList — mặc định cho List. LinkedList hầu như không dùng.
• ArrayDeque — best cho stack/queue.
• HashSet / HashMap — O(1) mặc định. LinkedHashSet/Map giữ thứ tự insert. TreeSet/Map sorted + O(log n).
• HashSet/HashMap yêu cầu equals/hashCode đúng cho element/key.
• Java 8+ HashMap treeify bucket > 8 → chống DoS hash collision.
• List.of / Set.of / Map.of (Java 9+) cho immutable.
• List.copyOf / ...copyOf cho defensive snapshot.
• ConcurrentModificationException — dùng removeIf thay vì modify trong loop.
• Rule declare bằng interface, instantiate bằng class: List<String> x = new ArrayList<>().

11. Tự kiểm tra

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10_000; i++) list.add(i);

for (int i = 0; i < list.size(); i++) {
    sum += list.get(i);   // O(n)
}

Map<String, Integer> m = new HashMap<>();
m.put("a", 1);
m.put("b", 2);
m.put("c", 3);

for (var e : m.entrySet()) {
    System.out.println(e.getKey() + "=" + e.getValue());
}

List<String> names = new ArrayList<>(List.of("alice", "bob", "charlie"));
for (String name : names) {
    if (name.startsWith("b")) names.remove(name);
}

Bài tiếp theo: Mini-challenge: LRU Cache với LinkedHashMap