第9講 | 對比Hashtable、HashMap、TreeMap有什么不同？

Map 是廣義 Java 集合框架中的另外一部分，HashMap 作為框架中使用頻率最高的類型之一，它本身以及相關類型自然也是面試考察的熱點。

今天我要問你的問題是，對比 Hashtable、HashMap、TreeMap 有什么不同？談談你對 HashMap 的掌握。

典型回答

Hashtable、HashMap、TreeMap 都是最常見的一些 Map 實現，是以鍵值對的形式存儲和操作數據的容器類型。

Hashtable 是早期 Java 類庫提供的一個哈希表實現，本身是同步的，不支持 null 鍵和值，由于同步導致的性能開銷，所以已經很少被推薦使用。

HashMap 是應用更加廣泛的哈希表實現，行為上大致上與 HashTable 一致，主要區(qū)別在于 HashMap 不是同步的，支持 null 鍵和值等。通常情況下，HashMap 進行 put 或者 get 操作，可以達到常數時間的性能，所以它是絕大部分利用鍵值對存取場景的首選，比如，實現一個用戶 ID 和用戶信息對應的運行時存儲結構。

TreeMap 則是基于紅黑樹的一種提供順序訪問的 Map，和 HashMap 不同，它的 get、put、remove 之類操作都是 O（log(n)）的時間復雜度，具體順序可以由指定的 Comparator 來決定，或者根據鍵的自然順序來判斷。

考點分析

上面的回答，只是對一些基本特征的簡單總結，針對 Map 相關可以擴展的問題很多，從各種數據結構、典型應用場景，到程序設計實現的技術考量，尤其是在 Java 8 里，HashMap 本身發(fā)生了非常大的變化，這些都是經常考察的方面。

很多朋友向我反饋，面試官似乎鐘愛考察 HashMap 的設計和實現細節(jié)，所以今天我會增加相應的源碼解讀，主要專注于下面幾個方面：

理解 Map 相關類似整體結構，尤其是有序數據結構的一些要點。

從源碼去分析 HashMap 的設計和實現要點，理解容量、負載因子等，為什么需要這些參數，如何影響 Map 的性能，實踐中如何取舍等。

理解樹化改造的相關原理和改進原因。

除了典型的代碼分析，還有一些有意思的并發(fā)相關問題也經常會被提到，如 HashMap 在并發(fā)環(huán)境可能出現無限循環(huán)占用 CPU、size 不準確等詭異的問題。

我認為這是一種典型的使用錯誤，因為 HashMap 明確聲明不是線程安全的數據結構，如果忽略這一點，簡單用在多線程場景里，難免會出現問題。

理解導致這種錯誤的原因，也是深入理解并發(fā)程序運行的好辦法。對于具體發(fā)生了什么，你可以參考這篇很久以前的分析，里面甚至提供了示意圖，我就不再重復別人寫好的內容了。

知識擴展

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 需要保持一致性，狀態(tài)改變返回的哈希值仍然要一致。

equals 的對稱、反射、傳遞等特性。

這方面內容網上有很多資料，我就不在這里詳細展開了。

針對有序 Map 的分析內容比較有限，我再補充一些，雖然 LinkedHashMap 和 TreeMap 都可以保證某種順序，但二者還是非常不同的。

LinkedHashMap 通常提供的是遍歷順序符合插入順序，它的實現是通過為條目（鍵值對）維護一個雙向鏈表。注意，通過特定構造函數，我們可以創(chuàng)建反映訪問順序的實例，所謂的 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){@Overrideprotected boolean removeEldestEntry(Map.Entry<String, String> eldest) { // 實現自定義刪除策略，否則行為就和普遍Map沒有區(qū)別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);});// 觸發(fā)刪除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（自然順序）來決定。

我在上一講留給你的思考題提到了，構建一個具有優(yōu)先級的調度系統(tǒng)的問題，其本質就是個典型的優(yōu)先隊列場景，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;elsereturn 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 里面，到底有什么秘密呢？為了節(jié)省空間，我這里只截取了 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 方法最初的幾行，我們就可以發(fā)現幾個有意思的地方：

如果表格是 null，resize 方法會負責初始化它，這從 tab = resize() 可以看出。

resize 方法兼顧兩個職責，創(chuàng)建初始存儲表格，或者在容量不滿足需求的時候，進行擴容（resize）。

在放置新的鍵值對的過程中，如果發(fā)生下面條件，就會發(fā)生擴容。

if (++size > threshold)resize();

具體鍵值對在哈希表中的位置（數組 index）取決于下面的位運算：

i = (n - 1) & hash

仔細觀察哈希值的源頭，我們會發(fā)現，它并不是 key 本身的 hashCode，而是來自于 HashMap 內部的另外一個 hash 方法。注意，為什么這里需要將高位數據移位到低位進行異或運算呢？這是因為有些數據計算出的哈希值差異主要在高位，而 HashMap 里的哈希尋址是忽略容量以上的高位的，那么這種處理就可以有效避免類似情況下的哈希碰撞。

static final int hash(Object kye) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>>16;
}

我前面提到的鏈表結構（這里叫 bin），會在達到一定門限值時，發(fā)生樹化，我稍后會分析為什么 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 thresholdnewCap = oldThr;else {  // zero initial threshold signifies using defaultsfultsnewCap = 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 從創(chuàng)建到放入鍵值對的相關邏輯，現在思考一下，為什么我們需要在乎容量和負載因子呢？

   這是因為容量和負載系數決定了可用的桶的數量，空桶太多會浪費空間，如果使用的太滿則會嚴重影響操作的性能。極端情況下，假設只有一個桶，那么它就退化成了鏈表，完全不能提供所謂常數時間存的性能。

   既然容量和負載因子這么重要，我們在實踐中應該如何選擇呢？

   如果能夠知道 HashMap 要存取的鍵值對數量，可以考慮預先設置合適的容量大小。具體數值我們可以根據擴容發(fā)生的條件來做簡單預估，根據前面的代碼分析，我們知道它需要符合計算條件：

   負載因子 * 容量 > 元素數量
   

   所以，預先設置的容量需要滿足，大于“預估元素數量 / 負載因子”，同時它是 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 大量占用，這就構成了哈希碰撞拒絕服務攻擊，國內一線互聯網公司就發(fā)生過類似攻擊事件。

今天我從 Map 相關的幾種實現對比，對各種 Map 進行了分析，講解了有序集合類型容易混淆的地方，并從源碼級別分析了 HashMap 的基本結構，希望對你有所幫助。

一課一練

關于今天我們討論的題目你做到心中有數了嗎？留一道思考題給你，解決哈希沖突有哪些典型方法呢？

請你在留言區(qū)寫寫你對這個問題的思考，我會選出經過認真思考的留言，送給你一份學習鼓勵金，歡迎你與我一起討論。

過程中，如果一個對象哈希沖突，都被放置到同一個桶里，則會形成一個鏈表，我們知道鏈表查詢是線性的，會嚴重影響存取的性能。

而在現實世界，構造哈希沖突的數據并不是非常復雜的事情，惡意代碼就可以利用這些數據大量與服務器端交互，導致服務器端 CPU 大量占用，這就構成了哈希碰撞拒絕服務攻擊，國內一線互聯網公司就發(fā)生過類似攻擊事件。

今天我從 Map 相關的幾種實現對比，對各種 Map 進行了分析，講解了有序集合類型容易混淆的地方，并從源碼級別分析了 HashMap 的基本結構，希望對你有所幫助。

一課一練

關于今天我們討論的題目你做到心中有數了嗎？留一道思考題給你，解決哈希沖突有哪些典型方法呢？

請你在留言區(qū)寫寫你對這個問題的思考，我會選出經過認真思考的留言，送給你一份學習鼓勵金，歡迎你與我一起討論。

你的朋友是不是也在準備面試呢？你可以“請朋友讀”，把今天的題目分享給好友，或許你能幫到他。