- 云服務(wù)器優(yōu)惠
- 阿里云優(yōu)惠券
- 騰訊云優(yōu)惠券
- 京東云優(yōu)惠券
- 站點(diǎn)信息
- 問(wèn)題反饋
- 郵箱：[email protected]
關(guān)注微信
?2016-2026 Matools All rights reserved,
粵ICP備17059708號(hào)
HashMap中哈希算法的關(guān)鍵代碼
//重新計(jì)算哈希值 static final int hash(Object key) { int h; return (key == null) ? 0
: (h = key.hashCode()) ^ (h >>> 16);//key如果是null 新hashcode是0 否則 計(jì)算新的hashcode }
//計(jì)算數(shù)組槽位 (n - 1) & hash
HashMap的細(xì)節(jié)我們不談，只看這個(gè)哈希算法的細(xì)節(jié)(h = key.hashCode()) ^ (h >>> 16)
^按位異或運(yùn)算，只要位不同結(jié)果為1，不然結(jié)果為0；
>>> 無(wú)符號(hào)右移：右邊補(bǔ)0
為什么要無(wú)符號(hào)右移16位后做異或運(yùn)算
根據(jù)上面的說(shuō)明我們做一個(gè)簡(jiǎn)單演練
將h無(wú)符號(hào)右移16為相當(dāng)于將高區(qū)16位移動(dòng)到了低區(qū)的16位，再與原h(huán)ashcode做異或運(yùn)算，可以將高低位二進(jìn)制特征混合起來(lái)
從上文可知高區(qū)的16位與原h(huán)ashcode相比沒(méi)有發(fā)生變化，低區(qū)的16位發(fā)生了變化
我們可知通過(guò)上面(h = key.hashCode()) ^ (h >>> 16)進(jìn)行運(yùn)算可以把高區(qū)與低區(qū)的二進(jìn)制特征混合到低區(qū)，那么為什么要這么做呢？
我們都知道重新計(jì)算出的新哈希值在后面將會(huì)參與hashmap中數(shù)組槽位的計(jì)算，計(jì)算公式：(n - 1) & hash，假如這時(shí)數(shù)組槽位有16個(gè)，則槽位計(jì)算如下：
仔細(xì)觀察上文不難發(fā)現(xiàn)，高區(qū)的16位很有可能會(huì)被數(shù)組槽位數(shù)的二進(jìn)制碼鎖屏蔽，如果我們不做剛才移位異或運(yùn)算，那么在計(jì)算槽位時(shí)將丟失高區(qū)特征
也許你可能會(huì)說(shuō)，即使丟失了高區(qū)特征不同hashcode也可以計(jì)算出不同的槽位來(lái)，但是細(xì)想當(dāng)兩個(gè)哈希碼很接近時(shí)，那么這高區(qū)的一點(diǎn)點(diǎn)差異就可能導(dǎo)致一次哈希碰撞，所以這也是將性能做到極致的一種體現(xiàn)
使用異或運(yùn)算的原因
?異或運(yùn)算能更好的保留各部分的特征，如果采用&運(yùn)算計(jì)算出來(lái)的值會(huì)向1靠攏，采用|運(yùn)算計(jì)算出來(lái)的值會(huì)向0靠攏
為什么槽位數(shù)必須使用2^n
1、為了讓哈希后的結(jié)果更加均勻
這個(gè)原因我們繼續(xù)用上面的例子來(lái)說(shuō)明
假如槽位數(shù)不是16，而是17，則槽位計(jì)算公式變成：(17 - 1) & hash
從上文可以看出，計(jì)算結(jié)果將會(huì)大大趨同，hashcode參加&運(yùn)算后被更多位的0屏蔽，計(jì)算結(jié)果只剩下兩種0和16，這對(duì)于hashmap來(lái)說(shuō)是一種災(zāi)難
2、可以通過(guò)位運(yùn)算e.hash & (newCap - 1)來(lái)計(jì)算，a % (2^n) 等價(jià)于 a & (2^n - 1)?
，位運(yùn)算的運(yùn)算效率高于算術(shù)運(yùn)算，原因是算術(shù)運(yùn)算還是會(huì)被轉(zhuǎn)化為位運(yùn)算
?
?
?
說(shuō)了這么多點(diǎn)，上面提到的所有問(wèn)題，最終目的還是為了讓哈希后的結(jié)果更均勻的分部，減少哈希碰撞，提升hashmap的運(yùn)行效率
?
熱門(mén)工具 換一換