Buổi 7/10

    Lập trình tổng quát và khung Collections

    180 phút
    Thực hành: 0/20 bài

    Buổi 7: Lập trình tổng quát và khung Collections

    Hãy tưởng tượng bạn viết phần mềm quản lý thư viện trường. Cần một danh sách sách đang cho mượn, một danh sách mã thẻ độc giả không được trùng, một bảng tra cứu từ mã sách ra tên sách, và một hàng đợi các độc giả đang chờ mượn cuốn sách hot. Nếu chỉ có mảng như ở Buổi 3, bạn sẽ phải tự viết lại việc thêm, xóa, tìm, mở rộng kích thước cho từng loại — và mỗi lần đổi kiểu dữ liệu (từ sách sang độc giả) lại viết lại một bản sao. Java giải quyết hai vấn đề này bằng hai công cụ: lập trình tổng quát (generics) để viết một đoạn mã dùng được cho nhiều kiểu mà vẫn an toàn, và khung Collections (Java Collections Framework) — bộ sưu tập các cấu trúc dữ liệu dựng sẵn: danh sách, tập hợp, ánh xạ, hàng đợi. Hai chủ đề này gắn chặt với nhau: mọi collection đều là một lớp generic, nên bạn phải hiểu List<String> thực sự nghĩa là gì trước khi dùng nó thành thạo.

    Mục tiêu buổi học

    • Sau buổi này bạn có thể viết lớp và phương thức tổng quát (Box<T>, Pair<K, V>, <T> void print(T[] a)) và giải thích lợi ích so với dùng Object ép kiểu.
    • Sau buổi này bạn có thể đặt giới hạn kiểu (extends, nhiều giới hạn) và chọn đúng ký tự đại diện ? extends / ? super theo nguyên tắc PECS.
    • Sau buổi này bạn có thể mô tả phân cấp của khung Collections và chọn đúng cấu trúc (ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, LinkedHashMap, ArrayDeque, PriorityQueue) cho từng bài toán dựa trên độ phức tạp.
    • Sau buổi này bạn có thể duyệt collection bằng for-each và Iterator, xóa phần tử an toàn khi duyệt, và tự cài Iterable cho lớp của mình.
    • Sau buổi này bạn có thể sắp xếp theo nhiều tiêu chí bằng Comparable và Comparator, đồng thời dùng các hàm tiện ích của lớp Collections.

    Bản đồ buổi học

    Phần Nội dung Thời lượng gợi ý
    1. Lập trình tổng quát Lớp, phương thức tổng quát, giới hạn kiểu; bài nhóm 7.1 30 phút (lý thuyết 15 + thực hành 15)
    2. Ký tự đại diện và PECS ?, ? extends, ? super; bài nhóm 7.2 20 phút (lý thuyết 10 + thực hành 10)
    3. Khung Collections Phân cấp, chọn cấu trúc, độ phức tạp 15 phút (lý thuyết)
    4. List, Set, Queue/Deque ArrayList, LinkedList, HashSet, TreeSet, ArrayDeque, PriorityQueue; bài nhóm 7.3 40 phút (lý thuyết 15 + thực hành 25)
    5. Map HashMap, LinkedHashMap, TreeMap; bài nhóm 7.4 25 phút (lý thuyết 10 + thực hành 15)
    6. Iterator, Comparable, Comparator Duyệt, Iterable, sắp xếp nhiều khóa; bài nhóm 7.5 35 phút (lý thuyết 15 + thực hành 20)
    7. Lớp tiện ích Collections sort, reverse, max, frequency, bất biến…; bài nhóm 7.6 và tổng kết 15 phút (lý thuyết 5 + thực hành 10)

    Tổng 180 phút, trong đó thực hành khoảng 100 phút (hơn một nửa).

    1. Lập trình tổng quát (Generics)

    1.1. Vấn đề: dùng Object thì mất an toàn kiểu

    Trước Java 5, muốn viết một "cái hộp" chứa được mọi thứ, người ta cho nó chứa Object. Hộp nhận gì cũng được, nhưng khi lấy ra bạn phải ép kiểu và trình biên dịch không giúp bạn kiểm tra: nếu ép sai, lỗi chỉ lộ ra lúc chương trình đang chạy.

    📦 Generics: Box dùng Object và Box<T>

    ❌ Trước generics — Box(Object)

    Box — value: Object
    42 : Integer"hi" : String3.14 : Double
    Nhét gì cũng vào được → lấy ra không biết là kiểu gì.
    class Box {
        private Object value;
        void set(Object v) { value = v; }
        Object get() { return value; }
    }
     
    Box box = new Box();
    box.set(42);                    // Integer
    String s = (String) box.get();  // ép kiểu
    1. Biên dịch
    ✅ qua — compiler không biết value là gì
    2. Chạy
    💥 ClassCastException: Integer cannot be cast to String

    ✅ Có generics — Box<T>

    Box<String> — value: String
    "hi""java"42 ✖ bị từ chối
    Chỉ nhận String — Integer bị từ chối ngay khi biên dịch.
    class Box<T> {
        private T value;
        void set(T v) { value = v; }
        T get() { return value; }
    }
     
    Box<String> box = new Box<>();
    box.set(42);            // ❌ lỗi biên dịch
    String s = box.get();   // ✅ không cần ép kiểu
    1. Biên dịch
    ❌ báo lỗi ngay: int cannot be converted to String
    2. Chạy
    ✅ sửa xong là an toàn kiểu, không còn ClassCastException

    Với Object, lỗi kiểu chỉ lộ khi chạy (ClassCastException). Với generics Box<T>, trình biên dịch chặn sai kiểu ngay từ đầu và bạn khỏi phải ép kiểu.

    Hình so sánh hai cách: hộp Object (nhận bừa, ép kiểu khi lấy, lỗi ở thời điểm chạy) và hộp Box<T> (khai báo rõ kiểu, trình biên dịch chặn sai từ sớm). Chương trình dưới đây tái hiện lỗi của cách thứ nhất.

    Java · chạy thử được
    class ObjectBox {
    private Object value;
    void set(Object v) { value = v; }
    Object get() { return value; }
}

public class Main {
    public static void main(String[] args) {
        ObjectBox box = new ObjectBox();
        box.set("Java");               // bỏ vào một chuỗi
        try {
            Integer n = (Integer) box.get();   // ép nhầm sang Integer
            System.out.println(n);
        } catch (ClassCastException e) {
            System.out.println("Lỗi lúc chạy: ClassCastException");
        }
    }
}

    Đoạn mã biên dịch bình thường, nhưng chương trình lỗi khi chạy. Trong hệ thống thật, lỗi kiểu này có thể nằm ở một nhánh ít được chạy thử và chỉ nổ ra khi đã triển khai.

    1.2. Lớp tổng quát Box<T>

    Generics cho phép lớp nhận tham số kiểu (type parameter) viết trong cặp ngoặc nhọn ngay sau tên lớp. Chữ T chỉ là tên giữ chỗ ("Type"); khi dùng, bạn thay bằng kiểu thật. Quy ước tên: T (type), E (element, dùng trong collection), K và V (key và value), N (number).

    Java · chạy thử được
    class Box<T> {
    private T value;
    void set(T v) { value = v; }
    T get() { return value; }
}

public class Main {
    public static void main(String[] args) {
        Box<String> name = new Box<>();   // toán tử kim cương <> để compiler suy ra kiểu
        name.set("An");
        String s = name.get();            // không cần ép kiểu
        System.out.println("Xin chào " + s);

        Box<Integer> age = new Box<>();
        age.set(20);
        int a = age.get() + 1;            // tự động unboxing
        System.out.println("Năm sau: " + a);
        // name.set(5);                   // lỗi biên dịch: 5 không phải String
    }
}

    Điểm cốt lõi: dòng name.set(5) bị trình biên dịch từ chối ngay, thay vì chờ đến lúc chạy. Cặp ngoặc <> bỏ trống ở vế phải gọi là toán tử kim cương (diamond), compiler tự suy ra kiểu từ vế trái. Từ Java 10 bạn còn có thể viết var name = new Box<String>();.

    Lưu ý: Tham số kiểu chỉ nhận được kiểu tham chiếu (lớp, interface, mảng), không nhận kiểu nguyên thủy. Muốn hộp chứa int bạn viết Box<Integer>; Java tự đóng gói (autoboxing) int thành Integer và mở gói (unboxing) khi lấy ra.

    1.3. Lớp tổng quát nhiều tham số: Pair<K, V>

    Một lớp có thể có nhiều tham số kiểu. Pair<K, V> giữ hai giá trị có thể khác kiểu — hữu ích khi cần trả về hai kết quả từ một hàm, hay mô tả một cặp "mã sách – số lượng".

    Java · chạy thử được
    class Pair<K, V> {
    private final K first;
    private final V second;

    Pair(K first, V second) {
        this.first = first;
        this.second = second;
    }
    K getFirst() { return first; }
    V getSecond() { return second; }

    Pair<V, K> swap() {                 // đổi chỗ: kiểu trả về cũng đảo tham số
        return new Pair<>(second, first);
    }
    @Override
    public String toString() { return "(" + first + ", " + second + ")"; }
}

public class Main {
    public static void main(String[] args) {
        Pair<String, Integer> book = new Pair<>("Java co ban", 5);
        System.out.println(book);
        Pair<Integer, String> flipped = book.swap();
        System.out.println(flipped);
        System.out.println(flipped.getFirst() + 1);   // getFirst() là Integer
    }
}

    Hãy để ý kiểu trả về Pair<V, K> của swap(): nhờ generics, compiler biết flipped.getFirst() là Integer mà bạn không cần ép kiểu. Thư viện chuẩn không có sẵn lớp Pair đa dụng, nhưng bạn sẽ gặp các cặp tương tự như Map.Entry<K, V> ở phần Map.

    1.4. Phương thức tổng quát

    Không chỉ lớp, một phương thức cũng có thể có tham số kiểu riêng, khai báo trong ngoặc nhọn đặt trước kiểu trả về. Phương thức tĩnh bắt buộc phải khai báo như vậy nếu muốn dùng kiểu tổng quát (vì nó không thuộc về một đối tượng cụ thể).

    Java · chạy thử được
    public class Main {
    static <T> void printArray(T[] arr) {
        StringBuilder sb = new StringBuilder();
        for (T x : arr) sb.append(x).append(' ');
        System.out.println(sb.toString().trim());
    }

    static <T> void swap(T[] arr, int i, int j) {
        T tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }

    public static void main(String[] args) {
        Integer[] nums = {3, 1, 2};
        String[] words = {"a", "b", "c"};
        printArray(nums);          // compiler suy ra T = Integer
        swap(words, 0, 2);
        printArray(words);         // c b a
        Main.<String>printArray(words);   // chỉ rõ kiểu (hiếm khi cần)
    }
}

    Bạn không phải truyền kiểu khi gọi: compiler tự suy luận kiểu từ đối số. Lưu ý mảng phải là mảng đối tượng (Integer[]), không phải int[], vì T không thể là kiểu nguyên thủy.

    1.5. Giới hạn kiểu (bounded types)

    T không hạn chế thì chỉ gọi được các hàm của Object. Để so sánh hai phần tử, T phải có compareTo; vì thế ta giới hạn nó bằng extends:

    Java · chạy thử được
    public class Main {
    static <T extends Comparable<T>> T maxOf(T[] arr) {
        T best = arr[0];
        for (T x : arr)
            if (x.compareTo(best) > 0) best = x;
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxOf(new Integer[]{4, 9, 2}));
        System.out.println(maxOf(new String[]{"mango", "apple", "pear"}));
        System.out.println(maxOf(new Double[]{1.5, 0.5}));
    }
}

    Trong ngữ cảnh giới hạn kiểu, extends được dùng cho cả "kế thừa lớp" lẫn "cài đặt interface". Có thể đặt nhiều giới hạn nối bằng & (lớp, nếu có, phải đứng đầu):

    Java · chạy thử được
    public class Main {
    static <T extends Number & Comparable<T>> T minOf(T a, T b, T c) {
        T m = a;
        if (b.compareTo(m) < 0) m = b;
        if (c.compareTo(m) < 0) m = c;
        System.out.println("Giá trị double của min: " + m.doubleValue());  // method của Number
        return m;
    }

    public static void main(String[] args) {
        System.out.println(minOf(7, 3, 5));
        System.out.println(minOf(2.5, 9.0, 1.25));
    }
}

    Ở đây T vừa là Number (dùng được doubleValue()) vừa là Comparable (dùng được compareTo). Gọi minOf("a", "b", "c") sẽ lỗi biên dịch vì String không phải Number.

    1.6. Xóa kiểu (type erasure) và các hạn chế

    Để tương thích với mã Java cũ, thông tin generics chỉ có lúc biên dịch; sau khi compile, trình biên dịch "xóa" tham số kiểu (thay bằng Object hoặc giới hạn) và chèn sẵn phép ép kiểu. Hệ quả có thể kiểm chứng ngay:

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        List<String> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        System.out.println(a.getClass() == b.getClass());   // cùng một lớp lúc chạy
        System.out.println(a.getClass().getSimpleName());
    }
}

    Vì thế có những việc generics không cho phép:

    Không viết được Lý do Cách thay thế
    new T() Lúc chạy không còn biết T là gì Truyền vào Supplier<T> hoặc đối tượng mẫu
    new T[10] Không tạo được mảng generic Dùng ArrayList<T> hoặc ép (T[]) new Object[10] có cảnh báo
    Box<int> Tham số kiểu phải là tham chiếu Box<Integer>
    static T x; T thuộc về từng đối tượng, static thuộc về lớp Dùng phương thức tĩnh có <T> riêng
    x instanceof Box<String> Kiểu đã bị xóa x instanceof Box

    Cảnh báo: Box<Integer> không phải là lớp con của Box<Number> dù Integer là con của Number. Hộp chứa Integer không thay thế được hộp chứa Number (vì có thể bỏ Double vào hộp Number nhưng không bỏ được vào hộp Integer). Muốn "nhận cả họ kiểu" bạn cần ký tự đại diện ở phần tiếp theo.

    Mẹo: Đừng dùng raw type (viết List mà không có <…>). Nó tắt kiểm tra kiểu và chỉ tồn tại để tương thích mã cũ. Luôn viết List<String>, hoặc List<> ở vế phải với toán tử kim cương.

    Sau phần này bạn đã đủ kiến thức để tự viết lớp và phương thức tổng quát có giới hạn kiểu.

    Vừa học xong lớp và phương thức tổng quát cùng giới hạn kiểu, hãy làm các bài nhóm 7.1 để tự tay viết Box, Pair, hàm tìm lớn nhất bằng Comparable và Pair.swap().

    2. Ký tự đại diện và nguyên tắc PECS

    2.1. Vì sao List<Integer> không gán được cho List<Number>

    Giả sử bạn muốn viết một hàm tính tổng của một danh sách số. Viết tham số là List<Number> nghe hợp lý, nhưng khi truyền List<Integer> vào thì bị từ chối: hai kiểu này không có quan hệ cha–con dù Integer là con của Number. Lý do: nếu được phép, hàm có thể bỏ một Double vào danh sách mà thật ra chỉ chứa Integer. Java cho phép bạn nói "một danh sách chứa một kiểu nào đó thuộc họ Number" bằng ký tự đại diện (wildcard) ?.

    Cú pháp Đọc là Dùng khi
    List<?> Danh sách chứa kiểu gì đó chưa biết Chỉ cần duyệt, in, đếm — không quan tâm kiểu
    List<? extends Number> Danh sách Number hoặc con của Number Đọc phần tử ra (nguồn dữ liệu)
    List<? super Integer> Danh sách Integer hoặc cha của Integer Ghi phần tử vào (nơi chứa dữ liệu)

    2.2. ? extends T: chỉ để đọc

    Với List<? extends Number>, mọi phần tử lấy ra chắc chắn là Number nên bạn gọi được doubleValue(). Ngược lại, bạn không thể thêm gì vào (trừ null) vì compiler không biết danh sách thật sự chứa Integer hay Double.

    Java · chạy thử được
    public class Main {
    static double sumOfList(List<? extends Number> list) {
        double total = 0;
        for (Number n : list) total += n.doubleValue();
        return total;
    }

    public static void main(String[] args) {
        List<Integer> ints = Arrays.asList(1, 2, 3);
        List<Double> doubles = Arrays.asList(1.5, 2.5);
        System.out.println(sumOfList(ints));      // 6.0
        System.out.println(sumOfList(doubles));   // 4.0
    }
}

    Cùng một hàm nhận được cả List<Integer> lẫn List<Double>. Với List<?> bạn chỉ có thể dùng các thao tác không phụ thuộc kiểu như size() hay for (Object o : list).

    2.3. ? super T: chỉ để ghi

    Ngược lại, với List<? super Integer> bạn thêm được Integer vì mọi danh sách như vậy (List<Integer>, List<Number>, List<Object>) đều chấp nhận Integer. Nhưng khi lấy ra, bạn chỉ chắc chắn nhận được Object.

    Java · chạy thử được
    public class Main {
    static void addNumbers(List<? super Integer> list, int from, int to) {
        for (int i = from; i <= to; i++) list.add(i);
    }

    public static void main(String[] args) {
        List<Number> nums = new ArrayList<>();
        List<Object> objs = new ArrayList<>();
        addNumbers(nums, 1, 3);
        addNumbers(objs, 7, 8);
        System.out.println(nums);
        System.out.println(objs);
    }
}

    2.4. Nguyên tắc PECS

    Hai quy tắc trên gom lại thành khẩu quyết PECS — Producer Extends, Consumer Super: tham số nào sản xuất (cung cấp) dữ liệu cho hàm thì dùng extends; tham số nào tiêu thụ (nhận) dữ liệu thì dùng super. Hàm copy kinh điển minh họa cả hai:

    Java · chạy thử được
    public class Main {
    static <T> void copy(List<? super T> dest, List<? extends T> src) {
        for (T item : src) dest.add(item);   // src sản xuất, dest tiêu thụ
    }

    public static void main(String[] args) {
        List<Integer> src = List.of(1, 2, 3);
        List<Number> dest = new ArrayList<>(List.of(0.5));
        copy(dest, src);
        System.out.println(dest);
    }
}

    Mẹo: Cách nhớ nhanh: "đọc ra thì extends, ghi vào thì super, vừa đọc vừa ghi thì đừng dùng ký tự đại diện, hãy dùng chính T". Thư viện chuẩn cũng theo PECS, ví dụ Collections.copy(List<? super T> dest, List<? extends T> src).

    Ví dụ thực tế: Một hàm in báo cáo nhận List<? extends Student> sẽ in được cả danh sách sinh viên lẫn danh sách sinh viên cao học (lớp con), và bạn yên tâm hàm không thể "bỏ nhầm" một đối tượng lạ vào danh sách của người gọi.

    Vừa học xong ký tự đại diện và PECS, hãy làm nhóm 7.2 để tự viết hàm tính tổng ? extends Number và hàm copy giữa hai danh sách.

    3. Khung Collections: bức tranh tổng thể

    3.1. Phân cấp interface

    Java Collections Framework (JCF) là tập hợp interface và lớp cài đặt sẵn trong gói java.util để lưu và xử lý nhóm đối tượng. Toàn bộ khung dựa trên generics nên mọi collection đều có tham số kiểu phần tử. Điều quan trọng là bạn học interface trước, lớp cài đặt sau.

    🗂️ Họ Java Collections Framework
    «interface»Iterable<E>iterator() ← for-each«interface»Collection<E>add/remove/contains⚠ Cây riêngKHÔNG extends Collection«interface»List<E>get(i) · set(i, e)ArrayListmảng độngLinkedListdanh sách liên kết kép📋 Có thứ tự (theo chỉ số)Cho phép phần tử trùng«interface»Set<E>add(e) → booleanHashSetbảng băm · không thứ tựLinkedHashSetbăm + giữ thứ tự thêmTreeSetcây đỏ-đen · tự sắp xếp🚫 Không chứa phần tử trùngdựa trên equals/hashCode«interface»Queue<E>offer · poll · peekPriorityQueueheap · nhỏ nhất ra trướcArrayDequemảng vòng · hai đầu🚶 Hàng đợi FIFO / ưu tiênDeque: thêm/xóa cả hai đầu«interface»Map<K,V>put(k, v) · get(k)HashMapbảng bămLinkedHashMapgiữ thứ tự thêmTreeMapcây đỏ-đen · khóa sắp xếp🔑 Cặp khóa → giá trịKhóa không trùng, value tùy ý

    Mỗi nhóm một màu: List (có thứ tự, cho trùng), Set (không trùng), Queue (hàng đợi), Map (khóa → giá trị). Map là cây riêng, không kế thừa Collection.

    Hình cho thấy gốc là Iterable (cho phép for-each), rồi Collection chia ba nhánh List, Set, Queue; Map đứng riêng vì nó lưu cặp khóa–giá trị chứ không phải một dãy phần tử. Hãy đọc từ trên xuống: càng xuống dưới, interface càng cụ thể và lớp cài đặt (ArrayList, HashSet…) nằm ở các lá.

    Interface Đặc điểm Cài đặt thường dùng
    List<E> Có thứ tự, có chỉ số, cho phép trùng ArrayList, LinkedList
    Set<E> Không trùng, không có chỉ số HashSet, LinkedHashSet, TreeSet
    Queue<E> / Deque<E> Thêm cuối, lấy đầu (hàng đợi); Deque thêm/lấy cả hai đầu ArrayDeque, LinkedList, PriorityQueue
    Map<K, V> Ánh xạ khóa duy nhất → giá trị HashMap, LinkedHashMap, TreeMap

    3.2. Lập trình hướng interface

    Nguyên tắc vàng: khai báo biến bằng interface, tạo đối tượng bằng lớp cài đặt. Nhờ vậy đổi cấu trúc dữ liệu chỉ cần sửa đúng một dòng.

    Java · chạy thử được
    public class Main {
    static void show(Collection<Integer> c) {      // nhận mọi loại collection
        System.out.println(c.size() + " phần tử, có 3? " + c.contains(3));
    }

    public static void main(String[] args) {
        Collection<Integer> data = new ArrayList<>();   // đổi thành TreeSet cũng chạy
        data.add(3); data.add(1); data.add(3);
        show(data);

        data = new TreeSet<>(data);                     // loại trùng, sắp xếp
        show(data);
        System.out.println(data);
    }
}

    Cùng một hàm show dùng được cho ArrayList (3 phần tử, vì cho phép trùng) và TreeSet (2 phần tử). Các phương thức chung của Collection gồm add, remove, contains, size, isEmpty, clear, addAll, removeAll, retainAll, containsAll.

    3.3. Độ phức tạp: chọn cấu trúc theo thao tác

    Mỗi cấu trúc nhanh ở một số thao tác và chậm ở số khác. Biểu đồ dưới so sánh độ phức tạp trung bình của các cấu trúc phổ biến.

    Độ phức tạp trung bình của các thao tác trên List và Map
    ArrayListmảng độngLinkedListliên kết đôiHashMapbảng bămTreeMapcây đỏ–đenTruy cậpget(i) · get(key)O(1)truy cập mảngO(n)duyệt từ đầu/cuốiO(1)băm khóaO(log n)đi xuống câyThêm cuốiadd(e) · put(k, v)O(1)*khấu haoO(1)addLastO(1)băm khóaO(log n)cân bằng câyChèn giữaadd(i, e)O(n)dịch phần tửO(n)tìm vị trí—không có chỉ số—không có chỉ sốXóaremove(i) · remove(key)O(n)dịch phần tửO(n)tìm nútO(1)băm khóaO(log n)cân bằng câyTìm kiếmcontains(x) · containsKey(k)O(n)duyệt tuần tựO(n)duyệt tuần tựO(1)băm khóaO(log n)đi xuống câyO(1)O(log n)O(n)không áp dụngThanh nhỏ = mức tăng chi phí

    Đây là độ phức tạp lý thuyết trung bình theo số phần tử n, không phải thời gian đo thực tế (còn phụ thuộc hằng số, bộ nhớ đệm, JIT). * O(1) khấu hao: thỉnh thoảng ArrayList phải cấp lại mảng lớn hơn và sao chép (O(n)). HashMap suy giảm khi nhiều khóa trùng mã băm (từ Java 8 tối đa O(log n)). Map không có khái niệm chèn theo chỉ số.

    Đọc biểu đồ theo từng thao tác: truy cập theo chỉ số get(i) nhanh ở ArrayList nhưng chậm ở LinkedList; tìm theo khóa nhanh nhất ở HashMap (gần hằng số), còn TreeMap chậm hơn một chút nhưng giữ khóa luôn có thứ tự.

    Cấu trúc Thêm Tìm / contains Duyệt có thứ tự?
    ArrayList O(1) cuối, O(n) giữa O(n) Theo thứ tự chèn
    LinkedList O(1) hai đầu O(n) Theo thứ tự chèn
    HashSet / HashMap O(1) O(1) Không đảm bảo
    LinkedHashSet / LinkedHashMap O(1) O(1) Theo thứ tự chèn
    TreeSet / TreeMap O(log n) O(log n) Theo thứ tự sắp xếp

    Bảng đưa ra quy tắc chọn thực dụng: cần truy cập theo chỉ số → ArrayList; cần loại trùng và tìm nhanh → HashSet; cần tra cứu theo khóa → HashMap; cần kết quả luôn sắp xếp hoặc truy vấn khoảng → TreeSet/TreeMap; cần ngăn xếp/hàng đợi → ArrayDeque. Hãy thử trực tiếp: mô phỏng dưới đây thêm cùng một dãy phần tử vào các cấu trúc khác nhau để bạn thấy khác biệt về trùng lặp và thứ tự.

    Chọn đúng Collection

    Cùng một thao tác, mỗi cấu trúc phản ứng khác nhau
    Giá trị
    // chọn giá trị rồi bấm add / remove / contains
    ArrayList<Integer>
    Có thứ tự, cho phép trùng, truy cập theo chỉ số
    rỗng
    Chưa có thao tác
    LinkedHashSet<Integer>
    Không trùng, giữ thứ tự thêm vào
    rỗng
    Chưa có thao tác
    HashMap<Integer, Integer>
    Khóa duy nhất → giá trị (ở đây là số lần xuất hiện)
    rỗng
    Chưa có thao tác
    ArrayDeque<Integer> (queue)
    FIFO: vào cuối hàng (offer), ra đầu hàng (poll)
    rỗng
    Chưa có thao tác

    Gợi ý chọn: cần thứ tự + trùng → List; cần loại trùng → Set; cần tra theo khóa / đếm → Map; cần vào trước ra trước → Queue. Lưu ý list.remove(3) với int xóa theo chỉ số, nên dùng Integer.valueOf(3) để xóa theo giá trị.

    Cho cùng dãy phần tử có lặp, List giữ hết và đúng thứ tự, Set loại trùng, Map ghi đè giá trị theo khóa, Queue lấy ra theo thứ tự vào. Hãy quan sát cả bốn kết quả, đó là cách nhanh nhất để nhớ khác biệt.

    Lưu ý: Tất cả collection chỉ chứa đối tượng. List<int> không hợp lệ; dùng List<Integer>. Mỗi lần add(5) có một lần autoboxing; với dữ liệu hàng triệu số nguyên cần tốc độ, mảng int[] vẫn nhanh và tiết kiệm bộ nhớ hơn.

    4. List, Set và Queue/Deque

    4.1. List: danh sách có thứ tự

    List<E> là dãy phần tử có chỉ số bắt đầu từ 0, cho phép trùng. Hai cài đặt chính: ArrayList (mảng động, tự nới khi đầy) và LinkedList (danh sách liên kết đôi).

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        List<String> books = new ArrayList<>();
        books.add("Java");
        books.add("Python");
        books.add(1, "C++");            // chèn vào vị trí 1
        books.set(0, "Java 13");        // ghi đè
        System.out.println(books);
        System.out.println(books.get(2) + ", size=" + books.size());
        System.out.println(books.indexOf("C++") + " " + books.contains("Go"));
        books.remove("Python");         // xóa theo giá trị
        books.remove(0);                // xóa theo chỉ số
        System.out.println(books);
        for (String b : books) System.out.println("- " + b);
    }
}

    Bảng các thao tác thường dùng của List:

    Thao tác Ý nghĩa Ghi chú
    add(e) / add(i, e) Thêm cuối / chèn tại vị trí Chèn giữa phải dịch phần tử: O(n) với ArrayList
    get(i) / set(i, e) Đọc / ghi theo chỉ số O(1) với ArrayList, O(n) với LinkedList
    remove(i) / remove(Object) Xóa theo chỉ số / theo giá trị Xem cảnh báo bên dưới
    indexOf, contains Tìm (dùng equals) O(n)
    subList(from, to) Khung nhìn một đoạn Không phải bản sao
    List.of(...) Danh sách bất biến Thêm/xóa sẽ ném UnsupportedOperationException

    Cảnh báo: Với List<Integer>, list.remove(1) xóa phần tử ở chỉ số 1, còn muốn xóa giá trị 1 phải viết list.remove(Integer.valueOf(1)). Đây là bẫy hay gặp vì cả hai cùng biên dịch được nhưng cho kết quả khác nhau.

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(List.of(10, 20, 1));
        a.remove(1);                          // xóa chỉ số 1 (giá trị 20)
        System.out.println(a);
        a.remove(Integer.valueOf(1));         // xóa giá trị 1
        System.out.println(a);
        List<Integer> fixed = List.of(1, 2);
        try {
            fixed.add(3);
        } catch (UnsupportedOperationException e) {
            System.out.println("List.of là bất biến");
        }
    }
}

    LinkedList có cùng interface List nhưng mạnh ở thao tác hai đầu (addFirst, removeFirst). Thực tế ArrayList gần như luôn là lựa chọn đầu tiên vì nhanh hơn do dữ liệu nằm liền nhau trong bộ nhớ; chỉ chọn LinkedList khi chủ yếu thêm/xóa ở hai đầu mà không truy cập theo chỉ số.

    4.2. Set: tập hợp không trùng

    Set<E> đảm bảo mỗi phần tử xuất hiện một lần. add trả về true nếu thêm được, false nếu đã có. Ba cài đặt khác nhau ở thứ tự duyệt: HashSet (không đảm bảo thứ tự, nhanh nhất), LinkedHashSet (theo thứ tự thêm vào), TreeSet (luôn sắp xếp tăng dần).

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        int[] data = {5, 3, 5, 1, 3, 9};
        Set<Integer> seen = new HashSet<>();
        List<Integer> unique = new ArrayList<>();
        for (int x : data) {
            if (seen.add(x)) unique.add(x);     // add trả false nếu đã có
        }
        System.out.println("Giữ thứ tự xuất hiện: " + unique);

        Set<Integer> ordered = new LinkedHashSet<>();
        for (int x : data) ordered.add(x);
        System.out.println("LinkedHashSet: " + ordered);
        System.out.println("TreeSet: " + new TreeSet<>(ordered));
    }
}

    TreeSet (cây đỏ–đen) còn cung cấp các truy vấn theo thứ tự: first(), last(), floor(x) (lớn nhất không vượt quá x), ceiling(x) (nhỏ nhất không nhỏ hơn x), headSet, tailSet.

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> t = new TreeSet<>(List.of(10, 20, 30, 40));
        System.out.println(t.first() + " " + t.last());
        System.out.println(t.floor(25) + " " + t.ceiling(25));
        System.out.println(t.headSet(30) + " " + t.tailSet(30));
    }
}

    Các phép toán tập hợp ánh xạ trực tiếp vào các phương thức của Collection: hợp = addAll, giao = retainAll, hiệu = removeAll. Hãy tạo bản sao trước khi gọi vì chúng sửa trực tiếp tập gọi.

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        Set<Integer> a = new TreeSet<>(List.of(1, 2, 3, 4));
        Set<Integer> b = new TreeSet<>(List.of(3, 4, 5));

        Set<Integer> union = new TreeSet<>(a);   union.addAll(b);
        Set<Integer> inter = new TreeSet<>(a);   inter.retainAll(b);
        Set<Integer> diff  = new TreeSet<>(a);   diff.removeAll(b);
        System.out.println("Hợp:  " + union);
        System.out.println("Giao: " + inter);
        System.out.println("Hiệu: " + diff);
    }
}

    HashSet và HashMap dựa vào hashCode và equals như bạn đã học ở Buổi 5. Nếu lớp của bạn ghi đè equals mà quên hashCode, hai đối tượng "bằng nhau" có thể rơi vào hai ô băm khác nhau và HashSet coi chúng là hai phần tử.

    Java · chạy thử được
    import java.util.Objects;

class Book {
    final String title;
    Book(String title) { this.title = title; }
    @Override public boolean equals(Object o) {
        return o instanceof Book && ((Book) o).title.equals(title);
    }
    @Override public int hashCode() { return Objects.hash(title); }
}

public class Main {
    public static void main(String[] args) {
        Set<Book> shelf = new HashSet<>();
        shelf.add(new Book("Java"));
        shelf.add(new Book("Java"));
        System.out.println(shelf.size());   // 1 vì đã có equals + hashCode
    }
}

    Lưu ý: Phần tử của TreeSet (và khóa của TreeMap) không dùng equals/hashCode mà dùng thứ tự so sánh (compareTo hoặc Comparator): hai phần tử "so sánh bằng 0" bị coi là trùng. Đây là chỗ nối sang phần 6.

    4.3. Queue và Deque: hàng đợi và ngăn xếp

    Queue<E> mô tả hàng đợi FIFO (vào trước ra trước): thêm ở cuối, lấy ở đầu. Deque<E> (double-ended queue, đọc là "đếch") cho thao tác ở cả hai đầu, nên dùng được làm ngăn xếp LIFO (vào sau ra trước). Cài đặt khuyên dùng cho cả hai là ArrayDeque; LinkedList cũng cài đặt Deque nhưng chậm và tốn bộ nhớ hơn.

    Thao tác Queue (FIFO) Stack (LIFO, dùng Deque)
    Thêm offer(e) / add(e) (cuối) push(e) (đầu)
    Lấy và xóa poll() (đầu, trả null nếu rỗng) pop() (đầu, ném lỗi nếu rỗng)
    Chỉ xem peek() peek()
    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("a"); stack.push("b"); stack.push("c");
        System.out.println("Đỉnh stack: " + stack.peek());
        System.out.println("pop: " + stack.pop() + stack.pop() + stack.pop());

        Queue<String> queue = new ArrayDeque<>();
        queue.offer("An"); queue.offer("Binh"); queue.offer("Chi");
        System.out.println("Phục vụ: " + queue.poll());
        System.out.println("Còn lại: " + queue + ", rỗng? " + queue.isEmpty());
    }
}

    Một ứng dụng kinh điển của ngăn xếp là kiểm tra dấu ngoặc cân bằng: gặp ngoặc mở thì push, gặp ngoặc đóng thì pop và đối chiếu.

    Java · chạy thử được
    public class Main {
    static boolean balanced(String s) {
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[') st.push(c);
            else {
                if (st.isEmpty()) return false;
                char open = st.pop();
                if ((c == ')' && open != '(') || (c == ']' && open != '[')) return false;
            }
        }
        return st.isEmpty();
    }
    public static void main(String[] args) {
        System.out.println(balanced("([])"));
        System.out.println(balanced("([)]"));
        System.out.println(balanced("(("));
    }
}

    PriorityQueue<E> là hàng đợi ưu tiên cài bằng heap: poll() luôn lấy ra phần tử nhỏ nhất (theo thứ tự tự nhiên hoặc Comparator), không phải phần tử vào đầu tiên. Thêm/lấy đều O(log n). Muốn lấy lớn nhất, truyền Collections.reverseOrder().

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int x : new int[]{5, 1, 8, 3}) { minHeap.add(x); maxHeap.add(x); }
        System.out.println(minHeap.poll() + " " + minHeap.poll());   // 1 3
        System.out.println(maxHeap.poll() + " " + maxHeap.poll());   // 8 5
    }
}

    Cảnh báo: In ra cả PriorityQueue (System.out.println(pq)) không cho thứ tự sắp xếp, vì heap chỉ đảm bảo phần tử đầu là nhỏ nhất. Muốn lấy theo thứ tự, hãy poll() lần lượt. Tránh luôn lớp Stack và Vector cũ (đồng bộ chậm); dùng ArrayDeque.

    Ví dụ thực tế: Hàng chờ mượn sách là Queue; chức năng "hoàn tác" (undo) của trình soạn thảo là Deque dùng như stack; hệ thống xếp lịch xử lý yêu cầu theo mức độ khẩn cấp là PriorityQueue.

    Đến đây bạn đã nắm List, Set và Deque, đủ để giải các bài loại trùng, phép toán tập hợp và kiểm tra dấu ngoặc.

    Vừa học xong List, Set và Deque, hãy làm nhóm 7.3 để thực hành quản lý danh sách sinh viên, loại trùng giữ thứ tự, phép toán tập hợp và kiểm tra dấu ngoặc bằng ngăn xếp.

    5. Map: tra cứu theo khóa

    5.1. Khái niệm và các thao tác cơ bản

    Map<K, V> lưu các cặp khóa → giá trị; khóa là duy nhất, thêm lại cùng khóa sẽ ghi đè giá trị cũ. Đây là cấu trúc dùng nhiều nhất trong thực tế: từ mã sách ra tên sách, từ mã sinh viên ra điểm, từ từ khóa ra số lần xuất hiện.

    Cài đặt Thứ tự duyệt Cấu trúc Thêm/tìm
    HashMap Không đảm bảo Bảng băm O(1)
    LinkedHashMap Theo thứ tự thêm (hoặc thứ tự truy cập) Bảng băm + danh sách liên kết O(1)
    TreeMap Khóa tăng dần Cây đỏ–đen O(log n)
    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new TreeMap<>();
        stock.put("Java", 5);
        stock.put("Python", 3);
        stock.put("Java", 7);                       // ghi đè giá trị cũ
        stock.putIfAbsent("Go", 1);                 // chỉ thêm nếu chưa có
        System.out.println(stock);
        System.out.println(stock.get("Python") + " " + stock.get("Rust"));   // 3 null
        System.out.println(stock.getOrDefault("Rust", 0));
        System.out.println(stock.containsKey("Go") + " " + stock.containsValue(99));
        stock.remove("Go");
        for (Map.Entry<String, Integer> e : stock.entrySet())
            System.out.println(e.getKey() + " => " + e.getValue());
    }
}

    Điểm cần nhớ: get trả null nếu khóa không tồn tại, vì vậy int n = map.get(k) có thể ném NullPointerException khi unboxing; hãy dùng getOrDefault. Để duyệt, dùng keySet() (các khóa), values() (các giá trị) hoặc entrySet() (cả cặp, hiệu quả nhất khi cần cả hai). Mỗi phần tử của entrySet() có kiểu Map.Entry<K, V>.

    5.2. Mẫu đếm tần suất và gom nhóm

    Hai mẫu lập trình dùng Map thường xuyên nhất. Đếm tần suất: tăng giá trị theo khóa, dùng getOrDefault hoặc merge. Gom nhóm: mỗi khóa ứng với một List, dùng computeIfAbsent để tạo danh sách khi chưa có.

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        String text = "banana";
        Map<Character, Integer> freq = new TreeMap<>();
        for (char c : text.toCharArray())
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        System.out.println(freq);

        Map<Character, Integer> freq2 = new TreeMap<>();
        for (char c : text.toCharArray())
            freq2.merge(c, 1, Integer::sum);       // cách viết gọn hơn
        System.out.println(freq2.equals(freq));
    }
}
    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        String[][] students = {{"CNTT1", "An"}, {"KHMT", "Binh"}, {"CNTT1", "Chi"}};
        Map<String, List<String>> byClass = new TreeMap<>();
        for (String[] s : students)
            byClass.computeIfAbsent(s[0], k -> new ArrayList<>()).add(s[1]);
        for (Map.Entry<String, List<String>> e : byClass.entrySet())
            System.out.println(e.getKey() + ": " + e.getValue());
    }
}

    Mẹo: Muốn in kết quả HashMap theo thứ tự ổn định, chuyển sang TreeMap (sắp theo khóa) bằng new TreeMap<>(hashMap), hoặc dùng sẵn TreeMap/LinkedHashMap từ đầu. Đừng bao giờ dựa vào thứ tự duyệt của HashMap/HashSet: nó có thể khác nhau giữa các phiên bản Java.

    5.3. LinkedHashMap và bộ nhớ đệm LRU

    LinkedHashMap nhớ thứ tự thêm vào. Nếu bật chế độ access-order (tham số thứ ba của hàm tạo là true), phần tử vừa được get hoặc put sẽ chuyển xuống cuối danh sách. Ghi đè removeEldestEntry để tự xóa phần tử cũ nhất khi vượt dung lượng, ta có ngay bộ nhớ đệm LRU (Least Recently Used — xóa phần tử lâu chưa dùng nhất) chỉ với vài dòng.

    Java · chạy thử được
    class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LruCache(int capacity) {
        super(16, 0.75f, true);          // true = access-order
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;        // vượt dung lượng thì bỏ phần tử cũ nhất
    }
}

public class Main {
    public static void main(String[] args) {
        LruCache<String, Integer> cache = new LruCache<>(2);
        cache.put("a", 1);
        cache.put("b", 2);
        cache.get("a");                  // a vừa được dùng
        cache.put("c", 3);               // đầy: loại b (lâu chưa dùng nhất)
        System.out.println(cache.keySet());
    }
}

    Kết quả [a, c]: khóa b bị loại vì sau khi đọc a, b là phần tử lâu nhất chưa được dùng.

    5.4. TreeMap và truy vấn theo khoảng

    TreeMap giữ khóa luôn sắp xếp nên hỗ trợ các truy vấn mà HashMap không có: firstKey, lastKey, floorKey, ceilingKey, headMap, tailMap, subMap (đều là khung nhìn trên map gốc). Khóa của TreeMap phải so sánh được (Comparable) hoặc truyền Comparator lúc tạo.

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> grade = new TreeMap<>();
        grade.put(0, "Yếu");
        grade.put(5, "Trung bình");
        grade.put(7, "Khá");
        grade.put(9, "Giỏi");
        int score = 8;
        System.out.println(grade.floorEntry(score).getValue());   // mốc lớn nhất <= 8
        System.out.println(grade.firstKey() + " " + grade.lastKey());
        System.out.println(grade.headMap(7));                      // khóa < 7
        System.out.println(grade.subMap(5, 9));                    // 5 <= khóa < 9
    }
}

    Mẫu floorEntry rất hay dùng cho bảng quy đổi điểm theo khoảng: thay vì chuỗi if / else if, bạn lưu các mốc vào TreeMap và tra một lần.

    Đã đủ công cụ để đếm, gom nhóm và dựng bộ đệm LRU, bạn thực hành nhóm bài về Map.

    Vừa học xong HashMap, TreeMap và LinkedHashMap, hãy làm nhóm 7.4 để đếm tần suất ký tự, nhóm sinh viên theo lớp và cài một bộ đệm LRU.

    6. Iterator, Comparable và Comparator

    6.1. Iterable và Iterator

    Vòng for-each chạy được trên mọi đối tượng cài đặt Iterable<T>. Bên dưới, compiler dịch for-each thành việc gọi iterator() rồi lặp hasNext() / next(). Bạn dùng Iterator trực tiếp khi cần xóa phần tử trong lúc duyệt.

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
        Iterator<Integer> it = nums.iterator();
        while (it.hasNext()) {
            int x = it.next();
            if (x % 2 == 0) it.remove();    // xóa an toàn phần tử vừa trả về
        }
        System.out.println(nums);

        try {
            for (Integer x : nums) if (x == 3) nums.remove(x);   // sửa trực tiếp khi for-each
        } catch (ConcurrentModificationException e) {
            System.out.println("ConcurrentModificationException");
        }
    }
}

    Nếu bạn gọi list.remove trong lúc for-each đang duyệt, Java ném ConcurrentModificationException (cơ chế "fail-fast"). Cách đúng: dùng Iterator.remove(), hoặc gọn hơn từ Java 8 là removeIf:

    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
        nums.removeIf(x -> x % 2 == 0);
        System.out.println(nums);
    }
}

    Muốn lớp của bạn dùng được trong for-each, hãy cài Iterable<T> và trả về một Iterator<T>. Ví dụ dãy các số chẵn trong đoạn [l, r]:

    Java · chạy thử được
    class EvenRange implements Iterable<Integer> {
    private final int l, r;
    EvenRange(int l, int r) { this.l = l; this.r = r; }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int cur = (l % 2 == 0) ? l : l + 1;
            @Override public boolean hasNext() { return cur <= r; }
            @Override public Integer next() { int v = cur; cur += 2; return v; }
        };
    }
}

public class Main {
    public static void main(String[] args) {
        for (int x : new EvenRange(3, 10)) System.out.print(x + " ");
        System.out.println();
    }
}

    Lớp EvenRange không lưu danh sách nào cả mà sinh số theo yêu cầu; đó là ưu điểm của Iterator: duyệt một nguồn dữ liệu mà không cần biết nó tổ chức ra sao.

    6.2. Comparable: thứ tự tự nhiên

    Để sắp xếp được (Collections.sort, TreeSet, TreeMap, PriorityQueue), Java cần biết cách so sánh hai đối tượng. Lớp có một thứ tự tự nhiên thì cài interface Comparable<T> với phương thức compareTo: trả số âm nếu this đứng trước, 0 nếu bằng, số dương nếu đứng sau. String, Integer, Double đã cài sẵn.

    Java · chạy thử được
    class Student implements Comparable<Student> {
    final String name; final double gpa;
    Student(String name, double gpa) { this.name = name; this.gpa = gpa; }

    @Override
    public int compareTo(Student o) {
        return Double.compare(o.gpa, this.gpa);    // GPA giảm dần (cao đứng trước)
    }
    @Override public String toString() { return name + "(" + gpa + ")"; }
}

public class Main {
    public static void main(String[] args) {
        List<Student> list = new ArrayList<>();
        list.add(new Student("An", 3.2));
        list.add(new Student("Binh", 3.8));
        list.add(new Student("Chi", 3.5));
        Collections.sort(list);
        System.out.println(list);
    }
}

    Lưu ý: Dùng Double.compare, Integer.compare thay vì tự trừ (a - b) vì phép trừ có thể tràn số với giá trị lớn và double không trừ ra được int. Thứ tự của compareTo nên nhất quán với equals (hai đối tượng bằng nhau thì compareTo trả 0), nếu không TreeSet và HashSet sẽ cho kết quả khác nhau.

    6.3. Comparator: nhiều cách sắp xếp

    Comparable chỉ cho một thứ tự gắn với lớp. Thực tế bạn cần nhiều cách: theo tên, theo điểm, theo lớp rồi điểm… Comparator<T> là một đối tượng so sánh tách rời với phương thức compare(a, b). Từ Java 8 cách viết gọn nhất là lambda hoặc các hàm dựng sẵn như Comparator.comparing, thenComparing, reversed.

    Java · chạy thử được
    class Student {
    final String cls, name; final double gpa;
    Student(String cls, String name, double gpa) { this.cls = cls; this.name = name; this.gpa = gpa; }
    String getCls() { return cls; }
    String getName() { return name; }
    double getGpa() { return gpa; }
    @Override public String toString() { return cls + "/" + name + "/" + gpa; }
}

public class Main {
    public static void main(String[] args) {
        List<Student> list = new ArrayList<>(List.of(
            new Student("B", "Chi", 8.0), new Student("A", "An", 7.0),
            new Student("A", "Binh", 9.0), new Student("B", "Dung", 8.0)));

        list.sort(Comparator.comparing(Student::getName));
        System.out.println("Theo tên:         " + list);

        list.sort(Comparator.comparing(Student::getCls)
                            .thenComparing(Student::getGpa, Comparator.reverseOrder())
                            .thenComparing(Student::getName));
        System.out.println("Lớp, điểm giảm:   " + list);

        list.sort((x, y) -> Double.compare(y.getGpa(), x.getGpa()));   // lambda viết tay
        System.out.println("Điểm giảm (lambda): " + list);
    }
}

    Chuỗi comparing(...).thenComparing(...) đọc như một câu: "so theo lớp, nếu bằng thì theo điểm giảm dần, nếu vẫn bằng thì theo tên". Collections.sort và List.sort là sắp xếp ổn định (stable): hai phần tử bằng nhau giữ nguyên thứ tự ban đầu, nên bạn có thể sắp theo từng tiêu chí liên tiếp nếu cần.

    Comparable<T> Comparator<T>
    Nằm ở đâu Bên trong lớp (compareTo(T o)) Đối tượng riêng bên ngoài (compare(T a, T b))
    Số thứ tự Một thứ tự tự nhiên Bao nhiêu tùy ý
    Sửa được lớp? Cần sửa lớp Không cần (dùng cho cả lớp thư viện)
    Dùng khi Thứ tự hiển nhiên (số, chuỗi, ngày) Sắp theo ngữ cảnh, nhiều tiêu chí

    Mẹo: Dùng Comparator.comparing(Student::getGpa).reversed() để đảo chiều; với kiểu nguyên thủy dùng comparingInt/comparingDouble để tránh boxing. Muốn TreeMap/TreeSet sắp theo cách riêng, truyền Comparator vào hàm tạo: new TreeSet<>(Comparator.reverseOrder()).

    Vừa đủ để bạn duyệt và sắp xếp mọi collection theo ý mình.

    Vừa học xong Iterator, Comparable và Comparator, hãy làm nhóm 7.5: đếm bằng Iterator, sắp xếp sinh viên nhiều tiêu chí, và tự cài một Iterable.

    7. Lớp tiện ích Collections

    Lớp Collections (số nhiều, khác interface Collection) cung cấp các phương thức tĩnh làm việc trên collection; còn Arrays làm việc trên mảng (Buổi 3). Những hàm hay dùng nhất:

    Phương thức Tác dụng Yêu cầu
    sort(list) / sort(list, cmp) Sắp xếp tại chỗ (ổn định) Phần tử Comparable hoặc có Comparator
    reverse(list) Đảo ngược thứ tự —
    max(c) / min(c) Phần tử lớn nhất / nhỏ nhất Comparable hoặc Comparator
    frequency(c, x) Đếm số lần x xuất hiện Dùng equals
    binarySearch(list, key) Tìm nhị phân, trả chỉ số (âm nếu không có) List đã sắp tăng dần
    swap(list, i, j) Đổi chỗ hai phần tử —
    rotate(list, k) Dịch vòng k bước sang phải —
    nCopies(n, x) Danh sách bất biến gồm n bản sao —
    disjoint(a, b) true nếu hai collection không chung phần tử —
    unmodifiableList(list) Khung nhìn chỉ đọc Sửa → UnsupportedOperationException
    Java · chạy thử được
    public class Main {
    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(List.of(4, 1, 3, 1, 5));
        Collections.sort(a);
        System.out.println(a + " max=" + Collections.max(a) + " min=" + Collections.min(a));
        System.out.println("Số lần xuất hiện của 1: " + Collections.frequency(a, 1));
        System.out.println("binarySearch(4) = " + Collections.binarySearch(a, 4));
        Collections.reverse(a);
        System.out.println(a);
        Collections.swap(a, 0, a.size() - 1);
        Collections.rotate(a, 2);
        System.out.println(a);
        System.out.println(Collections.nCopies(3, "ha") + " " + Collections.disjoint(a, List.of(9)));
    }
}

    Đoạn mã trên in lần lượt danh sách đã sắp xếp cùng max/min, tần suất, vị trí tìm nhị phân, rồi các thao tác đảo, đổi chỗ, dịch vòng. Riêng unmodifiableList thường dùng để bảo vệ dữ liệu khi trả danh sách ra khỏi lớp (nhắc lại đóng gói ở Buổi 5): người gọi đọc được nhưng không sửa được danh sách nội bộ.

    Java · chạy thử được
    class Library {
    private final List<String> books = new ArrayList<>(List.of("Java", "SQL"));
    List<String> getBooks() { return Collections.unmodifiableList(books); }
    void add(String b) { books.add(b); }
}

public class Main {
    public static void main(String[] args) {
        Library lib = new Library();
        List<String> view = lib.getBooks();
        try {
            view.add("Hack");
        } catch (UnsupportedOperationException e) {
            System.out.println("Không được sửa trực tiếp");
        }
        lib.add("Python");
        System.out.println(view);      // khung nhìn phản ánh thay đổi hợp lệ
    }
}

    Cảnh báo: unmodifiableList chỉ là khung nhìn, không phải bản sao: nếu lớp gốc còn sửa danh sách, khung nhìn sẽ thấy thay đổi. Muốn bản chụp độc lập hãy dùng List.copyOf(list) hoặc new ArrayList<>(list). Cũng tránh Collections.shuffle không có Random cố định seed vì cho kết quả khác nhau mỗi lần chạy.

    Phần cuối của buổi là các bài trộn nhiều kiến thức: nhóm theo khóa, sắp xếp tùy biến, PriorityQueue.

    Vừa học xong toàn bộ khung Collections, hãy làm nhóm 7.6 (gom nhóm anagram, Top K từ phổ biến) để ghép Map, Comparator và cấu trúc dữ liệu phù hợp.

    Sai lầm thường gặp

    Sai lầm Hậu quả Cách đúng
    Dùng raw type (List không có <…>) hoặc Object thay generics Mất kiểm tra kiểu, ClassCastException lúc chạy Luôn khai báo List<String>, Box<T>
    Dùng List<Number> làm tham số để nhận List<Integer> Lỗi biên dịch vì generics bất biến List<? extends Number>
    Nhầm remove(int) với remove(Object) trên List<Integer> Xóa sai phần tử hoặc không xóa remove(Integer.valueOf(x)) để xóa theo giá trị
    Dựa vào thứ tự duyệt của HashSet/HashMap Kết quả không ổn định giữa các lần/phiên bản LinkedHashMap, TreeMap hoặc sắp xếp trước khi in
    Ghi đè equals mà không ghi đè hashCode HashSet/HashMap coi hai đối tượng bằng nhau là khác nhau Ghi đè cả hai (Objects.hash)
    Xóa phần tử trong for-each ConcurrentModificationException Iterator.remove() hoặc removeIf
    compare tự trừ (a - b) hoặc quên điều kiện phụ Tràn số, sắp xếp sai hoặc không ổn định Integer.compare, Double.compare, thenComparing
    In PriorityQueue để xem thứ tự Không thấy thứ tự sắp xếp poll() lần lượt cho đến khi rỗng
    Dùng get(i) trong vòng lặp trên LinkedList Chậm O(n²) Dùng for-each hoặc ArrayList

    Tóm tắt

    Chủ đề Nhớ
    Generics Box<T>, <T> void f(T x); compiler kiểm tra kiểu, lúc chạy kiểu bị xóa
    Giới hạn kiểu <T extends Comparable<T>>, nhiều giới hạn nối bằng &
    Wildcard PECS: đọc → ? extends, ghi → ? super
    List / Set / Deque ArrayList mặc định; HashSet loại trùng; TreeSet sắp xếp; ArrayDeque làm stack/queue
    Map HashMap nhanh; LinkedHashMap giữ thứ tự (LRU); TreeMap sắp theo khóa, có floor/ceiling
    Duyệt for-each cho đọc; Iterator.remove() / removeIf để xóa
    Sắp xếp Comparable thứ tự tự nhiên; Comparator.comparing(...).thenComparing(...)
    Collections sort, reverse, max/min, frequency, binarySearch, unmodifiableList

    Bài tập thực hành của buổi