HashMap 是使用頻率最高的類型之一，同時也是面試經常被問到的問題之一，這是因為 HashMap 的知識點有很多，同時它又屬于 Java 基礎知識的一部分，因此在面試中經常被問到。 本課時的面試題是，HashMap 底層是如何實現的？在 JDK 1.8 中它都做了哪些優化？ #### 典型回答 在 JDK 1.7 中 HashMap 是以數組加鏈表的形式組成的，JDK 1.8 之后新增了紅黑樹的組成結構，當鏈表大于 8 并且容量大于 64 時，鏈表結構會轉換成紅黑樹結構，它的組成結構如下圖所示：  數組中的元素我們稱之為哈希桶，它的定義如下： ``` static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> 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 的性能，而紅黑樹具有快速增刪改查的特點，這樣就可以有效的解決鏈表過長時操作比較慢的問題。 #### 考點分析 上面大體介紹了 HashMap 的組成結構，但面試官想要知道的遠遠不止這些，和 HashMap 相關的面試題還有以下幾個： * JDK 1.8 HashMap 擴容時做了哪些優化？ * 加載因子為什么是 0.75？ * 當有哈希沖突時，HashMap 是如何查找并確認元素的？ * HashMap 源碼中有哪些重要的方法？ * HashMap 是如何導致死循環的？ #### 知識擴展 * [ ] 1.HashMap 源碼分析 > 聲明：本系列課程在未做特殊說明的情況下，都是以目前主流的 JDK 版本 1.8 為例來進行源碼分析的。 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 = ``` * [ ] 什么是加載因子？加載因子為什么是 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<K,V> e; // 對 key 進行哈希操作 return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> 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<K,V>)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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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<K,V>[] resize() { // 擴容前的數組 Node<K,V>[] 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 開始擴容，將新的容量賦值給 table table = newTab; // 原數據不為空，將原數據復制到新 table 中 if (oldTab != null) { // 根據容量循環數組，復制非空元素到新 table for (int j = 0; j < oldCap; ++j) { Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order // 鏈表復制，JDK 1.8 擴容優化部分 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> 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<K,V> next = e.next; `時，交出了 CPU 的使用權，源碼如下： ``` void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> 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 替代，但這個問題在面試中被問到的幾率依然很大，所以在這里需要特別說明一下。 #### 小結 本課時介紹了 HashMap 的底層數據結構，在 JDK 1.7 時 HashMap 是由數組和鏈表組成的，而 JDK 1.8 則新增了紅黑樹結構，當鏈表長度達到 8 并且容器達到 64 時會轉換為紅黑樹存儲，以提升元素的操作性能。同時還介紹了 HashMap 的三個重要方法，查詢、添加和擴容，以及 JDK 1.7 resize() 在并發環境下導致死循環的原因。 #### 課后問答 * 1、hashMap負載因子選擇0.75的原因，除了老師講的兩個原因，還有一點是不是因為，為了提升擴容效率，HashMap的容量（capacity）有一個固定的要求，那就是一定是2的冪。所以，如果負載因子是3/4的話，那么和capacity的乘積結果就可以是一個整數 講師回復： 感謝補充。 * 2、HashMap采用鏈地址法，低十六位和高十六位異或以及hashlength-1來減少hash沖突2.在1.7采用頭插入，1.8優化為尾插入，因為頭插入容易產生環形鏈表死循環問題3.在1.7擴容位置為hash 原容量判斷，為0放低位，否則高位，低位位置不變，高位位置=原位置+原容量4.樹化和退樹化8和6的選擇，紅黑樹平均查找為logn，長度為8時，查找長度為3，而鏈表平均為8除以2；當為6時，查找長度一樣，而樹化需要時間；然后中間就一個數防止頻繁轉換5.容量設置為2的n次方主要是可以用位運算實現取模運算，位運算采用內存操作，且能解決負數問題；同時hashlength-1時，length-1為奇數的二進制都為1，index的結果就等同與hashcode后幾位，只要hashcode均勻，那么hash碰撞就少6.負載因子.75主要是太大容易造成hash沖突，太小浪費空間希望順便說下紅黑樹，自己看的時候有很多東西不太理解?? 講師回復： 紅黑樹的知識，后面的章節有專門講哈。 * 3、鏈表轉為紅黑樹那里，少了一個判斷條件：hash桶的長度大于等于64。兩個條件都滿足才會轉紅黑樹，不滿足后者會直接調用擴容方法 講師回復： 是需要滿足兩個條件，源碼 treeifyBin() 里面有關于 MIN_TREEIFY_CAPACITY (64) 的判斷。 * 4、為什么到8變成紅黑樹，到6才退化成單鏈 講師回復： 為了避免頻發的觸發類型轉換帶來的性能開銷 * 5、JDK8，擴容后鏈表不會反轉吧 講師回復： 不會的 * 6、在講死鏈問題時，t2 rehash是不是寫錯了？應該是resize吧？ 講師回復： java 1.7 是 rehash 沒寫錯哈。 * 7、"通過高位運算（e.hash newCap，那就不需要移動，這種理解對吧？ 講師回復： 是的，通過高位運算結果判斷是否要移動位置。 * 8、新增方法流程圖的左下角畫錯了吧，應該沒有準備插入這一步，而是直接插入鏈表，然后判斷大于8的話就轉紅黑樹 講師回復： 因為只有確定了 key 是否相等，才能判斷是修改操作還是添加操作，如果是修改操作的話那直接賦值就可以了，就不用再去判斷并新增元素了。 * 9、詢問一下，負載因子選擇0.75和泊松分布是否有關系 講師回復： 坦率的說，我覺得沒啥關聯關系。 * 10、當加載因子設置比較大的時候，擴容的門檻就被提高了，擴容發生的頻率比較低這句話的理解是不是說比如我把擴容因子設置為2 ，那么此時如果HashMap下一次擴容的時候需要的是2*16=32個長度的內存空間，那么老師解答一下這個這個內存分配機制，是否是這32個內存空間分配是否處于堆區分配，堆的優勢就是動態分配內存大小，加載因子設置過大，會導致在堆區分配內存空間難度變大嗎？如果是的話，擴容門檻變高，也就能夠說得通了，繼而擴容發生的概率降低也就是自然行得通。主要的問題還是沒有明白擴容因子設置過大，導致的內存分配難度變大這個問題。麻煩解答一下，還有上訴猜想是否正確，比如是否在堆區分配擴容因子之后長度空間。也請解答一下，學習感覺還是要追求本質。 講師回復： 可能表示的不是很清楚，“擴容因子設置過大，導致的內存分配難度變大這個問題”，這里的難度變大，不是指處理器的難度變大了，而是指業務場景的“難度變大了”，指的是擴容發生的門檻提高了，擴容的頻率降低了。 * 11、數組長度低于64的 即便是鏈表長度超過8也不會樹化,而是擴容操作,數組超過64在鏈表大于等于8的時候才會進行樹化吧? 講師回復： 需要同時滿足兩個條件才行 * 12、e.hash oldCap 得到的結果，高一位為 0，當結果為 0 時表示元素在擴容時位置不會發生任何變化，為什么高位為0，在擴容的時候，位置就不會再變了？ 講師回復： 源碼是這樣判斷的，可以理解為規定，0 不變，1變。就像井蓋必須是圓的一樣，那為什么不是方的一樣，它總得有一個形狀。 * 13、在resize()函數中，對于鏈表數組的遍歷里面的又套了一個循環不太理解這里為什么要這樣做，看起來是毫無意義的，除了做鏈表在數組中的移動以外沒有看到其他的含義，老師能夠解答一下嗎？ 講師回復： for (int j = 0; j < oldCap; ++j) { 嗎？這個擴容之后把舊數據賦值給新容器 * 14、最后transfer方法是在哪里執行的呢？ 講師回復： JDK 1.7 resize(int newCapacity) 的時候會調用 * 15、當加載因子設置比較大的時候，擴容的門檻就被提高了，擴容發生的頻率比較低，占用的空間會比較小，但此時發生Hash沖突的幾率就會提升，因此需要更復雜的數據結構來存儲元素，這樣對元素的操作時間就會增加。老師您好，這一句我沒懂，麻煩請解釋下，謝謝。1. 加載因子設置大，發生Hash沖突的幾率就會提升，是什么意思呢2. 對于這種情況，需要更復雜的數據結構來存儲，又如何理解 講師回復： 加載因子設置的比較大，那么 Hash 擴容發生的頻率就低了（門檻高了），數據存儲的就更秘籍了，因此發生沖突的概率就高了。更復雜的數據結構指的是紅黑樹。 * 16、個人認為只有當鏈表長度大于8而且哈希表的長度大于64時才會進行鏈表轉化為紅黑樹的操作?? 講師回復： 是這樣，滿足兩個條件，還有 MIN_TREEIFY_CAPACITY (64) 的判斷 * 17、老師您說的并發情況下是多線程訪問同一個hashmap實例的情況嗎？ 講師回復： 是的。 * 18、ConcurrentHashp是怎么實現的？感覺沒講完 講師回復： 感謝反饋，篇幅有限，這篇重點講解的是 HashMap。 * 19、什么結果高一位，自己想的叫法嗎？ 講師回復： 感謝反饋，中間少個逗號，“得到的結果，高一位為 0” * 20、不懂就問系列2.HashMap 死循環分析上面的那張圖 綠色的方塊指什么 講師回復： 綠色表示高一位為 0，無需移動位置的元素。 * 21、我記得以前看源碼發現鏈表轉換紅黑樹應該會先去判斷數組長度！當數組長度超過16后才會去把超過8的鏈表轉紅黑樹吧！難道是我看錯了？？ 講師回復： 數組長度 64 轉為紅黑樹