Java集合框架面試題

常見集合

集合可以看作是一種容器，用來存盤物件資訊，
陣列和集合的區別：
（1）陣列長度不可變化而且無法保存具有映射關系的資料；集合類用于保存數量不確定的資料，以及保存具有映射關系的資料，
（2）陣列元素既可以是基本型別的值，也可以是物件；集合只能保存物件，
Java集合類主要由兩個介面Collection和Map，
Collection介面派生出來的常用集合有：

• （主要）ArrayList、LinkedList
• （次要）HashSet、TreeSet、Vector(過去式)
  Map介面派生出來的常用集合有：
• （主要）HashMap
• （次要）TreeMap

簡要說明List、Set、Map的區別
List集合：有序、可重復集合，集合中每個元素都有其對應的順序索引，
實作List介面的集合主要有：ArrayList、LinkedList、Vector，

Set集合：有序，不可重復集合，重復元素會覆寫掉，
實作Set介面的集合主要有：HashSet、TreeSet，

Map集合：以鍵值對的方式存盤，元素無存入順序，元素不可重復，重復元素會覆寫掉，key、value都可以為null
實作Map介面的集合主要有：HashMap、HashTable、TreeMap，

（1）ArrayList
ArrayList是一個動態陣列，也是我們最常用的集合，是List類的典型實作，它允許任何符合規則的元素插入甚至包括null，每一個ArrayList都有一個初始容量10，該容量代表了陣列的大小，隨著容器中的元素不斷增加，容器的大小也會隨著增加，在每次向容器中增加元素的同時都會進行容量檢查，當快溢位時，就會進行擴容操作，所以如果我們明確所插入元素的多少，最好指定一個初始容量值，避免過多的進行擴容操作而浪費時間、效率，

（2）LinkedList
LinkedList是List介面的另一個實作，除了可以根據索引訪問集合元素外，LinkedList還實作了Deque介面，可以當作雙端佇列來使用，也就是說，既可以當作“堆疊”使用，又可以當作佇列使用，

（3）Vector
與ArrayList相似，但是Vector是同步的，所以說Vector是執行緒安全的動態陣列，它的操作與ArrayList幾乎一樣，

（4）HashSet
HashSet是不能保證元素的順序，不是執行緒同步的集合，如果多執行緒操作HashSet集合，則應通過代碼來保證其同步，集合元素值可以是null

（5）TreeSet
TreeSet可以保證元素處于排序狀態，它采用紅黑樹的資料結構來存盤集合元素，TreeSet支持兩種排序方法：自然排序和定制排序，默認采用自然排序，

（6）HashMap
HashMap基于hashing原理，通過put()和get()方法存盤和獲取物件，當我們將鍵值對傳遞給put()方法時，它呼叫建物件的hashCode()方法來計算hashCode值，然后找到bucket位置來儲存值物件，當獲取物件時，通過建物件的equals()方法找到正確的鍵值對，然后回傳物件，HashMap使用鏈表來解決碰撞問題，當發生碰撞了，物件將會存盤在鏈表的下一個節點中，

（7）HashTable
與HashMap的關系完全類似于ArrayList與Vertor，HashMap是執行緒不安全，HashTable是執行緒安全的，HashMap可以使用null值最為key或value；Hashtable不允許使用null值作為key和value，如果把null放進HashTable中，將會發生空指標例外，

（8）TreeMap
一個紅黑樹的資料結構，每個key-value對作為紅黑樹的一個節點，TreeMap存盤key-value對時，需要根據key對節點進行排序，

面試常問

1. ArrayList和Vector的區別，

Vector：執行緒安全，資料增長原來的2倍，
ArrayList：非執行緒安全，資料增長沒有明確規定，從原始碼來看是增長原來的1.5倍，

2. HashMap和HashTable的區別，

• 執行緒安全性不同：HashMap非執行緒安全，HashTable執行緒安全
• 繼承的父類不同：Hashtable繼承自Dictionary類，而HashMap繼承自AbstractMap類，但二者都實作了Map介面，
• key和value是否允許null值：Hashtable中，key和value都不允許出現null值
• 兩個遍歷方式的內部實作上不同：鏈接: Map集合遍歷

3. ArrayList,Vector,LinkedList的存盤性能和特性，

ArrayList和Vector都是使用陣列方式存盤資料，此陣列元素數大于實際存盤的資料以便增加和插入元素，它們都允許直接按序號索引元素，但是插入元素要涉及陣列元素移動等記憶體操作，所以索引資料快而插入資料慢，Vector由于使用了synchronized方法執行緒安全，性能上比ArrayList差，
而LinkedList使用雙向鏈表實作存盤，按序號索引資料需要進行前向或后向遍歷，所以索引資料較慢，但是插入資料時只需要記錄本項的前后項即可，所以插入速度較快，

4. HashMap的資料結構，

jdk1.7：Hashmap實際上是一個陣列和鏈表的散串列
jdk1.8：當鏈表中的元素超過了 8 個以后，會將鏈表轉換為紅黑樹

5. HashMap的作業原理是什么？

以鍵值對(key-value)的形式存盤元素的，HashMap需要一個hash函式，它使用hashCode()和equals()方法來向集合/從集合添加和檢索元素，當呼叫put()方法的時候，HashMap會計算key的hash值，然后把鍵值對存盤在集合中合適的索引上，如果key已經存在了，value會被更新成新值，HashMap的一些重要的特性是它的容量(capacity)，負載因子(loadfactor)和擴容極限(thresholdresizing)

6. HashMap什么時候進行擴容呢？

當hashmap中的元素個數超過陣列大小loadFactor（加載因子）時，就會進行陣列擴容，loadFactor的默認值為0.75，

7. List、Map、Set三個介面，存取元素時，各有什么特點？

List與Set具有相似性，它們都是單列元素的集合
Map與List和Set不同，它是雙列的集合
List表示有先后順序的集合
Set無法擁有重復元素
Map保存key-value值，value可多值

8. Set里的元素是不能重復的，那么用什么方法來區分重復與否呢?是用==還是equals()?它們有何區別?

Set里的元素是不能重復的，元素重復與否是使用equals()方法進行判斷的，equals()和==方法決定參考值是否指向同一物件equals()在類中被覆寫，為的是當兩個分離的物件的內容和型別相配的話，回傳真值，

9. 兩個物件值相同(x.equals(y)==true)，但卻可有不同的hashcode，這句話對不對？

對，如果物件要保存在HashSet或HashMap中，它們的equals相等，那么，它們的hashcode值就必須相等，如果不是要保存在HashSet或HashMap，則與hashcode沒有什么關系了，這時候hashcode不等是可以的，例如arrayList存盤的物件就不用實作hashcode，當然，我們沒有理由不實作，通常都會去實作的，

10. Java集合類框架的基本介面有哪些？

Collection：代表一組物件，每一個物件都是它的子元素，
Set：不包含重復元素的Collection，
List：有順序的collection，并且可以包含重復元素，
Map：可以把鍵(key)映射到值(value)的物件，鍵不能重復，

11. HashSet的底層實作是什么？

通過看原始碼知道HashSet的實作是依賴于HashMap的，HashSet的值都是存盤在HashMap中的，在HashSet的構造法中會初始化一個HashMap物件，HashSet不允許值重復，因此，HashSet的值是作為HashMap的key存盤在HashMap中的，當存盤的值已經存在時回傳false，

12. HashSet和TreeSet有什么區別？

HashSet是由一個hash表來實作的，因此，它的元素是無序的，add()，remove()，contains()TreeSet是由一個樹形的結構來實作的，它里面的元素是有序的，因此，add()，remove()，contains()方法的時間復雜度是O(logn)

13. 為什么集合類沒有實作Cloneable和Serializable介面？

克隆(cloning)或者是序列化(serialization)的語意和含義是跟具體的實作相關的，因此，應該由集合類的具體實作來決定如何被克隆或者是序列化，

14. 陣列(Array)和串列(ArrayList)有什么區別？什么時候應該使用Array而不是ArrayList？

Array可以包含基本型別和物件型別，ArrayList只能包含物件型別，Array大小是固定的，ArrayList的大小是動態變化的，ArrayList處理固定大小的基本資料型別的時候，這種方式相對比較慢，

15. Collection和Collections的區別，

collection是集合類的上級介面,繼承與它的介面主要是set和list，collections類是針對集合類的一個幫助類.它提供一系列的靜態方法對各種集合的搜索,排序,執行緒安全化等操作，

16. Comparable和Comparator介面是干什么的？列出它們的區別，

Java提供了只包含一個compareTo()方法的Comparable介面，這個方法可以個給兩個物件排序，具體來說，它回傳負數，0，正數來表明輸入物件小于，等于，大于已經存在的物件，
Java提供了包含compare()和equals()兩個方法的Comparator介面，compare()方法用來給兩個輸入引數排序，回傳負數，0，正數表明第一個引數是小于，等于，大于第二個引數，equals()方法需要一個物件作為引數，它用來決定輸入引數是否和comparator相等，只有當輸入引數也是一個comparator并且輸入引數和當前comparator的排序結果是相同的時候，這個方法才回傳true，