Giải thích phương thức HashMap # hash (int)

Question

Có thể ai đó vui lòng giải thích cho tôi phương pháp HashMap # hash (int) tĩnh không?

Lý do đằng sau nó để tạo ra băm phân phối đồng đều là gì?

/** 
* Applies a supplemental hash function to a given hashCode, 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. 
*/ 
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); 
} 

Ví dụ sẽ giúp tiêu hóa dễ dàng hơn.

Làm rõ Tôi biết về toán tử, bảng chân lý và hoạt động bitwise. Tôi thực sự không thể giải mã việc thực hiện cũng như bình luận thực sự. Hoặc thậm chí là lý do đằng sau nó.

Answer 1

>>> là sự dịch chuyển hợp lý (không có dấu mở rộng) (JLS 15.19 Shift Operators) và ^ là độc quyền bitwise hoặc (JLS 15.22.1 Integer Bitwise Operators). Vì lý do tại sao điều này được thực hiện, tài liệu cung cấp gợi ý: HashMap sử dụng bảng chiều dài hai chiều và băm bằng cách che đi các bit cao hơn và chỉ lấy các bit thấp hơn của mã băm của chúng.

// HashMap.java -- edited for conciseness 
static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

public V put(K key, V value) { 
    int hash = hash(key.hashCode()); 
    int index = indexFor(hash, table.length); 
    // ... 
} 

Vì vậy hash() nỗ lực để mang lại sự liên quan đến các bit cao hơn, mà nếu không sẽ được đeo mặt nạ đi (indexFor về cơ bản loại bỏ các bit cao của h và chỉ mất dưới k bit nơi length == (1 << k)).

Tương phản điều này với cách Hashtable (không được có bảng chiều dài hai chiều) sử dụng mã băm của khóa.

// Hashtable.java -- edited for conciseness 
public synchronized V get(Object key) { 
    int hash = key.hashCode(); 
    int index = (hash & 0x7FFFFFFF) % table.length; 
    // ... 
} 

Bằng cách làm các hoạt động % đắt hơn (thay vì mặt nạ chút đơn giản), hiệu suất của Hashtable là ít nhạy cảm với băm mã với phân phối nghèo ở các bit thấp hơn (đặc biệt là nếu table.length là một số nguyên tố).

Answer 2

Tôi không biết làm thế nào tất cả các công trình thay đổi, nhưng động cơ được đặt ra trong các ý kiến:

Cách HashMap được thực hiện dựa trên các chức năng hashCode là đủ cũng thực hiện. Đặc biệt, các bit thấp hơn của giá trị băm phải được phân bố đồng đều. Nếu bạn có nhiều va chạm trên các bit thấp hơn, HashMap sẽ không hoạt động tốt.

Bởi vì việc thực hiện hashCode nằm ngoài sự kiểm soát của HashMap (mỗi đối tượng có thể thực hiện riêng của họ), họ cung cấp một hàm băm bổ sung mà chuyển hashCode của đối tượng xung quanh một chút để đảm bảo rằng các bit thấp được phân phối ngẫu nhiên hơn. Một lần nữa, tôi không có ý tưởng làm thế nào điều này hoạt động chính xác (hoặc có hiệu quả như thế nào), nhưng tôi giả sử nó phụ thuộc vào ít nhất các bit cao hơn được phân phối như nhau (có vẻ như lưới bit cao hơn vào các bit thấp hơn).

Vì vậy, điều này là để cố gắng giảm thiểu va chạm (và do đó cải thiện hiệu suất) khi có phương pháp băm mã được triển khai kém.