【優雅的避坑】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)

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/143659.html

標籤：其他

上一篇：最新版SpringBoot結合ProGuard實作代碼混淆

下一篇：這本出自華為18級工程師之手的多執行緒高并發檔案絕對值得你一看