Tại sao HashMap lại phục hồi mã băm do đối tượng khóa cung cấp?

Question

Tôi đọc mã của lớp HashMap được cung cấp bởi Java 1.6 API và không thể hiểu đầy đủ nhu cầu của các hoạt động sau đây (tìm thấy trong cơ thể của đặt và có được phương pháp):

int hash = hash(key.hashCode()); 

nơi phương pháp hash() có cơ thể sau đây:

private static int hash(int h) { 
     h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

này có hiệu quả tính toán lại băm bằng cách thực hiện các hoạt động bit trên hashcode cung cấp. Tôi không thể hiểu được sự cần thiết phải làm như vậy mặc dù API khẳng định nó như sau:

này là rất quan trọng bởi vì HashMap sử dụng năng lượng-of-hai bảng chiều dài băm, mà khác gặp phải va chạm cho hashcodes rằng không khác nhau ở các bit thấp hơn.

Tôi hiểu rằng phân tích giá trị khóa được lưu trữ trong một mảng cấu trúc dữ liệu và vị trí chỉ mục của một mục trong mảng này được xác định bởi hàm băm của nó. Điều tôi không hiểu là hàm này sẽ thêm bất kỳ giá trị nào vào phân phối băm.

Answer 1

Như Helper đã viết, nó chỉ có trong trường hợp hàm băm hiện có cho các đối tượng chính bị lỗi và không thực hiện công việc đủ tốt để trộn các bit thấp hơn. Theo the source trích dẫn bởi pgras,

/** 
    * Returns index for hash code h. 
    */ 
static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

Các băm đang được ANDed với một sức mạnh-of-hai chiều dài (do đó, length-1 là đảm bảo được một chuỗi các 1s). Do ANDING này, chỉ có các bit thấp hơn của h đang được sử dụng. Phần còn lại của h bị bỏ qua. Giả sử rằng, vì lý do gì đó, băm ban đầu chỉ trả về số chia hết cho 2. Nếu bạn sử dụng nó trực tiếp, các vị trí lẻ của hashmap sẽ không bao giờ được sử dụng, dẫn đến tăng x2 về số lần va chạm. Trong một trường hợp bệnh lý thực sự, hàm băm xấu có thể làm cho một hashmap hoạt động giống như một danh sách hơn là một thùng chứa O (1).

Kỹ sư mặt trời phải chạy thử nghiệm cho thấy rằng quá nhiều hàm băm không đủ ngẫu nhiên trong các bit thấp hơn và nhiều hashmaps không đủ lớn để sử dụng các bit cao hơn. Trong những trường hợp này, các thao tác bit trong số hash(int h) của HashMap có thể cung cấp một sự cải thiện ròng so với hầu hết các trường hợp sử dụng dự kiến ​​(do tỷ lệ va chạm thấp hơn), mặc dù cần tính toán thêm.

Answer 2

Tôi ở đâu đó đọc này được thực hiện để đảm bảo phân phối tốt ngay cả khi triển khai hashCode của bạn, tốt, err, hút.

Answer 3

như bạn đã biết với hashmap, triển khai cơ bản là một hashtable, cụ thể là bảng băm thùng đóng. Hệ số tải xác định số lượng đối tượng thích hợp trong bộ sưu tập/tổng số nhóm.

Cho phép nói rằng bạn tiếp tục thêm các yếu tố khác. Mỗi khi bạn làm như vậy, và nó không phải là một bản cập nhật, nó chạy phương thức hashcode của đối tượng và sử dụng số lượng các thùng với toán tử modulo để quyết định đối tượng nào cần đi vào.

là n (số lượng phần tử trong bộ sưu tập)/m (số lượng nhóm) lớn hơn, hiệu suất của bạn cho lần đọc và viết trở nên tệ hơn và tệ hơn.

Giả sử thuật toán mã băm của bạn là tuyệt vời, hiệu suất vẫn còn phụ thuộc vào so sánh này n/m.

phục hồi cũng được sử dụng để thay đổi số lượng nhóm và vẫn giữ nguyên hệ số tải tương tự như bộ sưu tập đã được tạo.

Hãy nhớ rằng, lợi ích chính của bất kỳ triển khai băm nào là hiệu suất O (1) lý tưởng cho việc đọc và ghi.

Answer 4

Như bạn đã biết, object.hashCode() có thể bị người dùng ghi đè, do đó, việc triển khai thực sự tồi tệ sẽ làm tăng các bit cấp thấp hơn không ngẫu nhiên. Điều đó sẽ có xu hướng đám đông một số xô và sẽ để lại nhiều xô không được lấp đầy.

Tôi vừa tạo bản đồ trực quan về những gì họ đang cố gắng thực hiện trong băm. Dường như phương thức băm (int h) chỉ là tạo ra một số ngẫu nhiên bằng cách thực hiện phép hồi lưu mức bit để các số kết quả ngẫu nhiên hơn (và do đó thành các nhóm thống nhất hơn) được phân phối.

Mỗi bit được ánh xạ tới một chút khác nhau như sau:

 h1 = h1^h13^h21^h9^h6  
     h2 = h2^h14^h22^h10^h7 
     h3 = h3^h15^h23^h11^h8 
     h4 = h4^h16^h24^h12^h9 
     h5 = h5^h17^h25^h13^h10 

. . . .

đến h12.

Như bạn có thể thấy, mỗi bit của h sẽ rất xa chính nó. Vì vậy, nó sẽ được khá nhiều ngẫu nhiên và sẽ không để đám đông bất kỳ xô cụ thể. Hy vọng điều này giúp đỡ. Gửi cho tôi một email nếu bạn cần đầy đủ hình ảnh.