本文總結了Java集合容器的經典面試題，所有題目我都給出了自己思考，適合面試前複習掃盲使用。我不能保證裡面包含了所有集合面試題，但只要認真深挖好每一道題，做到觸類旁通，就能以不變應萬變。

• 大綱：
• 概述型面試題
• List
• Map
• 小結

概述類面試題

1. 請說一下Java容器集合的分類，各自的繼承結構

• Java中的容器集合分為兩大陣營，一個是Collection，一個是Map
• Collection下分為Set，List，Queue
• Set的常用實現類有HashSet，TreeSet等
• List的常用實現類有ArrayList，LinkedList等
• Queue的常用實現類有LinkedList，ArrayBlockingQueue等
• Map下沒有進一步分類，它的常用實現類有HashMap，ConcurrentHashMap等

能把上面的基本框架答出來基本就沒問題了，對於各種類型我只列舉了一些實際工作中常用的實現類。但其實在Set，List和Queue下還有更細的劃分，如果想要在面試時表現一番，那得對著JDK好好背一背了>_<

2. 請談一談Java集合中的fail-fast和fail-safe機制

fail-fast是一種錯誤檢測機制，Java在適合單線程使用的集合容器中很好地實現了fail-fast機制，舉一個簡單的例子：在多線程併發環境下，A線程在通過迭代器遍歷一個ArrayList集合，B線程同時對該集合進行增刪元素操作，這個時候線程A就會拋出併發修改異常，中斷正常執行的邏輯。

而fail-safe機制更像是一種對fail-fast機制的補充，它被廣泛地實現在各種併發容器集合中。回頭看上面的例子，如果線程A遍歷的不是一個ArrayList，而是一個CopyOnWriteArrayList，則符合fail-safe機制，線程B可以同時對該集合的元素進行增刪操作，線程A不會拋出任何異常。

要理解這兩種機制的表象，我們得瞭解這兩種機制背後的實現原理：

我們同樣用ArrayList解釋fail-fast背後的原理：首先ArrayList自身會維護一個modCount變數，每當進行增刪元素等操作時，modCount變數都會進行自增。當使用迭代器遍歷ArrayList時，迭代器會新維護一個初始值等於modCount的expectedModCount變數，每次獲取下一個元素的時候都會去檢查expectModCount和modCount是否相等。在上面舉的例子中，由於B線程增刪元素會導致modCount自增，當A線程遍歷元素時就會發現兩個變數不等，從而拋出異常。

CopyOnWriteArrayList所實現的fail-safe在上述情況下沒有拋出異常，它的原理是：當使用迭代器遍歷集合時，會基於原數組拷貝出一個新的數組（ArrayList的底層是數組），後續的遍歷行為在新數組上進行。所以線程B同時進行增刪操作不會影響到線程A的遍歷行為。

這種題目我覺得要先答出核心原理，如果你對多線程和單線程下容器的使用有自己的見解，可以考慮多聊點。

3. 如何一邊遍歷一邊刪除Collection中的元素？

使用集合迭代器自身的remove方法進行刪除

Iterator<Integer> it = list.iterator();
while(it.hasNext()){
   *// do something*
   it.remove();
}

可能筆試考的更多，算是Java的基本常識吧

List類面試題

4. 談談ArrayList和LinkedList的區別

本質的區別來源於兩者的底層實現：ArrayList的底層是數組，LinkedList的底層是雙向鏈表。

數組擁有O(1)的查詢效率，可以通過下標直接定位元素；鏈表在查詢元素的時候只能通過遍歷的方式查詢，效率比數組低。

數組增刪元素的效率比較低，通常要伴隨拷貝數組的操作；鏈表增刪元素的效率很高，只需要調整對應位置的指針即可。

以上是數組和鏈表的通俗對比，在日常的使用中，兩者都能很好地在自己的適用場景發揮作用。

比如說我們常常用ArrayList代替數組，因為封裝了許多易用的api，而且它內部實現了自動擴容機制，由於它內部維護了一個當前容量的指針size，直接往ArrayList中添加元素的時間複雜度是O(1)的，使用非常方便。

而LinkedList常常被用作Queue隊列的實現類，由於底層是雙向鏈表，能夠輕鬆地提供先入先出的操作。

我覺得可以分兩部分答，一個是數組與鏈表底層實現的不同，另一個是答ArrayList和LinkedList的實現細節。

5. 談談ArrayList和Vector的區別

兩者的底層實現相似，關鍵的不同在於Vector的對外提供操作的方法都是用synchronized修飾的，也就是說Vector在併發環境下是線程安全的，而ArrayList在併發環境下可能會出現線程安全問題。

由於Vector的方法都是同步方法，執行起來會在同步上消耗一定的性能，所以在單線程環境下，Vector的性能是不如ArrayList的

除了線程安全這點本質區別外，還有一個實現上的小細節區別：ArrayList每次擴容的大小為原來的1.5倍；Vector可以指定擴容的大小，預設是原來大小的兩倍。

感覺可以順帶談談多線程環境下ArrayList的替代品，比如CopyOnWriteArrayList，但是要談談優缺點。

6. 為什麼ArrayList的elementData數組要加上transient修飾

由於ArrayList有自動擴容機制，所以ArrayList的elementData數組大小往往比現有的元素數量大，如果不加transient直接序列化的話會把數組中空餘的位置也序列化了，浪費不少的空間。

ArrayList中重寫了序列化和反序列化對應的writeObject和readObject方法，在遍曆數組元素時，以size作為結束標誌，只序列化ArrayList中已經存在的元素。

細節題

Map類面試題

HashMap死亡連環Call即將來臨，看爽了記得點個贊啊

7. 請介紹一下HashMap的實現原理

1. 我們一般用HashMap存儲key-value類型的數據，它的底層是一個數組，當我們調用put方法的時候，首先會對key進行計算得出一個hash值，然後根據hash值計算出存放在數組上的位置
2. 這個時候我們會遇到兩種情況：一是數組上該位置為空，可以直接放入數據；還有一種情況是該位置已經存放值了，這就發生了哈希衝突。
3. 在現在使用較為普遍的JDK1.8中是這樣處理哈希衝突的：先用鏈表把衝突的元素串起來，如果鏈表的長度達到了8，並且哈希表的長度大於64，則把鏈表轉為紅黑樹。（在JDK1.7中沒有轉化為紅黑樹這一步，只用鏈表解決衝突）

先熱身

8. HashMap是怎樣確定key存放在數組的哪個位置的？

JDK1.8

首先計算key的hash值，計算過程是：先得到key的hashCode（int類型，4位元組），然後把hashCode的高16位與低16位進行異或，得到key的hash值。

接下來用key的hash值與數組長度減一的值進行按位與操作，得到key在數組中對應的下標。

追問：為什麼計算key的hash時要把hashCode的高16位與低16位進行異或？（變式：為什麼不直接用key的hashCode）

計算key在數組中的下標時，是通過hash值與數組長度減一的值進行按位與操作的。由於數組的長度通常不會超過2^16，所以hash值的高16位通常參與不了這個按位與操作。

為了讓hashCode的高16位能夠參與到按位與操作中，所以把hashCode的高16位與低16位進行異或操作，使得高16位的影響能夠均勻稀釋到低16位中，使得計算key位置的操作能夠充分散列均勻。

9. 為什麼要把鏈表轉為紅黑樹，閾值為什麼是8？

在極端情況下，比如說key的hashCode()返回的值不合理，或者多個密鑰共用一個hashCode，很有可能會在同一個數組位置產生嚴重的哈希衝突。

這種情況下，如果我們仍然使用使用鏈表把多個衝突的元素串起來，這些元素的查詢效率就會從O(1)下降為O(N)。為了能夠在這種極端情況下仍保證較為高效的查詢效率，HashMap選擇把鏈表轉換為紅黑樹，紅黑樹是一種常用的平衡二叉搜索樹，添加，刪除，查找元素等操作的時間複雜度均為O(logN)

至於閾值為什麼是8，這是HashMap的作者根據概率論的知識得到的。當key的哈希碼分佈均勻時，數組同一個位置上的元素數量是成泊松分佈的，同一個位置上出現8個元素的概率已經接近千分之一了，這側面說明如果鏈表的長度達到了8，key的hashCode()肯定是出了大問題，這個時候需要紅黑樹來保證性能，所以選擇8作為閾值。

追問：為什麼紅黑樹轉換回鏈表的閾值不是7而是6呢？

如果是7的話，那麼鏈表和紅黑樹之間的切換範圍值就太小了。如果我的鏈表長度不停地在7和8之間切換，那豈不是得來回變換形態？所以選擇6是一種折中的考慮。

10. 請說一下HashMap的擴容原理

1. 首先得到新的容量值和新的擴容閾值，預設都是原來大小的兩倍。
2. 然後根據新容量創建新的數組
3. 最後把元素從舊數組中遷移到新數組中

在JDK1.7中，遷移數據的時候所有元素都重新計算了hash，並根據新的hash重新計算數組中的位置。

在JDK1.8中，這個過程進行了優化：如果當前節點是單獨節點（後面沒有接著鏈表），則根據該節點的hash值與新容量減一的值按位與得到新的地址。

如果當前節點後面帶有鏈表，則根據每個節點的hash值與舊數組容量進行按位與的結果進行劃分。如果得到的值為0，這些元素會被分配回原來的位置；如果得到的結果不為0，則分配到新位置，新位置的下標為當前位置下標加上舊數組容量。

還有一種情況是當前節點是樹節點，那麼會調用一個專門的拆分方法進行拆分。

追問：為什麼HashMap不支持動態縮容？

開放性題目？以下是個人見解：

如果要支持動態縮容，可能就要把縮容安排在remove方法里，這樣可能會導致remove方法的時間複雜度從O(1)上升為O(N)。

還有一點可能和我們編寫Java代碼的習慣有關：由於Java有自動垃圾回收機制，讓我們得以可勁地new對象，Java也預設了我們這種吃飯不收拾盤子的行為。既然對象會被回收，HashMap動態縮容在這樣的大環境下似乎就顯得沒那麼重要了，這可以說是一種空間換時間的策略吧。

11. 為什麼HashMap中適合用Integer，String這樣的基礎類型作為key？

因為這些基礎類內部已經重寫了hashCode和equals方法，遵守了HashMap內部的規範。

追問：如果要用我們自己實現的類作為key，要註意什麼？

一定要重寫hashCode()和equals()方法，而且要遵從以下規則：

equals()是我們判斷兩個對象是否相同的依據，如果我們重寫了equals方法，用自己的邏輯去判斷兩個對象是否相同，那麼一定要保證：

兩個equals()返回true的對象，一定要返回相同的hashCode。

這樣，在HashMap的put方法中才能正確判斷key是否相同。

不是經常有一個問題嘛，兩個對象hashCode相同，equals一定返回true嗎？答案肯定是否的，這和你的設計密切相關：如果在你的編程思路中這兩個對象是不同的，那麼就算恰巧兩個對象的hashCode相同，equals也應該返回false。

12. 為什麼HashMap數組的長度是2的冪次方？

因為這樣能夠提高根據key計算數組位置的效率。

HashMap根據key計算數組位置的演算法是：用key的hash值與數組長度減1的值進行按位與操作。

在我們正常人的思維中，獲取數組的某個位置最直接的方法是對數組的長度取餘數。但是如果被除數是2的冪次方，那麼這個對數組長度取餘的方法就等價於對數組長度減一的值進行按位與操作。

在電腦中，位運算的效率遠高於取模運算，所以為了提高效率，把數組的長度設為2的冪次方。

13. HashMap與HashTable有什麼區別？

在JDK1.7之前，兩者的實現極為相似，最大的區別在於HashTable的方法都用synchronized關鍵字修飾起來了，表明它是線程安全的。

但是由於直接在方法上加synchronized關鍵字的同步效率較低，在併發情況下，官方推薦我們使用ConcurrentHashMap。

所以我們看到在JDK1.8中，官方甚至沒有對HashTable進行鏈表轉樹這樣的優化，HashTable已經不被推薦使用了。

14. 請說一下ConcurrentHashMap的實現原理

在JDK1.7中ConcurrentHashMap採用了一種分段鎖的機制，它的底層實現是一個segment數組，每個segment的底層結構和HashMap相似，也是數組加鏈表。

當對segment裡面的元素進行操作之前，需要獲得該segment獨有的一把ReentrantLock。ConcurrentHashMap如果不進行手動設置的話，預設有16個segment，可以支持16個線程對16個不同的segment進行併發寫操作。

在JDK1.8之後摒棄了segment這種臃腫的設計，新的實現和HashMap非常相似，底層用的也是數組加鏈表加紅黑樹。

在新實現中，在put方法里使用了CAS + synchronized進行同步。如果插入元素的位置為空，則使用CAS進行插入。如果插入的位置不為空，則對當前位置的對象進行加鎖，也就鏈表或紅黑樹的頭節點，加鎖後再進行後續的插入操作。

這樣設計的好處是：

1. CAS是十分輕量的加鎖操作，如果能夠直接插入，用CAS能夠大幅度節省加鎖的開銷。
2. 如果發生衝突，只用鎖住當前位置的頭結點，理論上數組的長度有多大，併發操作的線程數就能有多少，比原來只能有16個線程效率更高。

這道題如果想深挖擴展可以開始往Java多線程併發方面扯：synchronized，CAS。Java多線程方面我也會出一份總結，有興趣的不妨先點贊關註一波

小結

我感覺面試的時候對集合的考察會偏向實現原理多一些，所以一定要看一遍源碼，相比於框架的源碼，集合的源碼簡直太友好了。在筆試的時候可能還會考一些集合的使用，比如遍歷，排序，比較等等，這些算是Java基礎了，用得多也就熟了。

最後如果你覺得我的回答有問題，歡迎指正！

願各位有所收穫，共同進步，共勉！