## 10 Map源碼會問哪些面試題 ## 引導語 Map 在面試中，占據了很大一部分的面試題目，其中以 HashMap 為主，這些面試題目有的可以說得清楚，有的很難說清楚，如果是面對面面試的話，建議畫一畫。 ### 1 Map 整體數據結構類問題 #### 1.1 說一說 HashMap 底層數據結構 答：HashMap 底層是數組 + 鏈表 + 紅黑樹的數據結構，數組的主要作用是方便快速查找，時間復雜度是 O(1)，默認大小是 16，數組的下標索引是通過 key 的 hashcode 計算出來的，數組元素叫做 Node，當多個 key 的 hashcode 一致，但 key 值不同時，單個 Node 就會轉化成鏈表，鏈表的查詢復雜度是 O(n)，當鏈表的長度大于等于 8 并且數組的大小超過 64 時，鏈表就會轉化成紅黑樹，紅黑樹的查詢復雜度是 O(log(n))，簡單來說，最壞的查詢次數相當于紅黑樹的最大深度。 #### 1.2 HashMap、TreeMap、LinkedHashMap 三者有啥相同點，有啥不同點？ 答：相同點： 1. 三者在特定的情況下，都會使用紅黑樹； 2. 底層的 hash 算法相同； 3. 在迭代的過程中，如果 Map 的數據結構被改動，都會報 ConcurrentModificationException 的錯誤。 不同點： 1. HashMap 數據結構以數組為主，查詢非常快，TreeMap 數據結構以紅黑樹為主，利用了紅黑樹左小右大的特點，可以實現 key 的排序，LinkedHashMap 在 HashMap 的基礎上增加了鏈表的結構，實現了插入順序訪問和最少訪問刪除兩種策略; 2. 由于三種 Map 底層數據結構的差別，導致了三者的使用場景的不同，TreeMap 適合需要根據 key 進行排序的場景，LinkedHashMap 適合按照插入順序訪問，或需要刪除最少訪問元素的場景，剩余場景我們使用 HashMap 即可，我們工作中大部分場景基本都在使用 HashMap； 3. 由于三種 map 的底層數據結構的不同，導致上層包裝的 api 略有差別。 #### 1.3 說一下 Map 的 hash 算法 ``` static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` key 在數組中的位置公式：tab[(n - 1) & hash] 如上代碼是 HashMap 的hash 算法。 這其實是一個數學問題，源碼中就是通過以上代碼來計算 hash 的，首先計算出 key 的 hashcode，因為 key 是 Object，所以會根據 key 的不同類型進行 hashcode 的計算，接著計算 h ^ (h >>> 16) ，這么做的好處是使大多數場景下，算出來的 hash 值比較分散。 一般來說，hash 值算出來之后，要計算當前 key 在數組中的索引下標位置時，可以采用取模的方式，就是索引下標位置 = hash 值 % 數組大小，這樣做的好處，就是可以保證計算出來的索引下標值可以均勻的分布在數組的各個索引位置上，但取模操作對于處理器的計算是比較慢的，數學上有個公式，當 b 是 2 的冪次方時，a % b = a &（b-1），所以此處索引位置的計算公式我們可以更換為： (n-1) & hash。 此問題可以延伸出三個小問題： 1：為什么不用 key % 數組大小，而是需要用 key 的 hash 值 % 數組大小。 答：如果 key 是數字，直接用 key % 數組大小是完全沒有問題的，但我們的 key 還有可能是字符串，是復雜對象，這時候用 字符串或復雜對象 % 數組大小是不行的，所以需要先計算出 key 的 hash 值。 2：計算 hash 值時，為什么需要右移 16 位？ 答：hash 算法是 h ^ (h >>> 16)，為了使計算出的 hash 值更分散，所以選擇先將 h 無符號右移 16 位，然后再于 h 異或時，就能達到 h 的高 16 位和低 16 位都能參與計算，減少了碰撞的可能性。 3：為什么把取模操作換成了 & 操作？ 答：key.hashCode() 算出來的 hash 值還不是數組的索引下標，為了隨機的計算出索引的下表位置，我們還會用 hash 值和數組大小進行取模，這樣子計算出來的索引下標比較均勻分布。 取模操作處理器計算比較慢，處理器對 & 操作就比較擅長，換成了 & 操作，是有數學上證明的支撐，為了提高了處理器處理的速度。 4：為什么提倡數組大小是 2 的冪次方？ 答：因為只有大小是 2 的冪次方時，才能使 hash 值 % n(數組大小) == (n-1) & hash 公式成立。 #### 1.4 為解決 hash 沖突，大概有哪些辦法。 答：1：好的 hash 算法，細問的話復述一下上題的 hash 算法; 2：自動擴容，當數組大小快滿的時候，采取自動擴容，可以減少 hash 沖突; 3：hash 沖突發生時，采用鏈表來解決; 4：hash 沖突嚴重時，鏈表會自動轉化成紅黑樹，提高遍歷速度。 網上列舉的一些其它辦法，如開放定址法，盡量不要說，因為這些方法資料很少，實戰用過的人更少，如果你沒有深入研究的話，面試官讓你深入描述一下很難說清楚，反而留下不好的印象，說 HashMap 現有的措施就足夠了。 ### 2 HashMap 源碼細節類問題 #### 2.1 HashMap 是如何擴容的？ 答：擴容的時機： 1. put 時，發現數組為空，進行初始化擴容，默認擴容大小為 16; 2. put成功后，發現現有數組大小大于擴容的門閥值時，進行擴容，擴容為老數組大小的 2 倍; 擴容的門閥是 threshold，每次擴容時 threshold 都會被重新計算，門閥值等于數組的大小 * 影響因子（0.75）。 新數組初始化之后，需要將老數組的值拷貝到新數組上，鏈表和紅黑樹都有自己拷貝的方法。 #### 2.2 hash 沖突時怎么辦？ 答：hash 沖突指的是 key 值的 hashcode 計算相同，但 key 值不同的情況。 如果桶中元素原本只有一個或已經是鏈表了，新增元素直接追加到鏈表尾部； 如果桶中元素已經是鏈表，并且鏈表個數大于等于 8 時，此時有兩種情況： 1. 如果此時數組大小小于 64，數組再次擴容，鏈表不會轉化成紅黑樹; 2. 如果數組大小大于 64 時，鏈表就會轉化成紅黑樹。 這里不僅僅判斷鏈表個數大于等于 8，還判斷了數組大小，數組容量小于 64 沒有立即轉化的原因，猜測主要是因為紅黑樹占用的空間比鏈表大很多，轉化也比較耗時，所以數組容量小的情況下沖突嚴重，我們可以先嘗試擴容，看看能否通過擴容來解決沖突的問題。 #### 2.3 為什么鏈表個數大于等于 8 時，鏈表要轉化成紅黑樹了？ 答：當鏈表個數太多了，遍歷可能比較耗時，轉化成紅黑樹，可以使遍歷的時間復雜度降低，但轉化成紅黑樹，有空間和轉化耗時的成本，我們通過泊松分布公式計算，正常情況下，鏈表個數出現 8 的概念不到千萬分之一，所以說正常情況下，鏈表都不會轉化成紅黑樹，這樣設計的目的，是為了防止非正常情況下，比如 hash 算法出了問題時，導致鏈表個數輕易大于等于 8 時，仍然能夠快速遍歷。 延伸問題：紅黑樹什么時候轉變成鏈表。 答：當節點的個數小于等于 6 時，紅黑樹會自動轉化成鏈表，主要還是考慮紅黑樹的空間成本問題，當節點個數小于等于 6 時，遍歷鏈表也很快，所以紅黑樹會重新變成鏈表。 #### 2.4 HashMap 在 put 時，如果數組中已經有了這個 key，我不想把 value 覆蓋怎么辦？取值時，如果得到的 value 是空時，想返回默認值怎么辦？ 答：如果數組有了 key，但不想覆蓋 value ，可以選擇 putIfAbsent 方法，這個方法有個內置變量 onlyIfAbsent，內置是 true ，就不會覆蓋，我們平時使用的 put 方法，內置 onlyIfAbsent 為 false，是允許覆蓋的。 取值時，如果為空，想返回默認值，可以使用 getOrDefault 方法，方法第一參數為 key，第二個參數為你想返回的默認值，如 map.getOrDefault(“2”,“0”)，當 map 中沒有 key 為 2 的值時，會默認返回 0，而不是空。 #### 2.5 通過以下代碼進行刪除，是否可行？ ``` HashMap<String,String > map = Maps.newHashMap(); map.put("1","1"); map.put("2","2"); map.forEach((s, s2) -> map.remove("1")); ``` 答：不行，會報錯誤 ConcurrentModificationException，原因如下圖：  建議使用迭代器的方式進行刪除，原理同 ArrayList 迭代器原理，我們在《List 源碼會問那些面試題》中有說到。 #### 2.6 描述一下 HashMap get、put 的過程 答：我們在源碼解析中有說，可以詳細描述下源碼的實現路徑，說不清楚的話，可以畫一畫。 ### 3 其它 Map 面試題 #### 3.1 DTO 作為 Map 的 key 時，有無需要注意的點？ 答：DTO 就是一個數據載體，可以看做擁有很多屬性的 Java 類，我們可以對這些屬性進行 get、set 操作。 看是什么類型的 Map，如果是 HashMap 的話，一定需要覆寫 equals 和 hashCode 方法，因為在 get 和 put 的時候，需要通過 equals 方法進行相等的判斷；如果是 TreeMap 的話，DTO 需要實 現 Comparable 接口，因為 TreeMap 會使用 Comparable 接口進行判斷 key 的大小；如果是 LinkedHashMap 的話，和 HashMap 一樣的。 #### 3.2 LinkedHashMap 中的 LRU 是什么意思，是如何實現的。 答：LRU ，英文全稱：Least recently used，中文叫做最近最少訪問，在 LinkedHashMap 中，也叫做最少訪問刪除策略，我們可以通過 removeEldestEntry 方法設定一定的策略，使最少被訪問的元素，在適當的時機被刪除，原理是在 put 方法執行的最后，LinkedHashMap 會去檢查這種策略，如果滿足策略，就刪除頭節點。 保證頭節點就是最少訪問的元素的原理是：LinkedHashMap 在 get 的時候，都會把當前訪問的節點，移動到鏈表的尾部，慢慢的，就會使頭部的節點都是最少被訪問的元素。 #### 3.3 為什么推薦 TreeMap 的元素最好都實現 Comparable 接口？但 key 是 String 的時候，我們卻沒有額外的工作呢？ 答：因為 TreeMap 的底層就是通過排序來比較兩個 key 的大小的，所以推薦 key 實現 Comparable 接口，是為了往你希望的排序順序上發展， 而 String 本身已經實現了 Comparable 接口，所以使用 String 時，我們不需要額外的工作，不僅僅是 String ，其他包裝類型也都實現了 Comparable 接口，如 Long、Double、Short 等等。 ## 總結 Map 的面試題主要是 HashMap 為主，會問很多源碼方面的東西，TreeMap 和 LinkedHashMap 主要以功能和場景為主，作為加分項。 Map 的面試題型很多，但只要弄懂原理，題目再多變化，回答起來都會比較簡單。