Giải thích các hằng số được sử dụng trong khi tính toán giá trị băm của java.util.hash

Question

Ai đó có thể giải thích tầm quan trọng của các hằng số này và tại sao chúng được chọn?

static int hash(int h) { 
     // This function ensures that hashCodes that differ only by 
     // constant multiples at each bit position have a bounded 
     // number of collisions (approximately 8 at default load factor). 
     h ^= (h >>> 20)^(h >>> 12); 
     return h^(h >>> 7)^(h >>> 4); 
    } 

nguồn: thư viện java-SE6

Answer 1

Tôi cũng đã tự hỏi về như số "kỳ diệu". Theo như tôi biết, họ là số ma thuật.
Nó đã được chứng minh bằng thử nghiệm rộng rãi rằng số lẻ và số nguyên tố có các ưu tiên thú vị có thể được sử dụng trong băm (tránh phân cụm chính/phụ, v.v.).
Tôi tin rằng hầu hết các con số đều đến sau khi nghiên cứu và thử nghiệm chứng minh thống kê để phân phối tốt. Tại sao đặc biệt những con số này làm được điều đó, tôi không có ý tưởng nhưng tôi có ấn tượng (hy vọng đồng nghiệp ở đây có thể chính xác cho tôi nếu tôi cách tắt) không phải người thực hiện biết tại sao những cụ số trình bày những phẩm chất

Answer 2

Hiểu những gì làm cho một hàm băm tốt là khó khăn, vì thực tế có rất nhiều hàm khác nhau được sử dụng và cho các mục đích hơi khác nhau.

bảng băm Java làm việc như sau:

1. Họ yêu cầu đối tượng chủ chốt để tạo ra mã băm của nó. Việc triển khai phương thức hashCode() có thể có chất lượng biến đổi rõ ràng (trong trường hợp xấu nhất, trả lại giá trị không đổi!) Và chắc chắn sẽ không được điều chỉnh cho bảng băm cụ thể mà bạn đang làm việc.
2. Sau đó, họ sử dụng hàm trên để trộn các bit lên một chút, sao cho thông tin có trong các bit cao cũng được chuyển xuống các bit thấp. Điều này quan trọng vì tiếp theo…
3. Họ lấy mod của mã băm (w.r.t. số lượng các mảng bảng băm) để đưa chỉ mục vào mảng chuỗi bảng băm. Có một khả năng khác biệt là mảng bảng băm sẽ có kích thước tương đương với lũy thừa là 2, do đó việc trộn các bit trong bước 2 là quan trọng để đảm bảo chúng không bị vứt bỏ.
4. Sau đó, họ đi qua chuỗi cho đến khi họ đến được mục nhập bằng khóa bằng nhau (theo phương pháp equals()).

Để hoàn thành hình ảnh, số lượng mục nhập trong mảng bảng băm không cố định; nếu các chuỗi nhận được quá lâu mảng được thay thế bằng một mảng lớn hơn mới và tất cả mọi thứ được phục hồi. Điều đó tương đối nhanh và có ý nghĩa hiệu suất tốt cho các mẫu sử dụng thông thường (ví dụ: rất nhiều put() s theo sau là rất nhiều get() s).

Hằng số thực tế được sử dụng khá tùy ý (và có thể được chọn bằng thử nghiệm với một số đơn vị đơn giản bao gồm những thứ như số lượng lớn Integer và String giá trị) nhưng mục đích của chúng không: nhận thông tin trong toàn bộ giá trị được lan truyền đến hầu hết các bit thấp trong giá trị đảm bảo rằng các thông tin như hiện diện trong đầu ra của hashCode() được sử dụng hết mức có thể.

(Bạn sẽ không làm điều này với băm hoàn hảo hoặc băm mật mã; bất chấp tên tương tự, chúng có các chiến lược triển khai rất khác nhau. thông tin được di chuyển về mọi hướng, không chỉ cho các bit thấp.)