hàm băm hoàn hảo và lợi ích

Question

xem xét lớp này:

public final class MyDate { 
     private int year, month, day; 

     public MyDate(int year, int month, int day) { 
      this.year = year; 
      this.month = month; 
      this.day = day; 
     } 

     //Some stuff 

     @Override 
     public int hashCode() { 
      return ((year << 4) | month) << 5 | day; 
     } 
} 

Đây là một hàm băm hoàn hảo bởi vì trong ký ức chúng ta có:

Vì vậy, trong màu đỏ, 5 bits cửa hàng ngày (1 đến 31), trong màu vàng 4 bits lưu trữ tháng (1 đến 12) và các cửa hàng khác lưu trữ năm (1 đến 16777215).

Lợi ích của việc hoàn hảo hashFunction là gì? AFAIK, nó có thể đảm bảo việc thêm/xóa/chứa trong O(1) trong một HashSet nhưng tôi có thể nhận được lợi ích khác của việc có một?

Tôi thấy rằng nhiều hàm băm sử dụng số nguyên tố, cách tốt nhất để xây dựng một số là gì (tôi tưởng tượng rằng việc tạo một hàm băm hoàn hảo là không phổ biến/hiếm)?

---

EDIT:

Về số nguyên tố -> trả lời here

Answer 1

Một hàm băm hoàn hảo đảm bảo rằng bạn sẽ không có va chạm. Tuy nhiên, để có thể sử dụng, bạn phải biết chính xác tập hợp các giá trị khóa cần được băm, thường không phải như vậy.

Các hàm khác không hoàn hảo, nhưng hàm băm tốt (cùng với cơ chế giải quyết va chạm) không có yêu cầu đó và rất nhanh để tính toán, vì vậy chúng thường phù hợp hơn.

Answer 2

Theo Juampi nó nhanh. Nhanh như thế nào? Khoảng O (1). Redis là một ví dụ tuyệt vời về tra cứu thời gian liên tục trong bộ nhớ thông qua bảng băm.

Nếu bạn không có một thùng chính xác một phần tử trên kết quả của băm bạn cần sử dụng bằng để so sánh từng mục để bạn tra cứu O (1 cộng với z) trong đó z là kích thước nhóm.

Nhưng có chức năng băm rất chậm chắc chắn không phải là một ý tưởng tuyệt vời sau.