Map 是廣義 Java 集合框架中的另外一部分，HashMap 作為框架中使用頻率最高的類型之一，它本身以及相關類型自然也是面試考察的熱點。 今天我要問你的問題是，對比 Hashtable、HashMap、TreeMap 有什么不同？談談你對 HashMap 的掌握。 ## 典型回答 Hashtable、HashMap、TreeMap 都是最常見的一些 Map 實現，是以**鍵值對**的形式存儲和操作數據的容器類型。 Hashtable 是早期 Java 類庫提供的一個[哈希表](https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8)實現，本身是同步的，不支持 null 鍵和值，由于同步導致的性能開銷，所以已經很少被推薦使用。 HashMap 是應用更加廣泛的哈希表實現，行為上大致上與 HashTable 一致，主要區別在于 HashMap 不是同步的，支持 null 鍵和值等。通常情況下，HashMap 進行 put 或者 get 操作，可以達到常數時間的性能，所以**它是絕大部分利用鍵值對存取場景的首選**，比如，實現一個用戶 ID 和用戶信息對應的運行時存儲結構。 TreeMap 則是基于紅黑樹的一種提供順序訪問的 Map，和 HashMap 不同，它的 get、put、remove 之類操作都是 O（log(n)）的時間復雜度，具體順序可以由指定的 Comparator 來決定，或者根據鍵的自然順序來判斷。 ## 考點分析 上面的回答，只是對一些基本特征的簡單總結，針對 Map 相關可以擴展的問題很多，從各種數據結構、典型應用場景，到程序設計實現的技術考量，尤其是在 Java 8 里，HashMap 本身發生了非常大的變化，這些都是經常考察的方面。 很多朋友向我反饋，面試官似乎鐘愛考察 HashMap 的設計和實現細節，所以今天我會增加相應的源碼解讀，主要專注于下面幾個方面： * 理解 Map 相關類似整體結構，尤其是有序數據結構的一些要點。 * 從源碼去分析 HashMap 的設計和實現要點，理解容量、負載因子等，為什么需要這些參數，如何影響 Map 的性能，實踐中如何取舍等。 * 理解樹化改造的相關原理和改進原因。 除了典型的代碼分析，還有一些有意思的并發相關問題也經常會被提到，如 HashMap 在并發環境可能出現[無限循環占用 CPU](https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6423457)、size 不準確等詭異的問題。 我認為這是一種典型的使用錯誤，因為 HashMap 明確聲明不是線程安全的數據結構，如果忽略這一點，簡單用在多線程場景里，難免會出現問題。 理解導致這種錯誤的原因，也是深入理解并發程序運行的好辦法。對于具體發生了什么，你可以參考這篇很久以前的[分析](http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html)，里面甚至提供了示意圖，我就不再重復別人寫好的內容了。 ## 知識擴展 1.Map 整體結構 首先，我們先對 Map 相關類型有個整體了解，Map 雖然通常被包括在 Java 集合框架里，但是其本身并不是狹義上的集合類型（Collection），具體你可以參考下面這個簡單類圖。  Hashtable 比較特別，作為類似 Vector、Stack 的早期集合相關類型，它是擴展了 Dictionary 類的，類結構上與 HashMap 之類明顯不同。 HashMap 等其他 Map 實現則是都擴展了 AbstractMap，里面包含了通用方法抽象。不同 Map 的用途，從類圖結構就能體現出來，設計目的已經體現在不同接口上。 大部分使用 Map 的場景，通常就是放入、訪問或者刪除，而對順序沒有特別要求，HashMap 在這種情況下基本是最好的選擇。**HashMap 的性能表現非常依賴于哈希碼的有效性，請務必掌握 hashCode 和 equals 的一些基本約定**，比如： * equals 相等，hashCode 一定要相等。 * 重寫了 hashCode 也要重寫 equals。 * hashCode 需要保持一致性，狀態改變返回的哈希值仍然要一致。 * equals 的對稱、反射、傳遞等特性。 這方面內容網上有很多資料，我就不在這里詳細展開了。 針對有序 Map 的分析內容比較有限，我再補充一些，雖然 LinkedHashMap 和 TreeMap 都可以保證某種順序，但二者還是非常不同的。 * LinkedHashMap 通常提供的是遍歷順序符合插入順序，它的實現是通過為條目（鍵值對）維護一個雙向鏈表。注意，通過特定構造函數，我們可以創建反映訪問順序的實例，所謂的 put、get、compute 等，都算作“訪問”。 這種行為適用于一些特定應用場景，例如，我們構建一個空間占用敏感的資源池，希望可以自動將最不常被訪問的對象釋放掉，這就可以利用 LinkedHashMap 提供的機制來實現，參考下面的示例： ~~~ import java.util.LinkedHashMap; import java.util.Map; public class LinkedHashMapSample { public static void main(String[] args) { LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<String, String>(16, 0.75F, true){ @Override protected boolean removeEldestEntry(Map.Entry<String, String> eldest) { // 實現自定義刪除策略，否則行為就和普遍 Map 沒有區別 return size() > 3; } }; accessOrderedMap.put("Project1", "Valhalla"); accessOrderedMap.put("Project2", "Panama"); accessOrderedMap.put("Project3", "Loom"); accessOrderedMap.forEach( (k,v) -> { System.out.println(k +":" + v); }); // 模擬訪問 accessOrderedMap.get("Project2"); accessOrderedMap.get("Project2"); accessOrderedMap.get("Project3"); System.out.println("Iterate over should be not affected:"); accessOrderedMap.forEach( (k,v) -> { System.out.println(k +":" + v); }); // 觸發刪除 accessOrderedMap.put("Project4", "Mission Control"); System.out.println("Oldest entry should be removed:"); accessOrderedMap.forEach( (k,v) -> {// 遍歷順序不變 System.out.println(k +":" + v); }); } } ~~~ * 對于 TreeMap，它的整體順序是由鍵的順序關系決定的，通過 Comparator 或 Comparable（自然順序）來決定。 我在上一講留給你的思考題提到了，構建一個具有優先級的調度系統的問題，其本質就是個典型的優先隊列場景，Java 標準庫提供了基于二叉堆實現的 PriorityQueue，它們都是依賴于同一種排序機制，當然也包括 TreeMap 的馬甲 TreeSet。 類似 hashCode 和 equals 的約定，為了避免模棱兩可的情況，自然順序同樣需要符合一個約定，就是 compareTo 的返回值需要和 equals 一致，否則就會出現模棱兩可情況。 我們可以分析 TreeMap 的 put 方法實現： ~~~ public V put(K key, V value) { Entry<K,V> t = … cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); // ... } ~~~ 從代碼里，你可以看出什么呢？ 當我不遵守約定時，兩個不符合唯一性（equals）要求的對象被當作是同一個（因為，compareTo 返回 0），這會導致歧義的行為表現。 2.HashMap 源碼分析 前面提到，HashMap 設計與實現是個非常高頻的面試題，所以我會在這進行相對詳細的源碼解讀，主要圍繞： * HashMap 內部實現基本點分析。 * 容量（capacity）和負載系數（load factor）。 * 樹化 。 首先，我們來一起看看 HashMap 內部的結構，它可以看作是數組（Node\[\] table）和鏈表結合組成的復合結構，數組被分為一個個桶（bucket），通過哈希值決定了鍵值對在這個數組的尋址；哈希值相同的鍵值對，則以鏈表形式存儲，你可以參考下面的示意圖。這里需要注意的是，如果鏈表大小超過閾值（TREEIFY\_THRESHOLD, 8），圖中的鏈表就會被改造為樹形結構。  從非拷貝構造函數的實現來看，這個表格（數組）似乎并沒有在最初就初始化好，僅僅設置了一些初始值而已。 ~~~ public HashMap(int initialCapacity, float loadFactor){ // ... this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } ~~~ 所以，我們深刻懷疑，HashMap 也許是按照 lazy-load 原則，在首次使用時被初始化（拷貝構造函數除外，我這里僅介紹最通用的場景）。既然如此，我們去看看 put 方法實現，似乎只有一個 putVal 的調用： ~~~ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } ~~~ 看來主要的密碼似乎藏在 putVal 里面，到底有什么秘密呢？為了節省空間，我這里只截取了 putVal 比較關鍵的幾部分。 ~~~ final V putVal(int hash, K key, V value, boolean onlyIfAbent, boolean evit) { Node<K,V>[] tab; Node<K,V> p; int , i; if ((tab = table) == null || (n = tab.length) = 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == ull) tab[i] = newNode(hash, key, value, nll); else { // ... if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for first treeifyBin(tab, hash); // ... } } ~~~ 從 putVal 方法最初的幾行，我們就可以發現幾個有意思的地方： * 如果表格是 null，resize 方法會負責初始化它，這從 tab = resize() 可以看出。 * resize 方法兼顧兩個職責，創建初始存儲表格，或者在容量不滿足需求的時候，進行擴容（resize）。 * 在放置新的鍵值對的過程中，如果發生下面條件，就會發生擴容。 ~~~ if (++size > threshold) resize(); ~~~ * 具體鍵值對在哈希表中的位置（數組 index）取決于下面的位運算： ~~~ i = (n - 1) & hash ~~~ 仔細觀察哈希值的源頭，我們會發現，它并不是 key 本身的 hashCode，而是來自于 HashMap 內部的另外一個 hash 方法。注意，為什么這里需要將高位數據移位到低位進行異或運算呢？**這是因為有些數據計算出的哈希值差異主要在高位，而 HashMap 里的哈希尋址是忽略容量以上的高位的，那么這種處理就可以有效避免類似情況下的哈希碰撞。** ~~~ static final int hash(Object kye) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>>16; } ~~~ * 我前面提到的鏈表結構（這里叫 bin），會在達到一定門限值時，發生樹化，我稍后會分析為什么 HashMap 需要對 bin 進行處理。 可以看到，putVal 方法本身邏輯非常集中，從初始化、擴容到樹化，全部都和它有關，推薦你閱讀源碼的時候，可以參考上面的主要邏輯。 我進一步分析一下身兼多職的 resize 方法，很多朋友都反饋經常被面試官追問它的源碼設計。 ~~~ final Node<K,V>[] resize() { // ... else if ((newCap = oldCap << 1) < MAXIMUM_CAPACIY && oldCap >= DEFAULT_INITIAL_CAPAITY) newThr = oldThr << 1; // double there // ... else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaultsfults newCap = DEFAULT_INITIAL_CAPAITY; newThr = (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY； } if (newThr ==0) { float ft = (float)newCap * loadFator; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE); } threshold = neThr; Node<K,V>[] newTab = (Node<K,V>[])new Node[newap]; table = n； // 移動到新的數組結構 e 數組結構 } ~~~ 依據 resize 源碼，不考慮極端情況（容量理論最大極限由 MAXIMUM\_CAPACITY 指定，數值為 1<<30，也就是 2 的 30 次方），我們可以歸納為： * 門限值等于（負載因子）x（容量），如果構建 HashMap 的時候沒有指定它們，那么就是依據相應的默認常量值。 * 門限通常是以倍數進行調整 （newThr = oldThr << 1），我前面提到，根據 putVal 中的邏輯，當元素個數超過門限大小時，則調整 Map 大小。 * 擴容后，需要將老的數組中的元素重新放置到新的數組，這是擴容的一個主要開銷來源。 3\. 容量、負載因子和樹化 前面我們快速梳理了一下 HashMap 從創建到放入鍵值對的相關邏輯，現在思考一下，為什么我們需要在乎容量和負載因子呢？ 這是因為容量和負載系數決定了可用的桶的數量，空桶太多會浪費空間，如果使用的太滿則會嚴重影響操作的性能。極端情況下，假設只有一個桶，那么它就退化成了鏈表，完全不能提供所謂常數時間存的性能。 既然容量和負載因子這么重要，我們在實踐中應該如何選擇呢？ 如果能夠知道 HashMap 要存取的鍵值對數量，可以考慮預先設置合適的容量大小。具體數值我們可以根據擴容發生的條件來做簡單預估，根據前面的代碼分析，我們知道它需要符合計算條件： ~~~ 負載因子 * 容量 > 元素數量 ~~~ 所以，預先設置的容量需要滿足，大于“預估元素數量 / 負載因子”，同時它是 2 的冪數，結論已經非常清晰了。 而對于負載因子，我建議： * 如果沒有特別需求，不要輕易進行更改，因為 JDK 自身的默認負載因子是非常符合通用場景的需求的。 * 如果確實需要調整，建議不要設置超過 0.75 的數值，因為會顯著增加沖突，降低 HashMap 的性能。 * 如果使用太小的負載因子，按照上面的公式，預設容量值也進行調整，否則可能會導致更加頻繁的擴容，增加無謂的開銷，本身訪問性能也會受影響。 我們前面提到了樹化改造，對應邏輯主要在 putVal 和 treeifyBin 中。 ~~~ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // 樹化改造邏輯 } } ~~~ 上面是精簡過的 treeifyBin 示意，綜合這兩個方法，樹化改造的邏輯就非常清晰了，可以理解為，當 bin 的數量大于 TREEIFY\_THRESHOLD 時 * 如果容量小于 MIN\_TREEIFY\_CAPACITY，只會進行簡單的擴容。 * 如果容量大于 MIN\_TREEIFY\_CAPACITY ，則會進行樹化改造。 那么，為什么 HashMap 要樹化呢？ **本質上這是個安全問題。**因為在元素放置過程中，如果一個對象哈希沖突，都被放置到同一個桶里，則會形成一個鏈表，我們知道鏈表查詢是線性的，會嚴重影響存取的性能。 而在現實世界，構造哈希沖突的數據并不是非常復雜的事情，惡意代碼就可以利用這些數據大量與服務器端交互，導致服務器端 CPU 大量占用，這就構成了哈希碰撞拒絕服務攻擊，國內一線互聯網公司就發生過類似攻擊事件。 今天我從 Map 相關的幾種實現對比，對各種 Map 進行了分析，講解了有序集合類型容易混淆的地方，并從源碼級別分析了 HashMap 的基本結構，希望對你有所幫助。 ## 一課一練 關于今天我們討論的題目你做到心中有數了嗎？留一道思考題給你，解決哈希沖突有哪些典型方法呢？