Bên trong Collections

Bài trước: Garbage Collection — Bạn đã biết GC quản lý objects trên Heap. Bài này mở "nắp" các Collections phổ biến để hiểu tại sao chúng nhanh (hoặc chậm).

ArrayList Internals

Cấu trúc bên trong

ArrayList backed by mảng nội bộ Object[] elementData:

// Simplified ArrayList internals
public class ArrayList<E> {
    Object[] elementData;  // Mảng nội bộ chứa elements
    int size;              // Số elements thực tế

    // Default constructor — lazy allocation
    public ArrayList() {
        this.elementData = {};  // Empty array! Chưa allocate
    }

    // Constructor với initial capacity
    public ArrayList(int initialCapacity) {
        this.elementData = new Object[initialCapacity];
    }
}

Default Capacity và Growth

new ArrayList<>()    → elementData = {} (empty)
Lần add đầu tiên    → elementData = new Object[10] (default capacity = 10)
add thứ 11           → grow: capacity 10 → 15 (10 + 10/2)
add thứ 16           → grow: capacity 15 → 22
add thứ 23           → grow: capacity 22 → 33
...

Công thức growth:

int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5x
// >> 1 = chia 2 (bit shift right)
// 10 + 10/2 = 15
// 15 + 15/2 = 22 (integer division: 15/2 = 7)

Resize = Copy toàn bộ mảng

// Khi grow, ArrayList dùng System.arraycopy (native method)
elementData = Arrays.copyOf(elementData, newCapacity);
// 1. Tạo mảng mới kích thước newCapacity
// 2. Copy TẤT CẢ elements sang mảng mới
// 3. Mảng cũ → garbage → GC pressure

Trước grow:
elementData → [A][B][C][D][E][F][G][H][I][J]  (size=10, capacity=10)

Sau grow:
old array   → [A][B][C][D][E][F][G][H][I][J]  → GARBAGE (GC sẽ collect)
elementData → [A][B][C][D][E][F][G][H][I][J][ ][ ][ ][ ][ ]  (capacity=15)

Tại sao new ArrayList<>(1000) nhanh hơn

Nếu biết cần ~1000 elements, set initial capacity = 1000:

• Không set: ~17 lần resize (10→15→22→33→...→1000+), mỗi lần copy toàn bộ
• Set 1000: 0 lần resize, 0 lần copy

// ❌ 17 resizes
List<String> list = new ArrayList<>();

// ✅ 0 resizes
List<String> list = new ArrayList<>(1000);

Performance Analysis

Operation	Time	Giải thích
get(i)	O(1)	Array index access: elementData[i]
add(e) (cuối)	O(1) amortized	Thường O(1), đôi khi O(n) khi resize
add(i, e) (giữa)	O(n)	Shift elements sang phải: System.arraycopy
remove(i)	O(n)	Shift elements sang trái
contains(e)	O(n)	Linear scan toàn bộ mảng

LinkedList Internals

Cấu trúc Node

LinkedList dùng doubly-linked nodes:

// Simplified LinkedList internals
public class LinkedList<E> {
    Node<E> first;  // Head
    Node<E> last;   // Tail
    int size;

    private static class Node<E> {
        E item;        // Data
        Node<E> prev;  // Trỏ đến node trước
        Node<E> next;  // Trỏ đến node sau
    }
}

first                                               last
  │                                                   │
  ▼                                                   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ prev: null   │    │ prev: ●──────│───▶│ prev: ●──────│
│ item: "A"    │◀───│──────● :next │    │ item: "C"    │
│ next: ●──────│───▶│ item: "B"    │◀───│──────● :next │
│              │    │ next: ●──────│───▶│ next: null   │
└──────────────┘    └──────────────┘    └──────────────┘

Mỗi Node = 1 Object trên Heap

Node object:
┌───────────────────┐
│ Header:   12 bytes│
│ prev ref:  4 bytes│
│ item ref:  4 bytes│
│ next ref:  4 bytes│
│ Padding:   0 bytes│
│ Total:    24 bytes│ ← Mỗi node tốn 24 bytes overhead
└───────────────────┘

So sánh memory cho 1000 integers:

• ArrayList<Integer>: 1 array + 1000 Integer objects ≈ 4KB (array) + 16KB (Integers) = ~20KB
• LinkedList<Integer>: 1000 Node objects + 1000 Integer objects ≈ 24KB (Nodes) + 16KB (Integers) = ~40KB

Tại sao ArrayList thường nhanh hơn LinkedList?

CPU Cache Locality — lý do quan trọng nhất:

ArrayList (contiguous memory):
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ F │ G │ H │ ← Cache line load: 1 lần load, đọc nhiều
└───┴───┴───┴───┴───┴───┴───┴───┘

LinkedList (scattered on Heap):
┌───┐     ┌───┐         ┌───┐  ┌───┐
│ A │──●  │ C │──●       │ F │  │ B │──●
└───┘  │  └───┘  │      └───┘  └───┘  │
       ▼         ▼                     ▼
      ┌───┐     ┌───┐                ┌───┐
      │ D │     │ E │                │ G │
      └───┘     └───┘                └───┘
      ← Cache misses: mỗi node có thể ở vị trí khác nhau →

Khi nào dùng LinkedList?

Gần như không bao giờ. ArrayList tốt hơn trong hầu hết trường hợp nhờ:

• O(1) random access vs O(n) cho LinkedList
• CPU cache-friendly (contiguous memory)
• Ít memory overhead hơn

LinkedList chỉ tốt hơn khi:

• Thêm/xóa đầu list rất thường xuyên (addFirst, removeFirst)
• Dùng như Queue/Deque (nhưng ArrayDeque thường vẫn nhanh hơn)

HashMap Internals (Java 8+)

Cấu trúc Bucket Array

// Simplified HashMap internals
public class HashMap<K,V> {
    Node<K,V>[] table;      // Bucket array (mặc định 16)
    int size;                // Số entries
    float loadFactor;        // Mặc định 0.75
    int threshold;           // loadFactor * capacity

    static class Node<K,V> {
        int hash;
        K key;
        V value;
        Node<K,V> next;      // Linked list trong bucket
    }
}

Put Operation — Từng bước

map.put("name", "Java");

table (capacity = 16):
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │10 │11 │12 │13 │14 │15 │
└─┬─┴───┴─┬─┴───┴───┴───┴───┴─┬─┴───┴───┴───┴───┴───┴───┴───┴───┘
  │       │                   │
  ▼       ▼                   ▼
 [A:1]  [C:3]              [F:6]
  │       │
  ▼       ▼
 [B:2]  [D:4]    ← Collision: cùng bucket, linked list
                     (Java 8+: chuyển sang tree khi > 8 nodes)

Collision Resolution: List → Tree

Khi một bucket có quá nhiều entries (> 8 = TREEIFY_THRESHOLD):

Bucket entries ≤ 8: Linked List → O(n) lookup
Bucket entries > 8: Red-Black Tree → O(log n) lookup

Java 7:  Collision luôn linked list → O(n) worst case
Java 8+: List → Tree khi > 8 entries → O(log n) worst case

Tại sao threshold = 8?

Với hash function tốt, xác suất bucket có > 8 entries là cực nhấp (< 0.00000006). Threshold 8 là trade-off: linked list đơn giản và nhanh cho ≤ 8, tree chỉ cần cho collision bất thường.

Rehashing

Khi số entries vượt threshold (capacity × loadFactor):

Initial: capacity=16, loadFactor=0.75, threshold=12
Khi size > 12 → rehash:
  1. Tạo table mới gấp đôi: capacity=32
  2. Tính lại index cho TOÀN BỘ entries (hash & 31 thay vì hash & 15)
  3. Di chuyển entries sang table mới
  4. Table cũ → garbage

// Tại sao new HashMap<>(expectedSize) quan trọng
// Nếu cần 1000 entries:
Map<String, Integer> map = new HashMap<>();           // ❌ ~7 lần rehash
Map<String, Integer> map = new HashMap<>(1334);       // ✅ 0 lần rehash
// 1334 = 1000 / 0.75 + 1 (tính ngược từ loadFactor)

HashMap Performance

Operation	Best/Average	Worst (Java 8+)
put(k,v)	O(1)	O(log n) per bucket
get(k)	O(1)	O(log n) per bucket
remove(k)	O(1)	O(log n) per bucket
containsKey(k)	O(1)	O(log n) per bucket
containsValue(v)	O(n)	O(n) — scan tất cả

HashSet = HashMap dưới hood

// HashSet internals (simplified)
public class HashSet<E> {
    private HashMap<E, Object> map;
    private static final Object PRESENT = new Object();  // Dummy value

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }
}

HashSet chỉ là HashMap wrapper

• HashSet.add(e) → HashMap.put(e, PRESENT)
• HashSet.contains(e) → HashMap.containsKey(e)
• Memory: mỗi entry vẫn tốn 1 Node object + PRESENT reference

Nên hiểu HashMap là hiểu HashSet.

Lỗi thường gặp

Lỗi thường gặp

Lỗi 1: Không set initial capacity khi biết trước size

// ❌ Nhiều lần resize
List<User> users = new ArrayList<>();      // resize 7+ lần cho 1000 users
Map<String, User> map = new HashMap<>();   // rehash 7+ lần cho 1000 entries

// ✅ Set capacity
List<User> users = new ArrayList<>(1000);
Map<String, User> map = new HashMap<>(1334);  // 1000/0.75 + 1

Lỗi 2: Mutable key trong HashMap

// ❌ Thay đổi key sau khi put → hash thay đổi → get() trả về null!
List<String> key = new ArrayList<>(List.of("a", "b"));
map.put(key, "value");
key.add("c");            // Hash thay đổi!
map.get(key);            // null! Key ở bucket khác rồi

Lỗi 3: Nghĩ LinkedList nhanh hơn ArrayList cho insert/delete

// LinkedList.add(index, e) = O(n) vì phải duyệt đến index trước
// ArrayList.add(index, e) = O(n) vì shift elements
// Nhưng ArrayList nhanh hơn nhờ System.arraycopy (native) + cache locality

Bài tập

Bài 1: ArrayList Growth [Cơ bản]

Tính capacity của ArrayList sau mỗi lần grow, bắt đầu từ default (10), cho đến khi chứa được 100 elements:

Xem lời giải

Capacity: 10 → 15 → 22 → 33 → 49 → 73 → 109
Cần 6 lần grow để chứa 100 elements.

Tính: newCap = oldCap + oldCap/2 (integer division)
10 + 5 = 15
15 + 7 = 22
22 + 11 = 33
33 + 16 = 49
49 + 24 = 73
73 + 36 = 109 ← Đủ cho 100 elements

Nếu dùng new ArrayList<>(100) → 0 lần grow.

Bài 2: HashMap Bucket [Trung bình]

HashMap với capacity = 8. Cho các keys có hashCode(): A=1, B=9, C=17, D=5, E=13. Vẽ trạng thái bảng buckets sau khi put tất cả.

Xem lời giải

Bucket index = hashCode & (8-1) = hashCode & 7 (3 bit cuối)

A: 1 & 7 = 1
B: 9 & 7 = 1    ← Collision với A!
C: 17 & 7 = 1   ← Collision với A, B!
D: 5 & 7 = 5
E: 13 & 7 = 5   ← Collision với D!

Buckets:
[0]: empty
[1]: A → B → C   (linked list, 3 nodes)
[2]: empty
[3]: empty
[4]: empty
[5]: D → E        (linked list, 2 nodes)
[6]: empty
[7]: empty

Nhận xét: Distribution kém — 3 collisions ở bucket 1. Đây là ví dụ tại sao hash function tốt quan trọng.

Bài 3: Memory Estimation [Thách thức]

Ước tính memory sử dụng cho HashMap<String, Integer> chứa 10,000 entries (keys là String 10 characters, values là Integer). So sánh với dùng int[] cho cùng data.

Gợi ý

Tính: HashMap overhead + Node objects + String objects + Integer objects + bucket array.

• Node: ~32 bytes each (header + hash + key ref + value ref + next ref)
• String: ~56 bytes each (header + char[]/byte[] + hash + coder)
• Integer: ~16 bytes each
• Bucket array: ~16 bytes header + 4 bytes × buckets

Tóm tắt

Collection	Backing structure	Key insight
ArrayList	Object[] array	Contiguous memory, O(1) get, grows 1.5x
LinkedList	Doubly-linked nodes	Scattered memory, poor cache locality
HashMap	Bucket array + list/tree	O(1) amortized, rehash at 75% full
HashSet	HashMap<E, PRESENT>	Wrapper around HashMap

Đọc thêm

• Oracle: ArrayList API
• Oracle: HashMap API
• Baeldung: Internal Working of HashMap