設定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的幾個成員變數：
- 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()，而這個，來看原始碼：
部分原始碼已折疊，主要展示和容量有關的部分，
當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;這種方法計算的，來看一下：
恭喜你，都能猜對了！
小結
- 設定了初始容量的hashMap，其真實初始容量并不一定是指定的數值，而是HashMap內部計算過的
- hashMap的容量并不是固定不變的，當達到擴容條件時會進行擴容，從 16 擴容到 32、64、128…（Hash 會選擇大于當前容量的第一個 2 的冪作為容量）
- 不要以為指定了初始容量，hashMap就不擴容了
- 避免hashMap擴容的方法是傳入一個
1 + (int) (count / 0.75)計算出的初始值 - 還可以使用Guava的
newHashMapWithExpectedSize(int count)
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/143650.html
標籤：其他