Collections Framework trong Java: Làm Chủ Cấu Trúc Dữ Liệu

Collections Framework là gì?

Collections Framework là kiến trúc thống nhất để lưu trữ và thao tác nhóm đối tượng trong Java. Nó cung cấp các interfaces, implementations và algorithms để xử lý dữ liệu hiệu quả.

Phân cấp Collections

Collection (interface)
├── List (interface)
│   ├── ArrayList
│   ├── LinkedList
│   └── Vector
├── Set (interface)
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
└── Queue (interface)
    ├── PriorityQueue
    └── Deque
        └── ArrayDeque

Map (interface - không extend Collection)
├── HashMap
├── LinkedHashMap
└── TreeMap

List Interface

List lưu trữ phần tử có thứ tự và cho phép duplicate.

ArrayList

Mảng động, truy cập nhanh theo index:

List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("JavaScript");

// Truy cập: O(1)
String lang = list.get(0); // "Java"

// Tìm kiếm: O(n)
int index = list.indexOf("Python"); // 1

// Xóa: O(n)
list.remove("Python");
list.remove(0);

// Duyệt
for (String item : list) {
    System.out.println(item);
}

Khi nào dùng:

Cần truy cập ngẫu nhiên thường xuyên
Ít thêm/xóa phần tử ở giữa
Đọc nhiều hơn ghi

LinkedList

Danh sách liên kết đôi, thêm/xóa nhanh:

List<String> list = new LinkedList<>();
list.add("First");
list.add("Second");

// Thêm đầu/cuối: O(1)
((LinkedList<String>) list).addFirst("Zero");
((LinkedList<String>) list).addLast("Third");

// Truy cập: O(n)
String item = list.get(2);

// Xóa đầu/cuối: O(1)
((LinkedList<String>) list).removeFirst();

Khi nào dùng:

Thêm/xóa phần tử thường xuyên
Ít truy cập ngẫu nhiên
Implement Queue/Stack

Vector (Legacy)

Giống ArrayList nhưng synchronized. Hiện nay ít dùng.

// ❌ Cũ
Vector<String> vector = new Vector<>();

// ✅ Mới hơn
List<String> list = Collections.synchronizedList(new ArrayList<>());

Set Interface

Set lưu trữ phần tử không trùng lặp.

HashSet

Dựa trên hash table, không đảm bảo thứ tự:

Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple"); // Không thêm được (duplicate)

// Kiểm tra tồn tại: O(1)
boolean exists = set.contains("Apple"); // true

// Size
System.out.println(set.size()); // 2

// Duyệt (thứ tự không xác định)
for (String fruit : set) {
    System.out.println(fruit);
}

Khi nào dùng:

Cần loại bỏ duplicate
Không quan tâm thứ tự
Kiểm tra tồn tại nhanh

LinkedHashSet

Giữ thứ tự insertion:

Set<String> set = new LinkedHashSet<>();
set.add("C");
set.add("A");
set.add("B");

// Output: C, A, B (giữ thứ tự thêm vào)
set.forEach(System.out::println);

TreeSet

Sắp xếp tự động (tự nhiên hoặc Comparator):

Set<Integer> set = new TreeSet<>();
set.add(5);
set.add(1);
set.add(3);

// Output: 1, 3, 5 (đã sắp xếp)
set.forEach(System.out::println);

// Custom comparator
Set<String> names = new TreeSet<>(Comparator.reverseOrder());
names.add("Alice");
names.add("Bob");
names.add("Charlie");
// Output: Charlie, Bob, Alice

Khi nào dùng:

Cần dữ liệu luôn được sắp xếp
Range operations (subSet, headSet, tailSet)

Map Interface

Map lưu trữ cặp key-value, key không trùng lặp.

HashMap

Hash table, truy cập nhanh O(1):

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);
map.put("Charlie", 35);

// Get: O(1)
int age = map.get("Alice"); // 25

// Kiểm tra key
if (map.containsKey("Bob")) {
    System.out.println("Bob tồn tại");
}

// Kiểm tra value
if (map.containsValue(30)) {
    System.out.println("Có người 30 tuổi");
}

// Duyệt
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

// Lambda
map.forEach((key, value) -> {
    System.out.println(key + " = " + value);
});

Java 8+ methods:

// getOrDefault
int age = map.getOrDefault("Unknown", 0);

// putIfAbsent
map.putIfAbsent("David", 40);

// computeIfAbsent
map.computeIfAbsent("Eve", k -> 45);

// merge
map.merge("Alice", 1, (oldVal, newVal) -> oldVal + newVal);

LinkedHashMap

Giữ thứ tự insertion:

Map<String, Integer> map = new LinkedHashMap<>();
map.put("First", 1);
map.put("Second", 2);
map.put("Third", 3);

// Output: First, Second, Third (đúng thứ tự)
map.forEach((k, v) -> System.out.println(k));

LRU Cache:

Map<String, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 100; // Max 100 entries
    }
};

TreeMap

Sắp xếp theo key:

Map<String, Integer> map = new TreeMap<>();
map.put("Charlie", 35);
map.put("Alice", 25);
map.put("Bob", 30);

// Output: Alice, Bob, Charlie (sorted by key)
map.forEach((k, v) -> System.out.println(k + " = " + v));

Queue Interface

FIFO (First In First Out).

PriorityQueue

Sắp xếp theo priority:

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

// Poll theo thứ tự: 1, 3, 5
while (!queue.isEmpty()) {
    System.out.println(queue.poll());
}

// Custom comparator
Queue<String> pq = new PriorityQueue<>(Comparator.reverseOrder());

Deque (ArrayDeque)

Double-ended queue, thêm/xóa 2 đầu:

Deque<String> deque = new ArrayDeque<>();

// Thêm
deque.addFirst("First");
deque.addLast("Last");

// Xóa
String first = deque.removeFirst();
String last = deque.removeLast();

// Peek
String peekFirst = deque.peekFirst();

// Stack operations
deque.push("Top");
String top = deque.pop();

So sánh Performance

List

Operation	ArrayList	LinkedList
get(i)	O(1)	O(n)
add(e)	O(1)*	O(1)
add(i,e)	O(n)	O(n)
remove(i)	O(n)	O(n)

*Amortized O(1)

Set/Map

Collection	Add	Contains	Remove
HashSet	O(1)	O(1)	O(1)
TreeSet	O(log n)	O(log n)	O(log n)
HashMap	O(1)	O(1)	O(1)
TreeMap	O(log n)	O(log n)	O(log n)

Utility Classes

Collections

List<Integer> list = Arrays.asList(3, 1, 4, 1, 5);

// Sort
Collections.sort(list);

// Reverse
Collections.reverse(list);

// Shuffle
Collections.shuffle(list);

// Binary search (phải sorted trước)
int index = Collections.binarySearch(list, 4);

// Min/Max
int min = Collections.min(list);
int max = Collections.max(list);

// Unmodifiable
List<Integer> readOnly = Collections.unmodifiableList(list);

// Synchronized
List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());

// Empty collections
List<String> empty = Collections.emptyList();

Arrays

// Array to List
List<String> list = Arrays.asList("A", "B", "C");

// Sort array
int[] arr = {3, 1, 4, 1, 5};
Arrays.sort(arr);

// Binary search
int index = Arrays.binarySearch(arr, 4);

// Fill
Arrays.fill(arr, 0);

// Copy
int[] copy = Arrays.copyOf(arr, arr.length);

// Stream
Arrays.stream(arr).forEach(System.out::println);

Ví dụ thực tế

1. Đếm tần suất từ

public Map<String, Integer> countWords(String text) {
    Map<String, Integer> wordCount = new HashMap<>();
    
    String[] words = text.toLowerCase().split("\\s+");
    for (String word : words) {
        wordCount.merge(word, 1, Integer::sum);
    }
    
    return wordCount;
}

2. Loại bỏ duplicate giữ thứ tự

public List<String> removeDuplicates(List<String> list) {
    return new ArrayList<>(new LinkedHashSet<>(list));
}

3. Group by

Map<String, List<User>> usersByCity = users.stream()
    .collect(Collectors.groupingBy(User::getCity));

4. Cache với LRU

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

5. Top K elements

public List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.merge(num, 1, Integer::sum);
    }
    
    PriorityQueue<Integer> heap = new PriorityQueue<>(
        Comparator.comparingInt(count::get)
    );
    
    for (int num : count.keySet()) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    
    return new ArrayList<>(heap);
}

Best Practices

Code to interface, không phải implementation:

// ✅ GOOD
List<String> list = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();

// ❌ BAD
ArrayList<String> list = new ArrayList<>();
HashMap<String, Integer> map = new HashMap<>();

Chọn collection phù hợp:
- ArrayList: truy cập nhiều
- LinkedList: thêm/xóa nhiều
- HashSet: unique, không quan tâm thứ tự
- TreeSet: unique + sorted
- HashMap: key-value, truy cập nhanh
Initial capacity cho performance:

// Nếu biết trước size
List<String> list = new ArrayList<>(1000);
Map<String, Integer> map = new HashMap<>(1000);

Immutable collections (Java 9+):

List<String> list = List.of("A", "B", "C");
Set<Integer> set = Set.of(1, 2, 3);
Map<String, Integer> map = Map.of("A", 1, "B", 2);

Kết luận

Collections Framework là nền tảng quan trọng trong Java:

Chọn đúng collection cho use case
Hiểu rõ performance characteristics
Sử dụng utility classes hiệu quả
Code to interface

Nắm vững Collections giúp bạn viết code Java hiệu quả và professional hơn!