Tại sao HashMap trong Java có thể bị biến thành Red-Black Tree từ Java 8?

Cuộc tấn công từ chối dịch vụ bằng xung đột mã băm (Hash Collision DoS)#

Trước Java 8, cấu trúc dữ liệu HashMap sử dụng một mảng các thùng (Buckets), mỗi thùng là một danh sách liên kết đơn (LinkedList) để giải quyết xung đột mã băm (Chaining method).

Độ phức tạp lý tưởng để tìm kiếm một phần tử là $O(1)$. Tuy nhiên, nếu một kẻ tấn công cố tình gửi hàng triệu request chứa các chuỗi ký tự khác nhau nhưng có cùng một giá trị hashCode(), tất cả các phần tử này sẽ rơi vào cùng một bucket duy nhất:

• Danh sách liên kết kéo dài hàng triệu node.
• Độ phức tạp tìm kiếm bị thoái hóa từ $O(1)$ thành $O(N)$!
• Thao tác get() và put() tiêu tốn 100% CPU, làm tê liệt toàn bộ ứng dụng (Hash Collision Denial-of-Service Attack).

Cải tiến đột phá trong Java 8: Treeifying Threshold#

Để hóa giải cuộc tấn công này, đội ngũ phát triển Java đã đưa ra một cơ chế chuyển đổi cấu trúc tự động:

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

Quy tắc hoạt động:

1. Khi số lượng phần tử trong một bucket vượt quá ngưỡng TREEIFY_THRESHOLD = 8 và dung lượng mảng $\ge 64$:
   • Java sẽ tự động chuyển đổi danh sách liên kết đơn đó thành một Cây đỏ đen (Red-Black Tree - Cây nhị phân tìm kiếm tự cân bằng).
2. Lúc này, độ phức tạp tìm kiếm trong trường hợp xấu nhất giảm ngoạn mục từ $O(N)$ xuống còn: $$O(\log N)$$
3. Nếu các phần tử bị xóa bớt và số lượng giảm xuống dưới 6, cây sẽ tự động được chuyển đổi ngược lại thành LinkedList nhẹ nhàng để tiết kiệm bộ nhớ.

Vì sao lại chọn ngưỡng 8 mà không phải 2 hay 100?#

Theo phân phối xác suất Poisson: Với một hàm băm chuẩn (Uniform Hash Distribution), xác suất để 8 phần tử ngẫu nhiên rơi vào cùng một bucket là cực kỳ hiếm (nhỏ hơn 1 phần 10 triệu - $0.00000006$). Chỉ khi có sự cố bất thường hoặc tấn công có chủ đích thì ngưỡng 8 mới bị chạm tới!

Góc thảo luận#

Anh em đã từng phải viết lại phương thức equals() và hashCode() trong Java chưa? Quy tắc vàng khi override hai hàm này là gì?

Xem thêm nội dung liên quan:

• Bộ câu hỏi trắc nghiệm Java Chuyên sâu
• Học Cấu trúc Dữ liệu & Giải thuật