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提供的眾多集合類由兩大接口衍生而來：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è)賮砜匆幌逻@兩個(gè)接口衍生出來的常用集合類：
List類集合
圖片.png
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ù)組來實(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ù)組拷貝來實(shí)現(xiàn)指定位置的插入和刪除：
插入：
圖片.png
刪除：
圖片.png
LinkedList
LinkedList基于鏈表來實(shí)現(xiàn)集合的功能，其實(shí)現(xiàn)了靜態(tài)類Node芬首，集合中的每個(gè)對(duì)象都由一個(gè)Node保存赴捞，每個(gè)Node都擁有到自己的前一個(gè)和后一個(gè)Node的引用
LinkedList追加元素的過程示例：
圖片.png
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í)的讀操作無法保證能讀到這個(gè)寫操作的結(jié)果导绷。
Vector vs CopyOnWriteArrayList
二者均是線程安全的犀勒、基于數(shù)組實(shí)現(xiàn)的List
Vector是【絕對(duì)】線程安全的，CopyOnWriteArrayList只能保證讀線程會(huì)讀到【已完成】的寫結(jié)果妥曲，但無法像Vector一樣實(shí)現(xiàn)讀操作的【等待寫操作完成后再讀最新值】的能力
CopyOnWriteArrayList讀性能遠(yuǎn)高于Vector贾费，并發(fā)線程越多優(yōu)勢(shì)越明顯
CopyOnWriteArrayList占用更多的內(nèi)存空間
Map類集合
圖片.png
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)行過描述，我們直接來看一下Map接口的常用實(shí)現(xiàn)類
HashMap
HashMap將Entry對(duì)象存儲(chǔ)在一個(gè)數(shù)組中谎痢，并通過哈希表來實(shí)現(xiàn)對(duì)Entry的快速訪問：
圖片.png
由每個(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仿野。
圖片.png
HashMap的Entry類：
staticclassEntryimplementsMap.Entry{finalK key; V value; Entry next;inthash;}
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ā)性能从祝。
圖片.png
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í)的線程可見性档玻，無需加鎖便能實(shí)現(xiàn)線程安全的讀操作怀泊。
ConcurrentHashMap的HashEntry類：
staticfinalclassHashEntry {finalinthash;finalK key;volatileV value;volatileHashEntrynext;}
但是魚與熊掌不可兼得，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)行遍歷轴或。
圖片.png
TreeMap
TreeMap是基于紅黑樹實(shí)現(xiàn)的Map結(jié)構(gòu)昌跌，其Entry類擁有到左/右葉子節(jié)點(diǎn)和父節(jié)點(diǎn)的引用，同時(shí)還記錄了自己的顏色：
staticfinalclassEntryimplementsMap.Entry{ K key; V value; Entry left =null; Entry right =null; Entryparent;booleancolor = BLACK;}
紅黑樹實(shí)際是一種算法復(fù)雜但高效的平衡二叉樹照雁，具備二叉樹的基本性質(zhì)蚕愤，即任何節(jié)點(diǎn)的值大于其左葉子節(jié)點(diǎn)，小于其右葉子節(jié)點(diǎn)饺蚊，利用這種特性萍诱，TreeMap能夠?qū)崿F(xiàn)Entry的排序和快速查找。
TreeMap的Entry是有序的污呼，所以提供了一系列方便的功能裕坊，比如獲取以升序或降序排列的KeySet(EntrySet)、獲取在指定key(Entry)之前/之后的key(Entry)等等燕酷。適合需要對(duì)key進(jìn)行有序操作的場(chǎng)景籍凝。
ConcurrentSkipListMap
ConcurrentSkipListMap同樣能夠提供有序的Entry排列周瞎，但其實(shí)現(xiàn)原理與TreeMap不同，是基于跳表(SkipList)的：
圖片.png
如上圖所示饵蒂，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>{ finalNode<K,V>node;
finalIndex<K,V>down;//下引用 volatile Index<K,V>right;//右引用}
與TreeMap不同慰照，ConcurrentSkipListMap在進(jìn)行插入、刪除等操作時(shí)琉朽，只需要修改影響到的節(jié)點(diǎn)的右引用毒租，而右引用又是volatile的，所以ConcurrentSkipListMap是線程安全的漓骚。但ConcurrentSkipListMap與ConcurrentHashMap一樣蝌衔，不能保證數(shù)據(jù)的絕對(duì)一致性，在某些情況下有可能無法讀到正在被插入的數(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)完全一致炭庙，此處不再贅述饲窿。
圖片.png
Queue/Deque類集合
圖片.png
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 classNode<E> { volatile E item; volatileNode<E> next;}
由于Node類的成員都是volatile的芋肠，所以ConcurrentLinkedQueue自然是線程安全的。能夠保證入隊(duì)和出隊(duì)操作的原子性和一致性遵蚜，但在遍歷和size()操作時(shí)只能保證數(shù)據(jù)的弱一致性帖池。
LinkedBlockingQueue
與ConcurrentLinkedQueue不同，LinkedBlocklingQueue是一種無界的阻塞隊(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是無界的没宾，適合實(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é)：
