1. 前言

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

2. 哈希碼的作用

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

3. 二次Hash

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

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

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

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

 00000000000000000000000000000101
&00000000000000000000000000001111
=00000000000000000000000000000101
=5

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

 00000000000000010000000000000101
&00000000000000000000000000001111
=00000000000000000000000000001101
=5

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

如何解決這個(gè)問(wèn)題呢？最簡(jiǎn)單的辦法就是讓高位也參與到運(yùn)算，高位不一樣也會(huì)導(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通過(guò)將哈希碼的高16位與低16位進(jìn)行異或運(yùn)算，得到一個(gè)新的哈希碼，這樣就可以讓高位也參與到運(yùn)算，這個(gè)函數(shù)也被稱(chēng)作「擾動(dòng)函數(shù)」。

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

 0000000000000101
^0000000000000000
=0000000000000101

 00000000000000000000000000000101
&00000000000000000000000000001111
=00000000000000000000000000000101
=5

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

 0000000000000101
^0000000000000001
=0000000000000100

 00000000000000010000000000000100
&00000000000000000000000000001111
=00000000000000000000000000000100
=4

可以看到，HashMap通過(guò)加入一個(gè)擾動(dòng)函數(shù)，讓原本會(huì)發(fā)生碰撞的兩個(gè)哈希碼，不再?zèng)_突。

4. 為啥右移16位

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

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

5. 總結(jié)

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

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

最新評(píng)論