典型的雜湊函數首先將搜尋鍵轉換為稱為雜湊碼的整數值，然後將雜湊碼壓縮為雜湊表的索引。 Java 的根類別 Object 具有 hashCode 方法，該方法傳回整數雜湊碼。預設情況下，此方法傳回物件的記憶體位址。 hashCode方法的通用契約如下：
對於byte、short、int 和char 類型的搜尋鍵，只需將它們轉換為int 。因此，任何一種類型的兩個不同搜尋鍵將具有不同的雜湊碼。
對於 float 類型的搜尋鍵，使用 Float.floatToIntBits(key) 作為雜湊碼。注意，floatToIntBits(float f) 傳回一個 int 值，其位元表示與浮點數 f 的位元表示相同。因此， float 類型的兩個不同搜尋鍵將具有不同的雜湊碼。
對於long 類型的搜尋鍵，簡單地將其轉換為int 並不是一個好的選擇，因為所有僅前32 位不同的鍵都將具有相同的哈希碼。為了考慮前32位，將64位分成兩半，並執行異或運算將兩半組合起來。這個過程稱為折疊。 長鍵的雜湊碼是
int hashCode = (int)(key ^ (key >> 32));
請注意，>> 是右移運算符，它將位元向右移動 32 個位置。例如，1010110>> 2 產生 0010101。 ^ 是位元異或運算子。它對二進制操作數的兩個對應位元進行操作。例如，1010110 ^ 0110111 產生 1100001.
對於 double 類型的搜尋鍵，首先使用 Double.doubleToLongBits 方法將其轉換為 long 值，然後執行折疊為如下：
長位 = Double.doubleToLongBits(key);
int hashCode = (int)(位元 ^ (位元>>32));
搜尋鍵通常是字串，因此為字串設計一個好的雜湊函數很重要。一種直觀的方法是將所有字元的 Unicode 相加作為字串的雜湊碼。如果應用程式中的兩個搜尋鍵不包含相同的字母，則此方法可能有效，但如果搜尋鍵包含相同的字母，例如tod 和dot，則會產生大量衝突.
更好的方法是產生考慮字元位置的雜湊碼。具體來說，令雜湊碼為
s0*b(n - 1) + s1*b(n - 2) + c + sn-1
其中 si 是 s.charAt(i)。此表達式是某個正 b 的多項式，因此稱為多項式雜湊碼。使用霍納規則進行多項式計算（請參閱案例研究：將十六進位轉換為十進位），可以如下有效計算雜湊碼：
(...((s0*b + s1)b + s2)b + ... + sn-2)b + sn-1
此計算可能會導致長字串溢出，但算術溢出在 Java 中被忽略。您應該選擇適當的值 b 以盡量減少碰撞。實驗表明，b 的最佳選擇是 31、33、37、39 和 41。在 String 類別中，使用多項式雜湊程式碼覆寫 hashCode，其中 b 為 31.
鍵的雜湊碼可能是超出雜湊表索引範圍的大整數，因此您需要縮小它以適應索引的範圍。假設雜湊表的索引介於 0 和 N-1 之間。將整數縮放到 0 和 N-1 之間最常見的方法是使用
h(hashCode) = hashCode % N
為了確保索引分佈均勻，請選擇 N 為大於 2 的質數。
理想情況下，您應該為 N 選擇一個質數。然而，找到一個大的質數是很耗時的。在 java.util.HashMap 的 Java API 實作中，N 設定為 2 次方的值。這種選擇是有充分理由的。當N是2的冪的值時，
h(hashCode) = hashCode % N
與
相同h(hashCode) = hashCode & (N – 1)
與號 & 是位元 AND 運算子。如果兩個對應位元都是 1，則兩個對應位的 AND 會產生 1。例如，假設 N = 4 和 hashCode = 11，11 % 4 = 3，這與 01011 & 00011 = 11。 & 運算子的執行速度比 % 運算子快得多。
為了確保雜湊分佈均勻，在java.util.HashMap 的實作中，也使用了補充雜湊函數和主雜湊函數。此函數定義為：
private static int SupplementalHash(int h) {
h ^= (h >> 20) ^ (h >> 12);
回 h ^ (h >> 7) ^ (h >> 4);
}
^ 和 >>> 是位元異或和無符號右移運算。位元運算比乘法、除法和求餘運算快得多。您應該盡可能用位元運算來取代這些運算。
完整的雜湊函數定義為：h(hashCode) =supplementalHash(hashCode) % N
這與
相同
h(hashCode) =supplementalHash(hashCode) & (N – 1)因為
N 是 2 冪的值。
以上是雜湊函數和雜湊碼的詳細內容。更多資訊請關注PHP中文網其他相關文章！
