📚 Bài viết thuộc series Java Backend Zero to Hello 📌 Phần: Phase 1: Java Core Cơ Bản | Bài 13/86

---

BÀI 1.11: COLLECTIONS FRAMEWORK (PHẦN 2)

Mục tiêu

• Sử dụng Map và các implementation
• Sử dụng Queue và Deque
• Hiểu Comparable và Comparator
• Thực hành các bài toán thường gặp

---

1. MAP INTERFACE

Map lưu trữ cặp key-value, mỗi key là duy nhất.

1.1 HashMap

• Dựa trên bảng băm
• Không đảm bảo thứ tự
• Cho phép 1 key null, nhiều value null
• Thêm/tìm/xóa O(1)

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> map = new HashMap<>();

// Thêm
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);

// Lấy giá trị
int value = map.get("Apple");        // 1
Integer v = map.get("Mango");        // null
Integer v2 = map.getOrDefault("Mango", 0);  // 0

// Kiểm tra
boolean hasKey = map.containsKey("Apple");
boolean hasValue = map.containsValue(2);

// Xóa
map.remove("Apple");

// Cập nhật
map.put("Apple", 10);              // Ghi đè
map.putIfAbsent("Apple", 20);      // Chỉ thêm nếu chưa có
map.merge("Apple", 5, Integer::sum);  // Cộng dồn

// Kích thước
int size = map.size();
boolean isEmpty = map.isEmpty();

1.2 Duyệt Map

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

// Cách 1: entrySet
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

// Cách 2: keySet
for (String key : map.keySet()) {
    System.out.println(key + " = " + map.get(key));
}

// Cách 3: values
for (Integer value : map.values()) {
    System.out.println(value);
}

// Cách 4: forEach (Java 8+)
map.forEach((key, value) -> System.out.println(key + " = " + value));

1.3 LinkedHashMap

• Duy trì thứ tự thêm vào
• Chậm hơn HashMap một chút

Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("C", 3);
linkedMap.put("A", 1);
linkedMap.put("B", 2);
// Thứ tự: C, A, B

1.4 TreeMap

• Sắp xếp theo key
• Thêm/tìm/xóa O(log n)

import java.util.TreeMap;

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("C", 3);
treeMap.put("A", 1);
treeMap.put("B", 2);
// Thứ tự: A, B, C

// Lấy phần tử đầu/cuối
Map.Entry<String, Integer> first = treeMap.firstEntry();
Map.Entry<String, Integer> last = treeMap.lastEntry();

1.5 So sánh các Map

Tiêu chí	HashMap	LinkedHashMap	TreeMap
Thứ tự	Không	Thứ tự thêm	Sắp xếp theo key
Hiệu năng	O(1)	O(1)	O(log n)
Null key	Cho phép 1	Cho phép 1	Không cho phép
Khi nào dùng	Mặc định	Cần thứ tự	Cần sắp xếp

---

2. QUEUE INTERFACE

Hàng đợi - FIFO (First In First Out).

2.1 LinkedList implements Queue

import java.util.Queue;
import java.util.LinkedList;

Queue<String> queue = new LinkedList<>();

queue.offer("A");   // Thêm (trả về true/false)
queue.offer("B");
queue.offer("C");

String head = queue.peek();   // Lấy đầu, không xóa - "A"
String removed = queue.poll(); // Lấy và xóa đầu - "A"

System.out.println(queue);  // [B, C]

2.2 PriorityQueue

• Hàng đợi ưu tiên - phần tử nhỏ nhất ở đầu
• Dựa trên heap

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);

System.out.println(pq.poll());  // 1
System.out.println(pq.poll());  // 3
System.out.println(pq.poll());  // 5

// Comparator tùy chỉnh
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());

2.3 ArrayDeque

• Deque (Double-ended queue) - thêm/xóa 2 đầu
• Hiệu quả hơn Stack và LinkedList

import java.util.ArrayDeque;

ArrayDeque<String> deque = new ArrayDeque<>();
deque.offerFirst("A");   // Thêm đầu
deque.offerLast("B");    // Thêm cuối

deque.peekFirst();       // Lấy đầu
deque.peekLast();        // Lấy cuối

deque.pollFirst();       // Lấy và xóa đầu
deque.pollLast();        // Lấy và xóa cuối

---

3. COMPARABLE VÀ COMPARATOR

3.1 Comparable - So sánh tự nhiên

Class tự định nghĩa cách so sánh với chính nó.

public class Student implements Comparable<Student> {
    private String name;
    private int age;
    private double gpa;

    @Override
    public int compareTo(Student other) {
        // Sắp xếp theo GPA giảm dần
        return Double.compare(other.gpa, this.gpa);
    }
}

List<Student> students = new ArrayList<>();
Collections.sort(students);  // Sắp xếp theo compareTo

3.2 Comparator - So sánh tùy chỉnh

Định nghĩa cách so sánh bên ngoài class.

// Comparator cho Student
Comparator<Student> byName = (s1, s2) -> s1.getName().compareTo(s2.getName());
Comparator<Student> byAge = (s1, s2) -> Integer.compare(s1.getAge(), s2.getAge());
Comparator<Student> byGpaDesc = (s1, s2) -> Double.compare(s2.getGpa(), s1.getGpa());

// Sử dụng
students.sort(byName);
students.sort(byAge);
students.sort(byGpaDesc);

// Chain comparator
students.sort(Comparator.comparing(Student::getName)
                        .thenComparing(Student::getAge));

3.3 So sánh

Comparable	Comparator
Trong class	Bên ngoài class
1 cách so sánh	Nhiều cách
compareTo(T o)	compare(T o1, T o2)
Collections.sort(list)	list.sort(comparator)

---

4. CÁC BÀI TOÁN THƯỜNG GẶP

4.1 Đếm tần suất

public static Map<Character, Integer> countChars(String s) {
    Map<Character, Integer> map = new HashMap<>();
    for (char c : s.toCharArray()) {
        map.merge(c, 1, Integer::sum);
    }
    return map;
}

4.2 Nhóm phần tử

List<String> words = Arrays.asList("apple", "ant", "banana", "blue", "cherry");

Map<Character, List<String>> grouped = words.stream()
    .collect(Collectors.groupingBy(s -> s.charAt(0)));

System.out.println(grouped);
// {a=[apple, ant], b=[banana, blue], c=[cherry]}

4.3 Tìm phần tử xuất hiện nhiều nhất

public static <T> T findMostFrequent(List<T> list) {
    Map<T, Integer> freq = new HashMap<>();
    for (T item : list) {
        freq.merge(item, 1, Integer::sum);
    }
    return Collections.max(freq.entrySet(), Map.Entry.comparingByValue()).getKey();
}

4.4 Stack với Deque

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);   // Thêm
stack.push(2);
stack.push(3);

stack.pop();     // Lấy và xóa - 3
stack.peek();    // Lấy không xóa - 2

---

5. IMMUTABLE COLLECTIONS (Java 9+)

// Tạo collection không thể thay đổi
List<String> immutableList = List.of("A", "B", "C");
Set<Integer> immutableSet = Set.of(1, 2, 3);
Map<String, Integer> immutableMap = Map.of("A", 1, "B", 2);

// immutableList.add("D");  // ❌ UnsupportedOperationException

// Chuyển từ mutable sang immutable
List<String> mutable = new ArrayList<>(Arrays.asList("A", "B"));
List<String> immutable = Collections.unmodifiableList(mutable);

---

6. BÀI TẬP THỰC HÀNH

Bài 1: Từ điển đơn giản

public class Dictionary {
    private Map<String, String> words = new HashMap<>();

    public void add(String word, String meaning) {
        words.put(word.toLowerCase(), meaning);
    }

    public String lookup(String word) {
        return words.get(word.toLowerCase());
    }

    public List<String> getAllWords() {
        return new ArrayList<>(words.keySet());
    }
}

Bài 2: Quản lý điểm học sinh

• Lưu trữ điểm theo môn học
• Tính điểm trung bình
• Tìm học sinh có điểm cao nhất

Bài 3: Hàng đợi ưu tiên công việc

public class TaskScheduler {
    private PriorityQueue<Task> tasks = new PriorityQueue<>(
        Comparator.comparingInt(Task::getPriority).reversed()
    );

    public void addTask(Task task) {
        tasks.offer(task);
    }

    public Task getNext() {
        return tasks.poll();
    }
}

Bài 4: Cache đơn giản với LinkedHashMap

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

---

7. TÓM TẮT

Collection	Đặc điểm	Khi nào dùng
HashMap	Key-value, không thứ tự	Mặc định
LinkedHashMap	Key-value, có thứ tự	Cần thứ tự thêm
TreeMap	Key-value, sắp xếp	Cần sắp xếp theo key
Queue	FIFO	Hàng đợi
PriorityQueue	Ưu tiên	Cần xử lý theo độ ưu tiên
Deque	2 đầu	Stack, hàng đợi 2 chiều
Comparable	So sánh tự nhiên	Class có 1 cách so sánh
Comparator	So sánh tùy chỉnh	Nhiều cách so sánh

---

Bài tiếp theo: 1.12 Wrapper class & Autoboxing

---

🧭 Điều Hướng Series

⬅️ Bài trước: BÀI 1.10: COLLECTIONS FRAMEWORK (PHẦN 1)

📋 Lộ trình tổng quan: Xem Toàn Bộ Series

➡️ Bài tiếp theo: BÀI 1.12: WRAPPER CLASS & AUTOBOXING