Nhiều sách và hướng dẫn nói rằng kích thước của một bảng băm phải là nguyên tố phân phối đồng đều các khóa trong tất cả các nhóm. Nhưng Java HashMap luôn sử dụng kích thước là sức mạnh của hai. Không nên sử dụng một nguyên tố? Điều gì tốt hơn, một "nguyên tố" hoặc "sức mạnh của hai" là kích thước bảng băm?Java: Số "nguyên tố" hoặc "sức mạnh của hai" dưới dạng kích thước HashMap?
Sử dụng sức mạnh của hai mặt nạ hiệu quả trong các bit trên cùng của mã băm. Do đó, hàm băm chất lượng kém có thể hoạt động đặc biệt xấu trong trường hợp này.
Java HashMap giảm nhẹ điều này bằng cách mistrusting thực hiện của đối tượng hashCode() và applying a second level of hashing to its result:
Áp dụng một chức năng băm bổ sung cho một hashCode nhất định, trong đó bảo vệ chống lại các chức năng chất lượng băm nghèo. Điều này là rất quan trọng bởi vì HashMap sử dụng bảng băm chiều dài hai chiều, nếu không sẽ gặp phải các va chạm đối với hashCodes không khác nhau ở các bit thấp hơn.
Nếu bạn có chức năng băm tốt hoặc làm điều gì đó tương tự như những gì HashMap thực hiện, việc bạn sử dụng số nguyên tố, v.v ... có phải là không quan trọng.
Nếu, mặt khác, hàm băm có chất lượng không xác định hoặc kém, khi đó sử dụng số nguyên tố sẽ là đặt cược an toàn hơn. Tuy nhiên, nó sẽ làm cho các bảng có kích thước động được thực hiện, vì đột nhiên bạn cần có khả năng tạo ra các số nguyên tố thay vì chỉ nhân kích thước với một hệ số không đổi.
Hết sức tò mò: Tại sao? (hoặc bạn có tham khảo/liên kết giải thích điều này)? –
+1 để cập nhật –
Bạn có chắc kích thước của bảng không quan trọng? Không phải là điểm của hàm băm tốt để truyền dữ liệu ra ngoài bảng, để giảm số lần va chạm? Nhưng nếu bảng là rất nhỏ, sau đó va chạm sẽ tăng lên, bất kể hàm băm. Tui bỏ lỡ điều gì vậy? – pamphlet
Việc triển khai HashMap chuẩn có phương thức hash khôi phục mã băm của đối tượng của bạn để tránh lỗ hổng đó. Các bình luận trước the hash() method đọc:
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
Từ một thời gian điểm hiệu suất/tính xem điện-of-hai kích thước có thể được tính toán chỉ với mặt nạ chút đó là nhanh hơn so với sự phân chia số nguyên đó sẽ được yêu cầu khác.
Cách duy nhất để biết cái nào tốt hơn giữa số nguyên tố và lũy thừa của hai là để đánh giá nó.
Nhiều năm trước, khi viết một trình biên dịch có hiệu suất phụ thuộc mạnh vào tra cứu talbe biểu tượng, tôi đã thử nghiệm điều này bằng cách sử dụng một khối lớn các số nhận dạng được tạo. Ngay cả với một bản đồ ngây thơ, tôi thấy rằng sức mạnh của hai, như mong đợi, thậm chí còn ít phân phối và chuỗi dài hơn so với một số nguyên tố có kích thước tương tự nhau của các thùng. Nó vẫn chạy nhanh hơn, bởi vì tốc độ lựa chọn thùng bằng cách che mặt nạ bit.
Tôi thực sự nghi ngờ các nhà phát triển java.util sẽ không sử dụng thêm băm và sức mạnh của hai mà không có điểm chuẩn so với sử dụng số lượng nhóm chính. Đó là một điều thực sự rõ ràng để làm khi thiết kế một cấu trúc dữ liệu băm.
Vì lý do đó, tôi chắc chắn kích thước phục hồi và quyền lực của hai cung cấp hiệu suất tốt hơn cho các bản đồ băm Java điển hình so với số lượng nhóm chính.
Bạn có thể nên sử dụng bảng băm có kích thước chính nếu bạn sử dụng quadratic probing để giải quyết va chạm. Nếu bạn có một bảng có kích thước chính, thăm dò bậc hai sẽ nhấn một nửa số mục nhập, ít hơn nếu nó không phải là số nguyên tố. Vì vậy, bạn có thể không tìm thấy một nơi thích hợp để lưu trữ bạn nhập ngay cả khi bảng băm của bạn là ít hơn một nửa đầy đủ. Vì bản đồ băm Java không sử dụng thăm dò bậc hai, nên không cần sử dụng số nguyên tố làm kích thước.
Tôi nghi ngờ rằng họ thực sự nói chính xác điều đó và nếu họ làm sai. Đó chỉ là một cách để làm điều đó. – EJP