腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

詳解Java如何實(shí)現(xiàn)一個優(yōu)秀的散列表

更新時間：2023年07月18日 10:40:57 作者：月伴飛魚

這篇文章主要通過簡單的示例為大家詳細(xì)介紹了在Java中如何實(shí)現(xiàn)一個優(yōu)秀的散列表，文中的示例代碼講解詳細(xì)，具有一定的參考價(jià)值，需要的可以了解一下

前言

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

很簡單！

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

遍歷文檔中的每個單詞 word ，找到鍵值對中key為 word 的項(xiàng)，并對相關(guān)的value進(jìn)行自增操作。
如果該key= word 的項(xiàng)在 HashMap中不存在，我們就插入一個(word,1)的項(xiàng)表示新增。
這樣每組鍵值對表示的就是某個單詞對應(yīng)的數(shù)量，等整個文檔遍歷完成，我們就可以得到每個單詞的數(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)計(jì)單詞對應(yīng)數(shù)量的？我們下面會逐步來研究一下！

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

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

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

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

注意：這樣的代碼顯然有兩個很大的問題：

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

優(yōu)化1

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

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

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

第一個數(shù)組用于存放所有單詞，數(shù)組下標(biāo)就是單詞編號了，我們稱之為字典數(shù)組；
第二個數(shù)組用于存放每個單詞對應(yīng)的計(jì)數(shù)器，我們稱之為計(jì)數(shù)數(shù)組。

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

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

優(yōu)化2

優(yōu)化方式：

一種是我們維護(hù)一個有序的數(shù)據(jù)結(jié)構(gòu)，讓比較和插入的過程更加高效，而不是需要遍歷每一個元素判斷逐一判斷。
另一種思路就是我們是否能尋找到一種直接基于字符串快速計(jì)算出編號的方式，并將這個編號映射到一個可以在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)計(jì)N個單詞出現(xiàn)數(shù)量的時候，整體只需要O(N)的復(fù)雜度，相比于原來的需要遍歷字典的做法就明顯高效的多。

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

優(yōu)化3

使用散列！

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

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

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

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

這個問題被稱之為哈希碰撞。

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

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

以JDK（JDK14）的HashMap為例：

主要實(shí)現(xiàn)在 java.util 下的 HashMap 中，這是一個最簡單的不考慮并發(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)就是對key.hashCode()進(jìn)行了一次特別的位運(yùn)算。

hashcode方法

在Java中每個對象生成時都會產(chǎn)生一個對應(yīng)的hashcode。

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

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

我們就一起來看看JDK中對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í)差不多，我們來看看StringUTF16中hashcode的實(shí)現(xiàn)：

public?static?int?hashCode(byte[]?value)?{
????int?h?=?0;
????int?length?=?value.length?>>?1;
????for?(int?i?=?0;?i?<?length;?i++)?{
????????h?=?31?*?h?+?getChar(value,?i);
????}
????return?h;
}

其實(shí)就是對字符串逐位按照下面的方式進(jìn)行計(jì)算，和展開成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)于直接對原來的數(shù)據(jù)進(jìn)行移位運(yùn)算；這樣溢出的時候，部分位的信息就完全丟失了，可能增加哈希沖突的概率。

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

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

h>>>16

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

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

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

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

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

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

所以，JDK的代碼引入了^ h >>> 16 這樣的位運(yùn)算，其實(shí)就是把高16位的信息疊加到了低16位，這樣我們在取模的時候就可以用到高位的信息了。

如何處理哈希沖突呢？

JDK中采用的是開鏈法。

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