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