JDK提供了大量?jī)?yōu)秀的集合實(shí)現(xiàn)供開發(fā)者使用性湿，合格的程序員必須要能夠通過功能場(chǎng)景和性能需求選用最合適的集合纬傲，這就要求開發(fā)者必須熟悉Java的常用集合類。本文將就Java Collections Framework中常用的集合及其特點(diǎn)肤频、適用場(chǎng)景叹括、實(shí)現(xiàn)原理進(jìn)行介紹，供學(xué)習(xí)者參考宵荒。當(dāng)然汁雷，要真正深入理解Java的集合實(shí)現(xiàn)，還是要推薦去閱讀JDK的源碼报咳。
Java提供的眾多集合類由兩大接口衍生而來(lái)：Collection接口和Map接口
Collection接口
Collection接口定義了一個(gè)包含一批對(duì)象的集合侠讯。接口的主要方法包括：
- size() - 集合內(nèi)的對(duì)象數(shù)量
- add(E)/addAll(Collection) - 向集合內(nèi)添加單個(gè)/批量對(duì)象
- remove(Object)/removeAll(Collection) - 從集合內(nèi)刪除單個(gè)/批量對(duì)象
- contains(Object)/containsAll(Collection) - 判斷集合中是否存在某個(gè)/某些對(duì)象
- toArray() - 返回包含集合內(nèi)所有對(duì)象的數(shù)組
等
Map接口
Map接口在Collection的基礎(chǔ)上，為其中的每個(gè)對(duì)象指定了一個(gè)key少孝，并使用Entry保存每個(gè)key-value對(duì)继低，以實(shí)現(xiàn)通過key快速定位到對(duì)象(value)。Map接口的主要方法包括：
- size() - 集合內(nèi)的對(duì)象數(shù)量
- put(K,V)/putAll(Map) - 向Map內(nèi)添加單個(gè)/批量對(duì)象
- get(K) - 返回Key對(duì)應(yīng)的對(duì)象
- remove(K) - 刪除Key對(duì)應(yīng)的對(duì)象
- keySet() - 返回包含Map中所有key的Set
- values() - 返回包含Map中所有value的Collection
- entrySet() - 返回包含Map中所有key-value對(duì)的EntrySet
- containsKey(K)/containsValue(V) - 判斷Map中是否存在指定key/value
等
在了解了Collection和Map兩大接口之后稍走，我們?cè)賮?lái)看一下這兩個(gè)接口衍生出來(lái)的常用集合類：
List類集合
List接口繼承自Collection袁翁，用于定義以列表形式存儲(chǔ)的集合，List接口為集合中的每個(gè)對(duì)象分配了一個(gè)索引(index)婿脸，標(biāo)記該對(duì)象在List中的位置粱胜，并可以通過index定位到指定位置的對(duì)象。
List在Collection基礎(chǔ)上增加的主要方法包括：
- get(int) - 返回指定index位置上的對(duì)象
- add(E)/add(int, E) - 在List末尾/指定index位置上插入一個(gè)對(duì)象
- set(int, E) - 替換置于List指定index位置上的對(duì)象
- indexOf(Object) - 返回指定對(duì)象在List中的index位置
- subList(int,int) - 返回指定起始index到終止index的子List對(duì)象
等
List接口的常用實(shí)現(xiàn)類：
ArrayList
ArrayList基于數(shù)組來(lái)實(shí)現(xiàn)集合的功能狐树，其內(nèi)部維護(hù)了一個(gè)可變長(zhǎng)的對(duì)象數(shù)組焙压，集合內(nèi)所有對(duì)象存儲(chǔ)于這個(gè)數(shù)組中，并實(shí)現(xiàn)該數(shù)組長(zhǎng)度的動(dòng)態(tài)伸縮
ArrayList使用數(shù)組拷貝來(lái)實(shí)現(xiàn)指定位置的插入和刪除：
插入：
刪除：
LinkedList
LinkedList基于鏈表來(lái)實(shí)現(xiàn)集合的功能抑钟，其實(shí)現(xiàn)了靜態(tài)類Node涯曲，集合中的每個(gè)對(duì)象都由一個(gè)Node保存，每個(gè)Node都擁有到自己的前一個(gè)和后一個(gè)Node的引用
LinkedList追加元素的過程示例：
ArrayList vs LinkedList
- ArrayList的隨機(jī)訪問更高在塔，基于數(shù)組實(shí)現(xiàn)的ArrayList可直接定位到目標(biāo)對(duì)象幻件，而LinkedList需要從頭Node或尾Node開始向后/向前遍歷若干次才能定位到目標(biāo)對(duì)象
- LinkedList在頭/尾節(jié)點(diǎn)執(zhí)行插入/刪除操作的效率比ArrayList要高
- 由于ArrayList每次擴(kuò)容的容量是當(dāng)前的1.5倍，所以LinkedList所占的內(nèi)存空間要更小一些
- 二者的遍歷效率接近蛔溃，但需要注意绰沥，遍歷LinkedList時(shí)應(yīng)用iterator方式，不要用get(int)方式贺待，否則效率會(huì)很低
Vector
Vector和ArrayList很像徽曲，都是基于數(shù)組實(shí)現(xiàn)的集合，它和ArrayList的主要區(qū)別在于
- Vector是線程安全的麸塞，而ArrayList不是
- 由于Vector中的方法基本都是synchronized的秃臣，其性能低于ArrayList
- Vector可以定義數(shù)組長(zhǎng)度擴(kuò)容的因子，ArrayList不能
CopyOnWriteArrayList
與 Vector一樣哪工，CopyOnWriteArrayList也可以認(rèn)為是ArrayList的線程安全版奥此，不同之處在于 CopyOnWriteArrayList在寫操作時(shí)會(huì)先復(fù)制出一個(gè)副本，在新副本上執(zhí)行寫操作正勒，然后再修改引用得院。這種機(jī)制讓 CopyOnWriteArrayList可以對(duì)讀操作不加鎖，這就使CopyOnWriteArrayList的讀效率遠(yuǎn)高于Vector章贞。 CopyOnWriteArrayList的理念比較類似讀寫分離祥绞，適合讀多寫少的多線程場(chǎng)景。但要注意鸭限，CopyOnWriteArrayList只能保證數(shù)據(jù)的最終一致性蜕径，并不能保證數(shù)據(jù)的實(shí)時(shí)一致性，如果一個(gè)寫操作正在進(jìn)行中且并未完成败京，此時(shí)的讀操作無(wú)法保證能讀到這個(gè)寫操作的結(jié)果兜喻。
Vector vs CopyOnWriteArrayList
- 二者均是線程安全的、基于數(shù)組實(shí)現(xiàn)的List
- Vector是【絕對(duì)】線程安全的赡麦，CopyOnWriteArrayList只能保證讀線程會(huì)讀到【已完成】的寫結(jié)果朴皆，但無(wú)法像Vector一樣實(shí)現(xiàn)讀操作的【等待寫操作完成后再讀最新值】的能力
- CopyOnWriteArrayList讀性能遠(yuǎn)高于Vector帕识，并發(fā)線程越多優(yōu)勢(shì)越明顯
- CopyOnWriteArrayList占用更多的內(nèi)存空間
Map類集合
Map將key和value封裝至一個(gè)叫做Entry的對(duì)象中，Map中存儲(chǔ)的元素實(shí)際是Entry遂铡。只有在keySet()和values()方法被調(diào)用時(shí)肮疗，Map才會(huì)將keySet和values對(duì)象實(shí)例化。
每一個(gè)Map根據(jù)其自身特點(diǎn)扒接，都有不同的Entry實(shí)現(xiàn)伪货，以對(duì)應(yīng)Map的內(nèi)部類形式出現(xiàn)。
前文已經(jīng)對(duì)Map接口的基本特點(diǎn)進(jìn)行過描述钾怔，我們直接來(lái)看一下Map接口的常用實(shí)現(xiàn)類
HashMap
HashMap將Entry對(duì)象存儲(chǔ)在一個(gè)數(shù)組中碱呼，并通過哈希表來(lái)實(shí)現(xiàn)對(duì)Entry的快速訪問：
由每個(gè)Entry中的key的哈希值決定該Entry在數(shù)組中的位置。以這種特性能夠?qū)崿F(xiàn)通過key快速查找到Entry宗侦，從而獲得該key對(duì)應(yīng)的value愚臀。在不發(fā)生哈希沖突的前提下，查找的時(shí)間復(fù)雜度是O(1)凝垛。
如果兩個(gè)不同的key計(jì)算出的index是一樣的懊悯，就會(huì)發(fā)生兩個(gè)不同的key都對(duì)應(yīng)到數(shù)組中同一個(gè)位置的情況，也就是所謂的哈希沖突梦皮。HashMap處理哈 希沖突的方法是拉鏈法炭分，也就是說數(shù)組中每個(gè)位置保存的實(shí)際是一個(gè)Entry鏈表，鏈表中每個(gè)Entry都擁有指向鏈表中后一個(gè)Entry的引用剑肯。在發(fā)生哈希沖突時(shí)捧毛，將沖突的Entry追加至鏈表的頭部。當(dāng)HashMap在尋址時(shí)發(fā)現(xiàn)某個(gè)key對(duì)應(yīng)的數(shù)組index上有多個(gè)Entry让网，便會(huì)遍歷該位置上的 Entry鏈表呀忧，直到找到目標(biāo)的Entry。
HashMap的Entry類：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
HashMap由于其快速尋址的特點(diǎn)溃睹，可以說是最經(jīng)常被使用的Map實(shí)現(xiàn)類
Hashtable
Hashtable 可以說是HashMap的前身（Hashtable自JDK1.0就存在而账，而HashMap乃至整個(gè)Map接口都是JDK1.2引入的新特性），其實(shí)現(xiàn)思 路與HashMap幾乎完全一樣因篇，都是通過數(shù)組存儲(chǔ)Entry泞辐，以key的哈希值計(jì)算Entry在數(shù)組中的index，用拉鏈法解決哈希沖突竞滓。二者最大的不同在于咐吼，Hashtable是線程安全的，其提供的方法幾乎都是同步的商佑。
ConcurrentHashMap
ConcurrentHashMap是HashMap的線程安全版（自JDK1.5引入）锯茄，提供比Hashtable更高效的并發(fā)性能。
Hashtable 在進(jìn)行讀寫操作時(shí)會(huì)鎖住整個(gè)Entry數(shù)組茶没，這就導(dǎo)致數(shù)據(jù)越多性能越差肌幽。而ConcurrentHashMap使用分離鎖的思路解決并發(fā)性能晚碾，其將 Entry數(shù)組拆分至16個(gè)Segment中，以哈希算法決定Entry應(yīng)該存儲(chǔ)在哪個(gè)Segment牍颈。這樣就可以實(shí)現(xiàn)在寫操作時(shí)只對(duì)一個(gè)Segment 加鎖迄薄，大幅提升了并發(fā)寫的性能琅关。
在進(jìn)行讀操作時(shí)煮岁，ConcurrentHashMap在絕大部分情況下都不需要加鎖，其Entry中的value是volatile的涣易，這保證了value被修改時(shí)的線程可見性画机，無(wú)需加鎖便能實(shí)現(xiàn)線程安全的讀操作。
ConcurrentHashMap的HashEntry類：
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
}
但是魚與熊掌不可兼得新症，ConcurrentHashMap的高性能是有代價(jià)的（否則Hashtable就沒有存在價(jià)值了）步氏，那就是它不能保證讀操作的絕對(duì) 一致性。ConcurrentHashMap保證讀操作能獲取到已存在Entry的value的最新值徒爹，同時(shí)也能保證讀操作可獲取到已完成的寫操作的內(nèi)容荚醒，但如果寫操作是在創(chuàng)建一個(gè)新的Entry，那么在寫操作沒有完成時(shí)隆嗅，讀操作是有可能獲取不到這個(gè)Entry的界阁。
HashMap vs Hashtable vs ConcurrentHashMap
- 三者在數(shù)據(jù)存儲(chǔ)層面的機(jī)制原理基本一致
- HashMap不是線程安全的，多線程環(huán)境下除了不能保證數(shù)據(jù)一致性之外胖喳，還有可能在rehash階段引發(fā)Entry鏈表成環(huán)泡躯，導(dǎo)致死循環(huán)
- Hashtable是線程安全的，能保證絕對(duì)的數(shù)據(jù)一致性丽焊，但性能是問題较剃，并發(fā)線程越多，性能越差
- ConcurrentHashMap 也是線程安全的技健，使用分離鎖和volatile等方法極大地提升了讀寫性能写穴，同時(shí)也能保證在絕大部分情況下的數(shù)據(jù)一致性。但其不能保證絕對(duì)的數(shù)據(jù)一致性雌贱， 在一個(gè)線程向Map中加入Entry的操作沒有完全完成之前啊送，其他線程有可能讀不到新加入的Entry
LinkedHashMap
LinkedHashMap與HashMap非常類似，唯一的不同在于前者的Entry在HashMap.Entry的基礎(chǔ)上增加了到前一個(gè)插入和后一個(gè)插入的Entry的引用帽芽，以實(shí)現(xiàn)能夠按Entry的插入順序進(jìn)行遍歷删掀。
TreeMap
TreeMap是基于紅黑樹實(shí)現(xiàn)的Map結(jié)構(gòu)，其Entry類擁有到左/右葉子節(jié)點(diǎn)和父節(jié)點(diǎn)的引用导街，同時(shí)還記錄了自己的顏色：
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
}
紅黑樹實(shí)際是一種算法復(fù)雜但高效的平衡二叉樹披泪，具備二叉樹的基本性質(zhì)，即任何節(jié)點(diǎn)的值大于其左葉子節(jié)點(diǎn)搬瑰，小于其右葉子節(jié)點(diǎn)款票，利用這種特性控硼，TreeMap能夠?qū)崿F(xiàn)Entry的排序和快速查找。
關(guān)于紅黑樹的具體介紹艾少，可以參考這篇文章卡乾，非常詳細(xì)：http://blog.csdn.net/chenssy/article/details/26668941
TreeMap的Entry是有序的，所以提供了一系列方便的功能缚够，比如獲取以升序或降序排列的KeySet(EntrySet)幔妨、獲取在指定key(Entry)之前/之后的key(Entry)等等。適合需要對(duì)key進(jìn)行有序操作的場(chǎng)景谍椅。
ConcurrentSkipListMap
ConcurrentSkipListMap同樣能夠提供有序的Entry排列误堡，但其實(shí)現(xiàn)原理與TreeMap不同，是基于跳表(SkipList)的：
如上圖所示雏吭，ConcurrentSkipListMap由一個(gè)多級(jí)鏈表實(shí)現(xiàn)锁施，底層鏈上擁有所有元素，逐級(jí)上升的過程中每個(gè)鏈的元素?cái)?shù)遞減杖们。在查找時(shí)從頂層鏈出發(fā)悉抵，按先右后下的優(yōu)先級(jí)進(jìn)行查找，從而實(shí)現(xiàn)快速尋址摘完。
static class Index<K,V> {
final Node<K,V> node;
final Index<K,V> down;//下引用
volatile Index<K,V> right;//右引用
}
與TreeMap不同姥饰，ConcurrentSkipListMap在進(jìn)行插入、刪除等操作時(shí)描焰，只需要修改影響到的節(jié)點(diǎn)的右引用媳否，而右引用又是volatile的，所以ConcurrentSkipListMap是線程安全的荆秦。但ConcurrentSkipListMap與ConcurrentHashMap一樣篱竭，不能保證數(shù)據(jù)的絕對(duì)一致性，在某些情況下有可能無(wú)法讀到正在被插入的數(shù)據(jù)步绸。
TreeMap vs ConcurrentSkipListMap
- 二者都能夠提供有序的Entry集合
- 二者的性能相近掺逼，查找時(shí)間復(fù)雜度都是O(logN)
- ConcurrentSkipListMap會(huì)占用更多的內(nèi)存空間
- ConcurrentSkipListMap是線程安全的，TreeMap不是
Set類集合
Set 接口繼承Collection瓤介，用于存儲(chǔ)不含重復(fù)元素的集合吕喘。幾乎所有的Set實(shí)現(xiàn)都是基于同類型Map的，簡(jiǎn)單地說刑桑，Set是閹割版的Map氯质。每一個(gè)Set內(nèi)都有一個(gè)同類型的Map實(shí)例（CopyOnWriteArraySet除外，它內(nèi)置的是CopyOnWriteArrayList實(shí)例）祠斧，Set把元素作為key存儲(chǔ)在自己的Map實(shí)例中闻察，value則是一個(gè)空的Object。Set的常用實(shí)現(xiàn)也包括 HashSet、TreeSet辕漂、ConcurrentSkipListSet等呢灶，原理和對(duì)應(yīng)的Map實(shí)現(xiàn)完全一致，此處不再贅述钉嘹。
Queue/Deque類集合
Queue和Deque接口繼承Collection接口鸯乃，實(shí)現(xiàn)FIFO（先進(jìn)先出）的集合。二者的區(qū)別在于跋涣，Queue只能在隊(duì)尾入隊(duì)缨睡，隊(duì)頭出隊(duì)，而Deque接口則在隊(duì)頭和隊(duì)尾都可以執(zhí)行出/入隊(duì)操作
Queue接口常用方法：
- add(E)/offer(E)：入隊(duì)仆潮，即向隊(duì)尾追加元素宏蛉，二者的區(qū)別在于如果隊(duì)列是有界的，add方法在隊(duì)列已滿的情況下會(huì)拋出IllegalStateException性置，而offer方法只會(huì)返回false
- remove()/poll()：出隊(duì)，即從隊(duì)頭移除1個(gè)元素揍堰，二者的區(qū)別在于如果隊(duì)列是空的鹏浅，remove方法會(huì)拋出NoSuchElementException，而poll只會(huì)返回null
- element()/peek()：查看隊(duì)頭元素屏歹，二者的區(qū)別在于如果隊(duì)列是空的隐砸，element方法會(huì)拋出NoSuchElementException，而peek只會(huì)返回null
Deque接口常用方法：
- addFirst(E) / addLast(E) / offerFirst(E) / offerLast(E)
- removeFirst() / removeLast() / pollFirst() / pollLast()
- getFirst() / getLast() / peekFirst() / peekLast()
- removeFirstOccurrence(Object) / removeLastOccurrence(Object)
Queue接口的常用實(shí)現(xiàn)類：
ConcurrentLinkedQueue
ConcurrentLinkedQueue是基于鏈表實(shí)現(xiàn)的隊(duì)列蝙眶，隊(duì)列中每個(gè)Node擁有到下一個(gè)Node的引用：
private static class Node<E> {
volatile E item;
volatile Node<E> next;
}
由于Node類的成員都是volatile的季希，所以ConcurrentLinkedQueue自然是線程安全的。能夠保證入隊(duì)和出隊(duì)操作的原子性和一致性幽纷，但在遍歷和size()操作時(shí)只能保證數(shù)據(jù)的弱一致性式塌。
LinkedBlockingQueue
與ConcurrentLinkedQueue不同，LinkedBlocklingQueue是一種無(wú)界的阻塞隊(duì)列友浸。所謂阻塞隊(duì)列峰尝，就是在入隊(duì)時(shí)如果隊(duì)列已滿，線程會(huì)被阻塞收恢，直到隊(duì)列有空間供入隊(duì)再返回武学；同時(shí)在出隊(duì)時(shí)，如果隊(duì)列已空伦意，線程也會(huì)被阻塞火窒，直到隊(duì)列中有元素供出隊(duì)時(shí)再返回。LinkedBlocklingQueue同樣基于鏈表實(shí)現(xiàn)驮肉，其出隊(duì)和入隊(duì)操作都會(huì)使用ReentrantLock進(jìn)行加鎖熏矿。所以本身是線程安全的，但同樣的，只能保證入隊(duì)和出隊(duì)操作的原子性和一致性曲掰，在遍歷時(shí)只能保證數(shù)據(jù)的弱一致性疾捍。
ArrayBlockingQueue
ArrayBlockingQueue是一種有界的阻塞隊(duì)列，基于數(shù)組實(shí)現(xiàn)栏妖。其同步阻塞機(jī)制的實(shí)現(xiàn)與LinkedBlocklingQueue基本一致乱豆，區(qū)別僅在于前者的生產(chǎn)和消費(fèi)使用同一個(gè)鎖，后者的生產(chǎn)和消費(fèi)使用分離的兩個(gè)鎖吊趾。
ConcurrentLinkedQueue vsLinkedBlocklingQueue vs ArrayBlockingQueue
- ConcurrentLinkedQueue是非阻塞隊(duì)列宛裕，其他兩者為阻塞隊(duì)列
- 三者都是線程安全的
- LinkedBlocklingQueue是無(wú)界的，適合實(shí)現(xiàn)不限長(zhǎng)度的隊(duì)列论泛， ArrayBlockingQueue適合實(shí)現(xiàn)定長(zhǎng)的隊(duì)列
SynchronousQueue
SynchronousQueue算是JDK實(shí)現(xiàn)的隊(duì)列中比較奇葩的一個(gè)揩尸，它不能保存任何元素，size永遠(yuǎn)是0屁奏，peek()永遠(yuǎn)返回null岩榆。向其中插入元素的線程會(huì)阻塞，直到有另一個(gè)線程將這個(gè)元素取走坟瓢，反之從其中取元素的線程也會(huì)阻塞勇边，直到有另一個(gè)線程插入元素。
這種實(shí)現(xiàn)機(jī)制非常適合傳遞性的場(chǎng)景折联。也就是說如果生產(chǎn)者線程需要及時(shí)確認(rèn)到自己生產(chǎn)的任務(wù)已經(jīng)被消費(fèi)者線程取走后才能執(zhí)行后續(xù)邏輯的場(chǎng)景下粒褒，適合使用SynchronousQueue。
PriorityQueue & PriorityBlockingQueue
這兩種Queue并不是FIFO隊(duì)列诚镰，而是根據(jù)元素的優(yōu)先級(jí)進(jìn)行排序奕坟，保證最小的元素最先出隊(duì)，也可以在構(gòu)造隊(duì)列時(shí)傳入Comparator實(shí)例清笨，這樣PriorityQueue就會(huì)按照Comparator實(shí)例的要求對(duì)元素進(jìn)行排序月杉。
PriorityQueue是非阻塞隊(duì)列，也不是線程安全的函筋，PriorityBlockingQueue是阻塞隊(duì)列沙合，同時(shí)也是線程安全的。
Deque 的實(shí)現(xiàn)類包括LinkedList（前文已描述過）跌帐、ConcurrentLinkedDeque首懈、LinkedBlockingDeque，其實(shí)現(xiàn)機(jī)制與前文所述的ConcurrentLinkedQueue和LinkedBlockingQueue非常類似谨敛，此處不再贅述
最后究履，對(duì)本文中描述的常用集合實(shí)現(xiàn)類做一個(gè)簡(jiǎn)單總結(jié)：
