Java Internals & Concurrency
~8 phútCollections InternalsMiễn phí

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:

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 trướcJVM Internals

Tổng kết module — JVM Internals

Bài tiếp

Case Study: ArrayList.grow() — Vì sao 1.5x là magic number

Bài này có giúp bạn hiểu bản chất không?

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.

Thảo luận & góp ý

Hỏi đáp về bài này

Bài tiếp theo

Case Study: ArrayList.grow() — Vì sao 1.5x là magic number