HashMap internals — Separate chaining + treeify từ Java 8

Stack Overflow ghi rõ: HashMap.get() là amortized O(1). Junior dev tin tuyệt đối — và phần lớn trường hợp, họ đúng. Nhưng trong một buổi load test, một dev tinh nghịch fuzz API bằng 1000 request, mỗi request chứa key được thiết kế sao cho tất cả đều có hashCode = 0. Endpoint bình thường xử lý 1000 op/s bỗng spike CPU lên 100%, response time từ 5ms lên vài giây. Không có exception, không có timeout — chỉ có hệ thống chậm dần rồi nghẹt.

Bài này giải thích cơ chế bên trong HashMap: bucket array, chaining, treeify Java 8, resize, khi nào O(1) claim thực sự đứng vững và khi nào break. Sau bài này bạn đọc được HashMap.java source và benchmark đúng giá trị HashMap cho production.

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

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

Mỗi ngăn chứa một danh sách (linked list) khi nhiều hồ sơ cùng chữ cuối tên. Để tìm đúng người, bạn duyệt danh sách trong ngăn đó so sánh từng tên — equals(). Khi danh sách quá dài (8 hồ sơ trở lên), thay vì list, ngăn đó chuyển sang cấu trúc cây tìm kiếm — tìm O(log n) thay vì O(n). Khi tủ đầy 75%, thêm ngăn gấp đôi và sắp xếp lại.

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
// Since table.length is always a power of 2, (n-1) is a bitmask:
// n=16 -> n-1 = 0b1111 -> keeps only 4 lowest bits
// n=32 -> n-1 = 0b11111 -> keeps only 5 lowest bits
// Faster than % operator, equivalent when n is power-of-2
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
  [1]  null
  [2]  --> Node{hash, "beta", 200, null}
  [3]  --> Node{hash, "alpha", 100, next} --> Node{hash, "delta", 400, null}
  [4]  null
  ...
  [9]  --> Node{hash, "gamma", 300, null}
  ...
  [15] null

size = 4
threshold = 16 * 0.75 = 12

Các hằng số quan trọng:

// Treeify / untreeify thresholds
static final int TREEIFY_THRESHOLD     = 8;   // list length >= 8 -> treeify
static final int UNTREEIFY_THRESHOLD   = 6;   // tree size <= 6 -> back to list
static final int MIN_TREEIFY_CAPACITY  = 64;  // minimum table size before treeify
                                               // (if table < 64, resize instead)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int   DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

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 (line 628):

// Simplified from HashMap.putVal() -- OpenJDK 21, line ~628
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++) {
            if (p.next == null) {
                // Reached end of chain: append new node
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // binCount is 0-indexed
                    treeifyBin(tab, i);                // chain length hit 8, treeify
                break;
            }
            // Key already exists: update value
            if (p.hash == hash && (p.key == key || key.equals(p.key))) {
                p.value = value;
                break;
            }
            p = p.next;
        }
    }

    // 4. Resize if size exceeds threshold
    if (++size > threshold)
        resize();

    return null; // simplified: actual code returns old value
}

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. Khi binCount đạt TREEIFY_THRESHOLD - 1 (tức 7, 0-indexed), chain length là 8 — trigger treeifyBin.

4. Treeify Java 8 — defensive against bad keys

Khi một bucket tích lũy 8 entry, treeifyBin() được gọi. Nhưng không phải lúc nào cũng treeify ngay:

// treeifyBin -- OpenJDK 21, line ~770
final void treeifyBin(Node<K,V>[] tab, int index) {
    int n;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        // Table too small: resize is cheaper than treeify
        // Resize distributes entries to new buckets, reducing chain length
        resize();
    } else {
        // Table is large enough: convert linked list to red-black tree
        // ... (TreeNode conversion logic)
    }
}

Logic quyết định:

• Table size dưới 64: gọi resize() thay vì treeify. Lý do: resize đôi capacity thường phân tán key ra các bucket mới — chain tự ngắn lại mà không cần overhead của red-black tree.
• Table size từ 64 trở lên: convert bucket đó thành red-black tree — lookup thoái hóa từ O(n) xuống O(log n).

Khi entry trong tree giảm xuống 6 (qua remove), tree revert lại linked list — UNTREEIFY_THRESHOLD = 6 tránh thrashing giữa hai cấu trúc.

Vì sao TREEIFY_THRESHOLD = 8? Với uniform hash và load factor 0.75, xác suất để một bucket có đúng 8 entry xấp xỉ 1 trên 100 triệu (phân phối Poisson với tham số 0.75). Khi điều đó xảy ra, gần như chắc chắn hash function đang bị lạm dụng hoặc attacker đang cố tình tạo collision. Treeify là biện pháp defensive: giảm worst case từ O(n) xuống O(log n) mà không ảnh hưởng happy path.

Con số 4 sẽ trigger treeify quá thường xuyên với hash function bình thường — overhead không đáng. Con số 16 thì quá trễ — attacker có thể khai thác window dài hơn.

5. Resize operation

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, line ~700
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:

// For each node in old bucket[i], determine new bucket in doubled table:
// newCap = oldCap * 2 (e.g., 16 -> 32)
// New bitmask: (newCap - 1) = 0b11111, vs old (oldCap - 1) = 0b01111
// The extra bit is exactly bit at position oldCap (e.g., bit 4 for oldCap=16)
//
// (oldHash & oldCap) == 0  ->  extra bit is 0  ->  stays at index i
// (oldHash & oldCap) != 0  ->  extra bit is 1  ->  moves to index i + oldCap

if ((oldHash & oldCap) == 0) {
    // Entry stays in same bucket: loNode chain
} else {
    // Entry moves to i + oldCap: hiNode chain
}

Ví dụ: oldCap = 16, oldHash = 0b...10011 (bit 4 = 1). Entry ở bucket 3 (0011) di chuyển sang bucket 19 (10011). oldHash & 16 != 0 → new index = 3 + 16 = 19. Không cần gọi lại hash() hay hashCode().

Amortized analysis: mỗi lần resize, N entry phải được rehash. Nhưng resize xảy ra khi size tăng gấp đôi so với lần resize trước — mỗi entry trung bình chịu O(1) work do resize, amortized qua toàn bộ chuỗi put. Cross-link: Module 1 bài 03 (amortized analysis).

6. 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 vì head-insertion, phá cycle), nhưng race condition vẫn tồn tại — entry có thể bị mất, duplicate, hoặc bị 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
Map<String, Integer> wordCount = new ConcurrentHashMap<>();
words.parallelStream().forEach(w ->
    wordCount.merge(w, 1, Integer::sum)  // thread-safe
);
// Or: use Collectors.groupingByConcurrent for stream aggregation

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 — Hash collision attack (DoS)

Trước Java 8, attacker biết hash function của JVM (fixed algorithm, không có randomization) có thể tạo hàng nghìn String key với cùng hashCode. Gửi form, JSON, hoặc URL parameter chứa các key đó → tất cả vào cùng bucket → put và get đều O(n) → CPU spike, denial of service.

Java 8 treeify giảm worst case xuống O(log n) — giảm nhẹ thiệt hại nhưng không loại bỏ hoàn toàn. O(log n) với n = 10.000 vẫn là 13 so với 1 của happy path.

Defense:

• Validate và giới hạn số key trong input trước khi cho vào HashMap (Spring max-request-size, Jackson maxNestingDepth).
• Với untrusted key (user-controlled string), cân nhắc dùng hash function có randomized seed. Một số JVM config cho phép hash seed randomization.
• Log và alert khi một request chứa quá nhiều key trùng bucket.

Pitfall 3 — Mutable key trong HashMap

Put User u vào map khi hashCode() dựa trên email. Sau đó mutate u.email. get(u) trả về null — key bị "lạc" vào bucket cũ, tìm ở bucket mới không có.

// 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

Cross-link: Module 3 bài 01 (hash function — pitfall 2 mutable field). Fix: hashCode chỉ dùng final field; prefer record cho value object làm HashMap key.

7. 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.

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

HashMap vs LinkedHashMap: LinkedHashMap thêm doubly linked list xuyên qua tất cả entry theo insertion order (hoặc access order khi accessOrder = true). Access-order LinkedHashMap là backbone của LRU cache pattern — removeEldestEntry() override tự động evict entry cũ nhất. Cross-link: Module 2 bài 07 (LRU mini-challenge).

ConcurrentHashMap Java 8+: Java 7 chia table thành 16 segment cố định, mỗi segment có một lock (segment-level locking). Java 8 bỏ segment — dùng CAS (Compare-And-Swap) ở bucket level: putIfAbsent và addCount không cần lock khi bucket trống. Khi có collision mới cần synchronized block nhỏ hơn. Throughput cao hơn, contention thấp hơn — đặc biệt quan trọng khi key phân tán đều (uniform hash).

Redis dict: Redis dùng hash table với separate chaining tương tự, nhưng rehash theo kiểu incremental — thay vì block toàn bộ trong một resize, Redis duy trì hai table cùng lúc (ht[0] và ht[1]) và di chuyển một bucket mỗi lần có read/write. Không có latency spike do resize. Cross-link: Module 3 bài 11 (Redis case study).

Caffeine / Guava Cache: dùng segmented ConcurrentHashMap pattern với eviction policy bổ sung (W-TinyLFU trong Caffeine). Hiểu internals của HashMap giúp tuning maximumSize, initialCapacity, concurrencyLevel đúng giá trị.

9. Deep Dive

10. Tóm tắt

• HashMap = bucket array + chaining: Node<K,V>[] table, mỗi bucket là linked list. Bucket index tính bằng (n-1) & hash(key) — bit AND nhanh hơn modulo, chỉ đúng khi capacity là power-of-2.
• Put path: empty bucket → O(1) insert trực tiếp; collision → walk linked list, compare hash rồi equals(); khi chain đạt 8 entry → treeify.
• Treeify Java 8: chain dài từ 8 entry trở lên chuyển thành red-black tree — lookup thoái hóa từ O(n) xuống O(log n). Chỉ treeify khi table size từ 64 trở lên; nhỏ hơn thì resize trước.
• TREEIFY_THRESHOLD = 8: xác suất Poisson khoảng 1 trên 100 triệu với hash đều — khi đạt ngưỡng này gần như chắc chắn hash function bị lạm dụng.
• Resize: double capacity khi size vượt threshold. Smart re-distribution Java 8 dùng (oldHash & oldCap) để phân entry mà không recompute hashCode. Amortized O(1) per put.
• Mutable key = bug: hashCode đổi sau mutation → key "lạc" bucket, get() trả null, memory leak. Dùng final field hoặc record.
• HashMap không thread-safe: dùng ConcurrentHashMap hoặc synchronizedMap() khi multi-thread. Java 7 race condition gây infinite loop; Java 8 sửa loop nhưng vẫn data race.
• Pre-size để tránh resize: HashMap.newHashMap(expectedSize) (Java 19+) hoặc new HashMap<>((int)(n / 0.75 + 1)) cho latency-sensitive path.

11. Tự kiểm tra

Bài tiếp theo: Open addressing — linear/quadratic probing, robin hood