優化哈希策略

知識 11-07

（點擊

上方公眾號

，可快速關注）

來源：ImportNew - fzr

概述

散列策略會對HashMap或HashSet之類的散列集合的性能產生直接的影響。

內置的散列（又稱哈希）函數都是通用的，在大多數使用情況下都能表現很好。但是我們能不能做的更好呢，特別是當你對某個用例產生了很好的想法時？

測試一個散列策略

在

先前的一篇文章

中，我研究了一些測試散列策略的方法，其中特別注意了一種「正交位」優化的散列策略，它僅僅只是改變一個位就能確保每個散列結果儘可能的不同。

http://vanillajava.blogspot.co.uk/2015/08/comparing-hashing-strategies.html?view=magazine

然而，如果要對一個已知的元素或關鍵字集合進行散列，你就可以針對具體案例進行優化，而不是尋求一個通用方案。

減少衝突

一個散列集合中最主要的事情就是避免衝突了。所謂衝突，就是兩個以上關鍵字映射到同一個散列槽中。這些衝突意味著當有多個關鍵字映射到同一個散列槽中時你必須要付出更多的努力來檢查那些關鍵字是否是你想要的那個。理想狀態下一個散列槽中最多有一個關鍵字。

我只需要唯一的散列碼，是嗎？

通常的誤解是只要散列碼唯一就可以避免衝突。雖然都希望散列碼是唯一的，但它還不夠。

假設現在有一些關鍵字，每一個都有唯一的32位散列碼。如果你有40億散列槽，每個關鍵字都有自己的槽，那就沒有衝突了。對於所有的散列集合，這樣大的數組一般是不太現實的。事實上，HashMap和HashSet的大小都收到機器內存的限制，一般為2^30，大概剛剛超過10億。

當你只能有一個規模上比較實際的哈希集合時又該如何呢？散列槽的數目需要更小一些，而散列碼需對散列槽數目取模。如果散列槽數是2的冪值，你可以用最低位當掩碼。

來看個例子，ftse350.csv。如果把第一列作為關鍵字或是元素，就有352個字元串。這些字元串有唯一的String().hashCode()碼，但是假設我們只取這些散列碼的低位。會不會有衝突呢？

一個裝載因子是0.7（默認）的HashMap的大小是512，使用哈希碼的低九位作為掩碼。可以看到，儘管原始的哈希碼是唯一的，仍然有大約30%的關鍵字會衝突。

HashTesterMain的代碼在

這裡

。

https://github.com/OpenHFT/Chronicle-Algorithms/blob/master/src/test/java/net/openhft/chronicle/algo/hashing/HashTesterMain.java

為了減少糟糕的散列策略造成的影響，HashMap使用了擾動函數。Java 8里的實現相當簡單。

下面是來自HashMap.hash的源碼。想了解更多細節，可以閱讀Javadoc文檔。

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中規定好了，所以我們基本沒有機會改動，但我們可以定義一個新的哈希策略。

散列策略的組成部分

我會留意散列策略中的兩個部分。

魔法數字。你可以嘗試不同的數字以取得最佳效果。

代碼結構。你需要一個無論選取什麼樣的魔法數字都能提供一個好的結果的代碼結構。

魔法數字固然很重要，但是你並不想讓它過於重要；因為總是有些時候你選的數字並不適合你的使用場景。這就是為什麼你同時還需要一個即使在魔法數字選取很糟糕的情況下其最壞情況依然不是特別差的代碼結構。

用別的乘數代替31

可以看到，魔法數的選取的確很重要，但需要嘗試的數字太多了。我們需要寫一個測試程序，測試出一個不錯的隨機選擇。HashSearchMain的

源碼

。

https://github.com/OpenHFT/Chronicle-Algorithms/blob/master/src/test/java/net/openhft/chronicle/algo/hashing/HashSearcherMain.java

代碼的關鍵部分：

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和31作乘數，對於測試的關鍵字集合，前者只有81次碰撞而後者有103次。

如果你再加上擾動函數，碰撞會減少到大約68次。這已經很接近加倍數組規模時的衝突率了：不佔用更多內存，卻可以降低衝突率。

但是當我們向散列集合中添加新的關鍵字時會發生什麼呢？魔法數字還能表現良好嗎？這使我不得不研究最壞衝突率，以決定在面對更大範圍的輸入時，哪種代碼結構可能會表現得更好。hash()的最壞表現是250次碰撞，即70%的關鍵字發生衝突，確實很糟糕。擾動函數能稍稍提高性能，但作用也不大。注意：如果我們選擇與偏移值相加而不是異或會得到更糟糕的結果。

然而，如果選擇位移兩次——不僅僅是混合高低位，還有從產生的哈希值的四個部分選擇的位，結果發現，最壞情況的衝突率大大下降。這使我想到，在選擇的關鍵字改變的情況下，如果結構足夠好，魔法數的影響足夠低，我們得到糟糕結果的可能性就會降低。

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

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

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

變為

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

會發生什麼呢？