Java面試題之HashMap 的 hash 方法原理是什么
Warning:這是《Java 程序員進(jìn)階之路》專欄的第 55 篇。
回來(lái)后小二找到了我,于是我就寫下了這篇文章丟給他,并嚴(yán)厲地告訴他:再搞不懂就別來(lái)找我。聽(tīng)到這句話,心頭一陣酸,小二繃不住差點(diǎn)要哭 😭。
PS:本文 GitHub 上已同步,有 GitHub 賬號(hào)的小伙伴,記得看完后給二哥安排一波 star 呀!沖一波 GitHub 的 trending 榜單,求求各位了。
GitHub 地址:https://github.com/itwanger/toBeBetterJavaer
來(lái)看一下 hash 方法的源碼(JDK 8 中的 HashMap):
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
這段代碼究竟是用來(lái)干嘛的呢?
我們都知道,key.hashCode()
是用來(lái)獲取鍵位的哈希值的,理論上,哈希值是一個(gè) int 類型,范圍從-2147483648 到 2147483648。前后加起來(lái)大概 40 億的映射空間,只要哈希值映射得比較均勻松散,一般是不會(huì)出現(xiàn)哈希碰撞的。
但問(wèn)題是一個(gè) 40 億長(zhǎng)度的數(shù)組,內(nèi)存是放不下的。HashMap 擴(kuò)容之前的數(shù)組初始大小只有 16,所以這個(gè)哈希值是不能直接拿來(lái)用的,用之前要和數(shù)組的長(zhǎng)度做取模運(yùn)算,用得到的余數(shù)來(lái)訪問(wèn)數(shù)組下標(biāo)才行。
取模運(yùn)算有兩處。
取模運(yùn)算(“Modulo Operation”)和取余運(yùn)算(“Remainder Operation ”)兩個(gè)概念有重疊的部分但又不完全一致。主要的區(qū)別在于對(duì)負(fù)整數(shù)進(jìn)行除法運(yùn)算時(shí)操作不同。取模主要是用于計(jì)算機(jī)術(shù)語(yǔ)中,取余則更多是數(shù)學(xué)概念。
一處是往 HashMap 中 put 的時(shí)候(putVal
方法中):
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); }
一處是從 HashMap 中 get 的時(shí)候(getNode
方法中):
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {} }
其中的 (n - 1) & hash
正是取模運(yùn)算,就是把哈希值和(數(shù)組長(zhǎng)度-1)做了一個(gè)“與”運(yùn)算。
可能大家在疑惑:取模運(yùn)算難道不該用 %
嗎?為什么要用 &
呢?
這是因?yàn)?&
運(yùn)算比 %
更加高效,并且當(dāng) b 為 2 的 n 次方時(shí),存在下面這樣一個(gè)公式。
a % b = a & (b-1)
用 2 n 2^n 2n 替換下 b 就是:
我們來(lái)驗(yàn)證一下,假如 a = 14,b = 8,也就是 2 3 2^3 23,n=3。
14%8,14 的二進(jìn)制為 1110,8 的二進(jìn)制 1000,8-1 = 7 的二進(jìn)制為 0111,1110&0111=0110,也就是 0*
2 0 2^0 20+1*
2 1 2^1 21+1*
2 2 2^2 22+0*
2 3 2^3 23=0+2+4+0=6,14%8 剛好也等于 6。
這也正好解釋了為什么 HashMap 的數(shù)組長(zhǎng)度要取 2 的整次方。
因?yàn)椋〝?shù)組長(zhǎng)度-1)正好相當(dāng)于一個(gè)“低位掩碼”——這個(gè)掩碼的低位最好全是 1,這樣 & 操作才有意義,否則結(jié)果就肯定是 0,那么 & 操作就沒(méi)有意義了。
a&b 操作的結(jié)果是:a、b 中對(duì)應(yīng)位同時(shí)為 1,則對(duì)應(yīng)結(jié)果位為 1,否則為 0
2 的整次冪剛好是偶數(shù),偶數(shù)-1 是奇數(shù),奇數(shù)的二進(jìn)制最后一位是 1,保證了 hash &(length-1) 的最后一位可能為 0,也可能為 1(這取決于 h 的值),即 & 運(yùn)算后的結(jié)果可能為偶數(shù),也可能為奇數(shù),這樣便可以保證哈希值的均勻性。
& 操作的結(jié)果就是將哈希值的高位全部歸零,只保留低位值,用來(lái)做數(shù)組下標(biāo)訪問(wèn)。
假設(shè)某哈希值為 10100101 11000100 00100101
,用它來(lái)做取模運(yùn)算,我們來(lái)看一下結(jié)果。HashMap 的初始長(zhǎng)度為 16(內(nèi)部是數(shù)組),16-1=15,二進(jìn)制是 00000000 00000000 00001111
(高位用 0 來(lái)補(bǔ)齊):
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101
因?yàn)?15 的高位全部是 0,所以 & 運(yùn)算后的高位結(jié)果肯定是 0,只剩下 4 個(gè)低位 0101
,也就是十進(jìn)制的 5,也就是將哈希值為 10100101 11000100 00100101
的鍵放在數(shù)組的第 5 位。
明白了取模運(yùn)算后,我們?cè)賮?lái)看 put 方法的源碼:
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
以及 get 方法的源碼:
public V get(Object key) { HashMap.Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
它們?cè)谡{(diào)用 putVal 和 getNode 之前,都會(huì)先調(diào)用 hash 方法:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
那為什么取模運(yùn)算之前要調(diào)用 hash 方法呢?
看下面這個(gè)圖。
某哈希值為 11111111 11111111 11110000 1110 1010
,將它右移 16 位(h >>> 16),剛好是 00000000 00000000 11111111 11111111
,再進(jìn)行異或操作(h ^ (h >>> 16)),結(jié)果是 11111111 11111111 00001111 00010101
異或(^
)運(yùn)算是基于二進(jìn)制的位運(yùn)算,采用符號(hào) XOR 或者^
來(lái)表示,運(yùn)算規(guī)則是:如果是同值取 0、異值取 1
由于混合了原來(lái)哈希值的高位和低位,所以低位的隨機(jī)性加大了(摻雜了部分高位的特征,高位的信息也得到了保留)。
結(jié)果再與數(shù)組長(zhǎng)度-1(00000000 00000000 00000000 00001111
)做取模運(yùn)算,得到的下標(biāo)就是 00000000 00000000 00000000 00000101
,也就是 5。
還記得之前我們假設(shè)的某哈希值 10100101 11000100 00100101
嗎?在沒(méi)有調(diào)用 hash 方法之前,與 15 做取模運(yùn)算后的結(jié)果也是 5,我們不妨來(lái)看看調(diào)用 hash 之后的取模運(yùn)算結(jié)果是多少。
某哈希值 00000000 10100101 11000100 00100101
(補(bǔ)齊 32 位),將它右移 16 位(h >>> 16),剛好是 00000000 00000000 00000000 10100101
,再進(jìn)行異或操作(h ^ (h >>> 16)),結(jié)果是 00000000 10100101 00111011 10000000
結(jié)果再與數(shù)組長(zhǎng)度-1(00000000 00000000 00000000 00001111
)做取模運(yùn)算,得到的下標(biāo)就是 00000000 00000000 00000000 00000000
,也就是 0。
綜上所述,hash 方法是用來(lái)做哈希值優(yōu)化的,把哈希值右移 16 位,也就正好是自己長(zhǎng)度的一半,之后與原哈希值做異或運(yùn)算,這樣就混合了原哈希值中的高位和低位,增大了隨機(jī)性。
說(shuō)白了,hash 方法就是為了增加隨機(jī)性,讓數(shù)據(jù)元素更加均衡的分布,減少碰撞。
到此這篇關(guān)于Java面試題之HashMap 的 hash 方法原理是什么的文章就介紹到這了,更多相關(guān)Java HashMap內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
JavaWeb開(kāi)發(fā)中alias攔截器的使用方法
本文給大家介紹在JavaWeb開(kāi)發(fā)中alias攔截器的使用方法相關(guān)知識(shí),本文介紹的非常詳細(xì),具有參考借鑒價(jià)值,感興趣的朋友一起看下吧2016-08-08Java并發(fā) synchronized鎖住的內(nèi)容解析
這篇文章主要介紹了Java并發(fā) synchronized鎖住的內(nèi)容解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-09-09Java實(shí)現(xiàn)在正則表達(dá)式中控制大小寫的方法
這篇文章主要介紹了Java實(shí)現(xiàn)在正則表達(dá)式中控制大小寫的方法,結(jié)合實(shí)例形式分析了java正則表達(dá)式中傳遞控制參數(shù)的功能與相關(guān)操作技巧,需要的朋友可以參考下2017-04-04Springboot整合SpringSecurity實(shí)現(xiàn)登錄認(rèn)證和鑒權(quán)全過(guò)程
這篇文章主要介紹了Springboot整合SpringSecurity實(shí)現(xiàn)登錄認(rèn)證和鑒權(quán)全過(guò)程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12java通過(guò)URLClassLoader類加載器加載外部jar代碼示例
ClassLoader翻譯過(guò)來(lái)就是類加載器,普通的java開(kāi)發(fā)者其實(shí)用到的不多,但對(duì)于某些框架開(kāi)發(fā)者來(lái)說(shuō)卻非常常見(jiàn),下面這篇文章主要給大家介紹了關(guān)于java通過(guò)URLClassLoader類加載器加載外部jar的相關(guān)資料,需要的朋友可以參考下2024-01-01SpringBoot中AOP的動(dòng)態(tài)匹配和靜態(tài)匹配詳解
這篇文章主要介紹了SpringBoot中AOP的動(dòng)態(tài)匹配和靜態(tài)匹配詳解,在創(chuàng)建代理的時(shí)候?qū)δ繕?biāo)類的每個(gè)連接點(diǎn)使用靜態(tài)切點(diǎn)檢查,如果僅通過(guò)靜態(tài)切點(diǎn)檢查就可以知道連接點(diǎn)是不匹配的,則在運(yùn)行時(shí)就不再進(jìn)行動(dòng)態(tài)檢查了,需要的朋友可以參考下2023-09-09詳解Java8的forEach(...)如何提供index值
這篇文章主要介紹了詳解Java8的forEach(...)如何提供index值,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03Java Socket一對(duì)多通信實(shí)現(xiàn)之并發(fā)處理方式
這篇文章主要介紹了Java Socket一對(duì)多通信實(shí)現(xiàn)之并發(fā)處理方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08Java并發(fā)編程:CountDownLatch與CyclicBarrier和Semaphore的實(shí)例詳解
這篇文章主要介紹了Java并發(fā)編程:CountDownLatch與CyclicBarrier和Semaphore的實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-09-09