通過接合兩種哈希策略可以創造出一種更高效的算法，且不會有額外的內存與CPU開銷。

簡介

對于像 HashMap 或 HashSet 這些經過哈希排序的集合，key 的哈希策略對于它們的性能有直接影響。

內置的哈希算法是專門設計用于常規的哈希計算，并且在很多場景下都很適用。但在某些場景下（特別是當我們有一些更好的想法時）我們是否有更好的策略？

一種 hash 策略的測試

在前篇文章中我翻了不少測試 hash 策略的方法，并著重看了為“Orthogonal Bits”特別設計的測試同方法，即：只改變原始輸入的一個 bit，其 hash 結果是否也會改變。

另外，如果需要進行 hash 運算的元素/鍵是已知的，你應該為這種特殊情況進行優化而不是試圖使用常規的解決方案。

減少碰撞

在一個需要進行 hash 運算的容器中，最重要的是避免碰撞。碰撞就是兩個或多個 key 映射到了同一個位置。這也意味著你需要做一些額外工作來檢查某個 key 是否是你需要的那個，因為現在有多個 key 放到了同一個位置上。在理想情況下，每個位置最多只能有一個 key。

我需要的哈希碼是惟一的

避免碰撞的一個常見誤區是只保證哈希碼惟一就可以了。雖然惟一的哈希碼確實很需要，但只有它也不夠。

告訴你有一個鍵值的集合，并且它們都有唯一的 32 位哈希碼。假設你有一個 40 億量的數組桶（bucket），每一個鍵值都有它自己的桶，不能沖突。對這么大的數組構成的哈希集合通常是很讓人煩的。實際上，HashMap 和 HashSet 容納的量也是有限的，是 2^30，大致剛剛超過 10 億。

當你有一個實際大小的散列集合的時候會發生什么？大量的桶需要更小，哈希代碼需要按模計算桶的數量。如果桶的數量是 2 的冪，你可以使用最低位掩碼。

請看這個例子：ftse350.csv。 如果我們把此表的第一列作為 key 或元素，那就是 352 個字符串。這些字符串都有自己獨一無二的 String.hashCode() 返回值。然而，如果僅僅采用此返回值的一部分，會產生沖突嗎？

我們采用裝載因子為 0.7 (默認值)的 HashMap，它的范圍為 512。可以看到，在采用低 9 位的掩碼之后，會產生約 30% 的沖突，即便原始數據都是獨一無二的。

這里是 HashTesterMain 的代碼。

為了減少壞的哈希策略所帶來的影響，HashMap 采用擾動函數。Java 8 的實現比較簡單。我們從 HashMap.hash 的源碼中摘錄一段，閱讀 Java 文檔可以了解到更多的細節:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

此方法將原始哈希值的高位和低位混合，以降低低位部分的隨機性。上例中的高沖突情境可通過這一手段得到緩解。參照其第三列。

初探 String 類的哈希函數

下面是 String.hashCode() 的代碼:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

注意：由于 String 類的實現由 Javadoc 規定，我們并沒有多大機會去改動它。但我們的確可以定義一個新哈希策略。

哈希策略的組成部分

我會留意哈希策略里的兩部分，

• Magic numbers (魔法數字)。你可以嘗試不同的數字以取得最佳效果。

• 代碼的結構。你想要的代碼結構應該能提供一個好的結果，無論魔法數字的選取是多么地喪心病狂。

魔法數字固然重要，但你不會想讓它變得過于重要；因為總有些時候，你所選的數字并不合適。這就是為什么你同時需要一個即使在魔法數選取很糟糕的情況下最壞情況產出仍然低的代碼結構。

讓我們用別的乘數來代替 31。

可以發現，魔法數的選取的確有所影響，但值得一試的數字未免太多了。我們需要寫一個程序，隨機選取足夠的情況用以測試。HashSearchMain的源碼。

代碼的關鍵部分：

public static int hash(String s, int multiplier) {
    int h = 0;
    for (int i = 0; i < s.length(); i++) {
        h = multiplier * h + s.charAt(i);
    }
    return h;
}
private static int xorShift16(int hash) {
    return hash ^ (hash >> 16);
}
private static int addShift16(int hash) {
    return hash + (hash >> 16);
}
private static int xorShift16n9(int hash) {
    hash ^= (hash >>> 16);
    hash ^= (hash >>> 9);
    return hash;
}

可以發現，如果提供了好的乘數，或者剛好對你的鍵集合奏效的乘數，那重復相乘每個哈希值與下一字符之和就是有意義的。對比一下，對被測試的鍵集合采用130795作乘數僅僅發生了81次沖突，而采用31做乘數則發生了103次。

如果你同時還用的擾動函數，沖突將會減少至約68次。這樣的沖突率已經快要接近將桶數組所產生的效果了：我們并沒有占用更多內存，卻降低了沖突率。

但是，當我們向哈希集中添加新的鍵時會發生什么？我們的魔法數字還能持續奏效嗎？正是在這個前提下，我們研究最壞沖突率，以決定在面對更大范圍的輸入可能時，哪種代碼結構可能會表現得更好。hash() 的最壞表現是 250 處沖突：70% 的鍵沖突了，表現的確有點糟。擾動函數使得情況有所改進，但仍不夠好。注意：如果我們選擇與被移值相加而非去異或，所得的結果將會更糟。

然而，如果選擇位移兩次 —— 不僅僅是混合高低位兩部分，而是從四個部分hash函數所得哈希值的四個不同部分進行混合 —— 我們會發現，最壞情況的沖突率大幅下降。由此我想到，在所選鍵集會發生改變的情況下，如果我們的結構夠好，魔法數的影響夠低；我們得到壞結果的可能性就會降低。

如果在哈希函數中我們選擇了相加而非異或，會發生什么？

在擾動函數中采用異或而非相加可能會得到更好的結果。那如果我們將

h = multiplier * h + s.charAt(i);

替換成

h = multiplier * h ^ s.charAt(I);

會怎樣？

最佳情況下的表現稍微變好了些，然而最差情況下的沖突率明顯地變差了。由此我看出，魔法數選取的重要性上升了，也就是說，鍵的選取將會產生更大的影響。考慮到隨著時間的推移鍵的選取可能會發生變化，這種選擇顯得有些危險。

為何選擇奇數作為乘數

當與一個奇數相乘時，結果的地位既可能是0，又可能是1；因為0 * 1 = 0, 1 * 1 = 1. 然而，如果與偶數相乘，最低位將必定是0. 也就是說，這一位不再隨機變化了。讓我們看看，重復先前的測試，但僅僅采用偶數，結果會是什么樣。

如果你夠幸運，魔法數選對了，所得的結果將會和奇數情況下一樣好。然而如果倒霉，結果可能就很糟了。325處沖突即是說，512個桶里被使用的僅僅只有27個。

更為先進的哈西策略有何差異

對于我們使用的基于 City, Murmur, XXHash，以及 Vanilla Hash(我們自己實現的)：

• 該策略一次讀取64為數據，比一字節一字節地讀取更快

• 所得的有效值是兩個64位長的值

• 有效值被縮短至64位

• 從結果上來看，采用了更多的常量乘數

• 擾動函數更為復雜

我們在實現中使用長哈希值，因為：

• 我們為64位處理器做優化

• Java中最長的數據類型是64位的

• 如果你的哈希集很大(上百萬)，32位哈希值難以保持唯一

總結

通過探索哈希值的產生過程，我們得以將352個鍵的沖突數量從103處降至68處。同時，我們還有一定信心認為，如果鍵集發生變化，我們也已經降低了變化所可能造成的影響。

這是在沒有使用更多內存，甚至更多運算時間的情況下做到的。

我們仍可以選擇去利用更多的內存。

作為對比，可以看到，將桶數組大小翻倍可以提高最佳情況的下的表現，但你還是要面對老問題：魔法數與鍵集的不契合將會帶來高沖突。

結論

在擁有穩定鍵集的情況下，調整哈希策略可以顯著降低沖突概率。

你同時得測試，在沒有再優化的情況下，如果鍵集改變，情況將會變壞到何種程度。

結合這兩者，你就能夠發展出不需更多內存便能提升表現的哈希策略。

本文地址：http://www.oschina.net/translate/optimizing-a-hashing-strategy

原文地址：https://dzone.com/articles/optimizing-a-hashing-strategy