Module 4 — Collections Internals: tổng quan

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ẽ

• Giải thích vì sao ArrayList.grow() dùng 1.5x thay vì 2x (memory/allocator JVM).
• Trace HashMap internals: bucket array, separate chaining, treeify Java 8, resize.
• Diagnose hash-collision DoS và đọc HashMap.java/ArrayList.java source.

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: separate chaining + treeify từ Java 8, resize, hash-collision DoS.

Bài tiếp theo: ArrayList.grow() — Vì sao 1.5x là magic number