本文總結了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的實作原理
- 我們一般用HashMap存盤key-value型別的資料，它的底層是一個陣列，當我們呼叫put方法的時候，首先會對key進行計算得出一個hash值，然后根據hash值計算出存放在陣列上的位置
- 這個時候我們會遇到兩種情況：一是陣列上該位置為空，可以直接放入資料；還有一種情況是該位置已經存放值了，這就發生了哈希沖突，
- 在現在使用較為普遍的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的擴容原理
- 首先得到新的容量值和新的擴容閾值，默認都是原來大小的兩倍，
- 然后根據新容量創建新的陣列
- 最后把元素從舊陣列中遷移到新陣列中
在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進行插入，如果插入的位置不為空，則對當前位置的物件進行加鎖，也就鏈表或紅黑樹的頭節點，加鎖后再進行后續的插入操作，
這樣設計的好處是：
- CAS是十分輕量的加鎖操作，如果能夠直接插入，用CAS能夠大幅度節省加鎖的開銷，
- 如果發生沖突，只用鎖住當前位置的頭結點，理論上陣列的長度有多大，并發操作的執行緒數就能有多少，比原來只能有16個執行緒效率更高，
這道題如果想深挖擴展可以開始往Java多執行緒并發方面扯：synchronized，CAS，Java多執行緒方面我也會出一份總結，有興趣的不妨先點贊關注一波
小結
我感覺面試的時候對集合的考察會偏向實作原理多一些，所以一定要看一遍原始碼，相比于框架的原始碼，集合的原始碼簡直太友好了，在筆試的時候可能還會考一些集合的使用，比如遍歷，排序，比較等等，這些算是Java基礎了，用得多也就熟了，
最后如果你覺得我的回答有問題，歡迎指正！
愿各位有所識訓，共同進步，共勉！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/144541.html
標籤：Java
上一篇：Java Agent入門