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 的基本結構,希望對你有所幫助。
## 一課一練
關于今天我們討論的題目你做到心中有數了嗎?留一道思考題給你,解決哈希沖突有哪些典型方法呢?
- 前言
- 開篇詞
- 開篇詞 -以面試題為切入點,有效提升你的Java內功
- 模塊一 Java基礎
- 第1講 談談你對Java平臺的理解?
- 第2講 Exception和Error有什么區別?
- 第3講 談談final、finally、 finalize有什么不同?
- 第4講 強引用、軟引用、弱引用、幻象引用有什么區別?
- 第5講 String、StringBuffer、StringBuilder有什么區別?
- 第6講 動態代理是基于什么原理?
- 第7講 int和Integer有什么區別?
- 第8講 對比Vector、ArrayList、LinkedList有何區別?
- 第9講 對比Hashtable、HashMap、TreeMap有什么不同?
- 第10講 如何保證集合是線程安全的? ConcurrentHashMap如何實現高效地線程安全?
- 第11講 Java提供了哪些IO方式? NIO如何實現多路復用?
- 第12講 Java有幾種文件拷貝方式?哪一種最高效?
- 第13講 談談接口和抽象類有什么區別?
- 第14講 談談你知道的設計模式?
- 模塊二 Java進階
- 第15講 synchronized和ReentrantLock有什么區別呢?
- 第16講 synchronized底層如何實現?什么是鎖的升級、降級?
- 第17講 一個線程兩次調用start()方法會出現什么情況?
- 第18講 什么情況下Java程序會產生死鎖?如何定位、修復?
- 第19講 Java并發包提供了哪些并發工具類?
- 第20講 并發包中的ConcurrentLinkedQueue和LinkedBlockingQueue有什么區別?
- 第21講 Java并發類庫提供的線程池有哪幾種? 分別有什么特點?
- 第22講 AtomicInteger底層實現原理是什么?如何在自己的產品代碼中應用CAS操作?
- 第23講 請介紹類加載過程,什么是雙親委派模型?
- 第24講 有哪些方法可以在運行時動態生成一個Java類?
- 第25講 談談JVM內存區域的劃分,哪些區域可能發生OutOfMemoryError?
- 第26講 如何監控和診斷JVM堆內和堆外內存使用?
- 第27講 Java常見的垃圾收集器有哪些?
- 第28講 談談你的GC調優思路?
- 第29講 Java內存模型中的happen-before是什么?
- 第30講 Java程序運行在Docker等容器環境有哪些新問題?
- 模塊三 Java安全基礎
- 第31講 你了解Java應用開發中的注入攻擊嗎?
- 第32講 如何寫出安全的Java代碼?
- 模塊四 Java性能基礎
- 第33講 后臺服務出現明顯“變慢”,談談你的診斷思路?
- 第34講 有人說“Lambda能讓Java程序慢30倍”,你怎么看?
- 第35講 JVM優化Java代碼時都做了什么?
- 模塊五 Java應用開發擴展
- 第36講 談談MySQL支持的事務隔離級別,以及悲觀鎖和樂觀鎖的原理和應用場景?
- 第37講 談談Spring Bean的生命周期和作用域?
- 第38講 對比Java標準NIO類庫,你知道Netty是如何實現更高性能的嗎?
- 第39講 談談常用的分布式ID的設計方案?Snowflake是否受冬令時切換影響?
- 周末福利
- 周末福利 談談我對Java學習和面試的看法
- 周末福利 一份Java工程師必讀書單
- 結束語
- 結束語 技術沒有終點
- 結課測試 Java核心技術的這些知識,你真的掌握了嗎?