1. 前言

HashMap對于Java程序員來說一定不陌生，除了平時開發(fā)會經(jīng)常使用外，它也是面試官非常喜歡問的一個知識點(diǎn)。HashMap是哈希表的一個經(jīng)典實(shí)現(xiàn)，底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表，在JDK8中還引入了紅黑樹，以解決鏈表線性查找的效率問題。HashMap設(shè)計(jì)的非常優(yōu)秀，源碼兩千多行，有很多可以拿出來討論的點(diǎn)，本篇文章主要分析HashMap二次哈希的目的。

2. 哈希碼的作用

首先，我們得先了解哈希碼的作用是什么？HashMap底層采用數(shù)組+鏈表/紅黑樹的數(shù)據(jù)結(jié)構(gòu)來存儲鍵值對的映射關(guān)系，數(shù)組就是若干個哈希槽Solt，HashMap會通過Key算出的哈希碼來計(jì)算下標(biāo)Index，Index決定了鍵值對應(yīng)該落在哪個槽里。不同的哈希碼算出相同的下標(biāo)Index，就會導(dǎo)致哈希碰撞，一旦發(fā)生哈希碰撞，HashMap的查找效率就會從O(1)退化成O(n)或者O(logn)。所以，一個好的哈希函數(shù)應(yīng)該要盡可能的分散，否則就會影響到HashMap的效率。

3. 二次Hash

我們已經(jīng)知道，HashMap會根據(jù)哈希碼計(jì)算下標(biāo)，哈希碼的分散性越好，HashMap的效率也就越高。我們先看一下HashMap計(jì)算下標(biāo)的過程，就知道它為啥要做二次Hash了。

static int indexFor(int h, int length) {
    return h & (length-1);
}

上面是HashMap根據(jù)二次Hash計(jì)算出的哈希碼，計(jì)算鍵值對下標(biāo)的代碼，length是底層數(shù)組的長度。HashMap采用了位運(yùn)算，而非我們常見的取模運(yùn)算，這里你可以先略過，它倆的效果是一樣的。

我們先來看看如果不做二次Hash的情況下，會出現(xiàn)什么問題?，F(xiàn)在，我假設(shè)數(shù)組長度為16，那么當(dāng)哈希碼為5時，下標(biāo)Index結(jié)果是5。

 00000000000000000000000000000101
&00000000000000000000000000001111
=00000000000000000000000000000101
=5

當(dāng)哈希碼為65541時，下標(biāo)Index結(jié)果依然是5，不同的哈希碼算出相同的下標(biāo)，哈希碰撞了。

 00000000000000010000000000000101
&00000000000000000000000000001111
=00000000000000000000000000001101
=5

從這個與運(yùn)算的過程，大家肯定也都發(fā)現(xiàn)了，就是哈希碼的高位壓根就沒有參與運(yùn)算，全部被丟棄了。不管哈希碼的高位是多少，都不會影響最終Index的計(jì)算結(jié)果，因?yàn)橹挥械臀徊艆⑴c了運(yùn)算，這樣的哈希函數(shù)我們認(rèn)為是不好的，它會帶來更多的沖突，影響HashMap的效率。

如何解決這個問題呢？最簡單的辦法就是讓高位也參與到運(yùn)算，高位不一樣也會導(dǎo)致最終的Index結(jié)果不一樣，減少哈希碰撞的概率。事實(shí)上，HashMap也就是這么做的，下面是HashMap做二次Hash的源碼：

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

HashMap通過將哈希碼的高16位與低16位進(jìn)行異或運(yùn)算，得到一個新的哈希碼，這樣就可以讓高位也參與到運(yùn)算，這個函數(shù)也被稱作「擾動函數(shù)」。

我們用同樣的哈希碼，來看看經(jīng)過二次Hash后的哈希碼，是否會帶來不一樣的效果。
仍然假設(shè)數(shù)組長度為16，那么當(dāng)哈希碼為5時，下標(biāo)Index是5，結(jié)果不變。

 0000000000000101
^0000000000000000
=0000000000000101

 00000000000000000000000000000101
&00000000000000000000000000001111
=00000000000000000000000000000101
=5

當(dāng)哈希碼為65541時，下標(biāo)Index結(jié)果是4，竟然沒有發(fā)生哈希碰撞。

 0000000000000101
^0000000000000001
=0000000000000100

 00000000000000010000000000000100
&00000000000000000000000000001111
=00000000000000000000000000000100
=4

可以看到，HashMap通過加入一個擾動函數(shù)，讓原本會發(fā)生碰撞的兩個哈希碼，不再沖突。

4. 為啥右移16位

HashMap的擾動函數(shù)，是拿高16位和低16位做異或運(yùn)算，把高位的特征和地位的特征組合起來，以此來降低哈希碰撞的概率。為啥是16位？而不是8位或24位或其它位？

根據(jù)哈希碼計(jì)算下標(biāo)Index的過程，大家也發(fā)現(xiàn)了。實(shí)際上，只有數(shù)組長度以內(nèi)的低位才會參與運(yùn)算。例如數(shù)組長度是16，那么只有低4位會參與計(jì)算；如果數(shù)組長度是256，那么只有低8位會參與計(jì)算；如果數(shù)組長度是65536，那么只有低16位會參與計(jì)算。HashMap取16位是一個折中的數(shù)字，絕大部分情況下，HashMap數(shù)組的長度都不會超過65536。

5. 總結(jié)

HashMap底層采用數(shù)組+鏈表/紅黑樹來存儲鍵值對，會根據(jù)Key的哈希碼來計(jì)算鍵值對落在數(shù)組的哪個下標(biāo)。如果不同的哈希碼算出相同的下標(biāo)，就會導(dǎo)致哈希碰撞，影響HashMap的性能。HashMap要做的，就是盡量避免哈希碰撞，所以加入了擾動函數(shù)。擾動函數(shù)會將哈希碼的高16位與低16位做異或運(yùn)算，讓高位也參與到下標(biāo)的計(jì)算過程中來，從而影響最終下標(biāo)的計(jì)算結(jié)果，減少哈希碰撞的概率。至于為啥是16位，這是因?yàn)槟男┪粫⑴c到下標(biāo)的計(jì)算，取決于HashMap數(shù)組的長度，在絕大部分情況下，數(shù)組的長度都不會超過65536，16位是一個折中的數(shù)字。

到此這篇關(guān)于深入探究HashMap二次Hash原因的文章就介紹到這了,更多相關(guān)HashMap二次Hash內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論