空間預(yù)分配思想提升 HashMap 插入效率
HashMap容量初始化
都知道HashMap底層是由數(shù)組構(gòu)成，理論上我們顯示聲明HashMap容量為n時，其底層數(shù)組長度應(yīng)該也為n，實際并非如此，HashMap在初始化時會基于我們提供的容量n得到一個2的次方的上限閾值，舉個例子，假如我們初始化HashMap的代碼為new HashMap<>(15)，按照HashMap底層的算法，它首先會基于我們的容量減去1即得到14，也就是二進制1110。 然后開始基于當(dāng)前二進制的值進行移位運算然后和1110進行亦或，這里我們以>>>1運算為例，可以看到減去1的結(jié)果為14，通過無符號右移位后得到0111，然后進行按位或運算得到15。
經(jīng)過不斷的無符號右移結(jié)合亦或運算，保證了n的低位都是1：
最后基于這個全1的二進制值再加上1，由此得到一個2的次方的二進制，也就是16，也就是2的4次方:
查看HashMap可以印證這段邏輯，可以看到基于我們的初始化設(shè)置的容量initialCapacity會調(diào)用tableSizeFor獲得一個2的次方的閾值：
public HashMap(int initialCapacity, float loadFactor) {
//......
this.loadFactor = loadFactor;//默認(rèn)為0.75f
this.threshold = tableSizeFor(initialCapacity);
}步入tableSizeFor即可看到筆者上文所說的，先進行無符號右移在進行按位或運算，得到一個低位為全1的二進制數(shù)，然后再加上1，得到一個2的次方的上限閾值，由此完成HashMap初始化的第一步，我們得到的上限閾值為16，負(fù)載因子取默認(rèn)值即0.75:
static final int tableSizeFor(int cap) {
//容量減1
int n = cap - 1;
//基于n進行無符號右移得到低位包含1的字段，進行按位或保證低位盡可能都為1
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//基于計算結(jié)果加上1，得到2的次方
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}HashMap插入細(xì)節(jié)
接下來就是插入操作的細(xì)節(jié)，HashMap初次進行插入會對數(shù)組容量進行初始化，對應(yīng)的加載公式為上限閾值*負(fù)載因子，也就是16*0.75按照整形計算方式，最終得到值為12，對此我們給出入口代碼putVal，可以看到如果看到底層數(shù)組為空則會調(diào)用resize進行初始化：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//初次插入會調(diào)用resize初始化底層數(shù)組
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//......
return null;
}步入resize即可看到，初次初始化會基于上限閾值和負(fù)載因子相乘然后得到一個取整的2的次方的容量的數(shù)組：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr 設(shè)置為當(dāng)前閾值
int oldThr = threshold;
int newCap, newThr = 0;
//......
//初始化容量為上限閾值的值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//......
//默認(rèn)情況下新的閾值為0，于是步入該邏輯，將容量設(shè)置為上限閾值*負(fù)載因子然后取整
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//......
}那么問題也就來了，我們愿意是15時進行擴容，按照這套邏輯，我們?nèi)萘窟_到12時就會進行擴容，默認(rèn)情況下HashMap的擴容都是2倍擴容，在極端場景情況下，這種開銷是非常大的:
HashMap的容量設(shè)置多少合適
解決錯誤擴容時機的本質(zhì)原因就是初次put操作*0.75，對此我們可以提前基于當(dāng)前容量/0.75即可。實際上guava包的newHashMapWithExpectedSize方法就做到了這一點。該方法其底層容量計算公式為(int) ((float) expectedSize / 0.75F + 1.0F)，即基于當(dāng)前容量除0.75再加1，由此抵消put操作初始化時*0.75的傷害：
對此我們給出guava包的Maps工具下的newHashMapWithExpectedSize的源代碼：
public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
//調(diào)用capacity獲得可以抵消傷害的容量
return new HashMap<>(capacity(expectedSize));
}
static int capacity(int expectedSize) {
//......
if (expectedSize < Ints.MAX_POWER_OF_TWO) {
//提前/0.75+1進行預(yù)分配，用于抵消put操作的縮容
return (int) ((float) expectedSize / 0.75F + 1.0F);
}
return Integer.MAX_VALUE; // any large value
}壓測
我們以原生和guava工具包Maps對應(yīng)的newHashMapWithExpectedSize分別創(chuàng)建2的24次方的容量空間，然后進行鍵值對插入操作：
public class Main {
private static int SIZE = 1 << 24;
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<>(SIZE);
HashMap<Integer, Integer> map2 = Maps.newHashMapWithExpectedSize(SIZE);
batchSave(map);
batchSave(map2);
}
private static void batchSave(HashMap<Integer, Integer> map) {
long start = System.currentTimeMillis();
for (int i = 0; i < SIZE; i++) {
map.put(i, i);
}
long end = System.currentTimeMillis();
System.out.println((end - start) + "ms");
}
}可以看到，使用guava的API操作時間整整少了7s左右：
22821ms
15831ms
