HashMap指定初始容量，在不同版本JDK的計算，hashmapjdk

HashMap指定初始容量，在不同版本JDK的計算，hashmapjdk

HashMap的指定初始容量的構造函數：

public HashMap(int initialCapacity, float loadFactor) 

初始容量是根據參數 initialCapacity，求出 大於等於 initialCapacity 的最小的 2的N次方。

容量是2的N次方的原因，可參見 http://www.cnblogs.com/xwdreamer/archive/2012/06/03/2532832.html

1、在JDK低版本中，通過循環移位運算，保證了初始容量為2的N次方

public HashMap(int initialCapacity, float loadFactor) {  
    ......
    
    int capacity = 1;  
    while (capacity < initialCapacity)  
        capacity <<= 1;  
  
    ...... 
}

2、JDK1.8中，對該運算進行了優化

public HashMap(int initialCapacity, float loadFactor) {
    ......
    this.threshold = tableSizeFor(initialCapacity);
}

static final int tableSizeFor(int cap) {
    int n = cap - 1; 
    n |= n >>> 1;    
    n |= n >>> 2;   
    n |= n >>> 4;    
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

2.1 參數不是2的N次方，轉為二進制

1xxxxxxxx (假設9位，x中至少有一個為1)，大於等於該數的最小2的N次方如下，十位

1000000000

第一步 1xxxxxxxx - 1，由於低位至少有一個1，所以減1後，位數不變

第二步 n |= n >>> 1;   1xxxxxxxx 右移一位 變成 1xxxxxxx， 或運算後變為 11xxxxxxx ，不管低位

第三步 n |= n >>> 2;   11xxxxxxx 右移兩位 變成 11xxxxx， 或運算後變為 1111xxxxx ，不管低位 

第四步 n |= n >>> 4;   1111xxxxx 右移四位 變成 1111x， 或運算後變為 11111111x ，不管低位

...... 

最終能保證所有低位上都是1： 1xxxxxxxx -> 111111111 。 +1 變為 1000000000 ，是大於等於該數的最小2的N次方

右移或運算，截止到16，能保證最多32位上都是1，是因為int型的最大值2³¹-1，是31位

2.2 參數是2的N次方

舉例 1000， n-1後變為 111，右移或運算後還是 111， +1後變為 1000

3、比較

低版本中，假設傳參為2的N次方，比較 + 位移，一共計算了 2 * N 次

JDK1.8中，減法 + 位移 + 或運算，大概計算 11 次

也就是說，指定數組容量大於 2的6次方（64）後，JDK1.8的效率更高

4、傳參恰好為2的N次方時的優化

如果一個數n，其不為1，且n-1 & n = 0，那麼n就是一個2的整數次冪

JDK1.8裡加這個判斷可以減少計算

static final int tableSizeFor(int cap) {
    int n = cap - 1;

    if(cap & n == 0) // 傳參為2的N次方
        return (cap >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : cap;

    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}