為什么HashMap的長(zhǎng)度始終是2的N次方？

文章目錄：
①、拋出問(wèn)題
②、給出結(jié)論
③、論證問(wèn)題
④、& 和 % 運(yùn)算效率對(duì)比

相信對(duì) JDK 源碼感興趣的小伙伴，HashMap 的源碼你一定不會(huì)錯(cuò)過(guò)，里面有很多精妙的設(shè)計(jì)，也是面試的常用考點(diǎn)，本文我會(huì)點(diǎn)出一些。

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

1、拋出問(wèn)題

1.1 為什么 HashMap 的默認(rèn)初始容量長(zhǎng)度要是 1<<4 ?

為啥源碼這里不直接寫(xiě) 16 ？要寫(xiě)成 1<<4？知道的可以在評(píng)論區(qū)留言。

1.2 為什么 HashMap 初始化即使給定長(zhǎng)度，依然要重新計(jì)算一個(gè) 2 的數(shù)?

PS: 這個(gè)方法是 HashMap 用于計(jì)算初始化容量，結(jié)果是返回大于給定值的第一個(gè)2，比如 :

new HashMap(10)，其實(shí)際長(zhǎng)度是 16；

new HashMap(18)，實(shí)際長(zhǎng)度是32；

new HashMap(40)，實(shí)際長(zhǎng)度64。

涉及到兩個(gè)運(yùn)算符：

①、| : 或運(yùn)算符。

②、>>> : 無(wú)符號(hào)右移運(yùn)算符，移動(dòng)時(shí)忽略符號(hào)位，空位以 0 補(bǔ)齊。

這個(gè)算法也比較有意思，原理就是每一次運(yùn)算都是將現(xiàn)有的 0 的位轉(zhuǎn)換成 1，直到所有的位都為 1 為止；最后返回結(jié)果的時(shí)候，如果比最大值小，則返回結(jié)果+1，正好將所有的 1 轉(zhuǎn)換成 0，且進(jìn)了一位，剛好是 2 。

1.3 為什么 HashMap 每次擴(kuò)容是擴(kuò)大一倍，也就是 2 ?

當(dāng)存入HashMap的元素占比超過(guò)整個(gè)容量的75%（默認(rèn)加載因子 DEFAULT_LOAD_FACTOR = 0.75）時(shí)，進(jìn)行擴(kuò)容，而且在不超過(guò)int類型的范圍時(shí)，左移1位(長(zhǎng)度擴(kuò)為原來(lái)2倍)

1.4 為什么 HashMap 的計(jì)算索引算法是 &，而不是 % ？

新添加一個(gè)元素時(shí)，會(huì)計(jì)算這個(gè)元素在 HashMap 中的位置，算法分為兩步：

①、得到 hash 值

PS：其實(shí)這里的算法可以研究下，hashcode() 是一個(gè) native 修飾的方法，返回一個(gè) int 類型的值（根據(jù)內(nèi)存地址換算出來(lái)的一個(gè)值），然后將這個(gè)值無(wú)符號(hào)右移16位，高位補(bǔ)0，并與前面第一步獲得的hash碼進(jìn)行按位異或^ 運(yùn)算。

這樣做有什么用呢？這其實(shí)是一個(gè)擾動(dòng)函數(shù)，為了降低哈希碼的沖突。右位移16位，正好是32bit的一半，高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來(lái)加大低位的隨機(jī)性。

這樣混合后的低位摻雜了高位的部分特征，高位的信息也被變相保留下來(lái)。

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

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

這里的 n 是 HashMap 的長(zhǎng)度，hash 是上一步得到的值。

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

1.5 問(wèn)題總結(jié)

大家發(fā)現(xiàn)沒(méi)，通過(guò)我上面提出的四個(gè)問(wèn)題，前三個(gè)問(wèn)題 HashMap 的長(zhǎng)度始終保持在 2 。

①、默認(rèn)初始長(zhǎng)度是 2;

②、即使給定初始長(zhǎng)度，其值依舊是大于給定值的第一個(gè)偶數(shù)；

③、每次擴(kuò)容都是擴(kuò)大一倍，21；

然后第四個(gè)問(wèn)題，計(jì)算 HashMap 的元素索引時(shí)，我們得到了一個(gè) hash 值，居然是對(duì) HashMap 的長(zhǎng)度做 & 運(yùn)算，而不是做 % 運(yùn)算，這到底是是為什么呢？

2、給出結(jié)論

我們先直接給出結(jié)論：

當(dāng) lenth = 2 且X>0 時(shí)，X % length = X & (length - 1)

也就是說(shuō)，長(zhǎng)度為2的n次冪時(shí)，模運(yùn)算 % 可以變換為按位與 & 運(yùn)算。

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

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

上面兩個(gè)例子4和8都是2的n次冪，結(jié)論是成立的，那么當(dāng)長(zhǎng)度不為2的n次冪呢？

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

為什么是這樣？下面我們來(lái)詳細(xì)分析。

3、論證結(jié)論

首先我們要知道如下規(guī)則：

①、"<<" 左移：按二進(jìn)制形式把所有的數(shù)字向左移動(dòng)對(duì)應(yīng)的位數(shù)，高位移出（舍棄），低位的空位補(bǔ)零。左移一位其值相當(dāng)于乘2。

②、">>"右移：按二進(jìn)制形式把所有的數(shù)字向右移動(dòng)對(duì)應(yīng)的位數(shù)。對(duì)于左邊移出的空位，如果是正數(shù)則空位補(bǔ)0，若為負(fù)數(shù)，可能補(bǔ)0或補(bǔ)1，這取決于所用的計(jì)算機(jī)系統(tǒng)。右移一位其值相當(dāng)于除以2。

③、">>>"無(wú)符號(hào)右移：右邊的位被擠掉，對(duì)于左邊移出的空位一概補(bǔ)上0。

根據(jù)二進(jìn)制數(shù)的特點(diǎn)，相信大家很好理解。

現(xiàn)在對(duì)于給定一個(gè)任意的十進(jìn)制數(shù)XXX....XX，我們將其用二進(jìn)制的表示方法分解：

公式1：

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

回到上面的結(jié)論：當(dāng) lenth = 2 且X>0 時(shí)，X % length = X & (length - 1)

以及對(duì)于除法，除以一個(gè)數(shù)能用除法分配律，除以幾個(gè)數(shù)的和或差不能用除法分配律：

公式2：

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

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

通過(guò) 公式1以及 公式2，我們可以得出當(dāng)任意一個(gè)十進(jìn)制除以一個(gè)**2**的數(shù)時(shí)，我們可以將這個(gè)十進(jìn)制轉(zhuǎn)換成公式1的表示形式：

如果我們想求上面公式的余數(shù)，相信大家一眼就能看出來(lái)：

①、當(dāng) 0<= k <= n 時(shí)，余數(shù)為 X2+X2+......+X2+X2  ,也就是說(shuō) 比 k 大的 n次冪，我們都舍掉了（大的都能整除 2），比k小的我們都留下來(lái)了(小的不能整除2)。那么留來(lái)下來(lái)即為余數(shù)。

②、當(dāng) k > n 時(shí)，余數(shù)即為整個(gè)十進(jìn)制數(shù)。

看到這里，我們離證明結(jié)論已經(jīng)很近了。

再回到上面說(shuō)的二進(jìn)制的移位操作，向右移 n 位，表示除以 2n  次方，由此我們得到一個(gè)很重要的結(jié)論：

一個(gè)十進(jìn)制數(shù)對(duì)一個(gè)2 的數(shù)取余，我們可以將這個(gè)十進(jìn)制轉(zhuǎn)換為二進(jìn)制數(shù)，將這個(gè)二進(jìn)制數(shù)右移n位，移掉的這 n 位數(shù)即是余數(shù)。

知道怎么算余數(shù)了，那么我們?cè)趺慈カ@取這移掉的 n 為數(shù)呢？

我們?cè)倏?,2,2....2 用二進(jìn)制表示如下：

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

我們把上面的數(shù)字減一：

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

根據(jù)與運(yùn)算符&的規(guī)律，當(dāng)位上都是 1 時(shí)，結(jié)果才是 1，否則為 0。所以任意一個(gè)二進(jìn)制數(shù)對(duì) 2 取余時(shí)，我們可以將這個(gè)二進(jìn)制數(shù)與（2-1）進(jìn)行按位與運(yùn)算，保留的即是余數(shù)。

這就完美的證明了前面給出的結(jié)論：

當(dāng) lenth = 2 且X>0 時(shí)，X % length = X & (length - 1)

4、& 和 % 運(yùn)算效率

為什么要將 % 運(yùn)算改為 & 運(yùn)算，很顯然是因?yàn)?& 運(yùn)算在計(jì)算機(jī)底層只需要一個(gè)簡(jiǎn)單的 與邏輯門(mén)就可以實(shí)現(xiàn)，但是實(shí)現(xiàn)除法確實(shí)一個(gè)很復(fù)雜的電路，大家感興趣的可以下去研究下。

我這里在代碼層面，給大家做個(gè)測(cè)試，直觀的比較下速度：

 public class HashMapTest {
    public static void main(String[] args) {
        long num = 100000*100000;
        long startTimeMillis1 = System.currentTimeMillis();
        long result = 1;
        for (long i = 1; i < num; i++) {
            result %= i;
        }
        long endTimeMillis1 = System.currentTimeMillis();
        System.out.println("%: "+ (endTimeMillis1 - startTimeMillis1));

        long startTimeMillis2 = System.currentTimeMillis();
        result = 1;
        for (long i = 1; i < num; i++) {
            result &= i;
        }
        long endTimeMillis2 = System.currentTimeMillis();
        System.out.println("&: "+ (endTimeMillis2 - startTimeMillis2));
    }
}

打印結(jié)果如下：

差距還是很明顯的，而且這個(gè)結(jié)果還會(huì)隨著測(cè)試次數(shù)的增多而越拉越開(kāi)。

關(guān)于我