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 三者有啥相同點，有啥不同點？
答：相同點：
三者在特定的情況下，都會使用紅黑樹；底層的 hash 算法相同；在迭代的過程中，如果 Map 的數據結構被改動，都會報 ConcurrentModificationException 的錯誤。不同點：
HashMap 數據結構以數組為主，查詢非常快，TreeMap 數據結構以紅黑樹為主，利用了紅黑樹左小右大的特點，可以實現 key 的排序，LinkedHashMap 在 HashMap 的基礎上增加了鍊表的結構，實現了插入順序訪問和最少訪問刪除兩種策略;由於三種 Map 底層數據結構的差別，導致了三者的使用場景的不同，TreeMap 適合需要根據 key 進行排序的場景，LinkedHashMap 適合按照插入順序訪問，或需要刪除最少訪問元素的場景，剩餘場景我們使用 HashMap 即可，我們工作中大部分場景基本都在使用 HashMap；由於三種 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 是如何擴容的？
答：擴容的時機：
put 時，發現數組為空，進行初始化擴容，默認擴容大小為 16;put 成功後，發現現有數組大小大於擴容的門閥值時，進行擴容，擴容為老數組大小的 2 倍;擴容的門閥是 threshold，每次擴容時 threshold 都會被重新計算，門閥值等於數組的大小 * 影響因子（0.75）。
新數組初始化之後，需要將老數組的值拷貝到新數組上，鍊表和紅黑樹都有自己拷貝的方法。
2.2 hash 衝突時怎麼辦？
答：hash 衝突指的是 key 值的 hashcode 計算相同，但 key 值不同的情況。
如果桶中元素原本只有一個或已經是鍊表了，新增元素直接追加到鍊表尾部；
如果桶中元素已經是鍊表，並且鍊表個數大於等於 8 時，此時有兩種情況：
如果此時數組大小小於 64，數組再次擴容，鍊表不會轉化成紅黑樹;如果數組大小大於 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，原因如下圖：
總結
Map 的面試題主要是 HashMap 為主，會問很多源碼方面的東西，TreeMap 和 LinkedHashMap 主要以功能和場景為主，作為加分項。Map 的面試題型很多，但只要弄懂原理，題目再多變化，回答起來都會比較簡單。