為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把數(shù)據(jù)分配均勻，每個(gè)鏈表/紅黑樹(shù)長(zhǎng)度大致相同。這個(gè)實(shí)現(xiàn)就是把數(shù)據(jù)存到哪個(gè)鏈表/紅黑樹(shù)中的算法。
這個(gè)算法應(yīng)該如何設(shè)計(jì)呢?
我們首先可能會(huì)想到采用%取余的操作來(lái)實(shí)現(xiàn)。但是，重點(diǎn)來(lái)了：“取余(%)操作中如果除數(shù)是2的冪次則等價(jià)于與其除數(shù)減一的與(&)操作(也就是說(shuō) hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二進(jìn)制位操作 &，相對(duì)于%能夠提高運(yùn)算效率，這就解釋了 HashMap 的長(zhǎng)度為什么是2的冪次方。
那為什么是兩次擾動(dòng)呢?
這樣就是加大哈希值低位的隨機(jī)性，使得分布更均勻，從而提高對(duì)應(yīng)數(shù)組存儲(chǔ)下標(biāo)位置的隨機(jī)性&均勻性，最終減少Hash沖突，兩次就夠了，已經(jīng)達(dá)到了高位低位同時(shí)參與運(yùn)算的目的;
京公網(wǎng)安備 11010802030320號(hào)