背景
文章不聊HashMap的源碼實(shí)現(xiàn)母市，主要聊一聊幾個(gè)細(xì)節(jié)的問題。
HashMap處理沖突的方式是通過鏈表法來解決沖突损趋，其核心在于散列函數(shù)的均勻隨機(jī)患久。因此我們就來看一看HashMap是怎樣計(jì)算index的。
源碼很直接：
// capacity等于HashMap的length
int index = hash(key) & (capacity - 1)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
上述代碼就是HashMap計(jì)算index的方式浑槽。那么這里展開兩個(gè)問題：
- hash()之后的值蒋失，為什么要
& (capacity - 1) - hash()這個(gè)函數(shù)是為了什么？
問題1：
首先桐玻，我們需要得到一個(gè)小于length的index高镐。一個(gè)比較簡(jiǎn)單的方式就是對(duì)當(dāng)前的length進(jìn)行取余，也就是hash(key) % (capacity)
這里有一個(gè)優(yōu)化畸冲，那就是把%換成&嫉髓。其原理就是：a%(2^n) == a&(2^n-1)。
這也是為什么length需要是2的倍數(shù)的原因
因此也就變成了hash(key) & (capacity - 1)
補(bǔ)充：為什么a%(2^n) == a&(2^n-1)
通過一個(gè)例子來看一下：18 % 16 = 2
- 大于16的1肯定是16的整數(shù)倍邑闲，可以直接約掉
- 剩下&出來的值就是余數(shù)
問題2：
hash()函數(shù)一共做了兩件事：
- 將hashCode右移16位
- 將第一步的結(jié)果與hashCode進(jìn)行一個(gè)異或
為什么做這兩件事算行，咱們來展開一下。先看一種case苫耸，假設(shè)我們有一個(gè)對(duì)象州邢，hashCode為下圖：
這個(gè)hashCode有個(gè)特點(diǎn)：有幾位都是0
如果我們直接用這個(gè)HashCode與(capacity - 1)進(jìn)行與(&)操作，如果與的HashCode低位都是0褪子，那么無論(capacity - 1)是什么量淌，得到的值永遠(yuǎn)是0。
因此會(huì)出現(xiàn)：當(dāng)滿足這種case嫌褪，無論怎么計(jì)算index都是0呀枢。一個(gè)穩(wěn)定復(fù)現(xiàn)的沖突。
所以我們需要考慮如何解決這種情況笼痛。這里我們套用HashMap的方案“也就是右移裙秋，然后異或。
這里就會(huì)發(fā)現(xiàn)得到的index的確不是0了：
其原理也比較好理解：
先右移16位缨伊，那么原HashCode的低16位就變成了高的16位摘刑，高16位全部變成0。
將右移后的結(jié)果與原HashCode進(jìn)行異或刻坊，得到的結(jié)果：高16位還是原樣枷恕，低16位進(jìn)行了混合。因此之前為0的低位谭胚，變得不一定為0了徐块。
套用HashMap的方案隶校，我們的確解決了低位為0的情況
那么問題來了，如果高位是0怎么辦蛹锰？
怎么辦深胳？不需要辦呀...因?yàn)槲覀兺ㄟ^&求index，先從低位計(jì)算铜犬。 如果我們index需要計(jì)算高位舞终，那就意味著我們的HashMap已經(jīng)非常非常巨大了...
