文章首發(fā)在公眾號(hào)（月伴飛魚(yú)），之后同步到個(gè)人網(wǎng)站：https://xiaoflyfish.cn/

微信搜索：月伴飛魚(yú)，交個(gè)朋友，進(jìn)面試交流群

• 公眾號(hào)后臺(tái)回復(fù)666，可以獲得免費(fèi)電子書(shū)籍

覺(jué)得不錯(cuò)，希望點(diǎn)贊，在看，轉(zhuǎn)發(fā)支持一下，謝謝！

前言

假設(shè)現(xiàn)在有一篇很長(zhǎng)的文檔，如果希望統(tǒng)計(jì)文檔中每個(gè)單詞在文檔中出現(xiàn)了多少次，應(yīng)該怎么做呢？

很簡(jiǎn)單！

我們可以建一個(gè)HashMap，以String類型為Key，Int類型為Value；

• 遍歷文檔中的每個(gè)單詞 word ，找到鍵值對(duì)中key為 word 的項(xiàng)，并對(duì)相關(guān)的value進(jìn)行自增操作。

• 如果該key= word 的項(xiàng)在 HashMap中不存在，我們就插入一個(gè)(word,1)的項(xiàng)表示新增。

• 這樣每組鍵值對(duì)表示的就是某個(gè)單詞對(duì)應(yīng)的數(shù)量，等整個(gè)文檔遍歷完成，我們就可以得到每個(gè)單詞的數(shù)量了。

簡(jiǎn)單實(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)計(jì)單詞對(duì)應(yīng)數(shù)量的？我們下面會(huì)逐步來(lái)研究一下！

首先我們先來(lái)看看如果只統(tǒng)計(jì)某一個(gè)單詞的數(shù)量？

只需要開(kāi)一個(gè)變量，同樣遍歷所有單詞，遇到和目標(biāo)單詞一樣的，才對(duì)這個(gè)變量進(jìn)行自增操作；

• 等遍歷完成，我們就可以得到該單詞的數(shù)量了。

• 我們可以把所有可能出現(xiàn)的單詞都列出來(lái)，每個(gè)單詞，單獨(dú)用一個(gè)變量去統(tǒng)計(jì)它出現(xiàn)的數(shù)量，遍歷所有單詞，判斷當(dāng)前單詞應(yīng)該被累計(jì)到哪個(gè)變量中。

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

注意：這樣的代碼顯然有兩個(gè)很大的問(wèn)題：

1. 對(duì)單詞和計(jì)數(shù)器的映射關(guān)系是通過(guò)一堆if-else寫(xiě)死的，維護(hù)性很差；
2. 必須已知所有可能出現(xiàn)的單詞，如果遇到一個(gè)新的單詞，就沒(méi)有辦法處理它了。

優(yōu)化1

我們可以開(kāi)一個(gè)數(shù)組去維護(hù)計(jì)數(shù)器。

具體做法就是，給每個(gè)單詞編個(gè)號(hào)，直接用編號(hào)對(duì)應(yīng)下標(biāo)的數(shù)組元素作為它的計(jì)數(shù)器就好啦。

我們可以建立兩個(gè)數(shù)組：

• 第一個(gè)數(shù)組用于存放所有單詞，數(shù)組下標(biāo)就是單詞編號(hào)了，我們稱之為字典數(shù)組；

• 第二個(gè)數(shù)組用于存放每個(gè)單詞對(duì)應(yīng)的計(jì)數(shù)器，我們稱之為計(jì)數(shù)數(shù)組。

每遇到一個(gè)新的單詞，都遍歷一遍字典數(shù)組，如果沒(méi)有出現(xiàn)過(guò)，我們就將當(dāng)前單詞插入到字典數(shù)組結(jié)尾。

這樣做，整體的時(shí)間復(fù)雜度較高，還是不行。

優(yōu)化2

優(yōu)化方式：

• 一種是我們維護(hù)一個(gè)有序的數(shù)據(jù)結(jié)構(gòu)，讓比較和插入的過(guò)程更加高效，而不是需要遍歷每一個(gè)元素判斷逐一判斷。
• 另一種思路就是我們是否能尋找到一種直接基于字符串快速計(jì)算出編號(hào)的方式，并將這個(gè)編號(hào)映射到一個(gè)可以在O(1)時(shí)間內(nèi)基于下標(biāo)訪問(wèn)的數(shù)組中。

以單詞為例，英文單詞的每個(gè)字母只可能是 a-z。

我們用0表示a、1表示b，以此類推，用25表示z，然后將一個(gè)單詞看成一個(gè)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)計(jì)N個(gè)單詞出現(xiàn)數(shù)量的時(shí)候，整體只需要O(N)的復(fù)雜度，相比于原來(lái)的需要遍歷字典的做法就明顯高效的多。

這其實(shí)就是散列的思想了。

優(yōu)化3

使用散列！

散列函數(shù)的本質(zhì)，就是將一個(gè)更大且可能不連續(xù)空間（比如所有的單詞），映射到一個(gè)空間有限的數(shù)組里，從而借用數(shù)組基于下標(biāo)O(1)快速隨機(jī)訪問(wèn)數(shù)組元素的能力。

但設(shè)計(jì)一個(gè)合理的散列函數(shù)是一個(gè)非常難的事情。

• 比如對(duì)26進(jìn)制的哈希值再進(jìn)行一次對(duì)大質(zhì)數(shù)取mod的運(yùn)算，只有這樣才能用比較有限的計(jì)數(shù)數(shù)組空間去表示整個(gè)哈希表。

取了mod之后，我們很快就會(huì)發(fā)現(xiàn)，現(xiàn)在可能出現(xiàn)一種情況，把兩個(gè)不同的單詞用26進(jìn)制表示并取模之后，得到的值很可能是一樣的。

這個(gè)問(wèn)題被稱之為哈希碰撞。

如何實(shí)現(xiàn)

最后我們考慮一下散列函數(shù)到底需要怎么設(shè)計(jì)。

以JDK（JDK14）的HashMap為例：

• 主要實(shí)現(xiàn)在 java.util 下的 HashMap 中，這是一個(gè)最簡(jiǎn)單的不考慮并發(fā)的、基于散列的Map實(shí)現(xiàn)。

找到其中用于計(jì)算哈希值的hash方法：

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

可以發(fā)現(xiàn)就是對(duì)key.hashCode()進(jìn)行了一次特別的位運(yùn)算。

hashcode方法

在Java中每個(gè)對(duì)象生成時(shí)都會(huì)產(chǎn)生一個(gè)對(duì)應(yīng)的hashcode。

• 當(dāng)然數(shù)據(jù)類型不同，hashcode的計(jì)算方式是不一樣的，但一定會(huì)保證的是兩個(gè)一樣的對(duì)象，對(duì)應(yīng)的hashcode也是一樣的；

所以在比較兩個(gè)對(duì)象是否相等時(shí)，我們可以先比較hashcode是否一致，如果不一致，就不需要繼續(xù)調(diào)用equals，大大降低了比較對(duì)象相等的代價(jià)。

我們就一起來(lái)看看JDK中對(duì)String類型的hashcode是怎么計(jì)算的，我們進(jìn)入 java.lang 包查看String類型的實(shí)現(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是兩種字符串的編碼格式，實(shí)現(xiàn)思路其實(shí)差不多，我們來(lái)看看StringUTF16中hashcode的實(shí)現(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;
}

其實(shí)就是對(duì)字符串逐位按照下面的方式進(jìn)行計(jì)算，和展開(kāi)成26進(jìn)制的想法本質(zhì)上是相似的。

s[0]*31^(n-1)?+?s[1]*31^(n-2)?+?...?+?s[n-1]

為什么選擇了31？

首先在各種哈希計(jì)算中，我們比較傾向使用奇素?cái)?shù)進(jìn)行乘法運(yùn)算，而不是用偶數(shù)。

因?yàn)橛门紨?shù)，尤其是2的冪次，進(jìn)行乘法，相當(dāng)于直接對(duì)原來(lái)的數(shù)據(jù)進(jìn)行移位運(yùn)算；這樣溢出的時(shí)候，部分位的信息就完全丟失了，可能增加哈希沖突的概率。

為什么選擇了31這個(gè)奇怪的數(shù)，這是因?yàn)橛?jì)算機(jī)在進(jìn)行移位運(yùn)算要比普通乘法運(yùn)算快得多，而31*i可以直接轉(zhuǎn)化為(i << 5)- i ，這是一個(gè)性能比較好的乘法計(jì)算方式，現(xiàn)代的編譯器都可以推理并自動(dòng)完成相關(guān)的優(yōu)化。

具體可以參考《Effective Java》中的相關(guān)章節(jié)。

h>>>16

我們現(xiàn)在來(lái)看 ^ h >>> 16 又是一個(gè)什么樣的作用呢？

它的意思是就是將h右移16位并進(jìn)行異或操作，為什么要這么做呢？

因?yàn)槟莻€(gè)hash值計(jì)算出來(lái)這么大，那怎么把它連續(xù)地映射到一個(gè)小一點(diǎn)的連續(xù)數(shù)組空間呢？

所以需要取模，我們需要將hash值對(duì)數(shù)組的大小進(jìn)行一次取模。

我們需要對(duì)2的冪次大小的數(shù)組進(jìn)行一次取模計(jì)算。

但對(duì)二的冪次取模相當(dāng)于直接截取數(shù)字比較低的若干位，這在數(shù)組元素較少的時(shí)候，相當(dāng)于只使用了數(shù)字比較低位的信息，而放棄了高位的信息，可能會(huì)增加沖突的概率。

所以，JDK的代碼引入了^ h >>> 16 這樣的位運(yùn)算，其實(shí)就是把高16位的信息疊加到了低16位，這樣我們?cè)谌∧５臅r(shí)候就可以用到高位的信息了。

如何處理哈希沖突呢？

JDK中采用的是開(kāi)鏈法。

哈希表內(nèi)置數(shù)組中的每個(gè)槽位，存儲(chǔ)的是一個(gè)鏈表，鏈表節(jié)點(diǎn)的值存放的就是需要存儲(chǔ)的鍵值對(duì)。

如果碰到哈希沖突，也就是兩個(gè)不同的key映射到了數(shù)組中的同一個(gè)槽位，我們就將該元素直接放到槽位對(duì)應(yīng)鏈表的尾部。

總結(jié)一下

手寫(xiě)數(shù)據(jù)結(jié)構(gòu)統(tǒng)計(jì)單詞的數(shù)量正確的思路就是：

根據(jù)全文長(zhǎng)度大概預(yù)估一下會(huì)有多少個(gè)單詞，開(kāi)一個(gè)數(shù)倍于它的數(shù)組，再設(shè)計(jì)一個(gè)合理的hash函數(shù)，把每個(gè)單詞映射到數(shù)組的某個(gè)下標(biāo)，用這個(gè)數(shù)組計(jì)數(shù)統(tǒng)計(jì)就好啦。

當(dāng)然在實(shí)際工程中，我們不會(huì)為每個(gè)場(chǎng)景都單獨(dú)寫(xiě)一個(gè)這樣的散列表實(shí)現(xiàn)，也不用自己去處理復(fù)雜的擴(kuò)容場(chǎng)景。