HashMap 容量為什麼總是為 2 的次幂？

HashMap是根據key的hash值決策key放入到哪個桶（bucket）中，通過 tab=[(n - 1) & hash] 公式計算得出，其中tab是一個哈希表。

1. 為什麼要保證 capacity 是2的次幂呢？

1）在get方法實作中，實際上是比對連結清單中的 Node[] tab 中的資料。

(n - 1) & hash實際上是計算出 key 在 tab 中索引位置，當key的hash沒有沖突時，key在HashMap存儲的位置就是比對的node中的第一個節點。如果hash有沖突，就會在node裡面節點中查詢，直至比對到相等的key。

2）因為 n 永遠是2的次幂，是以 n-1 通過 二進制表示，永遠都是尾端以連續1的形式表示（00001111，00000011）

當(n - 1) 和 hash 做與運算時，會保留hash中 後 x 位的 1

例如 00001111 & 10000011 = 00000011

這樣做有2個好處

&運算速度快，至少比%取模運算塊

能保證 索引值 肯定在 capacity 中，不會超出數組長度

(n - 1) & hash，當n為2次幂時，會滿足一個公式：(n - 1) & hash = hash % n

2.為什麼要通過 (n - 1) & hash 決定桶的索引呢？

1）key具體應該在哪個桶中，肯定要和key挂鈎的，HashMap顧名思義就是通過hash算法高效的把存儲的資料查詢出來，是以HashMap的所有get 和 set 的操作都和hash相關。

2）既然是通過hash的方式，那麼不可避免的會出現hash沖突的場景。hash沖突就是指 2個key 通過hash算法得出的哈希值是相等的。hash沖突是不可避免的，是以如何盡量避免hash沖突，或者在hash沖突時如何高效定位到資料的真實存儲位置就是HashMap中最核心的部分。

3）首先要提的一點是 HashMap中 capacity 可以在構造函數中指定，如果不指定預設是2 的 (n = 4) 次方，即16。

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}      

4）HashMap中的hash也做了比較特别的處理，(h = key.hashCode()) ^ (h >>> 16)。

先獲得key的hashCode的值 h，然後 h 和 h右移16位 做異或運算。

實質上是把一個數的低16位與他的高16位做異或運算，因為在前面 (n - 1) & hash 的計算中，hash變量隻有末x位會參與到運算。使高16位也參與到hash的運算能減少沖突。

例如1000000的二進制是

00000000 00001111 01000010 01000000

右移16位：

00000000 00000000 00000000 00001111

異或

00000000 00001111 01000010 01001111

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}      

3.capacity 永遠都是 2 次幂，那麼如果我們指定 initialCapacity 不為 2次幂時呢，是不是就破壞了這個規則？

答案是：不會的，

HashMap

的tableSizeFor方法做了處理，能保證n永遠都是2次幂。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    //cap-1後，n的二進制最右一位肯定和cap的最右一位不同，即一個為0，一個為1，例如cap=17（00010001），n=cap-1=16（00010000）
    int n = cap - 1;
    //n = (00010000 | 00001000) = 00011000
    n |= n >>> 1;
    //n = (00011000 | 00000110) = 00011110
    n |= n >>> 2;
    //n = (00011110 | 00000001) = 00011111
    n |= n >>> 4;
    //n = (00011111 | 00000000) = 00011111
    n |= n >>> 8;
    //n = (00011111 | 00000000) = 00011111
    n |= n >>> 16;
    //n = 00011111 = 31
    //n = 31 + 1 = 32, 即最終的cap = 32 = 2 的 (n=5)次方
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}