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

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

今天我要問你的問題是，對(duì)比 Hashtable、HashMap、TreeMap 有什么不同？談?wù)勀銓?duì) HashMap 的掌握。

典型回答

Hashtable、HashMap、TreeMap 都是最常見的一些 Map 實(shí)現(xiàn)，是以鍵值對(duì)的形式存儲(chǔ)和操作數(shù)據(jù)的容器類型。

Hashtable 是早期 Java 類庫提供的一個(gè)哈希表實(shí)現(xiàn)，本身是同步的，不支持 null 鍵和值，由于同步導(dǎo)致的性能開銷，所以已經(jīng)很少被推薦使用。

HashMap 是應(yīng)用更加廣泛的哈希表實(shí)現(xiàn)，行為上大致上與 HashTable 一致，主要區(qū)別在于 HashMap 不是同步的，支持 null 鍵和值等。通常情況下，HashMap 進(jìn)行 put 或者 get 操作，可以達(dá)到常數(shù)時(shí)間的性能，所以它是絕大部分利用鍵值對(duì)存取場(chǎng)景的首選，比如，實(shí)現(xiàn)一個(gè)用戶 ID 和用戶信息對(duì)應(yīng)的運(yùn)行時(shí)存儲(chǔ)結(jié)構(gòu)。

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

考點(diǎn)分析

上面的回答，只是對(duì)一些基本特征的簡(jiǎn)單總結(jié)，針對(duì) Map 相關(guān)可以擴(kuò)展的問題很多，從各種數(shù)據(jù)結(jié)構(gòu)、典型應(yīng)用場(chǎng)景，到程序設(shè)計(jì)實(shí)現(xiàn)的技術(shù)考量，尤其是在 Java 8 里，HashMap 本身發(fā)生了非常大的變化，這些都是經(jīng)常考察的方面。

很多朋友向我反饋，面試官似乎鐘愛考察 HashMap 的設(shè)計(jì)和實(shí)現(xiàn)細(xì)節(jié)，所以今天我會(huì)增加相應(yīng)的源碼解讀，主要專注于下面幾個(gè)方面：

理解 Map 相關(guān)類似整體結(jié)構(gòu)，尤其是有序數(shù)據(jù)結(jié)構(gòu)的一些要點(diǎn)。

從源碼去分析 HashMap 的設(shè)計(jì)和實(shí)現(xiàn)要點(diǎn)，理解容量、負(fù)載因子等，為什么需要這些參數(shù)，如何影響 Map 的性能，實(shí)踐中如何取舍等。

理解樹化改造的相關(guān)原理和改進(jìn)原因。

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

我認(rèn)為這是一種典型的使用錯(cuò)誤，因?yàn)?HashMap 明確聲明不是線程安全的數(shù)據(jù)結(jié)構(gòu)，如果忽略這一點(diǎn)，簡(jiǎn)單用在多線程場(chǎng)景里，難免會(huì)出現(xiàn)問題。

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

知識(shí)擴(kuò)展

1.Map 整體結(jié)構(gòu)

首先，我們先對(duì) Map 相關(guān)類型有個(gè)整體了解，Map 雖然通常被包括在 Java 集合框架里，但是其本身并不是狹義上的集合類型（Collection），具體你可以參考下面這個(gè)簡(jiǎn)單類圖。

Hashtable 比較特別，作為類似 Vector、Stack 的早期集合相關(guān)類型，它是擴(kuò)展了 Dictionary 類的，類結(jié)構(gòu)上與 HashMap 之類明顯不同。

HashMap 等其他 Map 實(shí)現(xiàn)則是都擴(kuò)展了 AbstractMap，里面包含了通用方法抽象。不同 Map 的用途，從類圖結(jié)構(gòu)就能體現(xiàn)出來，設(shè)計(jì)目的已經(jīng)體現(xiàn)在不同接口上。

大部分使用 Map 的場(chǎng)景，通常就是放入、訪問或者刪除，而對(duì)順序沒有特別要求，HashMap 在這種情況下基本是最好的選擇。HashMap 的性能表現(xiàn)非常依賴于哈希碼的有效性，請(qǐng)務(wù)必掌握 hashCode 和 equals 的一些基本約定，比如：

equals 相等，hashCode 一定要相等。

重寫了 hashCode 也要重寫 equals。

hashCode 需要保持一致性，狀態(tài)改變返回的哈希值仍然要一致。

equals 的對(duì)稱、反射、傳遞等特性。

這方面內(nèi)容網(wǎng)上有很多資料，我就不在這里詳細(xì)展開了。

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

LinkedHashMap 通常提供的是遍歷順序符合插入順序，它的實(shí)現(xiàn)是通過為條目（鍵值對(duì)）維護(hù)一個(gè)雙向鏈表。注意，通過特定構(gòu)造函數(shù)，我們可以創(chuàng)建反映訪問順序的實(shí)例，所謂的 put、get、compute 等，都算作“訪問”。

這種行為適用于一些特定應(yīng)用場(chǎng)景，例如，我們構(gòu)建一個(gè)空間占用敏感的資源池，希望可以自動(dòng)將最不常被訪問的對(duì)象釋放掉，這就可以利用 LinkedHashMap 提供的機(jī)制來實(shí)現(xiàn)，參考下面的示例：

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) { // 實(shí)現(xiàn)自定義刪除策略，否則行為就和普遍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);});}
}

對(duì)于 TreeMap，它的整體順序是由鍵的順序關(guān)系決定的，通過 Comparator 或 Comparable（自然順序）來決定。

我在上一講留給你的思考題提到了，構(gòu)建一個(gè)具有優(yōu)先級(jí)的調(diào)度系統(tǒng)的問題，其本質(zhì)就是個(gè)典型的優(yōu)先隊(duì)列場(chǎng)景，Java 標(biāo)準(zhǔn)庫提供了基于二叉堆實(shí)現(xiàn)的 PriorityQueue，它們都是依賴于同一種排序機(jī)制，當(dāng)然也包括 TreeMap 的馬甲 TreeSet。

類似 hashCode 和 equals 的約定，為了避免模棱兩可的情況，自然順序同樣需要符合一個(gè)約定，就是 compareTo 的返回值需要和 equals 一致，否則就會(huì)出現(xiàn)模棱兩可情況。

我們可以分析 TreeMap 的 put 方法實(shí)現(xiàn)：

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);// ...}

從代碼里，你可以看出什么呢？ 當(dāng)我不遵守約定時(shí)，兩個(gè)不符合唯一性（equals）要求的對(duì)象被當(dāng)作是同一個(gè)（因?yàn)?#xff0c;compareTo 返回 0），這會(huì)導(dǎo)致歧義的行為表現(xiàn)。

2.HashMap 源碼分析

前面提到，HashMap 設(shè)計(jì)與實(shí)現(xiàn)是個(gè)非常高頻的面試題，所以我會(huì)在這進(jìn)行相對(duì)詳細(xì)的源碼解讀，主要圍繞：

HashMap 內(nèi)部實(shí)現(xiàn)基本點(diǎn)分析。

容量（capacity）和負(fù)載系數(shù)（load factor）。

樹化 。

首先，我們來一起看看 HashMap 內(nèi)部的結(jié)構(gòu)，它可以看作是數(shù)組（Node[] table）和鏈表結(jié)合組成的復(fù)合結(jié)構(gòu)，數(shù)組被分為一個(gè)個(gè)桶（bucket），通過哈希值決定了鍵值對(duì)在這個(gè)數(shù)組的尋址；哈希值相同的鍵值對(duì)，則以鏈表形式存儲(chǔ)，你可以參考下面的示意圖。這里需要注意的是，如果鏈表大小超過閾值（TREEIFY_THRESHOLD, 8），圖中的鏈表就會(huì)被改造為樹形結(jié)構(gòu)。

從非拷貝構(gòu)造函數(shù)的實(shí)現(xiàn)來看，這個(gè)表格（數(shù)組）似乎并沒有在最初就初始化好，僅僅設(shè)置了一些初始值而已。

public HashMap(int initialCapacity, float loadFactor){  // ... this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);
}

所以，我們深刻懷疑，HashMap 也許是按照 lazy-load 原則，在首次使用時(shí)被初始化（拷貝構(gòu)造函數(shù)除外，我這里僅介紹最通用的場(chǎng)景）。既然如此，我們?nèi)タ纯?put 方法實(shí)現(xiàn)，似乎只有一個(gè) putVal 的調(diào)用：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

看來主要的秘密似乎藏在 putVal 里面，到底有什么秘密呢？為了節(jié)省空間，我這里只截取了 putVal 比較關(guān)鍵的幾部分。

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ā)現(xiàn)幾個(gè)有意思的地方：

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

resize 方法兼顧兩個(gè)職責(zé)，創(chuàng)建初始存儲(chǔ)表格，或者在容量不滿足需求的時(shí)候，進(jìn)行擴(kuò)容（resize）。

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

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

具體鍵值對(duì)在哈希表中的位置（數(shù)組 index）取決于下面的位運(yùn)算：

i = (n - 1) & hash

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

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

我前面提到的鏈表結(jié)構(gòu)（這里叫 bin），會(huì)在達(dá)到一定門限值時(shí)，發(fā)生樹化，我稍后會(huì)分析為什么 HashMap 需要對(duì) bin 進(jìn)行處理。

可以看到，putVal 方法本身邏輯非常集中，從初始化、擴(kuò)容到樹化，全部都和它有關(guān)，推薦你閱讀源碼的時(shí)候，可以參考上面的主要邏輯。

我進(jìn)一步分析一下身兼多職的 resize 方法，很多朋友都反饋經(jīng)常被面試官追問它的源碼設(shè)計(jì)。

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；// 移動(dòng)到新的數(shù)組結(jié)構(gòu)e數(shù)組結(jié)構(gòu) }

依據(jù) resize 源碼，不考慮極端情況（容量理論最大極限由 MAXIMUM_CAPACITY 指定，數(shù)值為 1<<30，也就是 2 的 30 次方），我們可以歸納為：

門限值等于（負(fù)載因子）x（容量），如果構(gòu)建 HashMap 的時(shí)候沒有指定它們，那么就是依據(jù)相應(yīng)的默認(rèn)常量值。

門限通常是以倍數(shù)進(jìn)行調(diào)整 （newThr = oldThr << 1），我前面提到，根據(jù) putVal 中的邏輯，當(dāng)元素個(gè)數(shù)超過門限大小時(shí)，則調(diào)整 Map 大小。

擴(kuò)容后，需要將老的數(shù)組中的元素重新放置到新的數(shù)組，這是擴(kuò)容的一個(gè)主要開銷來源。

3. 容量、負(fù)載因子和樹化

   前面我們快速梳理了一下 HashMap 從創(chuàng)建到放入鍵值對(duì)的相關(guān)邏輯，現(xiàn)在思考一下，為什么我們需要在乎容量和負(fù)載因子呢？

   這是因?yàn)槿萘亢拓?fù)載系數(shù)決定了可用的桶的數(shù)量，空桶太多會(huì)浪費(fèi)空間，如果使用的太滿則會(huì)嚴(yán)重影響操作的性能。極端情況下，假設(shè)只有一個(gè)桶，那么它就退化成了鏈表，完全不能提供所謂常數(shù)時(shí)間存的性能。

   既然容量和負(fù)載因子這么重要，我們?cè)趯?shí)踐中應(yīng)該如何選擇呢？

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

   負(fù)載因子 * 容量 > 元素?cái)?shù)量
   

   所以，預(yù)先設(shè)置的容量需要滿足，大于“預(yù)估元素?cái)?shù)量 / 負(fù)載因子”，同時(shí)它是 2 的冪數(shù)，結(jié)論已經(jīng)非常清晰了。

   而對(duì)于負(fù)載因子，我建議：

   如果沒有特別需求，不要輕易進(jìn)行更改，因?yàn)?JDK 自身的默認(rèn)負(fù)載因子是非常符合通用場(chǎng)景的需求的。

   如果確實(shí)需要調(diào)整，建議不要設(shè)置超過 0.75 的數(shù)值，因?yàn)闀?huì)顯著增加沖突，降低 HashMap 的性能。

   如果使用太小的負(fù)載因子，按照上面的公式，預(yù)設(shè)容量值也進(jìn)行調(diào)整，否則可能會(huì)導(dǎo)致更加頻繁的擴(kuò)容，增加無謂的開銷，本身訪問性能也會(huì)受影響。

   我們前面提到了樹化改造，對(duì)應(yīng)邏輯主要在 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) {//樹化改造邏輯}
}

上面是精簡(jiǎn)過的 treeifyBin 示意，綜合這兩個(gè)方法，樹化改造的邏輯就非常清晰了，可以理解為，當(dāng) bin 的數(shù)量大于 TREEIFY_THRESHOLD 時(shí)：

如果容量小于 MIN_TREEIFY_CAPACITY，只會(huì)進(jìn)行簡(jiǎn)單的擴(kuò)容。

如果容量大于 MIN_TREEIFY_CAPACITY ，則會(huì)進(jìn)行樹化改造。

那么，為什么 HashMap 要樹化呢？

本質(zhì)上這是個(gè)安全問題。因?yàn)樵谠胤胖眠^程中，如果一個(gè)對(duì)象哈希沖突，都被放置到同一個(gè)桶里，則會(huì)形成一個(gè)鏈表，我們知道鏈表查詢是線性的，會(huì)嚴(yán)重影響存取的性能。

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

今天我從 Map 相關(guān)的幾種實(shí)現(xiàn)對(duì)比，對(duì)各種 Map 進(jìn)行了分析，講解了有序集合類型容易混淆的地方，并從源碼級(jí)別分析了 HashMap 的基本結(jié)構(gòu)，希望對(duì)你有所幫助。

一課一練

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

請(qǐng)你在留言區(qū)寫寫你對(duì)這個(gè)問題的思考，我會(huì)選出經(jīng)過認(rèn)真思考的留言，送給你一份學(xué)習(xí)鼓勵(lì)金，歡迎你與我一起討論。

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

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

今天我從 Map 相關(guān)的幾種實(shí)現(xiàn)對(duì)比，對(duì)各種 Map 進(jìn)行了分析，講解了有序集合類型容易混淆的地方，并從源碼級(jí)別分析了 HashMap 的基本結(jié)構(gòu)，希望對(duì)你有所幫助。

一課一練

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

請(qǐng)你在留言區(qū)寫寫你對(duì)這個(gè)問題的思考，我會(huì)選出經(jīng)過認(rèn)真思考的留言，送給你一份學(xué)習(xí)鼓勵(lì)金，歡迎你與我一起討論。

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