哈希策略

總覽

用于哈希鍵的策略可以直接影響哈希集合（例如HashMap或HashSet）的性能。

內(nèi)置的哈希函數(shù)被設(shè)計為通用的，并且可以在各種用例中很好地工作。 我們可以做得更好，特別是如果您對用例有一個很好的了解嗎？

測試哈希策略

在上一篇文章中，我介紹了多種測試哈希策略的方法，特別是針對“正交位”進(jìn)行了優(yōu)化的哈希策略，旨在確保每個哈希結(jié)果僅基于一個比特就盡可能地不同變化。

但是，如果您有一組已知的要散列的元素/鍵，則可以針對該特定用例進(jìn)行優(yōu)化，而不是嘗試查找通用解決方案。

減少碰撞

您想要避免在哈希集合中發(fā)生的主要事情之一是沖突。 這是兩個或更多鍵映射到同一存儲桶時。 這些沖突意味著您必須做更多的工作來檢查密鑰是否與您期望的一致，因為同一存儲桶中現(xiàn)在有多個密鑰。 理想情況下，每個存儲桶中最多有一個密鑰。

我只需要唯一的哈希碼，不是嗎？

一個常見的誤解是，為了避免沖突，您需要擁有唯一的哈希碼。 盡管非常需要唯一的哈希碼，但這還不夠。

假設(shè)您有一組密鑰，并且所有密鑰都有唯一的32位哈希碼。 如果您有一個包含40億個存儲桶的數(shù)組，則每個鍵都有其自己的存儲桶，并且不會發(fā)生沖突。 對于所有散列集合，通常不希望具有如此大的數(shù)組。 實際上，對于2 ^ 30或剛剛超過10億的數(shù)組，HashMap和HashSet受2大小的最大冪限制。

當(dāng)您擁有更實際大小的哈希集合時，會發(fā)生什么？ 存儲桶的數(shù)量需要更小，并且哈希碼被模塊化為存儲桶的數(shù)量。 如果存儲桶數(shù)是2的冪，則可以使用最低位的掩碼。

讓我們來看一個示例ftse350.csv。如果將第一列作為鍵或元素，則將獲得352個字符串。 這些字符串具有唯一的String.hashCode（），但是說我們采用了這些哈希碼的低位。 我們看到碰撞了嗎？

面具	屏蔽了String.hashCode（）	HashMap.hash（ 屏蔽了String.hashCode（））
32位	沒有碰撞	沒有碰撞
16位	1次碰撞	3次碰撞
15位	2次碰撞	4次碰撞
14位	6次碰撞	6次碰撞
13位	11次碰撞	9次碰撞
12位	17次碰撞	15次碰撞
11位	29次碰撞	25次碰撞
10位	57次碰撞	50次碰撞
9位	103次碰撞	92次碰撞

HashMap的加載因子為0.7（默認(rèn)值）的大小為512，它使用低9位的掩碼。 如您所見，即使我們從唯一的哈希碼開始，仍有大約30％的鍵發(fā)生沖突。

• HashTesterMain的代碼在這里。

為了減少不良的哈希策略的影響，HashMap使用了一種攪拌函數(shù)。 在Java 8中，這非常簡單。

從HashMap.hash的源代碼中，您可以閱讀Javadoc以獲得更多詳細(xì)信息

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

這將哈希碼的高位與低位混合，以改善低位的隨機(jī)性。 對于上述高碰撞率的情況，存在改進(jìn)。 請參閱第三列。

看一下String的哈希函數(shù)

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的實現(xiàn)是在Javadoc中定義的，因此幾乎沒有機(jī)會更改它，但是可以定義新的哈希策略。

哈希策略的組成部分。

在散列策略中，我要看兩部分。

• 魔術(shù)數(shù)字。 您可以嘗試不同的數(shù)字以找到最佳結(jié)果。
• 代碼的結(jié)構(gòu)。 您需要一種結(jié)構(gòu)，對于任何理智的幻數(shù)選擇都能獲得良好的結(jié)果。

盡管幻數(shù)很重要，但您不希望它們太重要的原因是，對于給定的用例，您總是有可能選擇不正確的幻數(shù)。 這就是為什么您還想要一種即使在選擇的魔術(shù)數(shù)不多的情況下也能獲得最差的情況下的結(jié)果的代碼結(jié)構(gòu)。

讓我們嘗試一些不同的乘數(shù)，而不是31。

乘數(shù)	碰撞
1個	230
2	167
3	113
4	99
5	105
6	102
7	93
8	90
9	100
10	91
11	91

您會看到魔術(shù)數(shù)字的選擇很重要，但是也有很多數(shù)字可供嘗試。 我們需要編寫一個測試來嘗試一個好的隨機(jī)選擇。 HashSearchMain的來源

哈希函數(shù)	最佳乘數(shù)	最低的碰撞	最差的乘數(shù)	最高碰撞
hash（）	130795	81次碰撞	126975	250次碰撞
xorShift16（哈希（））	2104137237	68次碰撞	-1207975937	237次碰撞
addShift16（hash（））	805603055	68次碰撞	-1040130049	243次碰撞
xorShift16n9（hash（））	841248317	69次碰撞	467648511	177次碰撞

要查看的關(guān)鍵代碼是

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; }

如您所見，如果您提供了一個良好的乘數(shù)，或者一個乘數(shù)恰好與您的鍵集配合使用，則每個哈希加下一個字符的重復(fù)乘數(shù)是合理的。 如果將130795作為乘數(shù)而不是31作為乘數(shù)，則對于測試的密鑰集，您只會得到81次碰撞，而不是103次碰撞。

如果同時使用攪拌功能，則可能發(fā)生68次碰撞。 這接近兩倍于數(shù)組大小的相同沖突率。 也就是說，無需使用更多內(nèi)存即可提高碰撞率。

但是，當(dāng)我們向哈希集合添加新密鑰時會發(fā)生什么，我們的幻數(shù)仍然對我們有利嗎？ 在這里，我著眼于最差的碰撞率，以確定在更大范圍的可能輸入下哪種結(jié)構(gòu)可能產(chǎn)生良好的結(jié)果。 hash（）的最壞情況是250次沖突，即70％的鍵碰撞，這是非常糟糕的。 攪動功能對此有所改善，但是仍然不是很好。 注意：如果我們添加移位后的值而不是對其進(jìn)行異或，則在這種情況下將得到更差的結(jié)果。

但是，如果我們進(jìn)行兩次移位，不僅要混合最高位和最低位，還要混合生成的哈希碼的四個不同部分的位，則我們發(fā)現(xiàn)最壞情況下的沖突率要低得多。 這向我表明，如果更改鍵的選擇，則由于結(jié)構(gòu)更好且魔術(shù)數(shù)字的選擇或輸入的選擇的重要性降低，我們不太可能收到不好的結(jié)果。

如果我們在哈希函數(shù)中添加而不是xor怎么辦？

在攪拌功能中，使用xor可能比使用add更好。 如果我們改變這個會發(fā)生什么

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

與

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

哈希函數(shù)	最佳乘數(shù)	最低的碰撞	最差分?jǐn)?shù)	最高碰撞
hash（）	1724087	78次碰撞	247297	285次碰撞
xorShift16（哈希（））	701377257	68次碰撞	-369082367	271次碰撞
addShift16（hash（））	-1537823509	67次碰撞	-1409310719	290次碰撞
xorShift16n9（hash（））	1638982843	68次碰撞	1210040321	206次碰撞

最佳情況下的數(shù)字稍好一些，但是最壞情況下的碰撞率則更高。 這向我表明，幻數(shù)的選擇更重要，但這也意味著鍵的選擇更重要。 這似乎是一個冒險的選擇，因為您必須考慮密鑰可能會隨著時間而變化。

為什么我們選擇奇數(shù)乘數(shù)？

當(dāng)您乘以奇數(shù)時，結(jié)果的低位機(jī)會等于0或1。這是因為0 * 1 = 0和1 * 1 =1。但是，如果將您乘以偶數(shù)，則低位總是為0。即不再是隨機(jī)的。 假設(shè)我們重復(fù)了先前的測試，但只使用了偶數(shù)，這看起來如何？

哈希函數(shù)	最佳乘數(shù)	最低的碰撞	最差分?jǐn)?shù)	最高碰撞
hash（）	82598	81次碰撞	290816	325次碰撞
xorShift16（哈希（））	1294373564	68次碰撞	1912651776	301次碰撞
addShift16（hash（））	448521724	69次碰撞	872472576	306次碰撞
xorShift16n9（hash（））	1159351160	66次碰撞	721551872	212次碰撞

如果您很幸運(yùn)，并且為您的魔術(shù)數(shù)字輸入了正確的結(jié)果，則結(jié)果與奇數(shù)一樣好，但是，如果您很不幸，結(jié)果可能會很糟糕。 325次碰撞意味著僅使用了512個鏟斗中的27個。

更多高級哈希策略有何不同？

對于基于City，Murmur，XXHash和Vanilla Hash（我們自己的）的哈希策略

• 散列策略一次讀取64位數(shù)據(jù)的速度比逐字節(jié)讀取數(shù)據(jù)的速度快。
• 計算的工作值是兩個64位值。
• 工作值減少到64位長。
• 結(jié)果，使用了更多的乘法常數(shù)。
• 攪拌功能更為復(fù)雜。

我們在實現(xiàn)中使用長哈希碼為：

• 我們針對64位處理器進(jìn)行了優(yōu)化，
• Java中最長的原始數(shù)據(jù)類型是64位，并且
• 如果您有大量的哈希集合（即數(shù)百萬個），則32位哈希不太可能是唯一的。

綜上所述

通過探索如何生成哈希碼，我們找到了將352個鍵的沖突次數(shù)從103個沖突減少到68個沖突的方法，但是比更改鍵集有一定的信心，我們已經(jīng)減少了這種影響。

這無需使用更多的內(nèi)存，甚至不需要更多的處理能力。
我們?nèi)匀豢梢赃x擇使用更多的內(nèi)存。

為了進(jìn)行比較，您可以看到將數(shù)組的大小加倍可以改善最佳情況，但是仍然存在一個問題，即密鑰集和幻數(shù)之間的未命中匹配仍然會具有較高的沖突率。

哈希函數(shù)	最佳乘數(shù)	最低的碰撞	最差分?jǐn)?shù)	最高碰撞
hash（）	2924091	37次碰撞	117759	250次碰撞
xorShift16（哈希（））	543157075	25次碰撞	– 469729279	237次碰撞
addShift16（hash（））	-1843751569	25次碰撞	– 1501097607	205次碰撞
xorShift16n9（hash（））	-2109862879	27次碰撞	-2082455553	172次碰撞

結(jié)論

在具有穩(wěn)定密鑰集的情況下，可以通過調(diào)整使用的哈希策略來顯著提高沖突率。 您還需要進(jìn)行測試，這些測試表明如果密鑰集未經(jīng)重新優(yōu)化就可能變壞。 結(jié)合使用這兩種方法，您可以開發(fā)新的哈希策略來提高性能，而不必使用更多的內(nèi)存或更多的CPU。

翻譯自: https://www.javacodegeeks.com/2015/09/an-introduction-to-optimising-a-hashing-strategy.html

哈希策略

總結(jié)

以上是生活随笔為你收集整理的哈希策略_优化哈希策略的简介的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。