二十個集合常見面試題！

1.說說你了解的集合

• 集合從大的方向分有兩個，一是Collection集合，二是Map集合，
• Collection集合下有List、Set、Queue，Map集合下有HashMap、LinkedHashMap、TreeMap、HashTable、ConcurrentHashMap，
• List集合下有ArrayList、LinkedList、Vector、CopyOnWriteArrayList，Set集合下有HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet

2.說說對ArrayList的理解

• ArrayList是List集合的一個實作類，其底層實作是陣列transient Object[] elementData;，陣列的查詢是直接通過索引，查詢速度比較快，時間復雜度是O(1)，增刪的話，根據增刪的位置，時間復雜度有所不同，如果是中間第i個位置，時間復雜度就是O(n-i)，簡單理解其時間復雜度是O(n)
• 擴容機制：當構造方法中沒有指定陣列的大小時，其默認初始容量是10，當超過這個默認值的時候，一定有一個擴容機制，其擴容機制是，當集合中元素的個數大于集合容量的時候，也就是add的時候集合放不下了，就會觸發擴容機制，擴容后的新集合容量是舊集合容量的1.5倍，原始碼：int newCapacity = oldCapacity + (oldCapacity >> 1);，
• 執行緒問題：ArrayList是執行緒不安全的，在add()方法的時候，首先會檢查一下陣列的容量是否夠用，如果夠用，那么就會執行elementData[size++] = e;方法，該陳述句執行了兩大步，第一大步是，將e放到elementData緩沖區，第二大步是，將size的大小進行加1操作，也就是說，這個操作并非原子性操作，當在并發的情況時，就會出現問題，

3.說說對LinkedList的理解

• LinkedList也是List的一個實作類，其底層是雙向鏈表，其內部有一個next指標指向下一個節點，一個prev指標，指向上一個節點，由于是鏈表的資料結構，所以在查詢的時候相對就比較慢了，時間復雜度是O(n)，因為當我們需要查詢某個元素的時候，需要從第一個節點開始遍歷，直到查詢結束，而他的增刪就比較快了，如果增加一個N節點，直接將后一個節點的prev指向N節點，N節點的next指向后一個節點，前一個節點的next指向N節點，N節點的prev指標指向前一個節點即可，時間復雜度為O(1)，空間復雜度一般比ArrayList大，因為每個節點都要存盤兩個指標，
• 執行緒問題：LinkedList也是執行緒不安全的，其添加元素的操作，通過linkLast方法在尾部進行添加的，添加完之后，并把size的大小加1，其他的不說，單單一個size++就不是原子性了，簡單的a加1操作會執行三步：1：把a的值加載到記憶體、2：將記憶體中的值，存盤到變數中、3：然后進行加1操作，

4.說說對Vector的理解

• Vector也是List的一個實作類，其底層也是一個陣列protected Object[] elementData;，底層ArrayList差不多，也就是加了synchronized的ArrayList，執行緒是安全的，效率沒有ArrayList高，一般不建議使用，

5.如果不使用Vector來解決ArrayList的執行緒安全問題，還有其他的解決方案嗎？

• 既然不建議使用Vector，還有一個包java.util.concurrent(JUC)包，它下面有一個類CopyOnWriteArrayList也是執行緒安全的，CopyOnWriteArrayList也是List的一個實作類，
• add方法用Lock鎖來解決并發問題，其中在進行添加資料的時候，用了copyOf方法，也就是復制了一份，然后再set進去，
• CopyOnWriteArrayList底層也是用的陣列，但是它的陣列是用volatile修飾了，主要是保證了資料的可見性，get操作時，并沒有加鎖，因為volatile保證了資料的可見性，當資料被修改的時候，讀操作能立刻知道，

6.說說List和Set的區別

• List的存盤順序是按照存入的順序來的，而Set是根據哈希值來的
• List可以存盤相同的元素，Set不可以存盤相同的元素

7.說說對HashSet的理解

• HashSet是Set集合的一個實作類，其底層實作是HashMap的key，初始化容量是16，負載因子是0.75，擴容機制，是變為原來的2倍，
• HashSet存盤元素的順序并不是按照存入時的順序（和List不同）而是按照哈希值來存的所以取資料也是按照哈希值取得，元素的哈希值是通過元素的hashcode方法來獲取的, HashSet首先判斷兩個元素的哈希值，如果哈希值一樣，接著會比較equals方法 如果 equals結果為true ，HashSet就視為同一個元素，如果equals 為false就不是同一個元素， 哈希值相同equals為false的元素是怎么存盤呢,就是在同樣的哈希值下順延（可以認為哈希值相同的元素放在一個哈希桶中），也就是哈希一樣的存一列，

8.說說對LinkedHashSet的理解

• LinkedHashSet是對在HashSet的基礎上維護了一個雙向鏈表，使得LinkedHashSet存取有序，

9.說說對TreeSet的理解

• TreeSet()是使用二叉樹的原理對新add()的物件按照指定的順序排序（升序、降序），每增加一個物件都會進行排序，將物件插入的二叉樹指定的位置，

10.如果想要對HashSet進行執行緒安全處理，應該怎么辦？

• 可以通過CopyOnWriteArraySet來實作，

11.queue是什么呢

• queue是一個佇列，先進先出（FIFO）的資料結構

12.聊聊對HashMap的理解（重要）

• 底層是JDK1.7是通過陣列+鏈表JDK1.8是通過陣列+鏈表+紅黑樹組成，所有的資料都是通過一個Node節點進行封裝，其中Node節點中封裝了hash值，key，value，和next指標，hash是通過key計算出的hashCode值進行對陣列容量減一求余得到的（官方的求余方式是通過&運算進行的），不同的key計算出來的hash值可能相同，解決沖突是通過拉鏈法（鏈表和紅黑樹）進行處理，正是因為這種存盤形勢，所以HashMap的存取順序是無序的，
• 懶加載機制，在put值的時候會判斷陣列是否為空，如果是就初始化陣列，而不是new的時候就初始化，
• HashMap是Map的一個實作類，其默認初始化容量大小是16，擴容機制是根據擴容因子來擴容的，當容量的使用量達到總容量的0.75時，就會觸發擴容，舉例說就是，當總容量是16時，使用量達到12，就會觸發擴容機制，
• 當我們put一個值的時候，通過key來計算出hash值，計算出來的hash值做為陣列的索引，Node節點中封裝了hash值，key，value和next，當鏈表的長度小于8的時候，處理沖突的方式是鏈表，大于等于8的時候，就會觸發紅黑樹方式存盤，
• 當元素個數小于等于6的時候，會觸發紅黑樹轉化為鏈表的形式，為什么不是小于等于7，是因為給一個過度，也就是防止添加一個剛好為8，洗掉一個剛好為7，這樣來回轉化，

13.說說對LinkedHashMap的理解

• LinkedHashMap解決了HashMap不能保證存取順序的問題，內部增加了一個鏈表用于維護元素存取順序，

14.說說對TreeMap的理解

• TreeMap實作SortedMap介面，能夠把它保存的記錄根據鍵排序，默認是按鍵值的升序排序，

15.如果想要保證HashMap的執行緒安全，應該怎么辦？

• 可以通過HashTable，該類的出現主要是解決了HashMap的執行緒安全問題，直接用了synchronized鎖，所以效率上不高，不建議使用（發現JDK1.0的執行緒問題，解決都很暴力），
• ConcurrentHashMap是java.util.concurrent包下的，并發包下的，他就是對HashMap進行了一個擴展，也就是解決了他的執行緒安全問題，ConcurrentHashMap用了大量的CAS來進行優化，

16.什么是CAS呢？

• CAS（Compare and swap）比較和替換是設計并發演算法時用到的一種技術，簡單來說，比較和替換是使用一個期望值和一個變數的當前值進行比較，如果當前變數的值與我們期望的值相等，就使用一個新值替換當前變數的值，

17.Collection 和 Collections 有什么區別？

• Collection 是一個集合介面（集合類的一個頂級介面），它提供了對集合物件進行基本操作的通用介面方法，Collection介面在Java 類別庫中有很多具體的實作，Collection介面的意義是為各種具體的集合提供了最大化的統一操作方式，其直接繼承介面有List與Set，
• Collections則是集合類的一個工具類，其中提供了一系列靜態方法，用于對集合中元素進行排序、搜索以及執行緒安全等各種操作，

18.ArrayList和LinkedList 的區別是什么？

• ArrayList底層的資料結構是陣列，支持隨機訪問，而 LinkedList 的底層資料結構是雙向回圈鏈表，不支持隨機訪問，使用下標訪問一個元素，ArrayList 的時間復雜度是 O(1)，而 LinkedList 是 O(n)，

19.ArrayList和Vector 的區別是什么？

• Vector使用了synchronized來實作執行緒同步，是執行緒安全的，而ArrayList是非執行緒安全的，
• Vector擴容每次會增加1倍，而ArrayList只會增加0.5倍，

20.HashMap和HashTable的區別？

• HashMap允許空鍵值，HashTable不允許，
• HashMap執行緒不安全（效率高），HashTable執行緒安全，