HashMap 計算 Hash 值的擾動函數

作者：老鄭 2023-02-13 08:01:49

理論上 hash 散列是一個 int 值，如果直接拿出來作為下標訪問 hashmap 的話，考慮到二進制 32 位，取值范圍在-2147483648 ~ 2147483647。大概有 40 億個 key ，只要哈希函數映射比較均勻松散，一般很難出現碰撞。

計算過程

以下代碼叫做 “擾動函數”

//java 8 中的散列值優化函數
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

一個客觀的問題：要存下 40 億長度的數組，服務器內存是不能放下的。通常咱們 HashMap 的默認長度為 16 。所以這個 hashCode , (key.hashCode ) 是不能直接來使用的。使用之前先做對數組長度的與運算，得到的值才能用來訪問數組下標。

代碼如下：

// n = hashmap 的長度
p = tab[i = (n - 1) & hash])

這里為什么要使用 n -1 ，來進行與運算，這里詳單與是一個”低位掩碼”, 以默認長度 16 為例子。和某個數進行與運算，結果的大小是 < 16 的。如下所示：

10000000 00100000 00001001
&   00000000 00000000 00001111
------------------------------
    00000000 00000000 00001001  // 高位全部歸 0, 只保留后四位

這個時候會有一個問題，如果本身的散列值分布松散，只要是取后面幾位的話，碰撞也會非常嚴重。還有如果散列本身做得不好的話，分布上成等差數列的漏洞，可能出現最后幾位出現規律性的重復。

這個時候“擾動函數”的價值就體現出來了。如下所示：

在 hash 函數中有這樣的一段代碼：(h = key.hashCode()) ^ (h >>> 16) 右位移 16 位，正好是32bit 的一半，與自己的高半區做成異或，就是為了混合原始的哈希碼的高位和低位，以此來加大低位的隨機性。并且混合后的低位摻雜了高位的部分特征，這樣高位的信息變相保存下來。其實按照開發經驗來說絕大多數情況使用的時候 HashMap 的長度不會超過 1000，所以提升低位的隨機性可以提升可以減少 hash 沖突，提升程序性能。

如果感興趣的小伙伴可以瀏覽下一下 Peter Lawlay 的專欄《An introduction to optimising a hashing strategy》的一個實驗：他隨機選取了 352 個字符串，在散列值完全沒有沖突的前提下，對低位做掩碼，取數組下標。

結果顯示，當 hashmap 的數組長度為 512 的時候，也就是采用低位掩碼取低 9 位的時候，在沒有擾動函數的情況下，發生了 103 次碰撞，接近 30%。而在使用擾動函數之后只有 92 次碰撞。碰撞減少了將近10%。說明擾動函數確實有功效的。

但是明顯 Java 8 覺得擾動做一次就夠用了，做 4 次的話，可能邊際效用也不大，為了效率考慮就改成了一次。

代碼演示?

import java.lang.reflect.Field;
import java.util.HashMap;

/**
 * HashMap 計算 hashKey
 * <p>
 * 演示：擾動函數
 *
 * @see HashMap#hash(Object)
 */
public class HashKeyTest {

    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
        HashMap<String, String> map = new HashMap<>();
        String k = "王羲之";
        String v = "大書法家";
        map.put(k, v);

        Field field = map.getClass().getDeclaredField("table");
        field.setAccessible(Boolean.TRUE);
        Object[] nodes = (Object[]) field.get(map);

        int h = k.hashCode();
        System.out.println("  h=" + h);
        System.out.println();
        // 調用 hashCode 結果
        System.out.println("  h=hashCode()    " + num0x(h) + "  調用 hashCode");
        // 無符號右移 16
        System.out.println("  h>>>16          " + num0x(h >>> 16));
        System.out.println("--------------------------------------------------");
        // 計算 hash
        System.out.println("  hash=h^(h>>>16) " + num0x(h ^ (h >>> 16)) + "  計算 hash");
        System.out.println("--------------------------------------------------");
        // 計算下標
        System.out.println("  (n-1)&hash      " + num0x(15 & (h ^ (h >>> 16))) + "  計算下標");
        System.out.println();
        int idx = (15 & (h ^ (h >>> 16)));
        // 輸出下標
        System.out.println("  下標: " + idx);
        // 在下標中去獲取數據
        System.out.println("  查詢結果:" + nodes[idx]);
    }

    /**
     * 輸入 int 轉換為 二進制字符串
     *
     * @param num 數字
     * @return 二進制字符串
     */
    static String num0x(int num) {
        String num0x = "";
        for (int i = 31; i >= 0; i--) {
            num0x += (num & 1 << i) == 0 ? "0" : "1";
        }
        return num0x;
    }
}

運行結果如下：

參考資料：https://www.zhihu.com/question/20733617

責任編輯：武曉燕來源：運維開發故事