Ai có thể giải thích về cách thiết kế hàm băm Hash() của HashMap?

Question

sau khi tôi đọc mã nguồn của JDK, tôi thấy hàm hash() của HashMap có vẻ thú vị. đang soucre của nó như thế này:

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); 
} 

Parameter h là hashCode từ Objects được đưa vào HashMap. Phương pháp này hoạt động như thế nào và tại sao? Tại sao phương pháp này có thể bảo vệ chống lại hàm băm hàm băm kém?

Answer 1

Hashtable sử dụng cách tiếp cận 'cổ điển' của số nguyên tố: để lấy 'chỉ mục' của một giá trị, bạn lấy hàm băm của khóa và thực hiện mô đun so với kích thước. Lấy một số nguyên tố như kích thước, cho (thường) một lây lan tốt đẹp trên các chỉ mục (tùy thuộc vào băm là tốt, tất nhiên).

HashMap sử dụng 'sức mạnh của phương pháp hai', có nghĩa là kích thước là sức mạnh của hai. Lý do là nó được cho là nhanh hơn các phép tính số nguyên tố. Tuy nhiên, vì sức mạnh của hai không phải là số nguyên tố, sẽ có nhiều va chạm hơn, đặc biệt là với các giá trị băm có cùng bit thấp hơn.

Tại sao? Mô đun được thực hiện dựa trên kích thước để lấy chỉ mục (bucket/slot) được tính toán đơn giản bởi: hash & (size-1) (chính xác là những gì được sử dụng trong HashMap để lấy chỉ mục!). Về cơ bản, đó là vấn đề với cách tiếp cận 'quyền lực của hai': nếu độ dài bị giới hạn, ví dụ: 16, giá trị mặc định của HashMap, chỉ các bit cuối cùng được sử dụng và do đó, các giá trị băm có cùng bit thấp hơn sẽ dẫn đến cùng một chỉ mục (bucket). Trong trường hợp 16, chỉ 4 bit cuối cùng được sử dụng để tính chỉ mục.

Đó là lý do tại sao băm thừa được tính và về cơ bản nó chuyển giá trị bit cao hơn và hoạt động trên chúng với giá trị bit thấp hơn. Lý do cho các con số 20, 12, 7 và 4, tôi không thực sự biết. Chúng được sử dụng khác nhau (trong Java 1.5 hay như vậy, hàm băm có chút khác biệt). Tôi cho rằng có nhiều tài liệu cao cấp hơn. Bạn có thể tìm thêm thông tin về lý do tại sao họ sử dụng các số họ sử dụng trong tất cả các loại tài liệu liên quan đến thuật toán, ví dụ:

http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming

http://mitpress.mit.edu/books/introduction-algorithms

http://burtleburtle.net/bob/hash/evahash.html#lookup sử dụng thuật toán khác nhau tùy thuộc vào độ dài (mà làm cho một số ý nghĩa).

http://www.javaspecialists.eu/archive/Issue054.html cũng có thể thú vị. Kiểm tra phản ứng của Joshua Bloch ở gần cuối bài báo: "Hàm băm thứ hai thay thế (mà tôi đã phát triển với sự trợ giúp của máy tính) có các thuộc tính thống kê mạnh mẽ để đảm bảo phân phối tốt.") Vì vậy, nếu bạn hỏi tôi , những con số đến từ một số loại phân tích được thực hiện bởi Josh mình, có lẽ được hỗ trợ bởi những người hiểu biết ai.

Vì vậy: sức mạnh của hai cung cấp tính toán nhanh hơn, nhưng cần thiết cho phép tính băm bổ sung để có chênh lệch tốt trên các vùng/thùng.