HashMap的數(shù)據(jù)是存儲在鏈表數(shù)組里面的。在對HashMap進行插入/刪除等操作時，都需要根據(jù)K-V對的鍵值定位到他應(yīng)該保存在數(shù)組的哪個下標中。
而這個通過鍵值求取下標的操作就叫做哈希。
HashMap的數(shù)組是有長度的，Java中規(guī)定這個長度只能是2的倍數(shù)，初始值為16。
求哈希簡單的做法是先求取出鍵值的hashcode，然后在將hashcode得到的int值對數(shù)組長度進行取模。為了考慮性能，Java總采用按位與操作實現(xiàn)取模操作。

先看代碼:

static int indexFor(int h, int length) {
   return h & (length-1);
}

按理說定位HashMap的角標應(yīng)該是根據(jù)h%length來計算，為啥這里用的是h & (length-1)。原來作者是考慮到
位運算(&)效率要比代替取模運算(%)高很多，主要原因是位運算直接對內(nèi)存數(shù)據(jù)進行操作，不需要轉(zhuǎn)成十進制，因此處理速度非?？?。

那么，為什么可以使用位運算(&)來實現(xiàn)取模運算(%)呢？這實現(xiàn)的原理如下：

X % 2^n = X & (2^n - 1)

2^{n表示2的n次方，也就是說，一個數(shù)對2}n取模 == 一個數(shù)和(2^n - 1)做按位與運算 。

假設(shè)n為3，則2^3 = 8，表示成2進制就是1000。2^3 -1 = 7 ，即0111。

此時X & (2^3 - 1) 就相當于取X的2進制的最后三位數(shù)。

從2進制角度來看，X / 8相當于 X >> 3，即把X右移3位，此時得到了X / 8的商，而被移掉的部分(后三位)，則是X % 8，也就是余數(shù)。

上面的解釋不知道你有沒有看懂，沒看懂的話其實也沒關(guān)系，你只需要記住這個技巧就可以了?；蛘吣憧梢哉?guī)讉€例子試一下。

6 % 8 = 6 ，6 & 7 = 6

10 % 8 = 2 ，10 & 7 = 2

image

所以，return h & (length-1);只要保證length的長度是2^n的話，就可以實現(xiàn)取模運算了。而HashMap中的length也確實是2的倍數(shù)，初始值是16，之后每次擴充為原來的2倍。