本章節主要分享一些Java中的集合在面試中常問的高頻問題，這裡給出的是相對比較簡略的答案，不過針對面試的回答，這些就足夠了，另外就是一定要加入自己的個人理解，不要背書形式的回答。

1.Java中的集合框架有哪些？

回答：Java 集合框架主要包括兩種類型的容器，一種是集合（Collection），存儲一個元素集合，另一種是圖（Map），存儲鍵/值對映射。

Collection 接口又有 3 種子類型，List、Set 和 Queue，再下面是一些抽象類，最後是具體實現類，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、TreeMap、LinkedHashMap 等等。

2.ArrayList和LinkedList的底層實現和區別？

回答：ArrayList底層使用的是 Object數組；LinkedList底層使用的是 雙向鏈表 數據結構。

ArrayList:增刪慢、查詢快，線程不安全，對元素必須連續存儲。

LinkedList:增刪快，查詢慢，線程不安全。

追問：說說ArrayList的擴容機制？

回答：通過閱讀ArrayList的源碼我們可以發現當以無參數構造方法創建 ArrayList 時，實際上初始化賦值的是一個空數組。當真正對數組進行添加元素操作時，才真正分配容量。即向數組中添加第一個元素時，數組容量擴為 10。當插入的元素個數大於當前容量時，就需要進行擴容了， ArrayList 每次擴容之後容量都會變為原來的 1.5 倍左右。

3.HashMap的底層實現？擴容？是否線程安全？

回答：在jdk1.7之前HashMap是基於數組和鏈表實現的，而且採用頭插法。

而jdk1.8 之後在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為 8）（將鏈錶轉換成紅黑樹前會判斷，如果當前數組的長度小於 64，那麼會選擇先進行數組擴容，而不是轉換為紅黑樹）時，將鏈錶轉化為紅黑樹，以減少搜索時間。採用尾插法。

HashMap默認的初始化大小為 16。當HashMap中的元素個數之和大於負載因子*當前容量的時候就要進行擴充，容量變為原來的 2 倍。（這裡注意不是數組中的個數，而且數組中和鏈/樹中的所有元素個數之和！）

注意：我們還可以在預知存儲數據量的情況下，提前設置初始容量（初始容量 = 預知數據量 / 加載因子）。這樣做的好處是可以減少 resize() 操作，提高 HashMap 的效率
美團面試的時候問到這個問題，還給出具體的值，讓我算出初始值設置為多少合適？

HashMap是線程不安全的，其主要體現：

1.在jdk1.7中，在多線程環境下，擴容時會造成環形鏈或數據丟失。

2.在jdk1.8中，在多線程環境下，會發生數據覆蓋的情況。

追問：HashMap擴容的時候為什麼是2的n次冪？

回答：數組下標的計算方法是（n-1）& hash，取余(%)操作中如果除數是2的冪次則等價於與其除數減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。並且採用二進制位操作 &，相對於%能夠提高運算效率，這就解釋了 HashMap 的長度為什麼是2的冪次方。

追問：HashMap的put方法說一下。

回答：通過閱讀源碼，可以從jdk1.7和1.8兩個方面來回答

1.根據key通過哈希算法與與運算得出數組下標

2.如果數組下標元素為空，則將key和value封裝為Entry對象（JDK1.7是Entry對象，JDK1.8是Node對象）並放入該位置。

3.如果數組下標位置元素不為空，則要分情況

(i)如果是在JDK1.7，則首先會判斷是否需要擴容，如果要擴容就進行擴容，如果不需要擴容就生成Entry對象，並使用頭插法添加到當前鏈表中。

(ii)如果是在JDK1.8中，則會先判斷當前位置上的TreeNode類型，看是紅黑樹還是鏈表Node

(a)如果是紅黑樹TreeNode，則將key和value封裝為一個紅黑樹節點並添加到紅黑樹中去，在這個過程中會判斷紅黑樹中是否存在當前key，如果存在則更新value。

(b)如果此位置上的Node對象是鏈表節點，則將key和value封裝為一個Node並通過尾插法插入到鏈表的最後位置去，因為是尾插法，所以需要遍歷鏈表，在遍歷過程中會判斷是否存在當前key，如果存在則更新其value，當遍歷完鏈表後，將新的Node插入到鏈表中，插入到鏈表後，會看當前鏈表的節點個數，如果大於8，則會將鏈錶轉為紅黑樹

(c)將key和value封裝為Node插入到鏈表或紅黑樹後，在判斷是否需要擴容，如果需要擴容，就結束put方法。

追問：HashMap源碼中在計算hash值的時候為什麼要右移16位？

回答：我的理解是讓元素在HashMap中更加均勻的分佈，具體的可以看下圖，下圖是《阿里調優手冊》里說的。

4.Java中線程安全的集合有哪些？

Vector：就比Arraylist多了個同步化機制（線程安全）。

Hashtable：就比Hashmap多了個線程安全。

ConcurrentHashMap:是一種高效但是線程安全的集合。

Stack：棧，也是線程安全的，繼承於Vector。

追問：說一下ConcurrentHashMap的底層實現，它為什麼是線程安全的？

回答：在jdk1.7是 分段的數組+鏈表 ，jdk1.8的時候跟HashMap1.8的時候一樣都是基於數組+鏈表/紅黑樹。

ConcurrentHashMap是線程安全的

（1）在jdk1.7的時候是使用分段所segment，每一把鎖只鎖容器其中一部分數據，多線程訪問容器里不同數據段的數據，就不會存在鎖競爭，提高並發訪問率。

（2）在jdk1.8的時候摒棄了 Segment的概念，而是直接用 Node 數組+鏈表+紅黑樹的數據結構來實現，並發控制使用 synchronized 和 CAS 來操作。synchronized只鎖定當前鏈表或紅黑二叉樹的首節點。

5.HashMap和Hashtable的區別

回答：

（1）線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的,因為 HashTable 內部的方法基本都經過synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧！）；

（2）對 Null key 和 Null value 的支持： HashMap 可以存儲 null 的 key 和 value，但 null 作為鍵只能有一個，null 作為值可以有多個；HashTable 不允許有 null 鍵和 null 值，否則會拋出 NullPointerException。

（3）初始容量大小和每次擴充容量大小的不同： ① 創建時如果不指定容量初始值，Hashtable 默認的初始大小為 11，之後每次擴充，容量變為原來的 2n+1。HashMap 默認的初始化大小為 16。之後每次擴充，容量變為原來的 2 倍。② 創建時如果給定了容量初始值，那麼 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為 2 的冪次方大小（HashMap 中的tableSizeFor()方法保證，下面給出了源代碼）。也就是說 HashMap 總是使用 2 的冪作為哈希表的大小,後面會介紹到為什麼是 2 的冪次方。

（4）底層數據結構： JDK1.8 以後的 HashMap 在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為 8）（將鏈錶轉換成紅黑樹前會判斷，如果當前數組的長度小於 64，那麼會選擇先進行數組擴容，而不是轉換為紅黑樹）時，將鏈錶轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。

（5）效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；