今天看 Java 源碼中關於 put 函數的取哈希表的索引的這個沒看懂。深究一番終於了解了其中的原因了。記錄一下
今天看 Java 源碼中關於 put 函數的取哈希表的索引的這個沒看懂。深究一番終於了解了其中的原因了。記錄一下
首先需要了解的是 HashMap 中哈希表的長度是 2^n，所以就有如下的公式：
(n - 1) & hash = hash % n
其中 n 為哈希表的長度且為 2 的次幂（注意順序），關於 hash% n 就是普通的我們想要把 hash 值映射到對應的表位置使用的
方法，就是通過 hash 對表長取餘，得出來的一定是比表長小的數，卡，就把 value 放到對應的位置即可。關鍵是
(n - 1) & hash 這個式子，是一個把表長減 1 然後和 hash 做 與 & 運算。首先解釋一下與 & 運算：
與運算是一種二進制運算：
運算規則：0&0=0;0&1=0;1&0=0;1&1=1; 就是說只有都為 1 才能為 1 其他一律為 0。
打個比方：
01011（十進制的 11）
00111（十進制的 7）
-—–
00011（十進制的 3）
OK，在查資料的時候還查到了位運算相關知識：
| 符號 | 描述 | 運算規則 |
|---|---|---|
| & | 與 | 兩個位都為 1 結果才為 1 |
| | | 或 | 兩個位都為 0 結果才為 0 |
| ^ | 異或 | 兩個位相同為 0 相異為 1 |
| ~ | 取反 | 0 變為 1，1 變為 0 |
| << | 左移 | 各個二進位左移若干位，高位丟棄，低位補 0 |
| >> | 右移 | 各個二進位右移若干位，對無符號數，高位補 0，有符號數不一樣 |
左移對於二進制相當於 * 2，右移相當於 / 2 。
拿十進制舉例：10 左移變為 100 就是乘十。右移變為 1 相當於除十；很有意思。Amazing
那麼演過正傳，還是談論取餘的，一個好好地取餘運算咋就能變成與運算呢？
上面提到右移的運算，對於二進制來說，右移以為相當於除 2，但是！重點來了。移出去的數就是除 2 的餘數！神奇不！看一下例子：
101001>>1 = 10100 余 1 對應的就是 41%2 余 1 接著往上推
101001>>2 = 1010 余 01 對應的就是 41%4 余 1 繼續
101001>>3 = 101 余 001 對應的就是 41%8 余 1 go on
101001>>4 = 10 余 1001 對應的就是 41%16 余 9
所以說對於 hash% x ,x 為 2^n 時就等於 hash 的二進制的低 n 位數，
那麼如何取到低 n 數呢？我們發現 2^n 數總是為 n+1 位為 1 後面都為 0 的數，比如
10 就是 2，100 就是 4,1000 就是 8,10000 就是 16，
那麼相應的 2^n-1 就是 n+1 位為 0 其餘為 1 的數，比如：
01 就是 1,011 就是 3,0111 就是 7,01111 就是 15。當這個數與 hash 做 與 & 運算的時候正好保留了 hash 的低 n 位數，就是這麼的 Amazing。
所以 hash%n=hash&(n-1) 當 2 為 2 的次幂時。那么這麼做有什麼好處麼？就是可以大大提高效率，位運算 (&) 效率要比代替取模運算 (%) 高很多，主要原因是位運算直接對內存數據進行操作，不需要轉成十進制，因此處理速度非常快。 對於 HashMap 裡的取哈希表的索引來說是經常要執行的部分。這樣就大大節省了開銷
引用一句大佬的話，形容的真的很透徹：
如果數組長度是 2 的整數次方時，也就是一個偶數，length-1 就是一個奇數，奇數的二進制最後一位是 1，因此不管 hash (key) 是多少，hash (key)&(length-1) 的二進制最後一位可能是 0，也可能是 1，取決於 hash (key)。即如果 hash (key) 是奇數的話，則映射到數組上第奇數個位置上。
如果 length 是一個奇數的話，length-1 就是一個偶數，偶數的二進制最後一位是 0，則不管 hash (key) 是奇數還是偶數，該元素都會被映射到數組上第偶數個位置上，奇數位置上沒有任何元素！
因此，數組長度是一個 2 的整數次方時，哈希碰撞的概率起碼能下降一半，而且所有元素也能均勻地分布在數組上。
注：求餘運算：a % b 就相當與 a - (a /b) * b 的運算
為了弄清這塊兒真的是找了很多資料。不得不說百度真的太辣雞了。公司還不能上谷歌和 StackOverFlow。影響查資料的效率。
但是下面這個文章就是點醒我的 trigger。
位與運算與取余