Java Collections Framework: Tối ưu hóa hiệu năng qua cấu trúc dữ liệu

1. Lời mở đầu: Collections không chỉ là “công cụ chứa dữ liệu”

Khi mới học Java, chúng ta thường nghĩ: “ArrayList để lưu danh sách, HashMap để lưu key-value, xong!”. Nhưng trong thực tế, việc chọn sai Collection có thể làm ứng dụng chậm đi hàng ngàn lần.

Hãy tưởng tượng bạn đang xây dựng một hệ thống xử lý 10 triệu bản ghi dữ liệu từ database. Nếu bạn chọn LinkedList thay vì ArrayList cho thao tác tìm kiếm, thời gian xử lý có thể tăng từ 0.5 giây lên 30 phút. Đó chính là sức mạnh của việc hiểu đúng về Collections Framework.

2. Big O Notation: Ngôn ngữ của Performance

2.1. Big O là gì và tại sao nó quan trọng?

Big O không phải là một công thức toán học khô khan. Nó là cách chúng ta đo lường tốc độ tăng trưởng của thời gian thực thi khi dữ liệu tăng lên.

Ví dụ thực tế:

Bạn cần tìm một người bạn tên “Minh” trong một danh sách:

  • O(1) - Constant Time: Bạn có số điện thoại của Minh, gọi trực tiếp → Luôn mất 1 bước
  • O(log n) - Logarithmic: Danh bạ điện thoại được sắp xếp theo ABC, bạn mở giữa sách, xem “M” ở bên nào → Mỗi lần giảm một nửa số trang cần tìm
  • O(n) - Linear: Bạn phải gọi từng người một trong danh sách 1000 người → 1000 cuộc gọi trong worst case
  • O(n²) - Quadratic: So sánh từng cặp người với nhau để tìm ai có tên giống nhau → 1 triệu phép so sánh (1000 × 1000)

2.2. Big O trong Collections Framework

Bảng tóm tắt quan trọng:

Collection        | Add   | Remove | Get   | Contains | Find
------------------|-------|--------|-------|----------|-------
ArrayList         | O(1)* | O(n)   | O(1)  | O(n)     | O(n)
LinkedList        | O(1)  | O(1)** | O(n)  | O(n)     | O(n)
HashSet           | O(1)  | O(1)   | N/A   | O(1)     | O(1)
TreeSet           | O(log n) | O(log n) | N/A | O(log n) | O(log n)
HashMap           | O(1)  | O(1)   | O(1)  | O(1)     | O(1)
TreeMap           | O(log n) | O(log n) | O(log n) | O(log n) | O(log n)
LinkedHashMap     | O(1)  | O(1)   | O(1)  | O(1)     | O(1)

* Amortized time (trung bình)
** At head or tail

Nhưng đừng chỉ nhìn vào bảng này mà ra quyết định! Hãy hiểu tại sao nó lại như vậy.

3. ArrayList vs LinkedList: Cuộc chiến của hai triết lý

3.1. ArrayList - Tư duy “Mảng liên tiếp”

Cấu trúc bên trong:

Memory Layout:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │   │   │   │  ← Continuous memory block
└───┴───┴───┴───┴───┴───┴───┴───┘
  0   1   2   3   4   5   6   7    ← Index

Tại sao Get O(1)?

  • Java biết địa chỉ bắt đầu của mảng: baseAddress
  • Để lấy phần tử index i: address = baseAddress + (i × sizeOfElement)
  • Không cần loop, tính toán trực tiếp!

Tại sao Remove O(n)?

Xóa phần tử index 2:
Before: [A, B, C, D, E]
         0  1  2  3  4

Step 1: Xóa C
Step 2: Dịch D, E sang trái
        [A, B, D, E]  ← Phải di chuyển 2 phần tử

Worst case: Xóa index 0 → Di chuyển toàn bộ mảng!

3.2. LinkedList - Tư duy “Chuỗi liên kết”

Cấu trúc bên trong:

Memory Layout (Doubly Linked List):
┌─────────┐    ┌─────────┐    ┌─────────┐
│ Prev: ∅ │◄───┤ Prev: A │◄───┤ Prev: B │
│ Data: A │    │ Data: B │    │ Data: C │
│ Next: B ├───►│ Next: C ├───►│ Next: ∅ │
└─────────┘    └─────────┘    └─────────┘

Tại sao Get O(n)?

  • Không có index trực tiếp
  • Phải đi từng bước từ head: head → next → next → ... → target
  • Lấy phần tử cuối cùng trong list 10,000 phần tử? 10,000 bước!

Tại sao Remove O(1) ở đầu/cuối?

Xóa node B:
Step 1: A.next = C
Step 2: C.prev = A
Step 3: Xóa B

Chỉ cần thay đổi 2 con trỏ! Không di chuyển dữ liệu.

3.3. Khi nào dùng cái nào?

Dùng ArrayList khi:

  • ✅ Truy cập random (get by index) nhiều
  • ✅ Thêm/xóa ở cuối list
  • ✅ Iterate qua toàn bộ list (cache-friendly)
  • ✅ 95% cases thực tế

Dùng LinkedList khi:

  • ✅ Thêm/xóa ở đầu list thường xuyên
  • ✅ Implement Queue/Deque
  • ✅ Không cần random access
  • ❌ Hiếm khi dùng trong thực tế

Benchmark thực tế:

Test: Add 1,000,000 elements và get random 1,000,000 times

ArrayList:
- Add: 45ms
- Get: 2ms (O(1) per operation)
- Total: 47ms

LinkedList:
- Add: 120ms (more overhead per node)
- Get: 15,000ms (O(n) per operation) 
- Total: 15,120ms

ArrayList nhanh hơn 300+ lần!

4. HashMap vs TreeMap: Sự đánh đổi giữa tốc độ và trật tự

4.1. HashMap - Phép màu của Hash Function

Nguyên lý hoạt động:

HashMap không lưu data tuần tự. Nó dùng Hash Function để chuyển key thành một số nguyên, rồi dùng số đó để tính vị trí trong mảng.

Ví dụ minh họa:
put("Alice", 25)

Step 1: Hash function
hashCode("Alice") → 2594821 (một số nguyên lớn)

Step 2: Map to array index
index = 2594821 % arrayLength
      = 2594821 % 16
      = 5

Step 3: Store at array[5]
┌───┬───┬───┬───┬───┬─────────────┬───┬───┐
│   │   │   │   │   │Alice → 25  │   │   │
└───┴───┴───┴───┴───┴─────────────┴───┴───┘
  0   1   2   3   4       5         6   7

Tại sao Get/Put O(1)?

  • Tính hash của key → Tính index → Truy cập trực tiếp mảng
  • Không cần loop qua tất cả elements!

Hash Collision - Vấn đề nan giải:

Điều gì xảy ra nếu 2 keys khác nhau có cùng hash?

put("Alice", 25) → index 5
put("Bob", 30)   → index 5  ← Collision!

Giải pháp: Chaining (Java 8-)
┌───┬───┬───┬───┬───┬────────────────────┬───┬───┐
│   │   │   │   │   │ Alice→25 → Bob→30 │   │   │
└───┴───┴───┴───┴───┴────────────────────┴───┴───┘
                        Linked List

Java 8+: Nếu chain quá dài (>8), chuyển thành Red-Black Tree
→ Worst case O(n) → O(log n)

Load Factor & Resizing:

HashMap có capacity (kích thước mảng) và load factor (0.75 default).

Initial capacity: 16
Load factor: 0.75

Khi size > 16 × 0.75 = 12:
→ Resize mảng lên 32
→ Rehash toàn bộ elements (expensive!)

Đây là lý do Add là O(1) "amortized" - 
thỉnh thoảng phải resize tốn O(n)

4.2. TreeMap - Cây đỏ-đen và trật tự tự nhiên

Cấu trúc bên trong:

TreeMap sử dụng Red-Black Tree - một Binary Search Tree tự cân bằng.

TreeMap structure:
           50 (Black)
          /  \
      30(R)   70(R)
     /  \     /  \
   20  40  60   80
   
Properties:
1. Every node is Red or Black
2. Root is Black
3. Red nodes have Black children
4. All paths have same number of Black nodes
→ Đảm bảo cân bằng → Height = O(log n)

Tại sao Put/Get O(log n)?

Khi insert/search, chúng ta đi từ root xuống leaf:

  • Mỗi bước so sánh và đi sang trái hoặc phải
  • Height của tree là log(n)
  • Ví dụ: 1,000,000 phần tử → chỉ cần ~20 bước so sánh!

TreeMap tự động sắp xếp:

TreeMap<String, Integer> map = new TreeMap<>();
map.put("Zebra", 1);
map.put("Apple", 2);
map.put("Mango", 3);

System.out.println(map);
// {Apple=2, Mango=3, Zebra=1}  ← Sorted by key!

Iterate qua TreeMap → đã sorted!
for (String key : map.keySet()) {
    // Apple → Mango → Zebra
}

4.3. HashMap vs TreeMap: Decision Matrix

Dùng HashMap khi:

  • ✅ Cần tốc độ tối đa (O(1))
  • ✅ Không quan tâm thứ tự keys
  • ✅ Lookup, insert, delete thường xuyên
  • ✅ Default choice cho 90% cases

Dùng TreeMap khi:

  • ✅ Cần keys được sắp xếp tự động
  • ✅ Cần range queries: subMap(from, to)
  • ✅ Cần firstKey(), lastKey(), floorKey(), ceilingKey()
  • ✅ Acceptable với O(log n)

Ví dụ thực tế:

Use case: Cache lưu user sessions

HashMap:
✅ Fast lookup: "Session ID" → User object
✅ Không cần order
→ Perfect choice!

Use case: Leaderboard game (high score)

TreeMap<Integer, Player>:
✅ Auto-sorted by score
✅ firstKey() → Highest score
✅ lastKey() → Lowest score
→ Great fit!

4.4. LinkedHashMap - The Best of Both Worlds?

LinkedHashMap = HashMap + Doubly Linked List

Maintains insertion order:
put("A", 1) → put("C", 3) → put("B", 2)

Iterate: A, C, B  (insertion order)
HashMap would be: random order
TreeMap would be: A, B, C (sorted)

Performance:

  • Get/Put: O(1) (like HashMap)
  • Iteration: Predictable order
  • Memory: Slightly more overhead (extra pointers)

Use case:

  • LRU Cache implementation
  • Khi cần vừa nhanh vừa giữ order

5. Memory Management: Điều Java làm ngầm

5.1. ArrayList Growth Strategy

Initial capacity: 10
Growth formula: newCapacity = oldCapacity + (oldCapacity >> 1)
                             = oldCapacity × 1.5

Lifecycle:
Capacity: 10 → 15 → 22 → 33 → 49 → 73 → ...

Khi add element 11:
1. Allocate new array[15]
2. Copy 10 elements to new array
3. Add element 11
4. Old array → Garbage Collection

Optimization tip:

// Bad: Resize nhiều lần
List<String> list = new ArrayList<>(); // capacity 10
for (int i = 0; i < 10000; i++) {
    list.add("item");  // Resize at 10, 15, 22, 33, ...
}

// Good: Pre-allocate
List<String> list = new ArrayList<>(10000);
for (int i = 0; i < 10000; i++) {
    list.add("item");  // No resize needed!
}

Performance: 10-50% faster

5.2. HashMap Memory Overhead

HashMap memory structure:
- Array of buckets (default 16)
- Each entry stores: key, value, hash, next pointer

Memory per entry ≈ 32 bytes overhead
+ actual key/value size

Example:
HashMap<Integer, Integer> with 1000 entries:
- Data: 8 bytes/entry (int key + int value)
- Overhead: 32 bytes/entry
- Total: 40 bytes/entry × 1000 = 40 KB

Comparision:
Array of int[1000]: 4 KB
HashMap<Integer>: 40 KB → 10x more memory!

5.3. LinkedList Memory Explosion

LinkedList node structure:
class Node<E> {
    E item;           // 8 bytes (reference)
    Node<E> next;     // 8 bytes
    Node<E> prev;     // 8 bytes
}

Total: 24 bytes overhead per element

ArrayList:
- Store references in array: 8 bytes/element

LinkedList with 10,000 elements:
- Data: 80 KB (references)
- Overhead: 240 KB (node pointers)
- Total: 320 KB

ArrayList with 10,000 elements:
- Data: 80 KB
- Overhead: ~0 KB
- Total: 80 KB

LinkedList uses 4x more memory!

6. Performance Tips từ kinh nghiệm thực tế

6.1. Avoid unnecessary boxing

Bad:
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
    list.add(i);  // Autoboxing: int → Integer object
}
Memory: ~4 MB data + ~16 MB objects = 20 MB

Good:
int[] array = new int[1000000];
for (int i = 0; i < 1000000; i++) {
    array[i] = i;  // Primitive
}
Memory: 4 MB

5x memory reduction!

6.2. Choose right initial capacity

// Nếu biết trước size
Map<String, String> map = new HashMap<>(10000);

// Tính toán capacity từ expected size
int expectedSize = 1000;
int capacity = (int) (expectedSize / 0.75) + 1;  // Load factor
Map<String, String> map = new HashMap<>(capacity);

// Tránh resize → Faster & less GC

6.3. Use EnumMap/EnumSet khi có thể

// Super fast & memory efficient
enum Status { PENDING, ACTIVE, COMPLETED }

Map<Status, User> map = new EnumMap<>(Status.class);
// Internally uses array → O(1) với overhead cực thấp
// Faster than HashMap

7. Kết luận: Tư duy Performance-First

Key Takeaways:

✅ Big O không phải lý thuyết khô khan - Nó quyết định app của bạn chạy trong 1 giây hay 1 giờ
✅ ArrayList > LinkedList trong 95% cases - Đừng dùng LinkedList “cho fun”
✅ HashMap cho speed, TreeMap cho order - Hiểu trade-off
✅ Pre-allocate collections - Tránh resize, giảm GC
✅ Primitives > Objects - Memory matters
✅ Profile before optimize - Đừng guess, hãy measure

Câu hỏi tự kiểm tra:

  1. Tại sao ArrayList.get() nhanh hơn LinkedList.get()?
  2. HashMap resolve collision như thế nào?
  3. Khi nào TreeMap tốt hơn HashMap?
  4. ArrayList tốn bao nhiêu memory cho 10,000 Integers?
  5. Load factor trong HashMap ảnh hưởng gì?

Nếu bạn trả lời được tất cả, chúc mừng - bạn đã hiểu tại sao, không chỉ cái gì!

Tài liệu tham khảo:

📚 Effective Java (Joshua Bloch)
📊 Java Collections Performance
🛠️ JMH Benchmarking
🎥 Java Memory Model Deep Dive

Happy Optimizing! 🚀

#Java #Collections #Performance #BigO #DataStructures #MemoryOptimization