背景
文章不聊HashMap的源碼實現(xiàn)，主要聊一聊幾個細節(jié)的問題。
HashMap處理沖突的方式是通過鏈表法來解決沖突，其核心在于散列函數(shù)的均勻隨機。因此我們就來看一看HashMap是怎樣計算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計算index的方式。那么這里展開兩個問題：
- hash()之后的值，為什么要
& (capacity - 1) - hash()這個函數(shù)是為了什么？
問題1：
首先，我們需要得到一個小于length的index。一個比較簡單的方式就是對當前的length進行取余，也就是hash(key) % (capacity)
這里有一個優(yōu)化，那就是把%換成&。其原理就是：a%(2^n) == a&(2^n-1)。
這也是為什么length需要是2的倍數(shù)的原因
因此也就變成了hash(key) & (capacity - 1)
補充：為什么a%(2^n) == a&(2^n-1)
通過一個例子來看一下：18 % 16 = 2
- 大于16的1肯定是16的整數(shù)倍，可以直接約掉
- 剩下&出來的值就是余數(shù)
問題2：
hash()函數(shù)一共做了兩件事：
- 將hashCode右移16位
- 將第一步的結(jié)果與hashCode進行一個異或
為什么做這兩件事，咱們來展開一下。先看一種case，假設(shè)我們有一個對象，hashCode為下圖：
這個hashCode有個特點：有幾位都是0
如果我們直接用這個HashCode與(capacity - 1)進行與(&)操作，如果與的HashCode低位都是0，那么無論(capacity - 1)是什么，得到的值永遠是0。
因此會出現(xiàn)：當滿足這種case，無論怎么計算index都是0。一個穩(wěn)定復現(xiàn)的沖突。
所以我們需要考慮如何解決這種情況。這里我們套用HashMap的方案“也就是右移，然后異或。
這里就會發(fā)現(xiàn)得到的index的確不是0了：
其原理也比較好理解：
先右移16位，那么原HashCode的低16位就變成了高的16位，高16位全部變成0。
將右移后的結(jié)果與原HashCode進行異或，得到的結(jié)果：高16位還是原樣，低16位進行了混合。因此之前為0的低位，變得不一定為0了。
套用HashMap的方案，我們的確解決了低位為0的情況
那么問題來了，如果高位是0怎么辦？
怎么辦？不需要辦呀...因為我們通過&求index，先從低位計算。 如果我們index需要計算高位，那就意味著我們的HashMap已經(jīng)非常非常巨大了...
