HashMap treeify — phòng thủ hash-collision DoS từ Java 8

TL;DR: HashMap trước Java 8 có worst case O(n): mọi key rơi cùng bucket thì get/put phải duyệt cả linked list. Attacker biết hash function có thể chế hàng nghìn key cùng hashCode — một request nhỏ đủ làm CPU spike 100% (hash-collision DoS). Java 8 (JEP 180) thêm treeify: chain đạt TREEIFY_THRESHOLD = 8 và table có từ MIN_TREEIFY_CAPACITY = 64 bucket trở lên → bucket chuyển thành red-black tree, worst case còn O(log n). Ngưỡng 8 chọn theo phân phối Poisson (tham số ~0.5 với load factor 0.75): hash tử tế gần như không bao giờ chạm ngưỡng — chạm nghĩa là hash bị lạm dụng. Treeify giảm thiệt hại nhưng không thay được validate input.

Trong một buổi load test, một dev fuzz API bằng 1000 request, mỗi request chứa key thiết kế sao cho tất cả đều hashCode = 0. Endpoint đang 1000 op/s bỗng spike CPU 100%, response time từ 5ms lên vài giây — không exception, không timeout, chỉ chậm dần rồi nghẹt.

Bài trước đã trace happy path: hash đều, chain ngắn, get là O(1). Bài này mổ đường phòng thủ khi hash không tử tế: vì sao 8, vì sao 64, red-black tree cứu được gì — và tầng phòng thủ nào vẫn phải đứng trước HashMap.

1. Ngăn tủ quá đầy — từ danh sách sang cây

Nhớ lại analogy tủ hồ sơ ở bài trước: mỗi ngăn (bucket) đựng một danh sách hồ sơ, tìm đúng người thì duyệt danh sách so từng tên. Ngăn càng dài, duyệt càng lâu. Khi một ngăn dồn tới 8 hồ sơ, tủ đổi chiến thuật: xếp ngăn đó thành cây tìm kiếm — tra O(log n) thay vì lật từng tờ O(n).

Ba hằng số điều khiển cơ chế này trong HashMap.java:

static final int TREEIFY_THRESHOLD    = 8;   // chain length >= 8 -> try treeify
static final int UNTREEIFY_THRESHOLD  = 6;   // tree size <= 6 -> back to list
static final int MIN_TREEIFY_CAPACITY = 64;  // min table size before treeify (else resize)

Ba con số này không tùy hứng — mỗi con số trả lời một câu hỏi thiết kế riêng, đi lần lượt dưới đây.

2. Vì sao TREEIFY_THRESHOLD = 8?

Với uniform hash và load factor 0.75, phân phối số entry trên một bucket xấp xỉ phân phối Poisson với tham số ~0.5 (trung bình mỗi bucket chứa ~0.5 entry, vì table luôn thưa sau resize — đừng nhầm với load factor 0.75). Xác suất để một bucket có đúng 8 entry xấp xỉ 6 phần 100 triệu — block comment trong HashMap.java ghi "less than 1 in ten million", tức ít hơn 1 trên 10 triệu. Khi điều đó xảy ra, gần như chắc chắn hash function bị lạm dụng — hoặc hashCode() của key class cực tệ, hoặc attacker cố tình tạo collision.

Treeify vì thế là biện pháp defensive: giảm worst case từ O(n) xuống O(log n) mà không đụng happy path — map bình thường không bao giờ trả chi phí cho nó.

Vì sao không phải con số khác?

• Threshold = 4: treeify quá thường xuyên ngay cả với hash bình thường — overhead red-black tree không đáng, và tree nhỏ không nhanh hơn list bao nhiêu do cache locality kém hơn.
• Threshold = 16: attacker có window dài gấp đôi để exploit trước khi defense kích hoạt.

Còn UNTREEIFY_THRESHOLD = 6 (không phải 8): khi remove làm tree co xuống 6 entry, tree revert lại linked list. Khoảng đệm 8/6 là hysteresis — nếu hai ngưỡng bằng nhau, map dao động quanh 8 entry sẽ liên tục dựng cây rồi phá cây (thrashing).

3. treeifyBin — resize trước, treeify sau

Chain đạt 8 chưa chắc đã treeify. Trước khi đọc code, tự quyết đã:

// treeifyBin -- OpenJDK 21
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 (spreads entries, shortens chain)
        resize();
    } else {
        // Table is large enough: convert linked list to red-black tree
        // ... (TreeNode conversion logic)
    }
}

Logic quyết định:

• Table nhỏ (dưới 64 bucket): gọi resize() thay vì treeify. Chain dài lúc này thường chỉ vì quá ít bucket — nhân đôi capacity phân tán key ra bucket mới, chain tự ngắn lại mà không cần overhead của cây.
• Table từ 64 bucket trở lên: capacity đã đủ lớn mà chain vẫn dài 8 — resize không cứu được nữa (key cố tình cùng hash thì phân tán kiểu gì cũng về cùng bucket). Lúc này mới convert bucket thành red-black tree.

flowchart TD
    A["put lam chain dat 8 entry"] --> B{"table.length duoi 64?"}
    B -->|"Dung"| C["resize: nhan doi capacity<br/>key phan tan, chain tu ngan lai"]
    B -->|"Sai"| D["treeifyBin: linked list -> red-black tree<br/>lookup O(log n)"]
    D --> E{"remove khien tree con 6 entry?"}
    E -->|"Dung"| F["untreeify: tro lai linked list"]

4. Hash-collision DoS — tấn công và phòng thủ

Trước Java 8, attacker biết hash function của JVM (String.hashCode() là thuật toán cố định, public, không randomization) có thể precompute hàng nghìn String key cùng hashCode. Nhét chúng vào form, JSON key, hoặc URL parameter — server deserialize vào HashMap, tất cả rơi vào cùng bucket, mỗi put/get là O(n). Một request vài trăm KB tiêu tốn CPU tương đương hàng triệu operation — denial of service với chi phí attacker gần bằng 0.

Java 8 treeify giảm worst case xuống O(log n) — nhẹ thiệt hại nhưng không loại bỏ hẳn: O(log n) với n = 10.000 vẫn là ~13 bước so với 1 bước của happy path, và attacker vẫn ép map dựng cây liên tục.

Defense theo thứ tự hiệu quả — treeify chỉ là tầng cuối:

1. Giới hạn input trước khi parse — validate số key tối đa trong JSON/form (Jackson StreamReadConstraints, Spring max-request-size). Chặn từ cửa, rẻ nhất.
2. Rate limiting theo IP/user cho endpoint nhận key tùy ý từ client.
3. Treeify (Java 8+) — lưới an toàn cuối, tự động, không config.
4. Hash seed randomization — một số runtime cho phép randomize seed per-process để attacker không precompute được (Java hiện chỉ randomize cho một số cấu trúc nội bộ, không phải String.hashCode() public).

Đây là defense-in-depth: không tầng nào một mình đủ, và không tầng nào thay được tầng đứng trước nó.

5. Deep Dive

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

• HashMap internals — bucket array, chaining, resize — cơ chế nền của bài này: happy path O(1), put path, resize.
• Hàm băm — khoá Thuật toán — uniform distribution và hashCode/equals contract, điều kiện để không bao giờ chạm ngưỡng treeify.
• ConcurrentHashMap nội thất — ConcurrentHashMap cũng treeify bucket theo cùng ngưỡng, nhưng phối hợp với CAS per-bucket.

6. Tóm tắt

• Treeify (Java 8, JEP 180): chain đạt 8 entry chuyển bucket thành red-black tree — lookup thoái hóa từ O(n) xuống O(log n). Đây là defense chống hash xấu, không phải optimization cho hash tốt.
• TREEIFY_THRESHOLD = 8 theo phân phối Poisson (tham số ~0.5): hash đều gần như không bao giờ chạm (xác suất ~1/17 triệu) — chạm ngưỡng là tín hiệu hash bị lạm dụng.
• UNTREEIFY_THRESHOLD = 6 tạo hysteresis với ngưỡng 8 — tránh thrashing dựng/phá cây khi size dao động quanh ngưỡng.
• MIN_TREEIFY_CAPACITY = 64: table nhỏ thì resize thay vì treeify — phân tán key rẻ hơn dựng cây; chỉ treeify khi resize hết cứu được.
• Hash-collision DoS: attacker precompute key cùng hashCode, mọi operation thành O(n). Treeify giảm còn O(log n) — giảm thiệt hại, không miễn nhiễm.
• Defense-in-depth: giới hạn input + rate limiting đứng trước; treeify là lưới an toàn cuối.

7. Tự kiểm tra

Đọc thêm ở khoá Thuật toán: Open addressing — probing tuyến tính/bậc hai, robin hood — chiến lược xử lý va chạm còn lại, và vì sao Java chọn chaining chứ không chọn nó.

Bài tiếp theo: Mini-challenge — chẩn đoán P99 spike và collision DoS