優(yōu)化哈希策略-java開發(fā)java經(jīng)驗技巧

《優(yōu)化哈希策略-java開發(fā)java經(jīng)驗技巧》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

1、優(yōu)化哈希策略?編程開發(fā)技術優(yōu)化哈希策略木文由ImportNew?fzr翻譯自javacodegeekso歡迎加入翻譯小組。轉載請見文末要求。概述散列策略會對HashMap或HashSet之類的散列集合的性能產(chǎn)生直接的影響。內置的散列（乂稱哈希）函數(shù)都是通用的，在大多數(shù)使用情況下都能表現(xiàn)很好。但是我們能不能做的更好呢，特別是當你對某個用例產(chǎn)牛了很好的想法吋？測試一個散列策略在先前的一篇文章中，我研究了一些測試散列策略的方法，其中特別注意了一種“止交位”優(yōu)化的散列策略，它僅僅只是改變一個位就能確保每個散列結果

2、盡可能的不同。.然而，如果要對一個已知的元索或關鍵字集合進行散列，你就可以針對具體案例進行優(yōu)化，而不是尋求一個通用方案。減少沖突一個散列集合中最主耍的事情就是避免沖突了。所謂沖突，就是兩個以上關鍵字映射到同一個散列槽中。這些沖突意味著當有多個關鍵字映射到同一個散列槽中時你必須要付出更多的努力來檢查那些關鍵字是否是你想要的那個。理想狀態(tài)下一個散列槽中最多有一個關鍵字。我只需要唯一的散列碼，是嗎?通常的誤解是只要散列碼唯一就口J以避免沖突。雖然都希望散列碼是唯一的，但它還不夠。假設現(xiàn)在有一些關鍵字，每一個都有

3、唯一的32位散列碼。如果你有40億散列槽,每個關鍵字都有口己的槽，那就沒有沖突了。對于所有的散列集合，這樣大的數(shù)組一般是不太現(xiàn)實的。事實上，HashMap和HashSet的人小都收到機器內存的限制，一般為2飛0,大概剛剛超過10億。當你只能冇一個規(guī)模上比較實際的哈希集合時又該如何呢？散列槽的數(shù)目需要更小一些，而散列碼需對散列槽數(shù)目取模。如果散列槽數(shù)是2的幕值，你可以用最低位當掩碼。來看個例子，ftse350.csvo如果把第一列作為關鍵字或是元素，就有352個字符串。這些字符串有唯一的StringO.ha

4、shCodc()碼,但是假設我們只取這些散列碼的低位。會不會有沖突呢？MaskString.hashCode()maskedHashMap.hash(String.hashCodeO)masked32bitsNocollisionsNocollisions16bits1collision3collisions15bits2collisions4collisions14bits6collisions6collisions13bits11collisions9collisions12bits17collisi

5、ons15collisions11bits29collisions25collisions10bits57collisions50collisions9bits103collisions92collisions一個裝載因子是0.7(默認)的HashMap的大小是512,使用哈希碼的低九位作為掩碼?？梢钥吹?，盡管原始的哈希碼是唯一的，仍然有大約30%的關鍵字會沖突。?HashTcstcrMain的代碼在這里。為了減少糟糕的散列策略造成的影響，HashMap使用了擾動函數(shù)。Java8里的實現(xiàn)相當簡單。下面是來

6、自HashMap.hash的源碼。想了解更多細節(jié),可以閱讀Javadoc文檔。staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())八(h>>>16);}這個方法混合了原始哈希碼的高位和低位，以此來提高低位的隨機性。對于像上面的那樣有相當高的沖突率的情況，這就是一個改善方法。請參看第三列。初探String類的散列函數(shù)卜面是String.hashCodcO的代碼:publicinthashCode(){inth二ha

7、sh;if(h二二0&&value,length>0){charval[]=value;for(inti=0;i

8、然很重要，但是你并不想讓它過丁重要；因為總是冇些時候你選的數(shù)字并不適合你的使用場景。這就是為什么你同時還需要一個即使在魔法數(shù)字選取很耕糕的情況下其最壞情況依然不是特別差的代碼結構。用別的乘數(shù)代替31MultiplierCollisions12302167311349951056102793890910010911191可以看到，魔法數(shù)的選取的確很重要，但需要嘗試的數(shù)字太多了。我們需要寫一個測試程序，測試出一個不錯的隨機選擇。I