CSDN知識庫 - 為什麼HashMap的長度始終是2的N次方？－鑽石舞台

作者 | IT可樂

來源 | IT可樂

文章目錄：①、拋出問題②、給出結論③、論證問題④、& 和 % 運算效率對比

相信對 JDK 源碼感興趣的小夥伴，HashMap 的源碼你一定不會錯過，裡面有很多精妙的設計，也是面試的常用考點，本文我會點出一些。

但是本文我不詳細介紹 HashMap 源碼，想了解的可以看我之前的文章，本篇文章主要是給大家解惑這樣幾個問題。

1、拋出問題

1.1 為什麼 HashMap 的默認初始容量長度要是 1<<4 ?

為啥源碼這裡不直接寫 16 ？要寫成 1<<4？知道的可以在評論區留言。

1.2 為什麼 HashMap 初始化即使給定長度，依然要重新計算一個 2 的數?

PS: 這個方法是 HashMap 用於計算初始化容量，結果是返回大於給定值的第一個2，比如 :

new HashMap(10)，其實際長度是 16；

new HashMap(18)，實際長度是32；

new HashMap(40)，實際長度64。

涉及到兩個運算符：

①、| : 或運算符。

②、>>> : 無符號右移運算符，移動時忽略符號位，空位以 0 補齊。

這個算法也比較有意思，原理就是每一次運算都是將現有的 0 的位轉換成 1，直到所有的位都為 1 為止；最後返回結果的時候，如果比最大值小，則返回結果+1，正好將所有的 1 轉換成 0，且進了一位，剛好是 2 。

1.3 為什麼 HashMap 每次擴容是擴大一倍，也就是 2 ?

當存入HashMap的元素占比超過整個容量的75%（默認加載因子 DEFAULT_LOAD_FACTOR = 0.75）時，進行擴容，而且在不超過int類型的範圍時，左移1位(長度擴為原來2倍)

1.4 為什麼 HashMap 的計算索引算法是 &，而不是 % ？

新添加一個元素時，會計算這個元素在 HashMap 中的位置，算法分為兩步：

①、得到 hash 值

PS：其實這裡的算法可以研究下，hashcode() 是一個 native 修飾的方法，返回一個 int 類型的值（根據內存地址換算出來的一個值），然後將這個值無符號右移16位，高位補0，並與前面第一步獲得的hash碼進行按位異或^ 運算。

這樣做有什麼用呢？這其實是一個擾動函數，為了降低哈希碼的衝突。右位移16位，正好是32bit的一半，高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。

這樣混合後的低位摻雜了高位的部分特徵，高位的信息也被變相保留下來。

也就是保證考慮到高低Bit位都參與到Hash的計算中。

②、索引值 i = (n-1) & hash

這裡的 n 是 HashMap 的長度，hash 是上一步得到的值。

注意：這裡是用的按位與 & ，而不是用的取模 %。

1.5 問題總結

大家發現沒，通過我上面提出的四個問題，前三個問題 HashMap 的長度始終保持在 2 。

①、默認初始長度是 2;

②、即使給定初始長度，其值依舊是大於給定值的第一個偶數；

③、每次擴容都是擴大一倍，21；

然後第四個問題，計算 HashMap 的元素索引時，我們得到了一個 hash 值，居然是對 HashMap 的長度做 & 運算，而不是做 % 運算，這到底是是為什麼呢？

2、給出結論

我們先直接給出結論：

當 lenth = 2 且X>0 時，X % length = X & (length - 1)

也就是說，長度為2的n次冪時，模運算 % 可以變換為按位與 & 運算。

比如：9 % 4 = 1，9的二進制是 1001 ,4-1 = 3,3的二進制是 0011。9 & 3 = 1001 & 0011 = 0001 = 1

再比如：12 % 8 = 4,12的二進制是 1100,8-1 = 7,7的二進制是 0111。12 & 7 = 1100 & 0111 = 0100 = 4

上面兩個例子4和8都是2的n次冪，結論是成立的，那麼當長度不為2的n次冪呢？

比如：9 % 5 = 4，9的二進制是 1001，5-1 = 4,4的二進制是0100。9 & 4 = 1001 & 0100 = 0000 = 0。顯然是不成立的。

為什麼是這樣？下面我們來詳細分析。

3、論證結論

首先我們要知道如下規則：

①、"<<" 左移：按二進制形式把所有的數字向左移動對應的位數，高位移出（捨棄），低位的空位補零。左移一位其值相當於乘2。

②、">>"右移：按二進制形式把所有的數字向右移動對應的位數。對於左邊移出的空位，如果是正數則空位補0，若為負數，可能補0或補1，這取決於所用的計算機系統。右移一位其值相當於除以2。

③、">>>"無符號右移：右邊的位被擠掉，對於左邊移出的空位一概補上0。

根據二進制數的特點，相信大家很好理解。

現在對於給定一個任意的十進制數XXX....XX，我們將其用二進制的表示方法分解：

公式1：

XXX....XX = X*2+X*2+......+X*2+X*2

回到上面的結論：當 lenth = 2 且X>0 時，X % length = X & (length - 1)

以及對於除法，除以一個數能用除法分配律，除以幾個數的和或差不能用除法分配律：

公式2：

成立：（a+b）÷c=a÷c+b÷c

不成立：a÷（b+c）≠a÷c+a÷c

通過公式1以及公式2，我們可以得出當任意一個十進制除以一個**2**的數時，我們可以將這個十進制轉換成公式1的表示形式：

如果我們想求上面公式的餘數，相信大家一眼就能看出來：

①、當 0<= k <= n 時，餘數為 X2+X2+......+X2+X2 ,也就是說比 k 大的 n次冪，我們都舍掉了（大的都能整除 2），比k小的我們都留下來了(小的不能整除2)。那麼留來下來即為餘數。

②、當 k > n 時，餘數即為整個十進制數。

看到這裡，我們離證明結論已經很近了。

再回到上面說的二進制的移位操作，向右移 n 位，表示除以 2n次方，由此我們得到一個很重要的結論：

一個十進制數對一個2 的數取余，我們可以將這個十進制轉換為二進制數，將這個二進制數右移n位，移掉的這 n 位數即是餘數。

知道怎麼算餘數了，那麼我們怎麼去獲取這移掉的 n 為數呢？

我們再看2,2,2....2 用二進制表示如下：

0001，0010，0100，1000，10000......

我們把上面的數字減一：

0000，0001，0011，0111，01111......

根據與運算符&的規律，當位上都是 1 時，結果才是 1，否則為 0。所以任意一個二進制數對 2 取余時，我們可以將這個二進制數與（2-1）進行按位與運算，保留的即是餘數。

這就完美的證明了前面給出的結論：

當 lenth = 2 且X>0 時，X % length = X & (length - 1)

4、&和 % 運算效率

為什麼要將 % 運算改為 & 運算，很顯然是因為 & 運算在計算機底層只需要一個簡單的與邏輯門就可以實現，但是實現除法確實一個很複雜的電路，大家感興趣的可以下去研究下。

我這裡在代碼層面，給大家做個測試，直觀的比較下速度：

publicclassHashMapTest{publicstaticvoidmain(String[]args){longnum=100000*100000;longstartTimeMillis1=System.currentTimeMillis();longresult=1;for(longi=1;i<num;i++){result%=i;}longendTimeMillis1=System.currentTimeMillis();System.out.println("%:"+(endTimeMillis1-startTimeMillis1));longstartTimeMillis2=System.currentTimeMillis();result=1;for(longi=1;i<num;i++){result&=i;}longendTimeMillis2=System.currentTimeMillis();System.out.println("&:"+(endTimeMillis2-startTimeMillis2));}}

打印結果如下：