99 Ngày Java — Ngày 34: HashMap hoạt động thế nào

Suốt 33 ngày, HashMap xuất hiện ở khắp nơi — repository in-memory Ngày 30, khử trùng Ngày 31, và ta luôn tin lời hứa O(1) của nó. Hôm nay mở nắp capo xem lời hứa ấy chạy bằng gì: bucket và phép trộn hash, va chạm và cú nâng cấp treeify của Java 8, load factor và cái giá của resize, cùng họ method hiện đại merge/computeIfAbsent. Đây là câu hỏi phỏng vấn Java "quốc dân" — sau bài này bạn trả lời được bằng hiểu, không bằng thuộc.

Sketchnote Ngày 34: HashMap hoạt động thế nào — mảng bucket và hash, va chạm với treeify, load factor và resize, duyệt entrySet và bốn quy tắc sống còn

Từ key đến bucket — phép màu O(1)

// Bên trong HashMap: MẢNG các "bucket" — mỗi bucket chứa các entry
// (rút gọn từ mã nguồn JDK)
public class HashMap<K, V> {
    Node<K, V>[] table;        // mảng bucket — mặc định 16 ô
    int size;                  // số entry đang có

    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;       // entry sau trong CÙNG bucket (khi va chạm)
    }
}

// put("java", 1) đi qua 3 bước:
// 1. hash: lấy key.hashCode() rồi TRỘN thêm (h ^ (h >>> 16)) — giảm va chạm
// 2. index = hash & (n - 1)   // n là lũy thừa 2 → phép AND thay cho chia lấy dư, nhanh hơn
// 3. đặt entry vào table[index]

// get("java") đi đúng con đường đó:
// hash → index → tới thẳng bucket → so hash rồi equals để tìm đúng entry
// KHÔNG duyệt mảng — đó là phép màu O(1)

// Vì sao cần CẢ hashCode lẫn equals (Ngày 24)?
// - hashCode: tìm ĐÚNG BUCKET (khoanh vùng)
// - equals:   tìm ĐÚNG ENTRY trong bucket (xác nhận)
// Hai chữ ký khác vai — thiếu một là mọi thứ sụp (Ngày 33 đã nếm)

Cấu trúc lõi chỉ là mảng các bucket: hashCode của key được trộn thêm (h ^ (h >>> 16)) rồi AND với n-1 ra thẳng chỉ số — không duyệt, không tìm kiếm: đó là toàn bộ phép màu O(1).
Chi tiết ăn điểm phỏng vấn: capacity luôn là lũy thừa của 2 để hash & (n-1) thay cho phép chia lấy dư — rẻ hơn ở tầng CPU; và bước trộn hash giúp key có hashCode "xấu" vẫn rải đều bucket.
Phân vai rõ ràng của cặp Ngày 24: hashCode khoanh vùng (đúng bucket), equals xác nhận (đúng entry trong bucket) — hiểu phân vai này là tự giải thích được mọi bug "trùng lặp ma" của Ngày 33.

Va chạm — và cú nâng cấp treeify

// Va chạm (collision): hai key khác nhau — cùng bucket. Chuyện THƯỜNG NGÀY.
map.put("FB", 1);   // giả sử rơi vào bucket 5
map.put("Ea", 2);   // "FB" và "Ea" có hashCode BẰNG NHAU thật sự trong Java!
// → bucket 5 giờ là danh sách liên kết: FB → Ea

// get("Ea"): tới bucket 5 → đi dọc danh sách, equals từng key → tìm thấy
// Va chạm ít: danh sách 1–2 node — vẫn gần O(1)

// Java 8 nâng cấp: bucket quá dài (≥ 8 node, bảng đủ to)
// → chuyển danh sách thành CÂY ĐỎ-ĐEN (treeify)
// Tra cứu bucket xấu nhất: O(n) tụt xuống O(log n)

// Vì sao phải phòng xa? hashCode TỒI:
class KeyTồi { @Override public int hashCode() { return 42; } }
// → MỌI key chung một bucket — HashMap thành... LinkedList trá hình
// get() từ O(1) tụt còn O(n) — "map chậm bí ẩn" trong production là đây
// (Trước Java 8, đây còn là đòn tấn công DoS thật sự qua HTTP param!)

// Bài học: sức khỏe của HashMap = chất lượng hashCode của KEY
// record/String/Integer — hashCode tốt sẵn. Class tự viết — Ngày 24 là kim chỉ nam

Va chạm là bình thường, không phải lỗi: hai key khác nhau chung bucket thì nối thành danh sách — "FB" và "Ea" là cặp trùng hashCode nổi tiếng của chính String Java.
Java 8 thêm lưới an toàn treeify: bucket dài ≥ 8 chuyển từ danh sách sang cây đỏ-đen — trường hợp xấu nhất từ O(n) còn O(log n); trước đó, hashCode tệ từng là đòn tấn công DoS thật qua HTTP param trùng hash.
Thông điệp lớn: hiệu năng HashMap không nằm trong HashMap — nó nằm trong chất lượng hashCode của key bạn đưa vào: String/record tốt sẵn, class tự viết thì Ngày 24 là kim chỉ nam.

Load factor và cái giá của resize

// Load factor & resize — vì sao bảng không bao giờ để mình quá chật
// Mặc định: capacity 16, load factor 0.75
// → threshold = 16 × 0.75 = 12: entry thứ 13 kích hoạt RESIZE

// Resize làm gì?
// 1. Cấp mảng MỚI gấp đôi (16 → 32 → 64...)
// 2. REHASH: đặt lại TỪNG entry vào vị trí mới (index phụ thuộc n!)
// → O(n) mỗi lần — đắt hơn nhiều cú "nới rộng" của ArrayList (chỉ chép, Ngày 32)

// Load factor là nút vặn cân bằng:
// 0.75 (mặc định)  — điểm ngọt: ít va chạm, không phí quá nhiều ô trống
// cao hơn (0.9)    — tiết kiệm RAM, nhiều va chạm hơn
// thấp hơn (0.5)   — nhanh hơn chút, tốn RAM hơn — hiếm khi cần chỉnh

// Biết trước số lượng? Nói với constructor (bài học lặp lại từ Ngày 32):
Map<String, User> theoUsername = new HashMap<>(1_000_000 / 3 * 4);
// hoặc dễ nhớ hơn từ Java 19:
Map<String, User> map = HashMap.newHashMap(1_000_000);   // tự tính capacity theo 0.75
// → nạp 1 triệu entry KHÔNG một lần resize/rehash nào — nhanh hơn thấy rõ

Công thức đáng nhớ: threshold = capacity × loadFactor — 16 × 0.75 = 12: entry thứ 13 châm ngòi resize gấp đôi + rehash toàn bộ (vị trí phụ thuộc n, nên phải đặt lại từng entry — đắt hơn cú chép mảng của ArrayList Ngày 32).
0.75 là điểm ngọt cân giữa va chạm và ô trống — hầu như không bao giờ cần chỉnh; thứ đáng chỉnh là capacity ban đầu khi biết trước số lượng.
Từ Java 19 có HashMap.newHashMap(n) — nói "tôi sẽ chứa n entry" và để nó tự tính capacity: nạp triệu entry không một lần rehash; cùng bài học pre-size đã gặp ở ArrayList và StringBuilder.

Duyệt entry và bộ tứ method hiện đại

// Duyệt Map — và họ method hiện đại thay cho if-else quanh get
Map<String, Integer> demTu = new HashMap<>();

// Duyệt ĐÚNG: entrySet — mỗi entry một lần chạm
for (Map.Entry<String, Integer> e : demTu.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}
// Duyệt SAI kiểu cũ: for key trong keySet() rồi map.get(key) — TRA HAI LẦN mỗi vòng

// Sửa map khi đang duyệt for-each? Fail-fast — bạn cũ Ngày 32:
for (String k : demTu.keySet()) {
    if (k.isBlank()) demTu.remove(k);      // 💥 ConcurrentModificationException
}
demTu.keySet().removeIf(String::isBlank);  // ✅ removeIf qua view — an toàn

// Bộ tứ hiện đại — đếm từ không còn if-else:
demTu.merge(tu, 1, Integer::sum);          // chưa có: đặt 1 — có rồi: cộng dồn

map.getOrDefault("k", 0);                  // hết thời null check thủ công
map.putIfAbsent("k", macDinh);             // chỉ đặt khi chưa có
cache.computeIfAbsent(key, k -> tinhToanDat(k));   // vắng thì TÍNH rồi nhớ — cache 1 dòng
// computeIfAbsent chính là cache-aside pattern thu nhỏ (khóa System Design buổi 5!)

Duyệt qua entrySet — một lần chạm mỗi entry; kiểu cũ keySet + get trong vòng lặp là tra hai lần vô ích; và sửa-khi-duyệt vẫn nổ ConcurrentModificationException như Ngày 32 — thuốc vẫn là removeIf (chạy được trên cả keySet/values vì chúng là view sống của map).
Bộ tứ hiện đại xóa sổ if-else quanh get: getOrDefault, putIfAbsent, merge (đếm/gộp một dòng), computeIfAbsent (vắng thì tính rồi nhớ).
computeIfAbsent đáng nhớ nhất: nó là cache-aside pattern thu nhỏ — miss thì tính, hit thì trả — đúng pattern buổi 5 khóa System Design, nằm gọn trong một method của java.util.

Bốn quy tắc sống còn

// Bốn quy tắc sống còn khi dùng HashMap

// 1. KEY PHẢI BẤT BIẾN (Ngày 29 + 33)
Map<List<String>, User> nguyHiem = new HashMap<>();
List<String> key = new ArrayList<>(List.of("a"));
nguyHiem.put(key, user);
key.add("b");                   // hashCode đổi → entry LẠC vĩnh viễn trong map
nguyHiem.get(key);              // null — dù entry vẫn "ở đó"
// → key chuẩn: String, Integer, record, List.of — thứ KHÔNG đổi được

// 2. equals/hashCode phải là MỘT CẶP (Ngày 24)
// override một cái bỏ cái kia = trùng lặp ma + entry lạc — không có ngoại lệ

// 3. Cho phép 1 null key, nhiều null value — nhưng ĐỪNG lạm dụng
map.get(k);   // null nghĩa là gì: không có key? hay value là null?
map.containsKey(k);   // câu trả lời rõ ràng — hoặc tốt hơn: đừng cất null

// 4. HashMap KHÔNG thread-safe
// Nhiều thread cùng ghi: mất entry, size sai — và resize đồng thời từng gây treo cả CPU
// → đa luồng dùng ConcurrentHashMap (gặp lại ở phần concurrency)
// Còn Collections.synchronizedMap? Khóa cả map mỗi thao tác — chậm, ít khi đáng

Quy tắc 1 gói cả Ngày 29 + 33: key phải bất biến — key đổi hashCode sau khi put là entry lạc vĩnh viễn; quy tắc 2 là Ngày 24: equals/hashCode luôn đi đôi.
get trả null là câu trả lời nhập nhằng (không có key hay value là null?) — containsKey khi cần phân biệt, và tốt nhất: đừng cất null value.
HashMap không thread-safe: nhiều thread ghi đồng thời là mất entry, size sai — đa luồng dùng ConcurrentHashMap (hẹn phần concurrency); đây là ranh giới cuối của bài, biết để không bước qua trong vô thức.

Bài tập nhỏ

In "bản đồ bucket" thủ công: với capacity 16, tính index = hash & 15 cho 10 chuỗi bất kỳ và xếp chúng vào bucket — có cặp nào va chạm không?
Chứng minh "FB".hashCode() == "Ea".hashCode() rồi put cả hai — get từng key vẫn đúng: giải thích bằng phân vai hash/equals.
Viết KeyTồi với hashCode trả 42, nạp 100.000 entry và đo thời gian get so với key String — cảm nhận O(n) bằng đồng hồ.
Đo resize: nạp 1 triệu entry vào new HashMap<>() vs HashMap.newHashMap(1_000_000) — chênh bao nhiêu?
Đếm tần suất từ của một đoạn văn bằng merge — rồi in top 5 bằng cách đổ entrySet ra list và sort (Ngày 38 sẽ đẹp hơn nữa).
Dùng computeIfAbsent làm cache cho hàm fibonacci đệ quy (Ngày 25) — so tốc độ trước/sau khi có cache.

Kết luận

Bốn ý mang về: O(1) của HashMap = hash trộn → AND với n-1 → tới thẳng bucket, với hashCode khoanh vùng và equals xác nhận; va chạm là thường ngày — danh sách trong bucket, treeify cứu trường hợp xấu, còn hashCode tệ biến map thành LinkedList trá hình; load factor 0.75 kích hoạt resize + rehash O(n) — biết trước số lượng thì newHashMap(n); và key bất biến + bộ tứ merge/computeIfAbsent là phong cách 2026. Ngày 35 gặp hai anh em còn lại: TreeMap & LinkedHashMap — map có thứ tự, và màn ảo thuật LRU cache bằng đúng một method override. Hẹn gặp lại!