HashMap的高頻面試題
前言
關于Map相關，在真實面試中是非常常見的，一般都是以HashMap開始，逐漸展開與深入。今天總結了一些高頻面試題，希望對小伙伴們有幫助。
1. 說一說 HashMap 底層數(shù)據(jù)結構
【參考答案】
在JDK1.8中HashMap 底層是數(shù)組 + 鏈表 + 紅黑樹的數(shù)據(jù)結構，數(shù)組的主要作用是方便快速查找，時間復雜度是 O(1)，默認大小是 16，數(shù)組的下標索引是通過 key 的 hashcode 計算出來的，數(shù)組元素叫做 Node，當多個 key 的 hashcode 一致，但 key 值不同時，單個 Node 就會轉(zhuǎn)化成鏈表，鏈表的查詢復雜度是 O(n)，當鏈表的長度大于等于 8 并且數(shù)組的大小超過 64 時，鏈表就會轉(zhuǎn)化成紅黑樹，紅黑樹的查詢復雜度是 O(log(n))，簡單來說，最壞的查詢次數(shù)相當于紅黑樹的最大深度。
2. HashMap、TreeMap、LinkedHashMap 三者異同點？
【參考答案】
相同點：
三者在特定的情況下，都會使用紅黑樹； 底層的 hash 算法相同； 在迭代的過程中，如果 Map 的數(shù)據(jù)結構被改動，都會報 ConcurrentModificationException 的錯誤。
不同點：
HashMap 數(shù)據(jù)結構以數(shù)組為主，查詢非常快，TreeMap 數(shù)據(jù)結構以紅黑樹為主，利用了紅黑樹左小右大的特點，可以實現(xiàn) key 的排序，LinkedHashMap 在 HashMap 的基礎上增加了鏈表的結構，實現(xiàn)了插入順序訪問和最少訪問刪除兩種策略; 由于三種 Map 底層數(shù)據(jù)結構的差別，導致了三者的使用場景的不同，TreeMap 適合需要根據(jù) key 進行排序的場景，LinkedHashMap 適合按照插入順序訪問，或需要刪除最少訪問元素的場景，剩余場景我們使用 HashMap 即可，我們工作中大部分場景基本都在使用 HashMap； 由于三種 map 的底層數(shù)據(jù)結構的不同，導致上層包裝的 api 略有差別。
3. HashMap 是如何擴容的？
【參考答案】
擴容的時機：
put 時，發(fā)現(xiàn)數(shù)組為空，進行初始化擴容，默認擴容大小為 16; put 成功后，發(fā)現(xiàn)現(xiàn)有數(shù)組大小大于擴容的門閥值時，進行擴容，擴容為老數(shù)組大小的 2 倍;
擴容的門閥是 threshold，每次擴容時 threshold 都會被重新計算，門閥值等于數(shù)組的大小 * 影響因子（0.75）。
新數(shù)組初始化之后，需要將舊數(shù)組的值拷貝到新數(shù)組上，鏈表和紅黑樹都有自己拷貝的方法。
4. 如果發(fā)生hash 沖突時怎么辦？
【參考答案】
hash 沖突指的是 key 值的 hashcode 計算相同，但 key 值不同的情況。
如果桶中元素原本只有一個或已經(jīng)是鏈表了，新增元素直接追加到鏈表尾部；
如果桶中元素已經(jīng)是鏈表，并且鏈表個數(shù)大于等于 8 時，此時有兩種情況：
如果此時數(shù)組大小小于 64，數(shù)組再次擴容，鏈表不會轉(zhuǎn)化成紅黑樹; 如果數(shù)組大小大于 64 時，鏈表就會轉(zhuǎn)化成紅黑樹。
這里不僅僅判斷鏈表個數(shù)大于等于 8，還判斷了數(shù)組大小，數(shù)組容量小于 64 沒有立即轉(zhuǎn)化的原因，猜測主要是因為紅黑樹占用的空間比鏈表大很多，轉(zhuǎn)化也比較耗時，所以數(shù)組容量小的情況下沖突嚴重，我們可以先嘗試擴容，看看能否通過擴容來解決沖突的問題。
5. 為什么鏈表個數(shù)大于等于 8 時，鏈表要轉(zhuǎn)化成紅黑樹了？
【參考答案】
當鏈表個數(shù)太多了，遍歷可能比較耗時，轉(zhuǎn)化成紅黑樹，可以使遍歷的時間復雜度降低，但轉(zhuǎn)化成紅黑樹，有空間和轉(zhuǎn)化耗時的成本，我們通過泊松分布公式計算，正常情況下，鏈表個數(shù)出現(xiàn) 8 的概念不到千萬分之一，所以說正常情況下，鏈表都不會轉(zhuǎn)化成紅黑樹，這樣設計的目的，是為了防止非正常情況下，比如 hash 算法出了問題時，導致鏈表個數(shù)輕易大于等于 8 時，仍然能夠快速遍歷。
6. 那么紅黑樹什么時候會轉(zhuǎn)變成鏈表呢？
【參考答案】
當節(jié)點的個數(shù)小于等于 6 時，紅黑樹會自動轉(zhuǎn)化成鏈表，主要還是考慮紅黑樹的空間成本問題，當節(jié)點個數(shù)小于等于 6 時，遍歷鏈表也很快，所以紅黑樹會重新變成鏈表。
7. HashMap 在 put 時，如果數(shù)組中已經(jīng)有了這個 key，我不想把 value 覆蓋怎么辦？取值時，如果得到的 value 是空時，想返回默認值怎么辦？
【參考答案】
如果數(shù)組有了 key，但不想覆蓋 value ，可以選擇 putIfAbsent 方法，這個方法有個內(nèi)置變量 onlyIfAbsent，內(nèi)置是 true ，就不會覆蓋，我們平時使用的 put 方法，內(nèi)置 onlyIfAbsent 為 false，是允許覆蓋的。
取值時，如果為空，想返回默認值，可以使用 getOrDefault 方法，方法第一參數(shù)為 key，第二個參數(shù)為你想返回的默認值，如 map.getOrDefault(“2”,“0”)，當 map 中沒有 key 為 2 的值時，會默認返回 0，而不是空。
8. DTO 作為 Map 的 key 時，有無需要注意的點？
【參考答案】
DTO 就是一個數(shù)據(jù)載體，可以看做擁有很多屬性的 Java 類，我們可以對這些屬性進行 get、set 操作。
看是什么類型的 Map，如果是 HashMap 的話，一定需要覆寫 equals 和 hashCode 方法，因為在 get 和 put 的時候，需要通過 equals 方法進行相等的判斷；如果是 TreeMap 的話，DTO 需要實現(xiàn) Comparable 接口，因為 TreeMap 會使用 Comparable 接口進行判斷 key 的大小；如果是 LinkedHashMap 的話，和 HashMap 一樣的。
9. LinkedHashMap 中的 LRU 是什么意思，是如何實現(xiàn)的？
【參考答案】
LRU ，英文全稱：Least recently used，中文叫做最近最少訪問，在 LinkedHashMap 中，也叫做最少訪問刪除策略，我們可以通過 removeEldestEntry 方法設定一定的策略，使最少被訪問的元素，在適當?shù)臅r機被刪除，原理是在 put 方法執(zhí)行的最后，LinkedHashMap 會去檢查這種策略，如果滿足策略，就刪除頭節(jié)點。
保證頭節(jié)點就是最少訪問的元素的原理是：LinkedHashMap 在 get 的時候，都會把當前訪問的節(jié)點，移動到鏈表的尾部，慢慢的，就會使頭部的節(jié)點都是最少被訪問的元素。
10. 什么推薦 TreeMap 的元素最好都實現(xiàn) Comparable 接口？但 key 是 String 的時候，我們卻沒有額外的工作呢？
【參考答案】
因為 TreeMap 的底層就是通過排序來比較兩個 key 的大小的，所以推薦 key 實現(xiàn) Comparable 接口，是為了往你希望的排序順序上發(fā)展， 而 String 本身已經(jīng)實現(xiàn)了 Comparable 接口，所以使用 String 時，我們不需要額外的工作，不僅僅是 String ，其他包裝類型也都實現(xiàn)了 Comparable 接口，如 Long、Double、Short 等等。
總結
Map 的面試題主要是 HashMap 為主，會問很多源碼方面的東西，TreeMap 和 LinkedHashMap 主要以功能和場景為主，作為加分項。Map 的面試題型很多，但只要弄懂原理，題目再多變化，回答起來都會比較簡單。