HashMap為什麼是2的冪次方

一、HashMap為什麼是2的冪次方

HashMap 是 Java 集合體系中的一個底層實現工具類，採用散列表實現，因此其底層採用數組存儲。數組是一種隨機訪問結構，可以通過固定偏移量和下標的計算方式直接跳轉到指定位置。但是，散列表可以使元素在數組中的位置任意，所以必須通過散列函數計算元素所在位置，如果不重寫散列函數，Java 使用的是 hashCode() 方法的返回值，而 hashCode() 返回一個整數，所以 HashMap 底層的數組必須是整數下標。

散列表按照鍵值對存儲，也就是說要存儲兩個值：鍵和值，這裡我們稱之為 entry。這些 entry 存儲在一個 Entry 數組中，在 Java 8 中，該數組被 Node 數組取代，每個 Node 保存一個鍵值對。數組的長度是固定的，而且在初始化時必須得到指定，但是作為編程人員，在寫程序時很難事先預知將要存儲到 Map 中的鍵值對的數量，因此，Java 在該初始化確定數組長度後，如果達到一定條件時，自動對該數組進行擴展，進而改變數組長度。

在 HashMap 中，數組長度是2的冪次方，這是因為計算機在計算 hash 值時就需要用到 “& size – 1″，而計算機在做除法時除法的成本遠高於求餘數的成本，同時採用位運算的效率通常要比模運算的效率高，因此使用2的冪次方作為數組長度，是因為形式上最能體現出求餘數和位運算的最佳實踐。

    /**
     * 初始化容量（必須是 2 的冪且小於 1 << 30）
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

二、HashMap擴容為什麼是2倍

擴容的本質是數組擴容，數組的長度必須是2的冪次方，如果按1進行擴容數組長度的畫，每次擴容都要重新計算每個元素的位置，而2倍擴容操作是一次性完成，是為了加速計算，同時也為了防止出現哈希衝突，保證散列的均勻性。

    /**
     * 加載因子，當 HashMap 所容納的元素數量達到 totalSize * loadFactor 時，就需擴容
     */
    final float loadFactor;

    /**
     * 擴容操作，擴容後的大小必須是2的冪次方
     */
    final void resize() {
        //...
        newCap = oldCap << 1;
        //...
    }

三、HashMap的長度為什麼是2的冪次方

HashMap 的長度並不是隨意設置，而是必須是2的冪次方，這樣一來，可以使Entry放入數組時，並且計算出它的位置 index。使用 n & (length-1) 就相當於對 length 取模，但是比直接對 length 取模效率更高，因為&運算比%運算效率更高。

在 JDK1.7 中，HashMap 有一個默認的負載因子 loadFactor，如果散列表中當前元素個數超過了數組長度與負載因子的積，就需要進行擴容，否則，當hash表中的元素個數過多，會出現大量的hash衝突，會導致HashMap變慢。JDK1.8 對擴容機製做出了調整，基本上漸進時間複雜度從 O(n) 降低到了 O(1)。

    /**
     * 初始化容量（必須是 2 的冪且小於 1 << 30）
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    /**
     * 最大容量（必須是 2 的冪且小於 1 << 30）
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 鏈表的最小長度
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * 鏈表長度過長時，轉換成紅黑樹
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 當轉化紅黑樹後，最小的hash表容量大小
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 加載因子，當 HashMap 所容納的元素數量達到 totalSize * loadFactor 時，就需擴容
     */
    final float loadFactor;

四、HashMap為什麼鏈表選取3~5個

為了解決哈希衝突，Java 在 JDK1.8 中通過弱化了 Node 結構中的 next 指針，在鏈表長度等於8時才考慮紅黑樹化後的轉換。鏈錶轉換成紅黑樹，只針對 HashMap，ConcurrentHashMap 在 JDK1.8中並沒有這種轉化邏輯。由於紅黑樹的高度不高於 log(n)，相當於在鏈表長度大於8時，查找效率更高一些。

    /**
     * 當轉化紅黑樹後，最小的hash表容量大小
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 鏈表長度過長時，轉換成紅黑樹
     */
    static final int TREEIFY_THRESHOLD = 8;

通過以上分析，可以看出 HashMap 選擇 2 的冪次方作為數組長度的原因，HashMap 長度為什麼是2的冪次方，擴容為什麼是2倍，以及鏈表選取3~5個的相關原因。這些策略使得 HashMap 在底層實現中保證了時間和空間的效率。