雜湊函數和雜湊碼

典型的雜湊函數首先將搜尋鍵轉換為稱為雜湊碼的整數值，然後將雜湊碼壓縮為雜湊表的索引。 Java 的根類別 Object 具有 hashCode 方法，該方法傳回整數雜湊碼。預設情況下，此方法傳回物件的記憶體位址。 hashCode方法的通用契約如下：

1. 每當重寫 equals 方法時，都應該重寫 hashCode 方法，以確保兩個相等的物件傳回相同的雜湊碼。
2. 在程式執行過程中，多次呼叫hashCode方法會傳回相同的整數，前提是物件的資料沒有改變。
3. 兩個不相等的物件可能具有相同的雜湊碼，但您應該實作 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中文網其他相關文章！