HashMap的哈希函數為何用(n – 1) & hash
前言
在上一篇 Java 中HashMap詳解(含HashTable, ConcurrentHashMap) 中提到在map.put(key, value)的過程中，計算完key的hash值， 是通過hash & (n-1)來得出該元素在Node數組中的下標的，其中n是Node數組的長度。 其實我們更容易想到的是hash % n，這樣剛好會得到0~n-1之間的數字，可以用作數組下標。那麼為何此處是用的位運算呢？
結論
先說結論。 這裡有一個前提，那就是HashMap中Node數組的長度始終保持是2^n， 比如默認的16， 如果創建HashMap的時候指定了初始的capacity,而這個capacity可能不是2^n, 會在內部轉化一下，得到一個大於這個capacity的最小的2^n的數字來初始化數組。 每次擴容的時候也是進行2倍的擴容。
在這個前提下，hash & (n-1) 與 hash % n 是等價的。 而位運算更快一些。
論證
先來看一組數字：
| n （格式為2^m=十進位數字=二進位數字） | n-1 （格式為2^m – 1=十進位數字=二進位數字） |
| 2^2 = 4 = 100 | 2^2 – 1 = 3 = 011 |
| 2^3 = 8 = 1000 | 2^3 – 1 = 7 = 0111 |
| 2^4 = 16 = 10000 | 2^4 – 1 = 15 = 01111 |
| 2^5 = 32 = 100000 | 2^5 -1 = 31 = 011111 |
此處我們可以看到規律，2^m的二進位就是1的後面加上m個0, 而2^m -1的二進位就是0的後面加上m個1.
下面我們來看 hash % n（求餘數）的運算：
首先看hash/n，由於n=2^m， 我們先看hash/2的情況，這樣一來就簡單了，因為我們都知道，二進位的情況下，一個數字除以2其實就是右移一位，在左邊加一個0，右邊移出去一位。如果覺得不好理解，就類比十進位的數字除以10的情況，是一樣的。舉一反三一下，hash/4的情況自然就是右移2位，由於n=2^m， 其實hash/n的操作就是右移m位。
右移之後我們得到的是hash/n的整除，那麼餘數呢？其實就是我們移出去的數字。
舉個例子，假設hash = 18, n=4,我們知道18/4=4 , 18%4 =2,看看按照我們上面的運算是否會得到相同的結果：
18=10010， 4=2^2
| 1 | 0 | 0 | 1 | 0 | 右移2位 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| hash=18 | 數組長度n=4=2^2 | 18/4得到的整除 | 餘數18%4 | |||||||||
通過運算可以很容易的驗證18/4 = 00100 = 4 ， 而18%4 = 10 = 2， 是正確的。
現在假設Node數組進行了擴容n=8，再來看一下：
| 1 | 0 | 0 | 1 | 0 | 右移3位 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| hash=18 | 數組長度n=8=2^3 | 18/4得到的整除 | 餘數18%8 | ||||||||||
同樣經過運算18 / 8 = 10 = 2, 18 % 8 = 10 = 2， 是正確的。
現在我們可以看到規律， hash % (2^m)的結果， 其實是就是hash這個數字二進位表達的最後m位（被移出去的m位）
而前面我們又知道2^m-1其實就是0後面加上m個1. 還用上面的例子，我們看一下18 & (2^3-1)的運算：
| 18= | 1 | 0 | 0 | 1 | 0 |
| 2^3-1= | 0 | 0 | 1 | 1 | 1 |
| 與運算 | 0 | 0 | 0 | 1 | 0 |
我們知道，任何數字與1做與運算，還是得到該數字；任何數字與0做與運算，都得0，那麼hash & (2^m-1) ，高位的都是零,只得到低位的m個數字，與上面計算的hash % (2^m)是一樣的結果。
證明完成。
