哈希方法

Question

可能重複：
Explanation of HashMap#hash(int) method

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

誰能解釋詳細此方法，謝謝。

Answer 1

設計一個通用散列碼的問題之一是，你將所有這些努力都放在確保位的良好傳播上，然後有人出現並以這種方式使用它來完全撤銷那。

我們來看一個帶有X和Y（兩個整數）的座標類的經典示例。

這是一個典型的例子，因爲人們會用它來證明X^Y不是一個好的散列碼，因爲通常有幾個對象，其中X == Y（全部散列爲0）或者其X和Y是另一個的Y和X（將散列相同）和其他情況下，我們最終使用相同的散列碼。

歸結爲這樣一個事實，即整數有一個可能的範圍，覆蓋了四十億個值，在99％的使用中，它們往往最多少於幾百或幾萬。我們永遠無法擺脫試圖在四十億個可能的結果中傳播18quadrillion可能的價值，但我們可以努力使那些我們可能真正看到的，不太可能發生衝突。

現在，(X << 16 | X >> 16)^Y在這種情況下做得更好，將X中的位擴展得更多。

不幸的是，如果使用該散列的是做% someBinaryRoundNumer索引到一個表（或甚至% someOtherNumber，到稍微較小的程度上），那麼對下面someBinaryRoundNumber X的值 - 其中我們可以期望是最常見的 - 這個散列有效地變爲return Y。

我們所有的辛苦工作都浪費了！

重複使用的是用這樣的邏輯做一個散列，稍微好一點。

值得注意的是，對(X << 16 | X >> 16)^Y方法太過挑剔是不公平的，因爲散列的另一種用法可能具有優於給定備選方案的形式。

Answer 2

那麼不進入到精細的細節，但：

• 由於hascode（）和equals（）的合同，一個執行不力的哈希碼功能可能會導致具有相同的哈希碼不同實例。這意味着你可能有一個類用一個糟糕的hashcode（）方法實現，這樣類的equals（）方法將爲A和B實例返回false（這意味着它們與業務邏輯的角度不同）但hashcode（）方法爲實例A和B返回相同的值。同樣，根據hashcode（）和equals（）合約，這在技術上是有效的，但不是很合適的

• in a Htabletable-like structure如HashMap）「桶」用於根據其哈希碼將映射放置在映射內部。如果兩個實例具有相同的哈希碼（）（但根據equas（）方法不同），它們將被放置在同一個存儲桶中。從性能角度來看，這是不好的，因爲當你有很多這樣的情況時，你會失去一些類似Hashtable結構固有的檢索速度。被稱爲碰撞。發生什麼事情是，如果稍後有人使用「搜索」實例從hashmap中檢索某些內容，並且相應的哈希桶具有多個佔有者，則必須使用equals（）方法檢查該存儲桶中的每個元素，以找出哪個是需要檢索的那個。在極端情況下，HashMap可以像這樣轉換成鏈表。

• hash（int n）方法爲現有的hashcode（）值添加了一些額外的東西，以便防禦這種情況。