前言
本文主要介紹HashMap底層實作原理以及JDK8做了哪些優化包括加載因子為什麼是0.75以及HashMap中三個重要方法等等，希望對大家有幫助。
典型回答
在 JDK 1.7 中 HashMap 是以數組加連結清單的形式組成的，JDK 1.8 之後新增了紅黑樹的組成結構，當連結清單大于 8 并且容量大于 64 時，連結清單結構會轉換成紅黑樹結構，它的組成結構如下圖所示：
數組中的元素我們稱之為哈希桶，它的定義如下：
static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry,?> e = (Map.Entry,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }}
可以看出每個哈希桶中包含了四個字段：hash、key、value、next，其中 next 表示連結清單的下一個節點。
JDK 1.8 之是以添加紅黑樹是因為一旦連結清單過長，會嚴重影響 HashMap 的性能，而紅黑樹具有快速增删改查的特點，這樣就可以有效的解決連結清單過長時操作比較慢的問題
考點分析
JDK 1.8 HashMap 擴容時做了哪些優化？
HashMap 源碼中包含了以下幾個屬性：
// HashMap 初始化長度static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // HashMap 最大長度static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824 // 預設的加載因子 (擴容因子)static final float DEFAULT_LOAD_FACTOR = 0.75f; // 當連結清單長度大于此值且容量大于 64 時static final int TREEIFY_THRESHOLD = 8; // 轉換連結清單的臨界值，當元素小于此值時，會将紅黑樹結構轉換成連結清單結構static final int UNTREEIFY_THRESHOLD = 6; // 最小樹容量static final int MIN_TREEIFY_CAPACITY = 64
加載因子為什麼是 0.75？
加載因子也叫擴容因子或負載因子，用來判斷什麼時候進行擴容的，假如加載因子是 0.5，HashMap 的初始化容量是 16，那麼當 HashMap 中有 16*0.5=8 個元素時，HashMap 就會進行擴容。
那加載因子為什麼是 0.75 而不是 0.5 或者 1.0 呢？
這其實是出于容量和性能之間平衡的結果：
- 當加載因子設定比較大的時候，擴容的門檻就被提高了，擴容發生的頻率比較低，占用的空間會比較小，但此時發生 Hash 沖突的幾率就會提升，是以需要更複雜的資料結構來存儲元素，這樣對元素的操作時間就會增加，運作效率也會是以降低；
- 而當加載因子值比較小的時候，擴容的門檻會比較低，是以會占用更多的空間，此時元素的存儲就比較稀疏，發生哈希沖突的可能性就比較小，是以操作性能會比較高。
是以綜合了以上情況就取了一個 0.5 到 1.0 的平均數 0.75 作為加載因子。
HashMap 源碼中三個重要方法：查詢、新增和資料擴容。
查詢
public V get(Object key) { Node e; // 對 key 進行哈希操作 return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; // 非空判斷 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 判斷第一個元素是否是要查詢的元素 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 下一個節點非空判斷 if ((e = first.next) != null) { // 如果第一節點是樹結構，則使用 getTreeNode 直接擷取相應的資料 if (first instanceof TreeNode) return ((TreeNode)first).getTreeNode(hash, key); do { // 非樹結構，循環節點判斷 // hash 相等并且 key 相同，則傳回此節點 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null;}
從以上源碼可以看出，當哈希沖突時我們需要通過判斷 key 值是否相等，才能确認此元素是不是我們想要的元素。
HashMap 第二個重要方法：新增方法，源碼如下：
public V put(K key, V value) { // 對 key 進行哈希操作 return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 哈希表為空則建立表 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 根據 key 的哈希值計算出要插入的數組索引 i if ((p = tab[i = (n - 1) & hash]) == null) // 如果 table[i] 等于 null，則直接插入 tab[i] = newNode(hash, key, value, null); else { Node e; K k; // 如果 key 已經存在了，直接覆寫 value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果 key 不存在，判斷是否為紅黑樹 else if (p instanceof TreeNode) // 紅黑樹直接插入鍵值對 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { // 為連結清單結構，循環準備插入 for (int binCount = 0; ; ++binCount) { // 下一個元素為空時 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 轉換為紅黑樹進行處理 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // key 已經存在直接覆寫 value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 超過最大容量，擴容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;}
新增方法的執行流程，如下圖所示：
HashMap 第三個重要的方法是擴容方法，源碼如下：
final Node[] resize() { // 擴容前的數組 Node[] oldTab = table; // 擴容前的數組的大小和門檻值 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; // 預定義新數組的大小和門檻值 int newCap, newThr = 0; if (oldCap > 0) { // 超過最大值就不再擴容了 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 擴大容量為目前容量的兩倍，但不能超過 MAXIMUM_CAPACITY else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 目前數組沒有資料，使用初始化的值 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults // 如果初始化的值為 0，則使用預設的初始化容量 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新的容量等于 0 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[] newTab = (Node[])new Node[newCap]; // 開始擴容，将新的容量指派給 table table = newTab; // 原資料不為空，将原資料複制到新 table 中 if (oldTab != null) { // 根據容量循環數組，複制非空元素到新 table for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 如果連結清單隻有一個，則進行直接指派 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 紅黑樹相關的操作 ((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order // 連結清單複制，JDK 1.8 擴容優化部分 Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; // 原索引 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 原索引 + oldCap else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 将原索引放到哈希桶中 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 将原索引 + oldCap 放到哈希桶中 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab;}
從以上源碼可以看出，JDK 1.8 在擴容時并沒有像 JDK 1.7 那樣，重新計算每個元素的哈希值，而是通過高位運算(e.hash & oldCap)來确定元素是否需要移動，比如 key1 的資訊如下：
- key1.hash = 10 0000 1010
- oldCap = 16 0001 0000
使用 e.hash & oldCap 得到的結果，高一位為 0，當結果為 0 時表示元素在擴容時位置不會發生任何變化，而 key 2 資訊如下：
- key2.hash = 10 0001 0001
- oldCap = 16 0001 0000
這時候得到的結果，高一位為 1，當結果為 1 時，表示元素在擴容時位置發生了變化，新的下标位置等于原下标位置 + 原數組長度，如下圖所示：
其中紅色的虛線圖代表了擴容時元素移動的位置。
2.HashMap 死循環分析
以 JDK 1.7 為例，假設 HashMap 預設大小為 2，原本 HashMap 中有一個元素 key(5)，我們再使用兩個線程：t1 添加元素 key(3)，t2 添加元素 key(7)，當元素 key(3) 和 key(7) 都添加到 HashMap 中之後，線程 t1 在執行到 Entry next = e.next; 時，交出了 CPU 的使用權，源碼如下：
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry e : table) { while(null != e) { Entry next = e.next; // 線程一執行此處 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } }}
那麼此時線程 t1 中的 e 指向了 key(3)，而 next 指向了 key(7) ；之後線程 t2 重新 rehash 之後連結清單的順序被反轉，連結清單的位置變成了 key(5) → key(7) → key(3)，其中 “→” 用來表示下一個元素。
當 t1 重新獲得執行權之後，先執行 newTalbe[i] = e 把 key(3) 的 next 設定為 key(7)，而下次循環時查詢到 key(7) 的 next 元素為 key(3)，于是就形成了 key(3) 和 key(7) 的循環引用，是以就導緻了死循環的發生，如下圖所示：
當然發生死循環的原因是 JDK 1.7 連結清單插入方式為首部倒序插入，這個問題在 JDK 1.8 得到了改善，變成了尾部正序插入。
有人曾經把這個問題回報給了 Sun 公司，但 Sun 公司認為這不是一個問題，因為 HashMap 本身就是非線程安全的，如果要在多線程下，建議使用 ConcurrentHashMap 替代，但這個問題在面試中被問到的幾率依然很大，是以在這裡需要特别說明一下。
****為何初始容量要是2的指數幂? 索引定位:關鍵****
13 ---> 16 大于13又是最靠近13的2的指數次幂的值
****效率問題****:取模運算底層最終要換算成二進制進行處理 加法 > 乘法 > 除法 > 取模(運算效率) 是以要避免取餘操作
而且數組還需要進行擴容，擴容就涉及到了數組資料的遷移，對于數組中原有的每個值都要重新去計算hash值，再對應到索引的位置。大大影響效率。
****使用2的原因****
如果length是2的指數次幂，有hash % length == h &(length - 1) 與運算能極大提高運算效率，如果不是2的指數次幂
16 - 1 = 15
hashcode: 1101 0010 1010 1010
length: 0000 0000 0000 1111 = 0 - 15(結果一定在0~15之間,和取模結果保持一緻，在數組的範圍區間之内)