HashMap collision trong Java: từ hash function đến red-black tree

“HashMap hoạt động thế nào?” có lẽ là câu hỏi phỏng vấn Java phổ biến nhất mọi thời đại. Phần khó nhất — và cũng là phần phân biệt câu trả lời tốt với câu trả lời thuộc lòng — nằm ở cách nó xử lý collision.

TL;DR

• HashMap là một mảng các bucket. Vị trí bucket = (n - 1) & hash, với n là capacity (luôn là lũy thừa của 2).
• Collision xảy ra khi hai key khác nhau rơi vào cùng một bucket — do trùng hashCode() hoặc do trùng index sau phép &.
• Java xử lý collision bằng separate chaining: mỗi bucket chứa một linked list.
• Từ Java 8: khi một bucket có quá nhiều phần tử (ngưỡng 8) và table đủ lớn (≥ 64), linked list chuyển thành red-black tree → lookup trong bucket từ O(n) xuống O(log n). Khi co lại còn ≤ 6 thì chuyển về list.
• Khi số phần tử vượt capacity × loadFactor (mặc định 16 × 0.75 = 12), table resize gấp đôi, phân bố lại phần tử — cũng là cách giảm collision.
• hashCode() kém chất lượng hoặc key mutable là nguyên nhân chính gây collision nặng và bug.

flowchart LR
    K[key] --> H["hashCode()"] --> S["spread: h ^ (h >>> 16)"] --> I["index = (n-1) & hash"] --> B[bucket]
    B --> E{"bucket rỗng?"}
    E -- Có --> N[Đặt node vào]
    E -- Không --> C["COLLISION: duyệt list / tree, so sánh equals()"]

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

transient Node<K,V>[] table;   // mảng bucket

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;            // con trỏ tới node kế tiếp trong cùng bucket
}

Các hằng số quan trọng trong source code của JDK:

Hình dung một table có collision:

flowchart LR
    subgraph table["table (n = 16)"]
        b0["[0]"]
        b1["[1]"]
        b2["[2]"]
        b3["[3]"]
        b15["[15]"]
    end
    b0 --> n0["'apple'"]
    b1 --> x1[null]
    b2 --> n2a["'Aa'"] --> n2b["'BB'"] --> n2c["'cat'"]
    b3 --> n3["'dog'"]
    b15 --> x15[null]

Bucket [2] đang có collision: ba key cùng nằm trong một chain.

2. Từ key đến bucket: ba bước

2.1. hashCode() của key

Do class của key cung cấp. Ví dụ String.hashCode():

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

2.2. Spread: trộn bit cao xuống bit thấp

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Tại sao cần bước này? Phép tính index chỉ dùng vài bit thấp của hash (với n = 16 chỉ dùng 4 bit). Nếu các key chỉ khác nhau ở bit cao, chúng sẽ dồn vào cùng bucket. XOR 16 bit cao vào 16 bit thấp giúp bit cao cũng “góp mặt” vào index, với chi phí gần như bằng 0.

Lưu ý: key null luôn có hash 0 → luôn nằm ở bucket 0. HashMap cho phép một key null.

2.3. Tính index

index = (n - 1) & hash;

Vì n là lũy thừa của 2, n - 1 có dạng 0...01111, nên phép & tương đương hash % n nhưng nhanh hơn nhiều và luôn không âm. Đây là lý do capacity luôn được làm tròn lên lũy thừa của 2 — new HashMap<>(10) thực chất có capacity 16.

Ví dụ với n = 16 (n - 1 = 15 = 0b1111):

hash      = 0b ...1010 1101 0011   →  & 0b1111  →  0b0011 = 3
hash khác = 0b ...0111 0010 0011   →  & 0b1111  →  0b0011 = 3   ← COLLISION dù hash khác nhau

3. Hai loại collision

Index collision là bình thường và không tránh khỏi (nguyên lý chuồng bồ câu): hash có 2³² giá trị nhưng table chỉ có n bucket. Full hash collision thì do chất lượng hàm hashCode().

Kiểm chứng nhanh:

System.out.println("Aa".hashCode());   // 2112
System.out.println("BB".hashCode());   // 2112
// "AaAa", "AaBB", "BBAa", "BBBB" cũng cùng hashCode → có thể sinh ra vô số key trùng hash

4. put() xử lý collision thế nào

flowchart TB
    S["put(key, value)"] --> T{"table null?"}
    T -- Có --> R0["resize() - khởi tạo table 16"] --> I
    T -- Không --> I["i = (n-1) & hash"]
    I --> E{"table[i] rỗng?"}
    E -- Có --> NEW["table[i] = newNode"] --> SZ
    E -- Không --> F{"node đầu có cùng hash và equals(key)?"}
    F -- Có --> UPD[Ghi đè value, return value cũ]
    F -- Không --> TR{"bucket là TreeNode?"}
    TR -- Có --> PT["putTreeVal() - chèn vào red-black tree"] --> SZ
    TR -- Không --> L["Duyệt linked list"]
    L --> LF{"Tìm thấy key trùng?"}
    LF -- Có --> UPD
    LF -- Không --> APP["Nối node mới vào CUỐI list"]
    APP --> TH{"Độ dài chain đạt TREEIFY_THRESHOLD?"}
    TH -- Có --> TB["treeifyBin()"] --> SZ
    TH -- Không --> SZ{"++size > threshold?"}
    SZ -- Có --> RS["resize()"]
    SZ -- Không --> DONE[Xong]
    RS --> DONE

Điểm quan trọng khi so sánh key trong chain:

p.hash == hash && (p.key == key || (key != null && key.equals(p.key)))

1. So sánh hash trước (phép so sánh int, rất rẻ) để loại nhanh.
2. So sánh reference (==).
3. Cuối cùng mới gọi equals().

Đây là lý do contract equals() ↔ hashCode() quan trọng: nếu hai object equals nhưng hashCode khác nhau, chúng có thể nằm ở hai bucket khác nhau, HashMap sẽ coi là hai key khác nhau.

get() đi theo đúng lộ trình trên: tính index → kiểm tra node đầu → duyệt list hoặc tìm trong tree.

5. Treeify: từ linked list sang red-black tree (Java 8+)

5.1. Vì sao cần?

Với linked list, nếu nhiều key dồn vào một bucket, get()/put() trên bucket đó tốn O(k) với k là độ dài chain. Trường hợp xấu nhất (mọi key trùng hash) → O(n), HashMap thoái hóa thành linked list.

5.2. Điều kiện treeify

flowchart TB
    A[Chain dài tới ngưỡng TREEIFY_THRESHOLD = 8] --> B{"table.length >= MIN_TREEIFY_CAPACITY = 64?"}
    B -- Không --> C["resize() - gấp đôi table, chia chain ra"]
    B -- Có --> D["Chuyển bucket thành red-black tree (TreeNode)"]

Tại sao lại ưu tiên resize khi table còn nhỏ? Vì với table nhỏ, chain dài thường chỉ do thiếu bucket chứ không phải hash tệ — resize là giải pháp rẻ và hiệu quả hơn.

5.3. Tại sao ngưỡng là 8?

Với hash phân bố ngẫu nhiên tốt và load factor 0.75, số node trong một bucket tuân theo phân phối Poisson với tham số khoảng 0.5. Theo comment trong source code JDK, xác suất một bucket có 8 phần tử chỉ khoảng 0.00000006. Nghĩa là: nếu treeify xảy ra, gần như chắc chắn hashCode() có vấn đề (hoặc đang bị tấn công). Tree là “lưới an toàn”, không phải trạng thái bình thường.

Tại sao không treeify luôn từ đầu? TreeNode tốn khoảng gấp đôi bộ nhớ so với Node thường (thêm con trỏ parent, left, right, prev và cờ màu), và chi phí duy trì cân bằng cao hơn. Với chain ngắn, duyệt list tuần tự nhanh hơn.

Tại sao untreeify là 6 chứ không phải 8? Tạo hysteresis — tránh tình trạng một bucket dao động quanh 8 phần tử và liên tục chuyển qua lại giữa list và tree.

5.4. Tree được sắp xếp theo gì?

Red-black tree cần thứ tự giữa các key. HashMap so sánh theo thứ tự:

1. Giá trị hash.
2. Nếu trùng hash và key implement Comparable cùng kiểu → dùng compareTo().
3. Nếu vẫn không phân định được → tieBreakOrder() (so sánh tên class, rồi System.identityHashCode).

Hệ quả: key trùng hash và implement Comparable thì lookup thực sự O(log n). Key trùng hash nhưng không Comparable thì khi tìm kiếm có thể phải duyệt cả hai nhánh con → trong trường hợp tệ nhất vẫn có thể O(n). String, Integer, Long đều là Comparable nên được hưởng lợi đầy đủ.

6. Resize: giảm collision bằng cách thêm bucket

Khi size > threshold (threshold = capacity × loadFactor), table được nhân đôi.

Mẹo thông minh của Java 8: vì capacity gấp đôi, index mới chỉ phụ thuộc thêm một bit của hash — bit ở vị trí oldCap:

if ((e.hash & oldCap) == 0)  → giữ nguyên index j          (list "lo")
else                          → chuyển sang index j + oldCap (list "hi")

flowchart LR
    subgraph Old["Trước resize (n = 16)"]
        o5["[5]: A → B → C → D"]
    end
    subgraph New["Sau resize (n = 32)"]
        n5["[5]: A → C  (hash & 16 == 0)"]
        n21["[21]: B → D  (hash & 16 != 0)"]
    end
    o5 --> n5
    o5 --> n21

Không cần tính lại hash, không cần modulo, và thứ tự tương đối trong list được giữ nguyên. Tree bin cũng được tách đôi tương tự; phần nào còn ≤ 6 node sẽ chuyển về list.

Resize tốn O(n) — lý do nên khởi tạo capacity phù hợp khi biết trước số phần tử:

// Java 19+: tính sẵn capacity để chứa 1000 phần tử mà không resize
Map<String, User> map = HashMap.newHashMap(1000);

// Trước Java 19
Map<String, User> map = new HashMap<>((int) Math.ceil(1000 / 0.75));

Lưu ý: new HashMap<>(1000) không đủ để tránh resize — 1000 được làm tròn thành 1024, threshold là 768.

7. Java 7 vs Java 8

Bug kinh điển của Java 7: khi nhiều thread cùng resize một HashMap, head insertion kết hợp với việc đảo thứ tự list có thể tạo ra vòng lặp trong linked list → get() chạy vòng lặp vô hạn, CPU 100%. Java 8 dùng tail insertion nên không còn vòng lặp này, nhưng HashMap vẫn không thread-safe: vẫn có thể mất dữ liệu, size sai, hoặc hỏng cấu trúc tree.

8. Collision như một lỗ hổng bảo mật: Hash flooding

Kẻ tấn công có thể cố tình gửi hàng nghìn key có cùng hashCode (rất dễ sinh với String, như ví dụ "Aa"/"BB"). Nếu server lưu chúng vào HashMap — ví dụ khi parse query parameter, form data, JSON — mọi thao tác thoái hóa thành O(n), tổng chi phí O(n²) → Denial of Service với rất ít request.

Lịch sử xử lý:

• Năm 2011, lỗ hổng này được công bố rộng rãi, ảnh hưởng nhiều ngôn ngữ và web server.
• Java 7u6 thêm alternative hashing cho String (tùy chọn qua system property).
• Java 8 bỏ alternative hashing, thay bằng treeify — tấn công bằng key String trùng hash chỉ làm lookup thành O(log n), không còn O(n).

Đây là câu trả lời hay khi được hỏi: “Tại sao Java 8 lại thêm red-black tree vào HashMap?”

Bên cạnh đó, server còn giới hạn số lượng parameter (ví dụ Tomcat có maxParameterCount) như một lớp phòng thủ khác.

9. Những bug thực tế liên quan

9.1. hashCode() tệ

@Override
public int hashCode() {
    return 1;   // hợp lệ về contract, nhưng MỌI key rơi vào cùng bucket
}

Đúng về mặt logic nhưng performance thảm họa. Dùng Objects.hash(field1, field2), hoặc dùng record (Java 16+) để có equals/hashCode chuẩn tự động.

9.2. Override equals() mà quên hashCode()

Map<Point, String> map = new HashMap<>();
map.put(new Point(1, 2), "A");
map.get(new Point(1, 2));   // null! Hai object có hashCode (identity) khác nhau → khác bucket

9.3. Key mutable

List<Integer> key = new ArrayList<>(List.of(1, 2));
map.put(key, "value");
key.add(3);                 // hashCode của key thay đổi
map.get(key);               // null — map tìm ở bucket mới, node vẫn nằm ở bucket cũ
map.containsKey(key);       // false, nhưng map.size() == 1 → "memory leak" logic

Nguyên tắc: key của HashMap nên là immutable (String, Integer, record, enum…), hoặc ít nhất các field tham gia hashCode không được thay đổi sau khi put.

9.4. Dùng HashMap giữa nhiều thread

Dùng ConcurrentHashMap. Trong Java 8+, nó dùng CAS khi chèn vào bucket rỗng và synchronized trên node đầu của bucket khi có collision — nên lock chỉ ảnh hưởng một bucket, không phải cả map. Nó cũng treeify giống HashMap, nhưng không cho phép key hoặc value null (vì null gây mơ hồ giữa “không có key” và “value là null” trong môi trường đồng thời).

10. Độ phức tạp tổng hợp

Duyệt toàn bộ map tỉ lệ với capacity, không chỉ với số phần tử — map có capacity lớn nhưng ít phần tử vẫn duyệt chậm.

11. Câu hỏi phỏng vấn thường gặp

1. Collision là gì? Java xử lý thế nào? → Hai key cùng bucket; separate chaining bằng linked list, Java 8 thêm red-black tree.
2. Khi nào linked list chuyển thành tree? → Chain đạt ngưỡng 8 và capacity ≥ 64; nếu capacity < 64 thì resize.
3. Tại sao ngưỡng là 8, và tại sao untreeify là 6? → Theo phân phối Poisson rất hiếm khi xảy ra với hash tốt; 6 để tạo hysteresis.
4. Tại sao capacity luôn là lũy thừa của 2? → Tính index bằng & thay cho %; resize chỉ cần xét thêm 1 bit.
5. Tại sao hash() lại XOR với h >>> 16? → Đưa bit cao vào bit thấp vì index chỉ dùng bit thấp.
6. Chuyện gì xảy ra nếu override equals() mà không override hashCode()? → Object “bằng nhau” rơi vào bucket khác nhau, get trả về null.
7. Tại sao nên dùng immutable object làm key? → hashCode đổi sau khi put thì không tìm lại được entry.
8. HashMap có thread-safe không? Có vấn đề gì ở Java 7? → Không; Java 7 có thể vòng lặp vô hạn khi resize đồng thời; dùng ConcurrentHashMap.
9. Tại sao Java 8 thêm tree vào HashMap? → Giới hạn worst case, chống hash flooding DoS.