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