HashMap internals — bucket array, separate chaining và resize

4:58Bên Trong HashMap — Vì Sao 1 Chiếc Map Ghim CPU 100%5 phút nắm ý chính · bài viết dưới đây là bản đầy đủ ~14 phút

TL;DR: HashMap lưu entry trong Node<K,V>[] table — bucket array có length là power-of-2, nên bucket index tính bằng bit AND (n-1) & hash thay vì modulo. Put vào bucket trống là O(1) thật; collision thì walk linked list trong bucket, so hash trước rồi mới equals(). Khi size vượt threshold = capacity × 0.75, table nhân đôi và re-distribute: Java 8 dùng bit (oldHash & oldCap) để chia entry về bucket cũ hoặc bucket cũ + oldCap mà không recompute hash. Một put đơn lẻ trigger resize là O(n) — claim O(1) chỉ đúng amortized, nên code latency-sensitive phải pre-size.

Bài này đọc thẳng HashMap.java của OpenJDK. Phần nền — hash table hoạt động ra sao, va chạm là gì, load factor để làm gì — nằm ở khoá Thuật toán: Hàm băm và Open addressing. Ở đây ta đi tiếp một bước: xem Java chọn dựng hash table theo cách nào (separate chaining) và vì sao.

Stack Overflow ghi rõ: HashMap.get() là amortized O(1), và phần lớn trường hợp đúng. Nhưng trong một service latency-sensitive, một dev đo thấy hiện tượng lạ: 99.99% put xong trong vài chục nanosecond, riêng put thứ 786.433 tốn hàng chục millisecond — gấp cả triệu lần. Không GC, không lock. Thủ phạm là resize: đúng lúc size vượt ngưỡng, một put phải rehash toàn bộ table.

Bài này trace từng bước một put đi qua HashMap.java: bucket array, chaining, resize — và khi nào O(1) thực sự đứng vững. Xong bài, bạn đọc được source OpenJDK 21 và biết vì sao pre-size là optimization thật chứ không phải mê tín.

1. Analogy — Tủ chia ngăn đựng hồ sơ

Hình dung một tủ hồ sơ 16 ngăn. Nhân viên nộp hồ sơ, phân vào ngăn theo chữ cái cuối tên (hash function): ngăn A nhận tên kết thúc bằng a, ngăn B nhận b, cứ thế. Tìm hồ sơ "Nguyen Van An" thì chỉ mở ngăn A — không cần lục toàn tủ.

Khi nhiều hồ sơ cùng chữ cuối tên, ngăn chứa một danh sách (linked list); tìm đúng người thì duyệt danh sách so sánh từng tên — equals(). Tủ đầy 75%, thêm ngăn gấp đôi và sắp xếp lại. (Còn tình huống một ngăn bị nhồi bất thường — quá 8 hồ sơ — tủ có cơ chế phòng thủ riêng: bài sau.)

2. Cấu trúc bên trong

HashMap lưu dữ liệu trong một array of buckets:

// Core fields -- simplified from OpenJDK 21 HashMap.java
transient Node<K,V>[] table;       // bucket array, null until first use
transient int size;                // number of key-value pairs
int threshold;                     // resize trigger: capacity * loadFactor
final float loadFactor;            // default 0.75f

Mỗi Node chứa bốn field:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;     // cached hash of key
    final K key;
    V value;
    Node<K,V> next;     // linked list chain within bucket
}

Bucket index được tính bằng bit AND thay vì modulo:

// bucket index: (table.length - 1) & hash
// table.length is power-of-2, so (n-1) is a bitmask keeping the low bits:
// n=16 -> n-1 = 0b1111 -> keeps 4 lowest bits; faster than %, same result
int i = (table.length - 1) & hash(key);

ASCII diagram của HashMap với 16 bucket và 4 entry, 2 trong đó chained vào bucket 3:

table[]
  [0]  null
  [2]  --> Node{hash, "beta", 200, null}
  [3]  --> Node{hash, "alpha", 100, next} --> Node{hash, "delta", 400, null}
  [9]  --> Node{hash, "gamma", 300, null}
  [15] null
size = 4, threshold = 16 * 0.75 = 12

Hai hằng số điều khiển vòng đời table:

static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int   DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

(Bộ hằng số TREEIFY_* — ngưỡng chuyển bucket thành cây khi chain quá dài — thuộc cơ chế phòng thủ ở bài sau.)

3. Put operation step-by-step (Java 21 source)

Dưới đây là putVal — heart của HashMap.put(). Code đã simplified để tập trung cơ chế, nhưng sát với OpenJDK 21 source:

// Simplified from HashMap.putVal() -- OpenJDK 21
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 1. Lazy init: first put allocates the table
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. Bucket index via bit AND
    i = (n - 1) & hash;
    p = tab[i];
    if (p == null) {
        // 3a. Empty bucket: insert directly
        tab[i] = newNode(hash, key, value, null);
    } else if (p instanceof TreeNode) {
        // 3b. Bucket is treeified: delegate to red-black tree insert
        ((TreeNode<K,V>) p).putTreeVal(this, tab, hash, key, value);
    } else {
        // 3c. Walk linked list chain
        for (int binCount = 0; ; binCount++) {
            // Key already exists (checked for EVERY node, head first):
            // update value and return early -- size unchanged, no resize
            if (p.hash == hash && (p.key == key || key.equals(p.key))) {
                V oldValue = p.value;
                p.value = value;
                return oldValue;
            }
            if (p.next == null) {
                // Reached end of chain, no match: append new node
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // binCount is 0-indexed
                    treeifyBin(tab, i);                // defensive path, see next lesson
                break;
            }
            p = p.next;
        }
    }

    // 4. New mapping added: resize if size exceeds threshold
    if (++size > threshold) resize();
    return null; // new mapping: real putVal also returns null here
}

Hai trường hợp cần chú ý:

Bucket trống (case 3a): tạo Node mới gắn trực tiếp vào tab[i] — đây là happy path O(1) thực sự.

Collision (case 3c): duyệt linked list, so sánh từng node bằng hash == p.hash && key.equals(p.key). Kiểm tra hash trước khi equals() là optimization quan trọng — int comparison cực nhanh, chỉ gọi equals() khi hash match. Nhánh treeifyBin (chain chạm 8 entry) là đường phòng thủ chống hash xấu — mổ riêng ở bài sau.

4. Resize — chuyện gì xảy ra khi map đầy?

Resize được trigger khi size vượt threshold (= capacity * loadFactor). Với default values, HashMap 16-bucket resize lần đầu khi có hơn 12 entry.

// Resize doubles capacity and redistributes entries -- OpenJDK 21
final Node<K,V>[] resize() {
    int oldCap  = (table == null) ? 0 : table.length;
    int oldThr  = threshold;
    int newCap  = oldCap << 1;       // double capacity
    int newThr  = (int)(newCap * loadFactor);

    Node<K,V>[] newTab = (Node<K,V>[]) new Node[newCap];
    // ... rehash entries ...
    return newTab;
}

Smart re-distribution Java 8 — không cần recompute hash:

// Doubling oldCap -> newCap adds one bit (position oldCap) to the bitmask.
// That bit's value in hash is (oldHash & oldCap):
//   == 0 -> stays at index i;  != 0 -> moves to index i + oldCap
if ((oldHash & oldCap) == 0) {
    // Entry stays in same bucket: loNode chain
} else {
    // Entry moves to i + oldCap: hiNode chain
}

Zoom vào đúng một bucket để thấy bit đó làm việc:

Java gọi hai nửa đó là lo và hi: mỗi entry chỉ so đúng một bit đọc từ hash đã cache trong Node, nên không hashCode() nào được gọi lại.

Amortized analysis: mỗi resize rehash N entry, nhưng resize chỉ xảy ra khi size gấp đôi lần trước — trung bình mỗi entry chịu O(1) work amortized qua toàn chuỗi put. Cùng lập luận với ArrayList.grow() ở bài trước; chứng minh hình thức ở khoá Thuật toán — Amortized analysis.

5. Pitfall tổng hợp

Pitfall 1 — Concurrent put không thread-safe

Java 7: hai thread đồng thời put() vào cùng bucket trong khi resize có thể tạo cycle trong linked list — thread thứ ba sau đó gọi get() vào bucket đó sẽ loop vô hạn, CPU spike 100%, không bao giờ return.

Java 8: không còn infinite loop (resize dùng tail-insertion thay head-insertion, phá cycle), nhưng race condition vẫn còn — entry có thể mất, duplicate, hoặc ghi đè sai. Data corruption im lặng, khó debug.

// WRONG: HashMap shared across threads
Map<String, Integer> wordCount = new HashMap<>();
words.parallelStream().forEach(w ->
    wordCount.merge(w, 1, Integer::sum)  // race condition on merge
);
// CORRECT: ConcurrentHashMap (or Collectors.groupingByConcurrent)
Map<String, Integer> wordCount = new ConcurrentHashMap<>();
words.parallelStream().forEach(w ->
    wordCount.merge(w, 1, Integer::sum)  // thread-safe
);

Fix: dùng ConcurrentHashMap hoặc Collections.synchronizedMap(new HashMap<>()) (synchronized toàn table — kém hiệu suất hơn nhưng đúng).

Pitfall 2 — Mutable key trong HashMap

Put User u vào map với hashCode() dựa trên email, rồi mutate u.email. get(u) trả null — key "lạc" ở bucket cũ, tìm bucket mới không thấy.

// Dangerous: hashCode() depends on mutable field
User u = new User(1L, "[email protected]");
Map<User, String> roles = new HashMap<>();
roles.put(u, "admin");

u.setEmail("[email protected]");  // mutate field used in hashCode!
String role = roles.get(u);     // null -- key "lost" in wrong bucket
// Entry still in map (memory leak) but unreachable

Cùng motif "mutable field phá hash" ở khoá Thuật toán — Hàm băm. Fix: hashCode chỉ dùng final field; prefer record cho value object làm HashMap key.

6. Sizing best practice

Hint initial capacity để tránh resize trong critical path:

// Default HashMap: initial capacity 16, resize at 12 entries
Map<String, User> cache = new HashMap<>();  // will resize multiple times for 1000 entries

// Pre-sized: no resize needed for 1000 entries
// HashMap allocates next power-of-2 >= (expectedSize / loadFactor)
// For 1000 entries: 1000 / 0.75 = 1333 -> next power-of-2 = 2048
int expectedSize = 1000;
Map<String, User> cache = new HashMap<>((int)(expectedSize / 0.75 + 1));

// Java 19+: factory method handles the math for you
Map<String, User> cache = HashMap.newHashMap(expectedSize);

Load factor tradeoffs:

Default 0.75 là kết quả benchmark từ Sun Microsystems — điểm cân bằng giữa collision rate và memory footprint.

7. Ứng dụng thực tế

Cơ chế bucket/chaining/resize bạn vừa trace là nền của cả một họ cấu trúc — mỗi biến thể chỉnh đúng một chỗ:

• LinkedHashMap = HashMap + doubly linked list xuyên mọi entry (insertion/access order) — backbone của LRU cache qua removeEldestEntry().
• ConcurrentHashMap (Java 8+) = cùng bucket array nhưng thay lock toàn map bằng CAS per-bucket — nội thất mổ kỹ ở ConcurrentHashMap nội thất.
• Redis dict = separate chaining tương tự nhưng rehash incremental (hai table, dời một bucket mỗi lần truy cập) — tránh chính cái latency spike resize của HashMap.

8. Deep Dive

Liên kết khoá học khác

• Khoá Java — Map và Set — API HashMap/TreeMap/LinkedHashMap thực tế và best practices khi dùng trong ứng dụng.
• Khoá Java — toString, equals, hashCode — equals/hashCode contract bắt buộc đúng để HashMap định vị key chính xác.

9. Tóm tắt

• Node<K,V>[] table: bucket index = (n-1) & hash(key) (bit AND, fast — chỉ đúng khi capacity là power-of-2); hash() trộn h ^ (h>>>16) để phân đều khi table nhỏ.
• Resize: double capacity, Java 8 dùng (oldHash & oldCap) phân lại entry mà không recompute hashCode. Một put trigger resize = O(N); O(1) chỉ đúng amortized.
• Mutable key = bug nghiêm trọng: hashCode thay đổi sau mutation → key lạc bucket, get() trả null, entry bị giữ vĩnh viễn → memory leak. Dùng final field hoặc record.
• Không thread-safe: Java 7 resize race gây infinite loop 100% CPU; Java 8 sửa loop nhưng vẫn data race. Dùng ConcurrentHashMap thay vì synchronizedMap cho concurrent write.
• Pre-size: HashMap.newHashMap(expectedSize) (Java 19+) hoặc new HashMap<>((int)(n / 0.75 + 1)) để tránh resize trên hot path.

10. Tự kiểm tra

Bài tiếp theo: HashMap treeify — phòng thủ hash-collision DoS