Từ Java 8, HashMap xử lý bucket bị đụng độ nhiều như thế nào?

Trước Java 8, mọi entry trùng bucket nằm trên một danh sách liên kết → tra cứu xấu nhất là O(n). Từ Java 8, HashMap chuyển bucket thành cây đỏ-đen (red-black tree) khi bucket quá dài:

• TREEIFY_THRESHOLD = 8: bucket có từ 8 node trở lên thì cân nhắc chuyển sang cây.
• MIN_TREEIFY_CAPACITY = 64: nhưng nếu bảng còn nhỏ hơn 64 bucket thì resize thay vì treeify (bảng nhỏ thì đụng độ là do ít bucket, không phải do hàm băm xấu).
• UNTREEIFY_THRESHOLD = 6: khi resize/split làm cây còn ≤ 6 node thì đổi ngược về danh sách liên kết.

Kết quả: trường hợp xấu nhất của get/put giảm từ O(n) xuống O(log n). Đây cũng là biện pháp giảm tác hại của tấn công hash collision DoS (cố tình gửi hàng loạt key trùng hash).

Hai chi tiết hay bị hỏi thêm:
- HashMap trộn hash bằng h ^ (h >>> 16) để bit cao ảnh hưởng tới chỉ số bucket (vì chỉ số lấy bằng hash & (n - 1)).
- Node trong cây so sánh theo Comparable nếu key có cài; không thì so theo hash và tên class, nên cây chỉ giúp về độ phức tạp chứ không giúp sắp thứ tự.