集合類簡述

在沒有集合類之前，實際上在JAVA語言里已經有一種方法可以存儲對象，那就是數組。數組不僅可以存放基本數據類型也可以容納屬于同一種類型的對象。數組的操作是高效率的，但也有缺點。比如數組的長度是不可以變的，數組只能存放同一種類型的對象（或者說對象的引用）。

為了使程序方便地存儲和操縱數目不固定的一組數據，JDK中提供了Java集合類，所有Java集合類都位于Java.util包中，與Java數組不同，Java集合不能存放基本數據類型數據，而只能存放對象的引用。

集合特點

集合類的特點有三個：

第一點，集合類這種框架是高性能的。對基本類集（動態數組，鏈接表，樹和散列表）的實現是高效率的。一般人很少去改動這些已經很成熟并且高效的APl；

第二點，集合類允許不同類型的集合以相同的方式和高度互操作方式工作；

第三點，集合類容易擴展和修改，程序員可以很容易地稍加改造就能滿足自己的數據結構需求。

集合分類

Java中的集合類可以分為兩大類：一類是實現Collection接口；另一類是實現Map接口。

Collection是一個基本的集合接口，Collection中可以容納一組集合元素（Element）。

Collection接口中定義了一些操作集合的API：

Collection有兩個重要的子接口List和Set，它們都有各自經常使用的實現類，關系如下：

Map沒有繼承Collection接口，與Collection是并列關系。Map提供鍵（key）到值（value）的映射。一個Map中不能包含相同的鍵，每個鍵只能映射一個值。

Map中也提供了一些操作Map的API：

Map接口的一些常用實現類如下：

List

List表達一個有序的集合，List中的每個元素都有索引，使用此接口能夠準確的控制每個元素插入的位置。用戶也能夠使用索引來訪問List中的元素，List類似于Java的數組。

List接口有兩個經常使用的實現類，ArrayList和LinkedList。還有一個實現類Vector，不過實際開發中很少用。它們之間的區別為：

ArrayList的底層數據結構是一個數組，查詢通過數組下標查詢，查詢速度快，增刪慢，線程不安全。
LinkedList的底層數據結構是一個鏈表，增刪元素快，查詢慢，線程不安全。
Vector的底層數據結構也是一個數組，查詢速度快。它的方法上加了synchronized關鍵字，所以它是線程安全的，但也因此，它的效率很低，幾乎已經被淘汰了。

適用場景分析：當需要對數據進行對此訪問的情況下選用ArrayList，當需要對數據進行多次增加刪除修改時采用LinkedList。

Set

Set接口的特點是不能包含重復的元素。對Set中任意的兩個元素element1和element2都有elementl.equals(element2)= false。另外，Set最多有一個null元素。

Set接口常用的兩個實現類是HashSet和TreeSet，兩者的區別如下：

HashSet底層數據結構采用哈希表實現，元素無序且唯一，線程不安全，效率高，可以存儲null元素，元素的唯一性是靠所存儲元素類型是否重寫hashCode()和equals()方法來保證的，如果沒有重寫這兩個方法，則無法保證元素的唯一性。
TreeSet底層數據結構采用紅黑樹來實現，元素唯一且已經排好序；唯一性同樣需要重寫hashCode和equals()方法，二叉樹結構保證了元素的有序性。根據構造方法不同，分為自然排序（無參構造）和比較器排序（有參構造），自然排序要求元素必須實現Compareable接口，并重寫里面的compareTo()方法，元素通過比較返回的int值來判斷排序序列，返回0說明兩個對象相同，不需要存儲；比較器排需要在TreeSet初始化是時候傳入一個實現Comparator接口的比較器對象，或者采用匿名內部類的方式new一個Comparator對象，重寫里面的compare()方法；

適用場景分析：HashSet是基于Hash算法實現的，其性能通常都優于TreeSet。為快速查找而設計的Set，我們通常都應該使用HashSet，在我們需要排序的功能時，我們才使用TreeSet。

此外，還有一種Set類型，LinkedHashSet，它是HashSet的子類，底層數據結構采用鏈表+哈希表，鏈表保證元素的添加順序，哈希表保證元素的唯一性。

延伸一個面試題：HashSet是如何保證元素的唯一性？

當調用add()方法向集合中存入對象的時候，首先會使用 hash() 函數生成一個 int 類型的 hashCode 散列值，然后與已經存儲的元素的 hashCode 值作比較，如果 hashCode 值不相等，則所存儲的兩個對象一定不相等，此時把這個新元素存儲在它的 hashCode 位置上；如果 hashCode 相等，存儲元素的對象還是不一定相等，此時會調用 equals() 方法判斷兩個對象的內容是否相等，如果 equals() 返回true，則是同一個對象，無需存儲；如果 equals() 返回 false，那么就是不同的對象，就需要存儲，不過由于 hashCode 相同，HashSet會以鏈式結構將兩個對象保存在同一位置，這將導致性能下降，因此在編碼時應避免出現這種情況。

List與Set選型

List與Set都是存儲對象的，那我們實際開發中應該如何選擇呢？可以參考下圖：

Map

Map用于保存具有映射關系的數據，Map里保存著兩組數據：key和value，它們都可以使任何引用類型的數據，但key不能重復。所以通過指定的key就可以取出對應的value。

Map接口有四個比較重要的實現類，分別是HashMap、LinkedHashMap、TreeMap和HashTable。它們的區別如下：

HashMap的key值可以為null，但只能有一個key為null；它是線程不安全的，如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
LinkedHashMap繼承自HashMap，它主要是用鏈表實現來擴展HashMap類，HashMap中條目是沒有順序的，但是在LinkedHashMap中元素既可以按照它們插入的順序排序，也可以按它們最后一次被訪問的順序排序。
TreeMap基于紅黑樹數據結構的實現，鍵值可以使用Comparable或Comparator接口來排序。TreeMap繼承自AbstractMap，同時實現了接口NavigableMap，而接口NavigableMap則繼承自SortedMap。SortedMap是Map的子接口，使用它可以確保圖中的條目是排好序的。
Hashtable和HashMap很類似，它也是一個散列表，存儲的內容是鍵值對映射，不同之處在于，Hashtable是繼承自Dictionary的，Hashtable中的函數都是同步的，這意味著它也是線程安全的，另外，Hashtable中key和value都不可以為null。

在實際使用中，如果更新時不需要保持元素的順序，就使用HashMap，如果需要保持元素的插入順序或者訪問順序，就使用LinkedHashMap，如果需要使圖按照鍵值排序，就使用TreeMap。

遍歷Map的四種方式

Map不同于List和Set，它存儲的是key-value的鍵值對，不能像List和Set那樣直接使用 for 循環遍歷，可以通過下面四種方式遍歷Map：

必問面試題：HashMap的底層實現

HashMap采用Entry數組來存儲key-value對，每一個鍵值對組成了一個Entry實體，Entry類實際上是一個單向的鏈表結構，它具有Next指針，可以連接下一個Entry實體。只是在JDK1.8中，鏈表長度大于8的時候，鏈表會轉成紅黑樹。

在調用 HashMap 的 put 方法添加元素時，會對key的hashCode()做hash運算，計算index; 如果沒碰撞直接放到bucket里；如果碰撞了，以鏈表的形式存在buckets后；如果碰撞導致鏈表過長(大于等于TREEIFY_THRESHOLD)，就把鏈表轉換成紅黑樹(JDK1.8中的改動)；如果節點已經存在就替換old value(保證key的唯一性) 如果bucket滿了(超過load factor*current capacity)，就要resize。

在調用 HashMap 的 get 方法獲取元素時，會對key的hashCode()做hash運算，計算index; 如果在bucket里的第一個節點里直接命中，則直接返回；如果有沖突，則通過key.equals(k)去查找對應的Entry。

上面只是簡單的說了下 HashMap 在 put 和 get 時的主要過程，后期我會單獨開一篇文章，根據 HashMap 的源碼來說明它的具體原理。