集合類簡述

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

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

集合特點(diǎn)

集合類的特點(diǎn)有三個：

第一點(diǎn)，集合類這種框架是高性能的。對基本類集（動態(tài)數(shù)組，鏈接表，樹和散列表）的實(shí)現(xiàn)是高效率的。一般人很少去改動這些已經(jīng)很成熟并且高效的APl；

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

第三點(diǎn)，集合類容易擴(kuò)展和修改，程序員可以很容易地稍加改造就能滿足自己的數(shù)據(jù)結(jié)構(gòu)需求。

集合分類

Java中的集合類可以分為兩大類：一類是實(shí)現(xiàn)Collection接口；另一類是實(shí)現(xiàn)Map接口。

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

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

Collection有兩個重要的子接口List和Set，它們都有各自經(jīng)常使用的實(shí)現(xiàn)類，關(guān)系如下：

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

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

Map接口的一些常用實(shí)現(xiàn)類如下：

List

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

List接口有兩個經(jīng)常使用的實(shí)現(xiàn)類，ArrayList和LinkedList。還有一個實(shí)現(xiàn)類Vector，不過實(shí)際開發(fā)中很少用。它們之間的區(qū)別為：

• ArrayList的底層數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組，查詢通過數(shù)組下標(biāo)查詢，查詢速度快，增刪慢，線程不安全。
• LinkedList的底層數(shù)據(jù)結(jié)構(gòu)是一個鏈表，增刪元素快，查詢慢，線程不安全。
• Vector的底層數(shù)據(jù)結(jié)構(gòu)也是一個數(shù)組，查詢速度快。它的方法上加了synchronized關(guān)鍵字，所以它是線程安全的，但也因此，它的效率很低，幾乎已經(jīng)被淘汰了。

適用場景分析：當(dāng)需要對數(shù)據(jù)進(jìn)行對此訪問的情況下選用ArrayList，當(dāng)需要對數(shù)據(jù)進(jìn)行多次增加刪除修改時采用LinkedList。

Set

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

Set接口常用的兩個實(shí)現(xiàn)類是HashSet和TreeSet，兩者的區(qū)別如下：

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

適用場景分析：HashSet是基于Hash算法實(shí)現(xiàn)的，其性能通常都優(yōu)于TreeSet。為快速查找而設(shè)計(jì)的Set，我們通常都應(yīng)該使用HashSet，在我們需要排序的功能時，我們才使用TreeSet。

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

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

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

List與Set選型

List與Set都是存儲對象的，那我們實(shí)際開發(fā)中應(yīng)該如何選擇呢？可以參考下圖：

Map

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

Map接口有四個比較重要的實(shí)現(xiàn)類，分別是HashMap、LinkedHashMap、TreeMap和HashTable。它們的區(qū)別如下：

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

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

遍歷Map的四種方式

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

必問面試題：HashMap的底層實(shí)現(xiàn)

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

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

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

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