Module 4 — Collections Internals: tổng quan
Java Collections Framework nhìn từ bên trong: ArrayList.grow() 1.5x và HashMap chaining/treeify. Phần JDK hiện thực các ý tưởng thuật toán học ở track Thuật toán.
TL;DR: Module này mổ phần nội tạng JDK của hai cấu trúc dữ liệu bạn dùng mỗi ngày: ArrayList (mảng động) và HashMap (hash table). Khoá Thuật toán dạy ý tưởng của chúng mà không bám một ngôn ngữ nào (amortized doubling, hashing, va chạm, load factor). Ở đây ta đọc thẳng OpenJDK 21 source để thấy Oracle dựng những ý tưởng đó ra sao — vì sao họ chọn grow factor 1.5x (không phải 2x), vì sao treeify một bucket khi chuỗi dài quá 8.
Vì sao module này tồn tại
Bạn đã học ý tưởng mảng động và hash table ở khoá Thuật toán. Nhưng khi đọc code production Java, bạn gặp những con số rất cụ thể: ArrayList grow 1.5x, HashMap treeify ở ngưỡng 8, load factor 0.75. Đây là những lựa chọn kỹ thuật riêng của JVM — không phải lý thuyết thuật toán — và đáng hiểu để benchmark đúng, tránh hash-collision DoS, và đọc được OpenJDK source.
Sau module này bạn sẽ
- Explain vì sao
ArrayList.grow()dùng 1.5x thay vì 2x (memory utilization, block reuse) và hệ quả pre-sizing trong production. - Trace HashMap internals: bucket array, separate chaining, resize re-distribution, và khi nào claim O(1) thực sự đứng vững.
- Diagnose hash-collision DoS và cơ chế treeify/untreeify Java 8 phòng thủ suy biến O(n).
Liên hệ track Thuật toán
Module này là phần hiện thực; phần ý tưởng nằm ở khoá Thuật toán:
- Mảng động & amortized doubling → Thuật toán Căn bản — Amortized analysis.
- Hash table, collision, load factor → Thuật toán Cốt lõi — Hash function + Open addressing.
Lộ trình module
- Bài 01 — ArrayList.grow(): vì sao 1.5x là magic number, đọc OpenJDK source, benchmark.
- Bài 02 — HashMap internals: bucket array, separate chaining, put path, resize re-distribution.
- Bài 02b — HashMap treeify: phòng thủ hash-collision DoS từ Java 8 — vì sao 8, vì sao 64.
- Bài 03 — Mini-challenge: chẩn đoán P99 spike do resize storm và hash-collision DoS trong một ingest service, ghép cả ba bài.
- Bài 04 — Tổng kết: cheat sheet grow strategy, glossary, pitfall, và self-assessment ba outcome.
Bài tiếp theo: ArrayList.grow() — Vì sao 1.5x là magic number
Bài này đáng gửi cho bạn học cùng?
Copy link đã gắn nguồn — dán group, chat, hoặc LinkedIn.
Bài này có giúp bạn hiểu bản chất không?
Hỏi đáp về bài này
Chưa có câu hỏi
Có gì chưa rõ trong bài? Đặt câu hỏi đầu tiên — câu trả lời từ cộng đồng giúp bạn (và người sau).
Đặt câu hỏi đầu tiên