Tại sao bản đồ băm trong Java 8 sử dụng cây nhị phân thay vì danh sách liên kết?

Question

Gần đây tôi đã biết rằng trong bản đồ băm Java 8 sử dụng cây nhị phân thay vì danh sách liên kết và mã băm được sử dụng làm hệ số phân nhánh.I hiểu rằng trong trường hợp va chạm cao, việc tra cứu được giảm xuống O (log n) từ O (n) bằng cách sử dụng cây nhị phân. Câu hỏi của tôi là thực sự làm tốt khi độ phức tạp thời gian phân bổ vẫn là O (1) và có thể nếu bạn buộc lưu trữ tất cả các mục trong cùng một nhóm bằng cách cung cấp cùng một mã băm cho tất cả chìa khóa chúng ta có thể thấy sự khác biệt đáng kể về thời gian nhưng không ai trong tâm trí của họ sẽ làm điều đó.

Cây nhị phân cũng sử dụng nhiều không gian hơn danh sách được liên kết đơn lẻ vì nó lưu trữ cả hai nút trái và phải.Why tăng độ phức tạp của không gian khi hoàn toàn không có sự phức tạp về thời gian ngoại trừ một số trường hợp kiểm tra giả mạo.

Answer 1

Đây chủ yếu là thay đổi liên quan đến bảo mật. Mặc dù trong tình huống bình thường hiếm khi có thể có nhiều va chạm, nếu các khóa băm đến từ nguồn không đáng tin cậy (ví dụ như các tên tiêu đề HTTP nhận được từ máy khách), thì có thể và không khó để đặc biệt tạo đầu vào, do đó các khóa kết quả sẽ có cùng một hashcode. Bây giờ nếu bạn thực hiện nhiều lần tra cứu, bạn có thể bị từ chối dịch vụ. Có vẻ như có khá nhiều mã trong tự nhiên vốn dễ bị tấn công bởi loại tấn công này, do đó nó đã được quyết định sửa lỗi này ở phía Java.

Để biết thêm thông tin, tham khảo JEP-180.

Answer 2

Câu hỏi của bạn có chứa một số cơ sở sai.

1. A va chạm xô không nhất thiết là một va chạm băm. Bạn không cần phải có cùng một mã băm cho hai đối tượng để kết thúc tại cùng một nhóm. Thùng là một phần tử của một mảng và mã băm phải được ánh xạ tới một chỉ mục cụ thể. Vì kích thước mảng phải hợp lý đối với kích thước của Map, bạn không thể tăng kích thước mảng tùy ý để tránh va chạm với xô. Thậm chí còn có giới hạn lý thuyết rằng kích thước mảng có thể ở mức tối đa 2³¹ trong khi có 2³² mã băm có thể.
2. Việc có va chạm băm không phải là dấu hiệu của chương trình xấu. Đối với tất cả các đối tượng có không gian giá trị lớn hơn 2³², khả năng có các đối tượng riêng biệt có cùng mã băm là không thể tránh khỏi. String s là một ví dụ rõ ràng, nhưng ngay cả một số Point mang hai giá trị int hoặc một khóa đơn giản Long có va chạm băm không thể tránh khỏi. Vì vậy, chúng có thể phổ biến hơn bạn nghĩ và nó phụ thuộc rất nhiều vào trường hợp sử dụng.
3. Việc triển khai chỉ chuyển sang cây nhị phân khi số lần va chạm trong một nhóm vượt quá ngưỡng nhất định để chi phí bộ nhớ cao hơn chỉ áp dụng khi chúng sẽ trả hết. dường như có một sự hiểu lầm phổ biến liên quan đến cách họ làm việc. Kể từ khi va chạm xô không nhất thiết phải va chạm băm, tìm kiếm nhị phân đầu tiên sẽ tìm kiếm các mã băm. Chỉ khi các mã băm giống hệt nhau và khóa phù hợp thực hiện Comparable, thứ tự tự nhiên của nó sẽ được sử dụng. Các ví dụ bạn có thể đã tìm thấy trên web cố tình sử dụng cùng một mã băm cho các đối tượng để chứng minh việc sử dụng thực hiện Comparable nếu không sẽ không hiển thị. Những gì họ kích hoạt chỉ là phương sách cuối cùng của việc thực hiện.
4. Là Tagir pointed out, sự cố này có thể ảnh hưởng đến bảo mật của phần mềm dưới dạng dự phòng chậm có thể mở khả năng tấn công DoS. Đã có nhiều nỗ lực trong các phiên bản JRE trước đó để giải quyết vấn đề này có nhiều hạn chế hơn mức tiêu thụ bộ nhớ của cây nhị phân. Ví dụ, đã có một nỗ lực để phân ngẫu nhiên ánh xạ mã băm thành các mảng trong Java 7 gây ra phí khởi tạo như được ghi trong this bug report. Đây không phải là trường hợp với việc triển khai mới này.