本文鏈接：http://weizhan.51cto.com/article/view/591c117ef2dd875f6f298f42
JDK提供了大量優(yōu)秀的集合實現(xiàn)供開發(fā)者使用蠢沿，合格的程序員必須要能夠通過功能場景和性能需求選用最合適的集合伸头，這就要求開發(fā)者必須熟悉Java的常用集合類。本文將就Java Collections Framework中常用的集合及其特點搏予、適用場景熊锭、實現(xiàn)原理進行介紹弧轧，供學習者參考雪侥。當然，要真正深入理解Java的集合實現(xiàn)精绎，還是要推薦去閱讀JDK的源碼速缨。
Java提供的眾多集合類由兩大接口衍生而來：Collection接口和Map接口
Collection接口定義了一個包含一批對象的集合。接口的主要方法包括：
size() - 集合內(nèi)的對象數(shù)量
add(E)/addAll(Collection) - 向集合內(nèi)添加單個/批量對象
remove(Object)/removeAll(Collection) - 從集合內(nèi)刪除單個/批量對象
contains(Object)/containsAll(Collection) - 判斷集合中是否存在某個/某些對象
toArray() - 返回包含集合內(nèi)所有對象的數(shù)組
等
Map接口在Collection的基礎(chǔ)上代乃，為其中的每個對象指定了一個key旬牲，并使用Entry保存每個key-value對仿粹，以實現(xiàn)通過key快速定位到對象(value)。Map接口的主要方法包括：
size() - 集合內(nèi)的對象數(shù)量
put(K,V)/putAll(Map) - 向Map內(nèi)添加單個/批量對象
get(K) - 返回Key對應的對象
remove(K) - 刪除Key對應的對象
keySet() - 返回包含Map中所有key的Set
values() - 返回包含Map中所有value的Collection
entrySet() - 返回包含Map中所有key-value對的EntrySet
containsKey(K)/containsValue(V) - 判斷Map中是否存在指定key/value
等
在了解了Collection和Map兩大接口之后原茅，我們再來看一下這兩個接口衍生出來的常用集合類：
圖片.png
List接口繼承自Collection吭历，用于定義以列表形式存儲的集合，List接口為集合中的每個對象分配了一個索引(index)擂橘，標記該對象在List中的位置晌区，并可以通過index定位到指定位置的對象。
List在Collection基礎(chǔ)上增加的主要方法包括：
get(int) - 返回指定index位置上的對象
add(E)/add(int, E) - 在List末尾/指定index位置上插入一個對象
set(int, E) - 替換置于List指定index位置上的對象
indexOf(Object) - 返回指定對象在List中的index位置
subList(int,int) - 返回指定起始index到終止index的子List對象
等
List接口的常用實現(xiàn)類：
ArrayList基于數(shù)組來實現(xiàn)集合的功能通贞，其內(nèi)部維護了一個可變長的對象數(shù)組朗若，集合內(nèi)所有對象存儲于這個數(shù)組中，并實現(xiàn)該數(shù)組長度的動態(tài)伸縮
ArrayList使用數(shù)組拷貝來實現(xiàn)指定位置的插入和刪除：
插入：
圖片.png
刪除：
圖片.png
LinkedList基于鏈表來實現(xiàn)集合的功能昌罩，其實現(xiàn)了靜態(tài)類Node哭懈，集合中的每個對象都由一個Node保存，每個Node都擁有到自己的前一個和后一個Node的引用
LinkedList追加元素的過程示例：
圖片.png
ArrayList的隨機訪問更高茎用，基于數(shù)組實現(xiàn)的ArrayList可直接定位到目標對象遣总，而LinkedList需要從頭Node或尾Node開始向后/向前遍歷若干次才能定位到目標對象
LinkedList在頭/尾節(jié)點執(zhí)行插入/刪除操作的效率比ArrayList要高
由于ArrayList每次擴容的容量是當前的1.5倍，所以LinkedList所占的內(nèi)存空間要更小一些
二者的遍歷效率接近轨功，但需要注意彤避，遍歷LinkedList時應用iterator方式，不要用get(int)方式夯辖，否則效率會很低
Vector和ArrayList很像琉预，都是基于數(shù)組實現(xiàn)的集合，它和ArrayList的主要區(qū)別在于
Vector是線程安全的蒿褂，而ArrayList不是
由于Vector中的方法基本都是synchronized的圆米，其性能低于ArrayList
Vector可以定義數(shù)組長度擴容的因子，ArrayList不能
與 Vector一樣啄栓，CopyOnWriteArrayList也可以認為是ArrayList的線程安全版娄帖，不同之處在于 CopyOnWriteArrayList在寫操作時會先復制出一個副本，在新副本上執(zhí)行寫操作昙楚，然后再修改引用近速。這種機制讓 CopyOnWriteArrayList可以對讀操作不加鎖，這就使CopyOnWriteArrayList的讀效率遠高于Vector堪旧。 CopyOnWriteArrayList的理念比較類似讀寫分離削葱，適合讀多寫少的多線程場景。但要注意淳梦，CopyOnWriteArrayList只能保證數(shù)據(jù)的最終一致性析砸，并不能保證數(shù)據(jù)的實時一致性，如果一個寫操作正在進行中且并未完成爆袍，此時的讀操作無法保證能讀到這個寫操作的結(jié)果首繁。
Vector vs CopyOnWriteArrayList
二者均是線程安全的作郭、基于數(shù)組實現(xiàn)的List
Vector是【絕對】線程安全的，CopyOnWriteArrayList只能保證讀線程會讀到【已完成】的寫結(jié)果弦疮，但無法像Vector一樣實現(xiàn)讀操作的【等待寫操作完成后再讀最新值】的能力
CopyOnWriteArrayList讀性能遠高于Vector夹攒，并發(fā)線程越多優(yōu)勢越明顯
CopyOnWriteArrayList占用更多的內(nèi)存空間
圖片.png
Map將key和value封裝至一個叫做Entry的對象中，Map中存儲的元素實際是Entry胁塞。只有在keySet()和values()方法被調(diào)用時芹助，Map才會將keySet和values對象實例化。
每一個Map根據(jù)其自身特點闲先，都有不同的Entry實現(xiàn)状土，以對應Map的內(nèi)部類形式出現(xiàn)。
前文已經(jīng)對Map接口的基本特點進行過描述伺糠，我們直接來看一下Map接口的常用實現(xiàn)類
HashMap將Entry對象存儲在一個數(shù)組中蒙谓，并通過哈希表來實現(xiàn)對Entry的快速訪問：
圖片.png
由每個Entry中的key的哈希值決定該Entry在數(shù)組中的位置。以這種特性能夠?qū)崿F(xiàn)通過key快速查找到Entry训桶，從而獲得該key對應的value累驮。在不發(fā)生哈希沖突的前提下，查找的時間復雜度是O(1)舵揭。
如果兩個不同的key計算出的index是一樣的谤专，就會發(fā)生兩個不同的key都對應到數(shù)組中同一個位置的情況，也就是所謂的哈希沖突午绳。HashMap處理哈 希沖突的方法是拉鏈法置侍，也就是說數(shù)組中每個位置保存的實際是一個Entry鏈表，鏈表中每個Entry都擁有指向鏈表中后一個Entry的引用拦焚。在發(fā)生哈希沖突時蜡坊，將沖突的Entry追加至鏈表的頭部。當HashMap在尋址時發(fā)現(xiàn)某個key對應的數(shù)組index上有多個Entry赎败，便會遍歷該位置上的 Entry鏈表秕衙，直到找到目標的Entry。
圖片.png
HashMap的Entry類：
static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
int hash;
}
HashMap由于其快速尋址的特點僵刮，可以說是最經(jīng)常被使用的Map實現(xiàn)類
Hashtable 可以說是HashMap的前身（Hashtable自JDK1.0就存在据忘，而HashMap乃至整個Map接口都是JDK1.2引入的新特性），其實現(xiàn)思 路與HashMap幾乎完全一樣搞糕，都是通過數(shù)組存儲Entry勇吊，以key的哈希值計算Entry在數(shù)組中的index，用拉鏈法解決哈希沖突寞宫。二者最大的不同在于萧福，Hashtable是線程安全的，其提供的方法幾乎都是同步的辈赋。
ConcurrentHashMap是HashMap的線程安全版（自JDK1.5引入）鲫忍，提供比Hashtable更高效的并發(fā)性能。
圖片.png
Hashtable 在進行讀寫操作時會鎖住整個Entry數(shù)組钥屈，這就導致數(shù)據(jù)越多性能越差悟民。而ConcurrentHashMap使用分離鎖的思路解決并發(fā)性能，其將 Entry數(shù)組拆分至16個Segment中篷就，以哈希算法決定Entry應該存儲在哪個Segment射亏。這樣就可以實現(xiàn)在寫操作時只對一個Segment 加鎖，大幅提升了并發(fā)寫的性能竭业。
在進行讀操作時智润，ConcurrentHashMap在絕大部分情況下都不需要加鎖，其Entry中的value是volatile的未辆，這保證了value被修改時的線程可見性窟绷，無需加鎖便能實現(xiàn)線程安全的讀操作。
ConcurrentHashMap的HashEntry類：
static final class HashEntry {
final int hash;
final K key;
volatile V value;
volatile HashEntry next;
}
但是魚與熊掌不可兼得咐柜，ConcurrentHashMap的高性能是有代價的（否則Hashtable就沒有存在價值了）兼蜈，那就是它不能保證讀操作的絕對 一致性。ConcurrentHashMap保證讀操作能獲取到已存在Entry的value的最新值拙友，同時也能保證讀操作可獲取到已完成的寫操作的內(nèi)容为狸，但如果寫操作是在創(chuàng)建一個新的Entry，那么在寫操作沒有完成時遗契，讀操作是有可能獲取不到這個Entry的辐棒。
HashMap vs Hashtable vs ConcurrentHashMap
三者在數(shù)據(jù)存儲層面的機制原理基本一致
HashMap不是線程安全的，多線程環(huán)境下除了不能保證數(shù)據(jù)一致性之外牍蜂，還有可能在rehash階段引發(fā)Entry鏈表成環(huán)涉瘾，導致死循環(huán)
Hashtable是線程安全的，能保證絕對的數(shù)據(jù)一致性捷兰，但性能是問題立叛，并發(fā)線程越多，性能越差
ConcurrentHashMap 也是線程安全的贡茅，使用分離鎖和volatile等方法極大地提升了讀寫性能秘蛇，同時也能保證在絕大部分情況下的數(shù)據(jù)一致性。但其不能保證絕對的數(shù)據(jù)一致性顶考， 在一個線程向Map中加入Entry的操作沒有完全完成之前赁还，其他線程有可能讀不到新加入的Entry
LinkedHashMap與HashMap非常類似，唯一的不同在于前者的Entry在HashMap.Entry的基礎(chǔ)上增加了到前一個插入和后一個插入的Entry的引用驹沿，以實現(xiàn)能夠按Entry的插入順序進行遍歷艘策。
圖片.png
TreeMap是基于紅黑樹實現(xiàn)的Map結(jié)構(gòu)，其Entry類擁有到左/右葉子節(jié)點和父節(jié)點的引用渊季，同時還記錄了自己的顏色：
static final class Entry implements Map.Entry {
K key;
V value;
Entry left = null;
Entry right = null;
Entry parent;
boolean color = BLACK;
}
紅黑樹實際是一種算法復雜但高效的平衡二叉樹朋蔫，具備二叉樹的基本性質(zhì)罚渐，即任何節(jié)點的值大于其左葉子節(jié)點，小于其右葉子節(jié)點驯妄，利用這種特性荷并，TreeMap能夠?qū)崿F(xiàn)Entry的排序和快速查找。
關(guān)于紅黑樹的具體介紹青扔，可以參考這篇文章源织，非常詳細：http://blog.csdn.net/chenssy/article/details/26668941
TreeMap的Entry是有序的，所以提供了一系列方便的功能微猖，比如獲取以升序或降序排列的KeySet(EntrySet)谈息、獲取在指定key(Entry)之前/之后的key(Entry)等等。適合需要對key進行有序操作的場景凛剥。
ConcurrentSkipListMap同樣能夠提供有序的Entry排列侠仇，但其實現(xiàn)原理與TreeMap不同，是基于跳表(SkipList)的：
圖片.png
如上圖所示当悔，ConcurrentSkipListMap由一個多級鏈表實現(xiàn)傅瞻，底層鏈上擁有所有元素坞笙，逐級上升的過程中每個鏈的元素數(shù)遞減车摄。在查找時從頂層鏈出發(fā)毯欣，按先右后下的優(yōu)先級進行查找魄鸦，從而實現(xiàn)快速尋址尔艇。
static class Index {
final Node node;
final Index down;//下引用
volatile Index right;//右引用
}
與TreeMap不同盅藻，ConcurrentSkipListMap在進行插入癞己、刪除等操作時淘邻，只需要修改影響到的節(jié)點的右引用窑眯，而右引用又是volatile的屏积，所以ConcurrentSkipListMap是線程安全的。但ConcurrentSkipListMap與ConcurrentHashMap一樣磅甩，不能保證數(shù)據(jù)的絕對一致性炊林，在某些情況下有可能無法讀到正在被插入的數(shù)據(jù)。
TreeMap vs ConcurrentSkipListMap
二者都能夠提供有序的Entry集合
二者的性能相近卷要，查找時間復雜度都是O(logN)
ConcurrentSkipListMap會占用更多的內(nèi)存空間
ConcurrentSkipListMap是線程安全的渣聚，TreeMap不是
Set 接口繼承Collection，用于存儲不含重復元素的集合僧叉。幾乎所有的Set實現(xiàn)都是基于同類型Map的奕枝，簡單地說，Set是閹割版的Map瓶堕。每一個Set內(nèi)都有一個同類型的Map實例（CopyOnWriteArraySet除外隘道，它內(nèi)置的是CopyOnWriteArrayList實例），Set把元素作為key存儲在自己的Map實例中，value則是一個空的Object谭梗。Set的常用實現(xiàn)也包括 HashSet忘晤、TreeSet、ConcurrentSkipListSet等默辨，原理和對應的Map實現(xiàn)完全一致德频，此處不再贅述苍息。
圖片.png
圖片.png
Queue和Deque接口繼承Collection接口缩幸，實現(xiàn)FIFO（先進先出）的集合。二者的區(qū)別在于竞思，Queue只能在隊尾入隊表谊，隊頭出隊，而Deque接口則在隊頭和隊尾都可以執(zhí)行出/入隊操作
Queue接口常用方法：
add(E)/offer(E)：入隊盖喷，即向隊尾追加元素爆办，二者的區(qū)別在于如果隊列是有界的，add方法在隊列已滿的情況下會拋出IllegalStateException课梳，而offer方法只會返回false
remove()/poll()：出隊距辆，即從隊頭移除1個元素，二者的區(qū)別在于如果隊列是空的暮刃，remove方法會拋出NoSuchElementException跨算，而poll只會返回null
element()/peek()：查看隊頭元素，二者的區(qū)別在于如果隊列是空的椭懊，element方法會拋出NoSuchElementException诸蚕，而peek只會返回null
Deque接口常用方法：
addFirst(E) / addLast(E) / offerFirst(E) / offerLast(E)
removeFirst() / removeLast() / pollFirst() / pollLast()
getFirst() / getLast() / peekFirst() / peekLast()
removeFirstOccurrence(Object) / removeLastOccurrence(Object)
Queue接口的常用實現(xiàn)類：
ConcurrentLinkedQueue是基于鏈表實現(xiàn)的隊列，隊列中每個Node擁有到下一個Node的引用：
private static class Node {
volatile E item;
volatile Node next;
}
由于Node類的成員都是volatile的氧猬，所以ConcurrentLinkedQueue自然是線程安全的背犯。能夠保證入隊和出隊操作的原子性和一致性，但在遍歷和size()操作時只能保證數(shù)據(jù)的弱一致性盅抚。
與ConcurrentLinkedQueue不同漠魏，LinkedBlocklingQueue是一種無界的阻塞隊列。所謂阻塞隊列妄均，就是在入隊時如果隊列已滿柱锹，線程會被阻塞，直到隊列有空間供入隊再返回丛晦；同時在出隊時奕纫，如果隊列已空，線程也會被阻塞烫沙，直到隊列中有元素供出隊時再返回匹层。LinkedBlocklingQueue同樣基于鏈表實現(xiàn)，其出隊和入隊操作都會使用ReentrantLock進行加鎖。所以本身是線程安全的升筏，但同樣的撑柔，只能保證入隊和出隊操作的原子性和一致性，在遍歷時只能保證數(shù)據(jù)的弱一致性您访。
ArrayBlockingQueue是一種有界的阻塞隊列铅忿，基于數(shù)組實現(xiàn)。其同步阻塞機制的實現(xiàn)與LinkedBlocklingQueue基本一致灵汪，區(qū)別僅在于前者的生產(chǎn)和消費使用同一個鎖檀训，后者的生產(chǎn)和消費使用分離的兩個鎖。
ConcurrentLinkedQueue vsLinkedBlocklingQueue vs ArrayBlockingQueue
ConcurrentLinkedQueue是非阻塞隊列享言，其他兩者為阻塞隊列
三者都是線程安全的
LinkedBlocklingQueue是無界的峻凫，適合實現(xiàn)不限長度的隊列， ArrayBlockingQueue適合實現(xiàn)定長的隊列
SynchronousQueue算是JDK實現(xiàn)的隊列中比較奇葩的一個览露，它不能保存任何元素荧琼，size永遠是0，peek()永遠返回null差牛。向其中插入元素的線程會阻塞命锄，直到有另一個線程將這個元素取走，反之從其中取元素的線程也會阻塞偏化，直到有另一個線程插入元素脐恩。
這種實現(xiàn)機制非常適合傳遞性的場景。也就是說如果生產(chǎn)者線程需要及時確認到自己生產(chǎn)的任務已經(jīng)被消費者線程取走后才能執(zhí)行后續(xù)邏輯的場景下夹孔，適合使用SynchronousQueue被盈。
PriorityQueue & PriorityBlockingQueue
這兩種Queue并不是FIFO隊列，而是根據(jù)元素的優(yōu)先級進行排序搭伤，保證最小的元素最先出隊只怎，也可以在構(gòu)造隊列時傳入Comparator實例，這樣PriorityQueue就會按照Comparator實例的要求對元素進行排序怜俐。
PriorityQueue是非阻塞隊列身堡，也不是線程安全的，PriorityBlockingQueue是阻塞隊列拍鲤，同時也是線程安全的贴谎。
Deque 的實現(xiàn)類包括LinkedList（前文已描述過）、ConcurrentLinkedDeque季稳、LinkedBlockingDeque擅这，其實現(xiàn)機制與前文所述的ConcurrentLinkedQueue和LinkedBlockingQueue非常類似，此處不再贅述
最后景鼠，對本文中描述的常用集合實現(xiàn)類做一個簡單總結(jié)：
