Module 04 — Tổng kết & cheat sheet Collections Internals

Module này bóc nội tạng JDK của hai cấu trúc dữ liệu bạn dùng mỗi ngày — ArrayList và HashMap — và trả lời những con số cụ thể mà khoá Thuật toán không chạm tới: vì sao grow 1.5x, vì sao treeify ở ngưỡng 8. Trang này gom cả module thành một chỗ tra cứu nhanh.

🧵 Đã đi qua những gì

Sợi chỉ xuyên suốt là cùng một câu chuyện resize, khác chiến lược. Bài 01 — ArrayList.grow() đọc thẳng OpenJDK 21: ArrayList grow bằng oldCapacity + (oldCapacity >> 1) — 1.5x, không phải 2x của C++ std::vector — vì 1.5 nhỏ hơn golden ratio φ nên allocator tái sử dụng được block cũ, waste RAM trung bình 17% thay vì 25%, và tính bằng bit shift nguyên. Pre-size loại bỏ toàn bộ grow event. Bài 02 — HashMap internals trace một put đi qua bucket array: index bằng bit AND (n-1) & hash (nhanh hơn modulo, đòi capacity power-of-2), collision thì walk chain so hash trước equals() sau, resize nhân đôi khi size vượt capacity × 0.75 và re-distribute bằng bit (oldHash & oldCap) không recompute hash — O(1) chỉ đúng amortized. Bài 02b — treeify mổ đường phòng thủ khi hash không tử tế: chain đạt TREEIFY_THRESHOLD = 8 và table từ 64 bucket trở lên thì bucket chuyển thành red-black tree, hạ worst case từ O(n) xuống O(log n) — ngưỡng 8 chọn theo Poisson (chạm gần như chắc chắn là hash bị lạm dụng), nhưng treeify chỉ giảm thiệt hại DoS chứ không thay được validate input. Mini-challenge ghép cả ba vào một sự cố ingest service: P99 spike do resize storm của cả ArrayList lẫn HashMap, và CPU 100% do hash-collision DoS — cùng lúc, cùng root cause là cách khởi tạo collection.

flowchart TD
    A["Collection dong trong JDK"] --> B["ArrayList: mang lien tiep<br/>grow 1.5x, pre-size"]
    A --> C["HashMap: bucket + chaining<br/>resize 2x @ load factor 0.75"]
    C --> D["Treeify @ 8 entry<br/>phong thu collision DoS"]
    B --> E["Mini-challenge:<br/>resize storm + DoS trong 1 service"]
    C --> E
    D --> E

🗺️ Cheat sheet

📖 Glossary module

⚠️ Pitfall tổng hợp

1. Không pre-size collection biết trước kích thước (bài 01, 02).

// SAI -- default cap, resize storm khi biet truoc N
List<Row> rows = new ArrayList<>();
Map<String, Row> index = new HashMap<>();

// DUNG -- pre-size, 0 grow
List<Row> rows = new ArrayList<>(expectedCount);
Map<String, Row> index = HashMap.newHashMap(expectedCount);

2. Truyền thẳng số phần tử làm initial capacity của HashMap (bài 02). new HashMap<>(2000) vẫn resize một lần: constructor làm tròn 2000 lên power-of-2 là 2048, threshold = 2048 × 0.75 = 1536 → resize ở entry 1.537. Dùng HashMap.newHashMap(2000) hoặc new HashMap<>((int)(2000 / 0.75 + 1)).

3. Mutable key trong HashMap (bài 02). Mutate field dùng trong hashCode() sau khi put → key "lạc" bucket, get() trả null, entry unreachable (memory leak). Dùng final field hoặc record.

4. Coi treeify là đủ chống collision DoS (bài 02b). Treeify hạ worst case xuống O(log n) nhưng không chặn tấn công. Phòng thủ thật là giới hạn input + rate limiting đứng trước.

✅ Self-assessment

Bạn đã đạt module này nếu tự tin tick đủ ba ô — mỗi ô khớp một learning outcome:

• Explain được vì sao ArrayList.grow() dùng 1.5x thay vì 2x (memory utilization, block reuse) và hệ quả pre-sizing trong production.
  • Nếu chưa → đọc lại bài 01 — ArrayList.grow(), phần golden ratio (§4.2) và benchmark pre-size (§5).
• Trace được HashMap internals: bucket array, separate chaining, resize re-distribution, và khi nào claim O(1) thực sự đứng vững.
  • Nếu chưa → đọc lại bài 02 — HashMap internals, phần put path (§3) và smart re-distribution (§4).
• Diagnose được hash-collision DoS và cơ chế treeify/untreeify Java 8 phòng thủ suy biến O(n).
  • Nếu chưa → đọc lại bài 02b — treeify & collision DoS, rồi tự làm lại mini-challenge.

🚀 Học tiếp gì

Module này là chặng đầu của khoá Java Internals nhìn nội thất collection. Hai hướng đi tiếp tự nhiên:

• Bản thread-safe của chính hai cấu trúc này — ConcurrentHashMap nội thất ở Module 01: cùng bucket array + treeify, nhưng thay lock toàn map bằng CAS per-bucket.
• Phần ý tưởng thuật toán nền — nếu còn mơ hồ về amortized hay hash function, quay lại khoá Thuật toán — Amortized analysis và Hàm băm.

📚 Tài liệu mở rộng

• Source: OpenJDK 21 — ArrayList.java + HashMap.java — comment trong source giải thích từng quyết định thiết kế.
• JEP: JEP 180 — Handle Frequent HashMap Collisions With Balanced Trees (Java 8) — lý do và thiết kế treeify.
• Sách: Effective Java, 3rd Edition — Item 11 (override hashCode khi override equals) và Item 28 (prefer lists to arrays).

Bài đầu tiên của module kế: Stream I/O cổ điển