HashMap的數(shù)據(jù)是存儲在鏈表數(shù)組里面的。在對HashMap進行插入/刪除等操作時疗隶，都需要根據(jù)K-V對的鍵值定位到他應該保存在數(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的角標應該是根據(jù)h%length來計算埋市，為啥這里用的是h & (length-1)。原來作者是考慮到
位運算(&)效率要比代替取模運算(%)高很多道宅，主要原因是位運算直接對內(nèi)存數(shù)據(jù)進行操作，不需要轉(zhuǎn)成十進制樱报，因此處理速度非撑⒌保快。
那么，為什么可以使用位運算(&)來實現(xiàn)取模運算(%)呢嚷量？這實現(xiàn)的原理如下：
X % 2^n = X & (2^n - 1)
2n表示2的n次方逆趣，也就是說，一個數(shù)對2n取模 == 一個數(shù)和(2^n - 1)做按位與運算 汗贫。
假設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倍。
