Giới thiệu Collections Framework

Mục tiêu bài học

Sau bài này, bạn sẽ:

• Hiểu Collections Framework là gì và hierarchy của nó (List, Set, Queue, Map)
• Phân biệt Collection (interface) vs Collections (utility class) và Collection vs Map
• Nắm được lý do dùng Collections thay vì Arrays (dynamic size, rich API, generics)
• Biết cách chọn đúng collection cho từng use case (ArrayList, HashSet, HashMap, LinkedList...)
• Áp dụng diamond operator <> và các phương thức common của Collection interface

Collections Framework là gì?

Collections Framework là một kiến trúc thống nhất để biểu diễn và thao tác với các tập hợp (collections) trong Java. Nó cung cấp:

• Interfaces: Các kiểu dữ liệu trừu tượng đại diện cho collections (List, Set, Queue, Map)
• Implementations: Các triển khai cụ thể của các interface (ArrayList, HashSet, HashMap, ...)
• Algorithms: Các phương thức tiện ích để thao tác với collections (sorting, searching, shuffling, ...)

Lợi ích của Collections Framework

• Giảm công sức lập trình: Không cần tự implement các cấu trúc dữ liệu phổ biến
• Tăng tốc độ và chất lượng: Sử dụng các thuật toán đã được tối ưu hóa
• Tính tương thích: Các collection khác nhau có thể tương tác dễ dàng
• Dễ học và sử dụng: API nhất quán, dễ nhớ

Collection Hierarchy (Hệ thống phân cấp)

java.lang.Iterable
        |
        v
java.util.Collection
        |
        +----> List (ordered, allows duplicates)
        |        |
        |        +----> ArrayList
        |        +----> LinkedList
        |        +----> Vector (legacy)
        |
        +----> Set (no duplicates, unordered*)
        |        |
        |        +----> HashSet
        |        +----> LinkedHashSet (insertion-ordered)
        |        +----> TreeSet (sorted)
        |
        +----> Queue (FIFO - First In First Out)
                 |
                 +----> PriorityQueue
                 +----> Deque (double-ended queue)
                          |
                          +----> ArrayDeque
                          +----> LinkedList

java.util.Map (không extends Collection!)
        |
        +----> HashMap
        +----> LinkedHashMap (insertion-ordered)
        +----> TreeMap (sorted by keys)
        +----> Hashtable (legacy)

Lưu ý về Map

Map không phải là Collection! Map không extends từ interface Collection vì nó lưu trữ cặp key-value, không phải các phần tử đơn lẻ. Tuy nhiên, Map vẫn là một phần quan trọng của Collections Framework.

Tại sao Map không extends Collection?

Đây là một quyết định kiến trúc (architectural decision) quan trọng từ khi thiết kế Collections Framework:

Collection chứa các phần tử đơn lẻ (single values):

interface Collection<E> {
    boolean add(E element);      // Thêm 1 phần tử
    boolean remove(Object o);    // Xóa 1 phần tử
    boolean contains(Object o);  // Kiểm tra 1 phần tử
}

Map chứa cặp key-value (key-value pairs):

interface Map<K, V> {
    V put(K key, V value);       // Thêm cặp key-value
    V remove(Object key);        // Xóa theo key
    boolean containsKey(Object key);  // Kiểm tra key
}

Nếu Map extends Collection, sẽ gặp nhiều vấn đề:

• add(E element) sẽ thêm gì? Key hay value? Hay cả cặp?
• contains(Object o) sẽ check key hay value?
• remove(Object o) sẽ xóa theo key hay value?

Tuy nhiên, Map vẫn có thể chuyển sang Collection thông qua các view methods:

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);

Set<String> keys = map.keySet();           // Collection của keys
Collection<Integer> values = map.values(); // Collection của values
Set<Map.Entry<String, Integer>> entries = map.entrySet(); // Collection của entries

Collections Hierarchy Diagram

Sơ đồ Mermaid dưới đây minh họa toàn bộ hierarchy của Collections Framework, bao gồm cả Map (nhánh riêng biệt):

Chú thích:

• Hộp đỏ (Map): Không extends Collection - nhánh riêng biệt
• Hộp vàng đứt (legacy): Vector, Stack, Hashtable - nên tránh sử dụng
• Mũi tên nét liền: Inheritance/implementation relationship

Collection vs Collections

Đây là hai khái niệm khác nhau mà người mới học thường nhầm lẫn:

Khía cạnh	Collection (interface)	Collections (class)
Loại	Interface	Utility class
Package	java.util.Collection	java.util.Collections
Mục đích	Định nghĩa các phương thức chung cho List, Set, Queue	Cung cấp các phương thức static tiện ích
Ví dụ	List<String> list = new ArrayList<>();	Collections.sort(list);
Extends/Implements	Extends Iterable	Không extend/implement gì

// Collection - interface
Collection<String> collection = new ArrayList<>();
collection.add("Java");
collection.add("Python");

// Collections - utility class với static methods
List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1));
Collections.sort(numbers);  // Sắp xếp list
Collections.reverse(numbers);  // Đảo ngược list
Collections.shuffle(numbers);  // Xáo trộn ngẫu nhiên
int max = Collections.max(numbers);  // Tìm giá trị lớn nhất

Tại sao dùng Collections thay vì Arrays?

Arrays có nhiều hạn chế so với Collections:

Đặc điểm	Array	Collection
Kích thước	Fixed (cố định)	Dynamic (động)
Kiểu dữ liệu	Primitive hoặc Object	Chỉ Object (wrapper cho primitive)
API	Hạn chế, phải dùng vòng lặp	API phong phú: add, remove, contains, ...
Generics	Không hỗ trợ tốt	Hỗ trợ type-safe với Generics
Performance	Truy cập nhanh O(1)	Phụ thuộc implementation

// Array - kích thước cố định
String[] arrayNames = new String[3];
arrayNames[0] = "Alice";
arrayNames[1] = "Bob";
// arrayNames[3] = "Charlie";  // ArrayIndexOutOfBoundsException!

// Collection - kích thước động
List<String> listNames = new ArrayList<>();
listNames.add("Alice");
listNames.add("Bob");
listNames.add("Charlie");  // OK! Tự động mở rộng
listNames.add("David");    // Thêm bao nhiêu cũng được

Khi nào dùng Array?

• Khi biết chính xác số lượng phần tử và không thay đổi
• Khi cần performance cao nhất cho truy cập ngẫu nhiên
• Khi làm việc với primitive types và muốn tối ưu bộ nhớ
• Khi làm việc với multi-dimensional data (mảng 2D, 3D)

Generics trong Collections

Generics cho phép chỉ định kiểu dữ liệu mà collection sẽ chứa, giúp đảm bảo type-safety tại compile-time.

// Không dùng Generics (Java cũ - không khuyến khích)
List list = new ArrayList();
list.add("String");
list.add(123);  // OK, nhưng dễ gây lỗi runtime
String s = (String) list.get(1);  // ClassCastException tại runtime!

// Dùng Generics (Java hiện đại - khuyến khích)
List<String> stringList = new ArrayList<>();
stringList.add("String");
// stringList.add(123);  // Compile error! Type-safe
String s = stringList.get(0);  // Không cần cast

Diamond Operator (<>)

Từ Java 7+, bạn có thể dùng diamond operator để compiler tự suy luận kiểu:

// Java 6 và trước
List<String> list = new ArrayList<String>();

// Java 7+ với diamond operator
List<String> list = new ArrayList<>();  // Ngắn gọn hơn!

Overview các Interface chính

1. List Interface

• Ordered: Duy trì thứ tự thêm vào
• Allows duplicates: Cho phép phần tử trùng lặp
• Index-based access: Truy cập theo chỉ số (0, 1, 2, ...)

List<String> fruits = new ArrayList<>();
fruits.add("Apple");    // index 0
fruits.add("Banana");   // index 1
fruits.add("Apple");    // index 2 - duplicate OK!
String first = fruits.get(0);  // "Apple"

Implementations phổ biến: ArrayList, LinkedList

2. Set Interface

• No duplicates: Không cho phép phần tử trùng lặp
• Unordered (tùy implementation): Không đảm bảo thứ tự
• Mathematical set operations: Hỗ trợ các phép toán tập hợp

Set<String> uniqueNames = new HashSet<>();
uniqueNames.add("Alice");
uniqueNames.add("Bob");
uniqueNames.add("Alice");  // Không thêm được, đã tồn tại
System.out.println(uniqueNames.size());  // 2 (không phải 3)

Implementations phổ biến: HashSet, LinkedHashSet, TreeSet

3. Queue Interface

• FIFO: First In First Out (phần tử vào trước, ra trước)
• Head & Tail: Có đầu (head) và đuôi (tail)
• Special operations: offer, poll, peek

Queue<String> queue = new LinkedList<>();
queue.offer("First");   // Thêm vào tail
queue.offer("Second");
queue.offer("Third");
String head = queue.poll();  // Lấy và xóa từ head: "First"

Implementations phổ biến: LinkedList, PriorityQueue, ArrayDeque

4. Map Interface

• Key-Value pairs: Lưu trữ cặp key-value
• Unique keys: Mỗi key chỉ xuất hiện một lần
• Fast lookup: Tìm kiếm nhanh theo key

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 25);
ages.put("Bob", 30);
ages.put("Alice", 26);  // Overwrite giá trị cũ
int aliceAge = ages.get("Alice");  // 26

Implementations phổ biến: HashMap, LinkedHashMap, TreeMap

Chọn Collection nào?

Cần lưu key-value pairs?
    YES → Map
        Cần sắp xếp theo key? → TreeMap
        Cần thứ tự insertion? → LinkedHashMap
        Không quan tâm thứ tự? → HashMap
    NO → Collection
        Cho phép duplicates?
            YES → List
                Cần truy cập ngẫu nhiên nhanh? → ArrayList
                Cần thêm/xóa ở đầu/giữa nhiều? → LinkedList
            NO → Set
                Cần sắp xếp? → TreeSet
                Cần thứ tự insertion? → LinkedHashSet
                Không quan tâm thứ tự? → HashSet

        Cần xử lý FIFO/LIFO?
            YES → Queue/Deque
                Cần priority? → PriorityQueue
                Cần stack/queue operations? → ArrayDeque

Ví dụ tổng hợp

import java.util.*;

public class CollectionsIntroDemo {
    public static void main(String[] args) {
        // List - ordered, allows duplicates
        List<String> shoppingList = new ArrayList<>();
        shoppingList.add("Milk");
        shoppingList.add("Bread");
        shoppingList.add("Milk");  // Duplicate OK
        System.out.println("Shopping: " + shoppingList);
        // Output: [Milk, Bread, Milk]

        // Set - no duplicates
        Set<String> uniqueItems = new HashSet<>(shoppingList);
        System.out.println("Unique items: " + uniqueItems);
        // Output: [Milk, Bread]

        // Map - key-value pairs
        Map<String, Double> prices = new HashMap<>();
        prices.put("Milk", 2.50);
        prices.put("Bread", 1.99);
        prices.put("Eggs", 3.49);
        System.out.println("Price of Milk: $" + prices.get("Milk"));
        // Output: Price of Milk: $2.5

        // Queue - FIFO
        Queue<String> checkoutQueue = new LinkedList<>();
        checkoutQueue.offer("Customer 1");
        checkoutQueue.offer("Customer 2");
        checkoutQueue.offer("Customer 3");
        System.out.println("Now serving: " + checkoutQueue.poll());
        // Output: Now serving: Customer 1

        // Collections utility methods
        List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
        Collections.sort(numbers);
        System.out.println("Sorted: " + numbers);
        // Output: Sorted: [1, 2, 5, 8, 9]

        System.out.println("Max: " + Collections.max(numbers));
        // Output: Max: 9
    }
}

Common Methods của Collection Interface

Tất cả các implementation của Collection đều có các phương thức cơ bản sau:

Collection<String> collection = new ArrayList<>();

// Thêm phần tử
collection.add("element");
collection.addAll(Arrays.asList("a", "b", "c"));

// Xóa phần tử
collection.remove("element");
collection.removeAll(Arrays.asList("a", "b"));
collection.clear();  // Xóa tất cả

// Kiểm tra
boolean hasElement = collection.contains("element");
boolean isEmpty = collection.isEmpty();
int size = collection.size();

// Chuyển đổi
Object[] array = collection.toArray();
String[] stringArray = collection.toArray(new String[0]);

// Iteration
for (String item : collection) {
    System.out.println(item);
}

Legacy Collections - Tại sao nên tránh

Java có một số collection classes từ thời Java 1.0/1.1 được gọi là legacy classes. Chúng vẫn tồn tại để backward compatibility nhưng không nên dùng trong code mới:

Legacy Class	Vấn đề	Thay thế bằng
Vector	Synchronized everywhere → chậm	ArrayList
Stack	Extends Vector, design cũ	ArrayDeque
Hashtable	Synchronized, không cho null	HashMap
Enumeration	Tên method dài, thiếu remove	Iterator

// ❌ KHÔNG KHUYẾN KHÍCH: Legacy classes
Vector<String> vector = new Vector<>();      // Synchronized, chậm
Stack<Integer> stack = new Stack<>();        // Extends Vector, bad design
Hashtable<String, Integer> table = new Hashtable<>();  // Không cho null key/value

// ✅ KHUYẾN KHÍCH: Modern equivalents
List<String> list = new ArrayList<>();       // Nhanh hơn, không synchronized
Deque<Integer> deque = new ArrayDeque<>();   // Dùng làm stack
Map<String, Integer> map = new HashMap<>();  // Cho phép null, nhanh hơn

Tại sao Vector và Hashtable chậm?

Synchronized everywhere = mỗi method đều có synchronized keyword:

// Vector source code (simplified)
public class Vector<E> {
    public synchronized boolean add(E e) { ... }
    public synchronized E get(int index) { ... }
    public synchronized E remove(int index) { ... }
    // Mọi method đều synchronized!
}

Vấn đề: Ngay cả khi dùng single-threaded, vẫn phải trả overhead của synchronization → chậm không cần thiết.

Giải pháp: Dùng ArrayList (nhanh), nếu cần thread-safe thì wrap lại:

List<String> syncList = Collections.synchronizedList(new ArrayList<>());

Hoặc tốt hơn, dùng concurrent collections từ java.util.concurrent:

Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
List<String> copyOnWriteList = new CopyOnWriteArrayList<>();

Fail-Fast Iterators

Hầu hết Iterator trong Collections Framework là fail-fast - nếu collection bị modify (thêm/xóa) trong khi đang iterate (không qua Iterator), sẽ throw ConcurrentModificationException.

Fail-Fast Mechanism Diagram

Giải thích:

• Iterator lưu snapshot của modCount khi được tạo
• Mỗi lần gọi next(), kiểm tra modCount == expectedModCount
• Nếu collection bị modify từ bên ngoài (không qua Iterator) → modCount thay đổi → Exception!

Cơ chế modCount

Mỗi collection có một internal counter gọi là modCount (modification count) để track số lần bị modify:

// Simplified ArrayList implementation
public class ArrayList<E> {
    private int modCount = 0;  // Modification counter

    public boolean add(E e) {
        modCount++;  // Increment on modification
        // ... add logic
    }

    public E remove(int index) {
        modCount++;  // Increment on modification
        // ... remove logic
    }

    private class Itr implements Iterator<E> {
        int expectedModCount = modCount;  // Snapshot modCount khi tạo iterator

        public E next() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();  // Detect modification!
            }
            // ... next logic
        }
    }
}

Ví dụ minh họa

List<String> fruits = new ArrayList<>(Arrays.asList("Apple", "Banana", "Cherry"));

Iterator<String> iter = fruits.iterator();  // expectedModCount = 0

// Output: Apple
System.out.println(iter.next());

fruits.add("Date");  // modCount++ → modCount = 1

// ConcurrentModificationException!
// Vì modCount (1) != expectedModCount (0)
try {
    System.out.println(iter.next());
} catch (ConcurrentModificationException e) {
    System.out.println("Caught: " + e.getClass().getSimpleName());
}

💡 Cách nhớ: Fail-fast = "Phát hiện nhanh và báo lỗi ngay"

Iterator giống như người canh giữ cửa hàng - ghi nhớ số lượng hàng (modCount) khi bắt đầu. Nếu ai đó lấy/thêm hàng (modification) mà không qua người canh (Iterator), người canh sẽ phát hiện ngay và la lên (throw exception)!

Unmodifiable vs Immutable

Đây là một sự khác biệt quan trọng mà nhiều người nhầm lẫn:

Unmodifiable vs Immutable Comparison Diagram

Giải thích:

• Unmodifiable: Wrapper view → changes từ original list propagate đến view
• Immutable: True copy → changes từ original list KHÔNG ảnh hưởng copy

Collections.unmodifiableList() - Wrapper View

Unmodifiable = READ-ONLY WRAPPER, không phải truly immutable:

List<String> original = new ArrayList<>(Arrays.asList("A", "B", "C"));
List<String> unmodifiable = Collections.unmodifiableList(original);

// Không thể modify qua unmodifiable
// unmodifiable.add("D");  // UnsupportedOperationException

// NHƯNG: Thay đổi original → ảnh hưởng unmodifiable!
original.add("D");
System.out.println(unmodifiable);  // [A, B, C, D] - CHANGED!

List.copyOf() - True Immutable Copy (Java 10+)

Immutable = TRULY IMMUTABLE, tạo defensive copy:

List<String> original = new ArrayList<>(Arrays.asList("A", "B", "C"));
List<String> immutable = List.copyOf(original);

// Không thể modify qua immutable
// immutable.add("D");  // UnsupportedOperationException

// Thay đổi original → KHÔNG ảnh hưởng immutable
original.add("D");
System.out.println(immutable);  // [A, B, C] - UNCHANGED!

So sánh

Đặc điểm	Collections.unmodifiableList()	List.of() / List.copyOf()
Java version	Java 1.2+	Java 9+ / 10+
Type	Wrapper (view)	True copy
Original changes	Ảnh hưởng	Không ảnh hưởng
Null elements	Allowed	NOT allowed
Use case	Legacy code	Modern code

// Output minh họa sự khác biệt
List<String> mutable = new ArrayList<>(Arrays.asList("A", "B", "C"));

List<String> unmod = Collections.unmodifiableList(mutable);
List<String> immut = List.copyOf(mutable);

mutable.add("D");

System.out.println("Mutable: " + mutable);    // [A, B, C, D]
System.out.println("Unmodifiable: " + unmod); // [A, B, C, D] ← CHANGED!
System.out.println("Immutable: " + immut);    // [A, B, C] ← NOT CHANGED!

🔥 Bẫy OCP

List<Integer> original = new ArrayList<>(Arrays.asList(1, 2, 3));
List<Integer> view = Collections.unmodifiableList(original);

// Câu hỏi: view.size() = ?
original.add(4);
original.add(5);

System.out.println(view.size());  // Output: 5 (không phải 3!)

Giải thích: Collections.unmodifiableList() chỉ là wrapper view, không phải copy. Mọi thay đổi trên original đều ảnh hưởng đến view.

Thread-Safe Variants Overview

Collections Framework cung cấp nhiều cách để đạt được thread-safety:

1. Synchronized Wrappers (Java 1.2+)

Wrap collection hiện có với synchronized layer:

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Set<Integer> syncSet = Collections.synchronizedSet(new HashSet<>());
Map<String, User> syncMap = Collections.synchronizedMap(new HashMap<>());

// Mọi method call đều synchronized
syncList.add("Item");  // synchronized internally

// NHƯNG: Iteration vẫn cần manual sync!
synchronized (syncList) {
    for (String item : syncList) {
        System.out.println(item);
    }
}

Nhược điểm:

• Synchronized trên toàn bộ object → chậm với high concurrency
• Iteration không tự động synchronized

2. Concurrent Collections (Java 5+)

Implementations tối ưu cho concurrent access:

Map<String, User> map = new ConcurrentHashMap<>();       // Segment locking
Queue<Task> queue = new ConcurrentLinkedQueue<>();       // Lock-free
List<String> list = new CopyOnWriteArrayList<>();        // Copy-on-write

// Không cần external synchronization
map.put("key", user);
queue.offer(task);
list.add("item");

// Iteration thread-safe (không cần synchronized block)
for (String item : list) {
    System.out.println(item);
}

Ưu điểm:

• Hiệu suất tốt hơn với high concurrency
• Iteration thread-safe
• Specialized cho các use case khác nhau

3. Immutable Collections (Java 9+)

Immutable = automatically thread-safe:

List<String> immutable = List.of("A", "B", "C");
Set<Integer> immutableSet = Set.of(1, 2, 3);
Map<String, Integer> immutableMap = Map.of("A", 1, "B", 2);

// Thread-safe vì không thể modify
// Không cần synchronization overhead

So sánh

Approach	Performance	Use Case	Iteration Safety
Collections.synchronizedList()	Chậm	Legacy code	Manual sync needed
ConcurrentHashMap	Nhanh	High concurrency reads/writes	Automatic
CopyOnWriteArrayList	Chậm writes, nhanh reads	Many reads, few writes	Automatic
Immutable (List.of())	Nhanh nhất	Read-only data	Automatic

Thread-Safety

Hầu hết các implementation của Collections Framework KHÔNG thread-safe (không an toàn khi dùng đa luồng). Nếu cần thread-safety, sử dụng:

• Collections.synchronizedList(), Collections.synchronizedSet(), ... (old style)
• ConcurrentHashMap, CopyOnWriteArrayList từ java.util.concurrent (preferred)
• Immutable collections với List.of(), Set.of(), Map.of() (best for read-only)

Bài tập thực hành

Bài 1: Phân biệt Collection types

Tạo một chương trình minh họa sự khác nhau giữa List, Set, và Map bằng cách:

• Thêm các số 1, 2, 3, 2, 1 vào ArrayList
• Thêm các số 1, 2, 3, 2, 1 vào HashSet
• So sánh kết quả

Bài 2: Chuyển đổi giữa các Collection

Viết code để:

• Tạo một Array String[] names = {"Alice", "Bob", "Alice", "Charlie"}
• Chuyển sang List
• Loại bỏ duplicates bằng Set
• Chuyển về Array

Bài 3: Collections utility

Sử dụng class Collections để:

• Tạo một List số nguyên ngẫu nhiên
• Sắp xếp tăng dần
• Đảo ngược
• Xáo trộn
• Tìm min, max

Tổng kết

Trong bài này, bạn đã học:

• Collections Framework là hệ thống cấu trúc dữ liệu chuẩn của Java
• Phân biệt Collection (interface) và Collections (utility class)
• Hierarchy của Collections: List, Set, Queue, Map
• Tại sao dùng Collections thay vì Arrays
• Generics giúp đảm bảo type-safety
• Overview về 4 interface chính và cách chọn đúng collection

Các bài tiếp theo sẽ đi sâu vào từng loại collection cụ thể!

Đọc thêm

• Collections Framework Overview - Oracle
• Java Collections API - Oracle