HashMap là một trong những cấu trúc dữ liệu quan trọng nhất trong Java. Đằng sau API đơn giản put() / get() là một thiết kế tinh vi dựa trên hashing + bucket + cấu trúc dữ liệu thích nghi. Bài viết này đi sâu vào cách HashMap hoạt động bên trong, lý do tồn tại bucket, cách xử lý collision, và mở rộng sang ConcurrentHashMap trong môi trường đa luồng.

1. Vấn đề HashMap cần giải quyết

HashMap được thiết kế để:

• Lưu trữ số lượng lớn key–value
• Truy cập nhanh theo key
• Không yêu cầu key có thứ tự
• Hoạt động tốt với key bất kỳ (String, Object, UUID…)

Nếu chỉ dùng List/Array:

• get(key) → O(n)
• Không đáp ứng yêu cầu hiệu năng

👉 HashMap ra đời để giải quyết bài toán này.

2. Hashing – nền tảng của HashMap

HashMap dựa trên ý tưởng hashing:

key → hashCode() → hash → bucket index

Trong Java:

• Mỗi object có hashCode()
• HashMap dùng thêm bit spreading để phân tán hash tốt hơn

Công thức tính index (table size luôn là lũy thừa của 2):

index = (n - 1) & hash

✔ Nhanh hơn phép chia % ✔ Phân phối đều hơn

3. Bucket là gì và vì sao cần bucket?

3.1 Collision là không tránh khỏi

Không có hàm hash nào hoàn hảo.

Hai key khác nhau có thể cho cùng index:

keyA → index 3
keyB → index 3

Đây gọi là hash collision.

3.2 Bucket – quyết định thiết kế cốt lõi

Bucket là một container tại mỗi index trong table:

table[index] → bucket → (k1,v1) → (k2,v2) → ...

HashMap:

• Không cố tránh collision
• Chấp nhận collision có kiểm soát
• Khoanh vùng collision trong từng bucket

👉 Đây là trade-off giữa hiệu năng, bộ nhớ và tính linh hoạt.

4. Cấu trúc bucket trong Java HashMap (Java 8+)

4.1 LinkedList → Red-Black Tree

Tùy số lượng phần tử trong bucket:

Số entry trong bucket	Cấu trúc
≤ 8	LinkedList
> 8 (table ≥ 64)	Red-Black Tree

Các ngưỡng quan trọng:

• TREEIFY_THRESHOLD = 8
• UNTREEIFY_THRESHOLD = 6
• MIN_TREEIFY_CAPACITY = 64

👉 Mục tiêu: tránh worst-case O(n).

5. Quy trình put() trong HashMap (đơn giản hóa)

1. Tính hashCode() từ key
2. Tính bucket index
3. Nếu bucket rỗng → insert
4. Nếu bucket có data:
   • So sánh hash + equals
   • Nếu key trùng → overwrite value
   • Nếu khác → append vào bucket
5. Nếu bucket vượt threshold → treeify
6. Nếu vượt load factor → resize

6. Điều gì xảy ra khi có 2 key giống nhau?

map.put("A", 1);
map.put("A", 2);

• HashMap kiểm tra:
  • hashCode()
  • equals()
• Nếu trùng → ghi đè value

👉 HashMap không bao giờ chứa 2 key giống nhau.

7. Resize và Load Factor

7.1 Load factor là gì?

Mặc định:

loadFactor = 0.75

Khi:

size > capacity * loadFactor

→ HashMap resize (x2 capacity)

7.2 Resize có gì nguy hiểm?

• Rehash toàn bộ entry
• Tốn CPU, GC
• Không thread-safe

👉 Không nên resize thường xuyên trong PROD.

8. HashMap và vấn đề đa luồng

8.1 Vì sao HashMap không thread-safe?

• Không có lock
• Resize đồng thời → data corruption
• Có thể gây infinite loop (Java 7)

👉 Tuyệt đối không dùng HashMap trong môi trường multi-thread.

9. ConcurrentHashMap – HashMap cho đa luồng

9.1 Mục tiêu thiết kế

ConcurrentHashMap được tạo ra để:

• Thread-safe
• High concurrency
• Tránh lock toàn map

9.2 Bucket trong ConcurrentHashMap (Java 8+)

• Bucket vẫn tồn tại
• Nhưng mỗi bucket được bảo vệ bằng:
  • CAS
  • synchronized block (fine-grained)

✔ Cho phép nhiều thread đọc song song ✔ Ghi chỉ lock bucket liên quan

9.3 So sánh HashMap vs ConcurrentHashMap

Tiêu chí	HashMap	ConcurrentHashMap
Thread-safe	❌	✅
Locking	Không	Fine-grained
Read concurrency	❌	✅
Resize	Single-thread	Cooperative
Iterator	Fail-fast	Weakly consistent

10. Khi nào dùng cái nào?

Tình huống	Nên dùng
Local / single-thread	HashMap
Web / multi-thread	ConcurrentHashMap
Cache	ConcurrentHashMap / Caffeine
Performance cực cao, đơn luồng	HashMap

11. Bucket không chỉ có trong HashMap

Khái niệm bucket xuất hiện ở nhiều nơi:

• Redis hash
• Kafka partitioning
• Load balancer (consistent hashing)
• Database sharding

👉 Đây là pattern nền tảng của system design.

12. Key Takeaways

• Bucket là trade-off hợp lý giữa hiệu năng và bộ nhớ
• HashMap phụ thuộc mạnh vào hashCode() và equals()
• Không dùng HashMap trong multi-thread
• ConcurrentHashMap là lựa chọn mặc định cho server-side Java