【優雅的避坑】new HashMap(list.size())指定size就能完全避免擴容帶來的額外開銷了嗎？

設定HashMap的初始容量

設定HashMap的初始容量只是優化的開始。

HashMap在Java的使用中佔據著很重要的地位，平時使用的時候，相信很多Java程式設計師都知道在定義HashMap的時候，給它設定一個初始容量，以便減少hashMap擴容（resize）帶來的額外開銷，比如像我同（zi）事（ji）的這段程式碼：

@Test
public void longLongAGo() {
    int count = 1000000;

    System.out.println("---------------- 不設定hashMap初始容量 ------------");
    long start = System.currentTimeMillis();
    HashMap<Integer, Object> map = new HashMap<>();
    for (int i = 0; i < count; i++) {
        map.put(i, UUID.randomUUID());
    }
    long end = System.currentTimeMillis();
    System.out.println("新增1000000個元素耗時：" + (end - start));

    System.out.println("---------------- 設定hashMap初始容量 -------------------");
    long start1 = System.currentTimeMillis();
    HashMap<Integer, Object> map1 = new HashMap<>(count);
    for (int i = 0; i < count; i++) {
        map1.put(i, UUID.randomUUID());
    }
    long end1 = System.currentTimeMillis();
    System.out.println("新增1000000個元素耗時：" + (end1 - start1));
}
複製程式碼

我同事說他在初始化的時候設定了map的容量，不會在新增元素的過程中進行自動擴容了，大大提高了效能，從結果看確實如此！

所以，集合初始化時，指定集合初始值大小能提升效能。

然鵝，我抱著懷疑的態度，對比了設定初始容量和不設定初始容量時，hashMap的擴容次數，當設定初始容量為1000000時，容器並不是想象中的不擴容了，而是也擴容了1次：

@SneakyThrows
@Test
public void testing() {
    int count = 1000000;

    System.out.println("---------------- 初始化hashMap容量為1000000 ------------");
    int resizeCount = 0;
    HashMap<Integer, Object> map = new HashMap<>(count);
    Method capacityMethod = map.getClass().getDeclaredMethod("capacity");
    capacityMethod.setAccessible(true);
    int capacity = (int) capacityMethod.invoke(map);
    System.out.println("初始容量：" + capacity);
    for (int i = 0; i < count; i++) {
        map.put(i, UUID.randomUUID());
        int curCapacity = (int) capacityMethod.invoke(map);
        if (curCapacity > capacity) {
            System.out.println("當前容量：" + curCapacity);
            resizeCount++;
            capacity = curCapacity;
        }
    }
    System.out.println("hashMap擴容次數：" + resizeCount);

    System.out.println("---------------- 不初始化hashMap容量 -------------------");
    resizeCount = 0;
    HashMap<Integer, Object> map1 = new HashMap<>();
    Method capacityMethod1 = map1.getClass().getDeclaredMethod("capacity");
    capacityMethod1.setAccessible(true);
    int capacity1 = (int) capacityMethod1.invoke(map1);
    System.out.println("初始容量：" + capacity1);
    for (int i = 0; i < count; i++) {
        map1.put(i, UUID.randomUUID());
        int curCapacity = (int) capacityMethod1.invoke(map1);
        if (curCapacity > capacity1) {
            System.out.println("當前容量：" + curCapacity);
            resizeCount++;
            capacity1 = curCapacity;
        }
    }
    System.out.println("擴容次數：" + resizeCount);
}
複製程式碼

由於我們無法直接呼叫hashMap的capacity()方法，因此使用反射來檢視每新增一個元素，它的容量變化，以此來監測hashMap的擴容次數。

//使用反射，呼叫hashMap的capacity()方法
Method capacityMethod = map.getClass().getDeclaredMethod("capacity");
capacityMethod.setAccessible(true);
int capacity = (int) capacityMethod.invoke(map);
複製程式碼

關於反射，歡迎閱讀 Java最強大的技術之一：反射，可以對反射機制有個大致的瞭解。

差點跑偏了，現在回到上面程式的執行結果：

---------------- 初始化hashMap容量為1000000 ------------
初始容量：1048576
當前容量：2097152
hashMap擴容次數：1
---------------- 不初始化hashMap容量 -------------------
初始容量：16
當前容量：32
當前容量：64
當前容量：128
當前容量：256
當前容量：512
當前容量：1024
當前容量：2048
當前容量：4096
當前容量：8192
當前容量：16384
當前容量：32768
當前容量：65536
當前容量：131072
當前容量：262144
當前容量：524288
當前容量：1048576
當前容量：2097152
擴容次數：17
複製程式碼

通過執行結果發現：

設定了初始容量的hashMap，其初始容量並不是我指定的1000000，而是1048576（2^20）
hashMap的容量並不是固定不變的，當達到擴容條件時會進行擴容，從 16 擴容到 32、64、128…（Hash 會選擇大於當前容量的第一個 2 的冪作為容量）
即使制定了初始容量，而且初始容量是1048576，當新增1000000個元素（1000000是小於1048576）時，hashMap依然會擴容1次

為什麼會醬紫呢？帶著上面的三個發現，來看一下HashMap的擴容機制。

HashMap的擴容機制

先看一下HashMap的幾個成員變數：

HashMap成員變數

DEFAULT_INITIAL_CAPACITY：預設初始容量是2^4=16
DEFAULT_LOAD_FACTOR：預設的裝載係數是0.75，是用來衡量HashMap的容量滿的程度的
transient int size：map中k,v對的數目
final float loadFactor：裝載係數，預設值為0.75
int threshold：調整大小的下一個大小值(容量 × 裝載係數)。當實際 k,v 個數超過 threshold 時，HashMap 會將容量擴容

再來看一個方法capacity()：

final int capacity() {
    return (table != null) ? table.length :
        (threshold > 0) ? threshold :
        DEFAULT_INITIAL_CAPACITY;
}
複製程式碼

這是啥？前面不是已經定義了一個size變數了嗎？

可以把capacity看成是HashMap這個桶的體積（這個體積是可以變大的），而size是這個桶當前裝了多少東西。

桶的容量是由threshold定義的，而且預設容量是2的4次冪，也就是16，原始碼上是這樣寫的：

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
複製程式碼

1 << 4就是左移4位元的意思，也就是2^4=16。

那麼什麼時候擴容呢？這個很容易就能夠想到，我們向hashMap這個桶裡put資料，當桶的k,v對的數目size快填滿桶-逼近capacity時，這個桶將要擴容！

前面的例子已經展示了，hashMap並不是等size到了capacity才擴容，而是在到達capacity的某個值時就擴容了，這個值就是threshold的時候，hashMap進行resize()，而這個，來看原始碼：

HashMap擴容點源碼

部分原始碼已摺疊，主要展示和容量有關的部分。

當size增長到大於threshold的時候，hashMap進行resize()，而threshold = loadFactor * capacity，這樣就可以知道hashMap這個桶在什麼時候自動擴大它的體積了。

真正的避免HashMap擴容

前面分析到，當size > threshold的時候，hashMap進行擴容，利用threshold = loadFactor * capacity這個公式，我們在初始化的時候就有方向了。

首先肯定不能直接設定成loadFactor * capacity，因為這個數有可能不是2的冪，HashMap規定的容器容量必須是2的冪，既然如此，我設定成大於loadFactor * capacity的第一個2的冪的數就行了，可以這樣做：

int initCapacity = 1 + (int) (count / 0.75);
HashMap<Integer, Object> map = new HashMap<>(initCapacity);
複製程式碼

1 + (int) (count / 0.75)這個公式來源於HashMap原始碼：

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}
複製程式碼

這一段程式碼真的是天外飛仙！其目的是：根據傳入的容量值cap，通過一系列神仙操作計算，得到第一個比他大的 2 的冪並返回。

這些都是二進位制的位元運算，將數依次向右移位，然後和原值取或。可以隨便找一個數代入程式碼中驗證，結果就是第一個比它大的2的冪！

為什麼這樣做，或許就是因為 無符號右移 >>> 、或運算 | 就是快吧！

結果驗證

計算容量的公式前面已經搞出來了，現在驗證一下對不對：

@SneakyThrows
@Test
public void perfect() {
    int count = 1000000;

    int initCapacity = 1 + (int) (count / 0.75);
    HashMap<Integer, Object> map = new HashMap<>(initCapacity);
    Method capacityMethod = map.getClass().getDeclaredMethod("capacity");
    capacityMethod.setAccessible(true);
    int capacity = (int) capacityMethod.invoke(map);
    System.out.println("jdk hashMap default capacity:" + capacity);
    int resizeCount = 0;
    for (int i = 0; i < count; i++) {
        map.put(i, UUID.randomUUID());
        int curCapacity = (int) capacityMethod.invoke(map);
        if (curCapacity > capacity) {
            System.out.println("當前容量：" + curCapacity);
            resizeCount++;
            capacity = curCapacity;
        }
    }
    System.out.println("hashMap擴容次數：" + resizeCount);
複製程式碼

執行結果：

擴容次數為0，perfect！

把initCapacity=1333334這個數代入到HashMap的tableSizeFor方法就能算出容量為2097152=2^21了！

不想計算初始化容量-仍有他途

Guava是一種基於開源的Java庫，其中包含谷歌正在由他們很多專案使用的很多核心庫。這個庫是為了方便編碼，並減少編碼錯誤。這個庫提供用於集合，快取，支援原語，並行性，常見註解，字串處理，I/O和驗證的實用方法。

Guava中有現成的初始化HashMap的方法，它不用我們計算initCapacity，測試一把看看。

先引入Guava包：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>29.0-jre</version>
</dependency>
複製程式碼

測試：

@SneakyThrows
@Test
public void perfectWithGuava() {
    int count = 1000000;

    HashMap<Integer, Object> map = Maps.newHashMapWithExpectedSize(count);
    Method capacityMethod = map.getClass().getDeclaredMethod("capacity");
    capacityMethod.setAccessible(true);
    int capacity = (int) capacityMethod.invoke(map);
    System.out.println("guava hashMap default capacity:" + capacity);
    int resizeCount = 0;
    for (int i = 0; i < count; i++) {
        map.put(i, UUID.randomUUID());
        int curCapacity = (int) capacityMethod.invoke(map);
        if (curCapacity > capacity) {
            System.out.println("當前容量：" + curCapacity);
            resizeCount++;
            capacity = curCapacity;
        }
    }
    System.out.println("hashMap擴容次數：" + resizeCount);
}
複製程式碼

執行結果：

同樣能使HashMap不用擴容！

瞅一下關鍵程式碼：

... = Maps.newHashMapWithExpectedSize(count);

我猜這個newHashMapWithExpectedSize(int)的原始碼中肯定也是按照類似於HashMap的return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;這種方法計算的，來看一下：

Guava Maps源碼

恭喜你，都能猜對了！

小結

設定了初始容量的hashMap，其真實初始容量並不一定是指定的數值，而是HashMap內部計算過的
hashMap的容量並不是固定不變的，當達到擴容條件時會進行擴容，從 16 擴容到 32、64、128…（Hash 會選擇大於當前容量的第一個 2 的冪作為容量）
不要以為指定了初始容量，hashMap就不擴容了
避免hashMap擴容的方法是傳入一個1 + (int) (count / 0.75)計算出的初始值
還可以使用Guava的newHashMapWithExpectedSize(int count)