怎么還在問HashMap？
架構(gòu)前幾天一個(gè)小伙子向我吐槽，準(zhǔn)備了好久的面試，沒想到問了一個(gè)HashMap就結(jié)束了，之后大概了解了一下面試過程。其實(shí)前幾年對(duì)于HashMap,大家問的還是比較簡(jiǎn)單的，隨著大家水平的提高，這種簡(jiǎn)單的問題已經(jīng)攔不住大家了。
那么開始問一些經(jīng)常被忽視比較關(guān)鍵的小細(xì)節(jié)，開始卷起來，比如說HashMap創(chuàng)建的時(shí)候，要不要指定容量?如果要指定的話，多少是合適的?為什么?如果我有100個(gè)hashcode 不同的元素需要放在HashMap 中，初始值設(shè)置100合適嗎?
要設(shè)置HashMap的初始化容量嗎?設(shè)置多少合適呢?
如果我們沒有設(shè)置初始容量大小，隨著元素的不斷增加，HashMap會(huì)發(fā)生多次擴(kuò)容，而HashMap中的擴(kuò)容機(jī)制決定了每次擴(kuò)容都需要重建hash表，是非常影響性能的。我們可以看看resize()代碼：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//首次初始化后table為Null
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;//默認(rèn)構(gòu)造器的情況下為0
int newCap, newThr = 0;
if (oldCap > 0) {//table擴(kuò)容過
//當(dāng)前table容量大于最大值得時(shí)候返回當(dāng)前table
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//table的容量乘以2，threshold的值也乘以2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//使用帶有初始容量的構(gòu)造器時(shí)，table容量為初始化得到的threshold
newCap = oldThr;
else { //默認(rèn)構(gòu)造器下進(jìn)行擴(kuò)容
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//使用帶有初始容量的構(gòu)造器在此處進(jìn)行擴(kuò)容
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];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K,V> e;
if ((e = oldTab[j]) != null) {
// help gc
oldTab[j] = null;
if (e.next == null)
// 當(dāng)前index沒有發(fā)生hash沖突，直接對(duì)2取模，即移位運(yùn)算hash &（2^n -1）
// 擴(kuò)容都是按照2的冪次方擴(kuò)容，因此newCap = 2^n
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode)
// 當(dāng)前index對(duì)應(yīng)的節(jié)點(diǎn)為紅黑樹，這里篇幅比較長(zhǎng)且需要了解其數(shù)據(jù)結(jié)構(gòu)跟算法，因此不進(jìn)行詳解，當(dāng)樹的個(gè)數(shù)小于等于UNTREEIFY_THRESHOLD則轉(zhuǎn)成鏈表
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 把當(dāng)前index對(duì)應(yīng)的鏈表分成兩個(gè)鏈表，減少擴(kuò)容的遷移量
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
// 擴(kuò)容后不需要移動(dòng)的鏈表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 擴(kuò)容后需要移動(dòng)的鏈表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
// help gc
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// help gc
hiTail.next = null;
// 擴(kuò)容長(zhǎng)度為當(dāng)前index位置+舊的容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}那么創(chuàng)建時(shí)到底指定多少合適呢?是不是用多少設(shè)置成多少呢?如果是這樣還會(huì)這樣問你嗎。因?yàn)?，?dāng)我們使用HashMap(int initialCapacity)來初始化容量的時(shí)候，HashMap并不會(huì)使用我們傳進(jìn)來的initialCapacity直接作為初始容量。
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;
}所以當(dāng)我們 初始化時(shí)：
new HashMap<>(cap)
JDK實(shí)際上是找到第一個(gè)比用戶傳入的值大的2的冪。
那么我們直接初始化為2的冪不就行了。那么也是不正確的，因?yàn)槟愫雎粤艘粋€(gè)因素：loadFactor。
loadFactor是負(fù)載因子，當(dāng)HashMap中的元素個(gè)數(shù)(size)超過 threshold = loadFactor * capacity時(shí)，就會(huì)進(jìn)行擴(kuò)容。
也就是說，如果我們HashMap 中要保存7個(gè)元素，我們?cè)O(shè)置默認(rèn)值為7后，JDK會(huì)默認(rèn)處理為8。我們期望的是HashMap 在我們PUT 的時(shí)候不進(jìn)行擴(kuò)容，這樣對(duì)性能就沒有影響，但是事實(shí)不是這樣的，這個(gè)HashMap在元素個(gè)數(shù)達(dá)到 8*0.75 = 6的時(shí)候就會(huì)進(jìn)行一次擴(kuò)容。
public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
HashMap<String, Integer> hashMap = new HashMap<>(7);
Class clazz = HashMap.class;
// threshold是hashmap對(duì)象里的一個(gè)私有變量，若hashmap的size超過該數(shù)值，則擴(kuò)容。這是通過反射獲取該值
Field field = clazz.getDeclaredField("threshold");
field.setAccessible(true);
int threshold_begin = (int) field.get(hashMap);
System.out.println("init size:"+threshold_begin);
int threshold = 0;
for (int i = 0; i < 8; i++) {
hashMap.put(String.valueOf(i), 0);
if ((int) field.get(hashMap) != threshold) {
threshold = (int) field.get(hashMap);
System.out.println("Start capacity:"+threshold);
// 默認(rèn)的負(fù)載因子是0.75,也就是說實(shí)際容量是/0.75
System.out.println("after capacity:"+(int) field.get(hashMap) / 0.75);
System.out.println("==================");
}
}
}
那么我們到底該怎么設(shè)置呢?其實(shí)可以參考JDK8中putAll方法中的實(shí)現(xiàn)：
比如我們計(jì)劃向HashMap中放入7個(gè)元素的時(shí)候，我們通過expectedSize / 0.75F + 1.0F計(jì)算，7/0.75 + 1 = 10 ,10經(jīng)過JDK處理之后，會(huì)被設(shè)置成16，這就大大的減少了擴(kuò)容的幾率。但是會(huì)犧牲一些內(nèi)存。
其實(shí)這個(gè)算法在guava 中已經(jīng)有實(shí)現(xiàn)：
Map<String, String> map = Maps.newHashMapWithExpectedSize(7);
public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
return new HashMap(capacity(expectedSize));
}
static int capacity(int expectedSize) {
if (expectedSize < 3) {
CollectPreconditions.checkNonnegative(expectedSize, "expectedSize");
return expectedSize + 1;
} else {
return expectedSize < 1073741824 ? (int)((float)expectedSize / 0.75F + 1.0F) : 2147483647;
}
}其實(shí)這也就是一種內(nèi)存換性能的做法，不過在目前的大環(huán)境中，算力成本的低廉和高網(wǎng)絡(luò)帶寬，使大部分開發(fā)人員在遇到性能問題時(shí)就無腦的通過增加服務(wù)器的CPU和內(nèi)存來解決問題，其實(shí)一個(gè)大的優(yōu)化都是通過一個(gè)個(gè)小優(yōu)化累加起來的吧。不過現(xiàn)在來看問這些東西大部分還是為了篩選，金三銀四祝大家面試順利。
