如何實現(xiàn)一個優(yōu)秀的散列表！
文章首發(fā)在公眾號（月伴飛魚），之后同步到個人網(wǎng)站：https://xiaoflyfish.cn/
微信搜索：月伴飛魚，交個朋友，進(jìn)面試交流群
公眾號后臺回復(fù)666，可以獲得免費電子書籍
覺得不錯，希望點贊，在看，轉(zhuǎn)發(fā)支持一下，謝謝！
前言
假設(shè)現(xiàn)在有一篇很長的文檔，如果希望統(tǒng)計文檔中每個單詞在文檔中出現(xiàn)了多少次，應(yīng)該怎么做呢？
很簡單！
我們可以建一個HashMap，以String類型為Key，Int類型為Value；
遍歷文檔中的每個單詞
word，找到鍵值對中key為word的項，并對相關(guān)的value進(jìn)行自增操作。如果該key=
word的項在 HashMap中不存在，我們就插入一個(word,1)的項表示新增。這樣每組鍵值對表示的就是某個單詞對應(yīng)的數(shù)量，等整個文檔遍歷完成，我們就可以得到每個單詞的數(shù)量了。
簡單實現(xiàn)下，代碼示例如下：
import?java.util.HashMap;
import?java.util.Map;
public?class?Test?{
????public?static?void?main(String[]?args)?{
????????Map?map?=?new?HashMap<>();
????????String?doc?=?"yue?ban?fei?yu";
????????String[]?words?=?doc.split("?");
????????for?(String?s?:?words)?{
????????????if?(!map.containsKey(s))?{
????????????????map.put(s,?1);
????????????}?else?{
????????????????map.put(s,?map.get(s)?+?1);
????????????}
????????}
????????System.out.println(map);
????}
}
那HashMap是怎么做到高效統(tǒng)計單詞對應(yīng)數(shù)量的？我們下面會逐步來研究一下！
首先我們先來看看如果只統(tǒng)計某一個單詞的數(shù)量？
只需要開一個變量，同樣遍歷所有單詞，遇到和目標(biāo)單詞一樣的，才對這個變量進(jìn)行自增操作；
等遍歷完成，我們就可以得到該單詞的數(shù)量了。
我們可以把所有可能出現(xiàn)的單詞都列出來，每個單詞，單獨用一個變量去統(tǒng)計它出現(xiàn)的數(shù)量，遍歷所有單詞，判斷當(dāng)前單詞應(yīng)該被累計到哪個變量中。
import?java.util.HashMap;
import?java.util.Map;
public?class?Main?{
????public?static?void?main(String[]?args)?{
????????int[]?cnt?=?new?int[20000];
????????String?doc?=?"a?b?c?d";
????????String[]?words?=?doc.split("?");
????????int?a?=?0;
????????int?b?=?0;
????????int?c?=?0;
????????int?d?=?0;
????????
????????for?(String?s?:?words)?{
???????????if?(s?==?"a")?a++;
???????????if?(s?==?"b")?b++;
???????????if?(s?==?"c")?c++;
???????????if?(s?==?"d")?d++;???
????????}
????}
}
注意：這樣的代碼顯然有兩個很大的問題：
對單詞和計數(shù)器的映射關(guān)系是通過一堆if-else寫死的，維護(hù)性很差； 必須已知所有可能出現(xiàn)的單詞，如果遇到一個新的單詞，就沒有辦法處理它了。
優(yōu)化1
我們可以開一個數(shù)組去維護(hù)計數(shù)器。
具體做法就是，給每個單詞編個號，直接用編號對應(yīng)下標(biāo)的數(shù)組元素作為它的計數(shù)器就好啦。
我們可以建立兩個數(shù)組：
第一個數(shù)組用于存放所有單詞，數(shù)組下標(biāo)就是單詞編號了，我們稱之為字典數(shù)組；
第二個數(shù)組用于存放每個單詞對應(yīng)的計數(shù)器，我們稱之為計數(shù)數(shù)組。
每遇到一個新的單詞，都遍歷一遍字典數(shù)組，如果沒有出現(xiàn)過，我們就將當(dāng)前單詞插入到字典數(shù)組結(jié)尾。
這樣做，整體的時間復(fù)雜度較高，還是不行。
優(yōu)化2
優(yōu)化方式：
一種是我們維護(hù)一個有序的數(shù)據(jù)結(jié)構(gòu)，讓比較和插入的過程更加高效，而不是需要遍歷每一個元素判斷逐一判斷。 另一種思路就是我們是否能尋找到一種直接基于字符串快速計算出編號的方式，并將這個編號映射到一個可以在O(1)時間內(nèi)基于下標(biāo)訪問的數(shù)組中。
以單詞為例，英文單詞的每個字母只可能是 a-z。
我們用0表示a、1表示b，以此類推，用25表示z，然后將一個單詞看成一個26進(jìn)制的數(shù)字即可。
import?java.util.HashMap;
import?java.util.Map;
public?class?Main?{
????public?static?void?main(String[]?args)?{
????????int[]?cnt?=?new?int[20000];
????????String?doc?=?"a?b?c?d";
????????String[]?words?=?doc.split("?");
????????for?(String?s?:?words)?{
????????????int?tmp?=?0;
????????????for?(char?c:?s.toCharArray())?{
????????????????tmp?*=?26;
????????????????tmp?+=?(c?-?'a');
????????????}
????????????cnt[tmp]++;
????????}
????????String?target?=?"a";
????????int?hash?=?0;
????????for?(char?c:?target.toCharArray())?{
????????????hash?*=?26;
????????????hash?+=?c?-?'a';
????????}
????????System.out.println(cnt[hash]);
????}
}
這樣我們統(tǒng)計N個單詞出現(xiàn)數(shù)量的時候，整體只需要O(N)的復(fù)雜度，相比于原來的需要遍歷字典的做法就明顯高效的多。
這其實就是散列的思想了。
優(yōu)化3
使用散列！
散列函數(shù)的本質(zhì)，就是將一個更大且可能不連續(xù)空間（比如所有的單詞），映射到一個空間有限的數(shù)組里，從而借用數(shù)組基于下標(biāo)O(1)快速隨機(jī)訪問數(shù)組元素的能力。
但設(shè)計一個合理的散列函數(shù)是一個非常難的事情。
比如對26進(jìn)制的哈希值再進(jìn)行一次對大質(zhì)數(shù)取mod的運(yùn)算，只有這樣才能用比較有限的計數(shù)數(shù)組空間去表示整個哈希表。
取了mod之后，我們很快就會發(fā)現(xiàn)，現(xiàn)在可能出現(xiàn)一種情況，把兩個不同的單詞用26進(jìn)制表示并取模之后，得到的值很可能是一樣的。
這個問題被稱之為哈希碰撞。
如何實現(xiàn)
最后我們考慮一下散列函數(shù)到底需要怎么設(shè)計。
以JDK（JDK14）的HashMap為例：
主要實現(xiàn)在 java.util下的HashMap中，這是一個最簡單的不考慮并發(fā)的、基于散列的Map實現(xiàn)。
找到其中用于計算哈希值的hash方法：
static?final?int?hash(Object?key)?{
????int?h;
????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
}
可以發(fā)現(xiàn)就是對key.hashCode()進(jìn)行了一次特別的位運(yùn)算。
hashcode方法
在Java中每個對象生成時都會產(chǎn)生一個對應(yīng)的hashcode。
當(dāng)然數(shù)據(jù)類型不同，hashcode的計算方式是不一樣的，但一定會保證的是兩個一樣的對象，對應(yīng)的hashcode也是一樣的；
所以在比較兩個對象是否相等時，我們可以先比較hashcode是否一致，如果不一致，就不需要繼續(xù)調(diào)用equals，大大降低了比較對象相等的代價。
我們就一起來看看JDK中對String類型的hashcode是怎么計算的，我們進(jìn)入 java.lang 包查看String類型的實現(xiàn)：
public?int?hashCode()?{
????//?The?hash?or?hashIsZero?fields?are?subject?to?a?benign?data?race,
????//?making?it?crucial?to?ensure?that?any?observable?result?of?the
????//?calculation?in?this?method?stays?correct?under?any?possible?read?of
????//?these?fields.?Necessary?restrictions?to?allow?this?to?be?correct
????//?without?explicit?memory?fences?or?similar?concurrency?primitives?is
????//?that?we?can?ever?only?write?to?one?of?these?two?fields?for?a?given
????//?String?instance,?and?that?the?computation?is?idempotent?and?derived
????//?from?immutable?state
????int?h?=?hash;
????if?(h?==?0?&&?!hashIsZero)?{
????????h?=?isLatin1()???StringLatin1.hashCode(value)
???????????????????????:?StringUTF16.hashCode(value);
????????if?(h?==?0)?{
????????????hashIsZero?=?true;
????????}?else?{
????????????hash?=?h;
????????}
????}
????return?h;
}
Latin和UTF16是兩種字符串的編碼格式，實現(xiàn)思路其實差不多，我們來看看StringUTF16中hashcode的實現(xiàn)：
public?static?int?hashCode(byte[]?value)?{
????int?h?=?0;
????int?length?=?value.length?>>?1;
????for?(int?i?=?0;?i?????????h?=?31?*?h?+?getChar(value,?i);
????}
????return?h;
}
其實就是對字符串逐位按照下面的方式進(jìn)行計算，和展開成26進(jìn)制的想法本質(zhì)上是相似的。
s[0]*31^(n-1)?+?s[1]*31^(n-2)?+?...?+?s[n-1]
為什么選擇了31？
首先在各種哈希計算中，我們比較傾向使用奇素數(shù)進(jìn)行乘法運(yùn)算，而不是用偶數(shù)。
因為用偶數(shù)，尤其是2的冪次，進(jìn)行乘法，相當(dāng)于直接對原來的數(shù)據(jù)進(jìn)行移位運(yùn)算；這樣溢出的時候，部分位的信息就完全丟失了，可能增加哈希沖突的概率。
為什么選擇了31這個奇怪的數(shù)，這是因為計算機(jī)在進(jìn)行移位運(yùn)算要比普通乘法運(yùn)算快得多，而31*i可以直接轉(zhuǎn)化為(i << 5)- i ，這是一個性能比較好的乘法計算方式，現(xiàn)代的編譯器都可以推理并自動完成相關(guān)的優(yōu)化。
具體可以參考《Effective Java》中的相關(guān)章節(jié)。
h>>>16
我們現(xiàn)在來看 ^ h >>> 16 又是一個什么樣的作用呢？
它的意思是就是將h右移16位并進(jìn)行異或操作，為什么要這么做呢？
因為那個hash值計算出來這么大，那怎么把它連續(xù)地映射到一個小一點的連續(xù)數(shù)組空間呢？
所以需要取模，我們需要將hash值對數(shù)組的大小進(jìn)行一次取模。
我們需要對2的冪次大小的數(shù)組進(jìn)行一次取模計算。
但對二的冪次取模相當(dāng)于直接截取數(shù)字比較低的若干位，這在數(shù)組元素較少的時候，相當(dāng)于只使用了數(shù)字比較低位的信息，而放棄了高位的信息，可能會增加沖突的概率。
所以，JDK的代碼引入了^ h >>> 16 這樣的位運(yùn)算，其實就是把高16位的信息疊加到了低16位，這樣我們在取模的時候就可以用到高位的信息了。
如何處理哈希沖突呢？
JDK中采用的是開鏈法。
哈希表內(nèi)置數(shù)組中的每個槽位，存儲的是一個鏈表，鏈表節(jié)點的值存放的就是需要存儲的鍵值對。
如果碰到哈希沖突，也就是兩個不同的key映射到了數(shù)組中的同一個槽位，我們就將該元素直接放到槽位對應(yīng)鏈表的尾部。
總結(jié)一下
手寫數(shù)據(jù)結(jié)構(gòu)統(tǒng)計單詞的數(shù)量正確的思路就是：
根據(jù)全文長度大概預(yù)估一下會有多少個單詞，開一個數(shù)倍于它的數(shù)組，再設(shè)計一個合理的hash函數(shù)，把每個單詞映射到數(shù)組的某個下標(biāo)，用這個數(shù)組計數(shù)統(tǒng)計就好啦。
當(dāng)然在實際工程中，我們不會為每個場景都單獨寫一個這樣的散列表實現(xiàn)，也不用自己去處理復(fù)雜的擴(kuò)容場景。