死磕 java集合之終結(jié)篇

概覽

我們先來(lái)看一看java中所有集合的類關(guān)系圖。

這里面的類太多了，請(qǐng)放大看，如果放大還看不清，請(qǐng)?jiān)俜糯罂?，如果還是看不清，請(qǐng)放棄。

我們下面主要分成五個(gè)部分來(lái)逐個(gè)擊破。

List

List中的元素是有序的、可重復(fù)的，主要實(shí)現(xiàn)方式有動(dòng)態(tài)數(shù)組和鏈表。

java中提供的List的實(shí)現(xiàn)主要有ArrayList、LinkedList、CopyOnWriteArrayList，另外還有兩個(gè)古老的類Vector和Stack。

關(guān)于List相關(guān)的問(wèn)題主要有：

（1）ArrayList和LinkedList有什么區(qū)別？

（2）ArrayList是怎么擴(kuò)容的？

（3）ArrayList插入、刪除、查詢?cè)氐臅r(shí)間復(fù)雜度各是多少？

（4）怎么求兩個(gè)集合的并集、交集、差集？

（5）ArrayList是怎么實(shí)現(xiàn)序列化和反序列化的？

（6）集合的方法toArray()有什么問(wèn)題？

（7）什么是fail-fast？

（8）LinkedList是單鏈表還是雙鏈表實(shí)現(xiàn)的？

（9）LinkedList除了作為L(zhǎng)ist還有什么用處？

（10）LinkedList插入、刪除、查詢?cè)氐臅r(shí)間復(fù)雜度各是多少？

（11）什么是隨機(jī)訪問(wèn)？

（12）哪些集合支持隨機(jī)訪問(wèn)？他們都有哪些共性？

（13）CopyOnWriteArrayList是怎么保證并發(fā)安全的？

（14）CopyOnWriteArrayList的實(shí)現(xiàn)采用了什么思想？

（15）CopyOnWriteArrayList是不是強(qiáng)一致性的？

（16）CopyOnWriteArrayList適用于什么樣的場(chǎng)景？

（17）CopyOnWriteArrayList插入、刪除、查詢?cè)氐臅r(shí)間復(fù)雜度各是多少？

（18）CopyOnWriteArrayList為什么沒(méi)有size屬性？

（19）比較古老的集合Vector和Stack有什么缺陷？

關(guān)于List的問(wèn)題大概就這么多，你都能回答上來(lái)嗎？

點(diǎn)擊下面鏈接可以直接到相應(yīng)的章節(jié)查看：

死磕 Java集合之ArrayList源碼分析

死磕 java集合之LinkedList源碼分析

死磕 java集合之CopyOnWriteArrayList源碼分析

Map

Map是一種(key/value)的映射結(jié)構(gòu)，其它語(yǔ)言里可能稱作字典（Dictionary），包括java早期也是叫做字典，Map中的元素是一個(gè)key只能對(duì)應(yīng)一個(gè)value，不能存在重復(fù)的key。

java中提供的Map的實(shí)現(xiàn)主要有HashMap、LinkedHashMap、WeakHashMap、TreeMap、ConcurrentHashMap、ConcurrentSkipListMap，另外還有兩個(gè)比較古老的Map實(shí)現(xiàn)HashTable和Properties。

關(guān)于Map的問(wèn)題主要有：

（1）什么是散列表？

（2）怎么實(shí)現(xiàn)一個(gè)散列表？

（3）java中HashMap實(shí)現(xiàn)方式的演進(jìn)？

（4）HashMap的容量有什么特點(diǎn)？

（5）HashMap是怎么進(jìn)行擴(kuò)容的？

（6）HashMap中的元素是否是有序的？

（7）HashMap何時(shí)進(jìn)行樹化？何時(shí)進(jìn)行反樹化？

（8）HashMap是怎么進(jìn)行縮容的？

（9）HashMap插入、刪除、查詢?cè)氐臅r(shí)間復(fù)雜度各是多少？

（10）HashMap中的紅黑樹實(shí)現(xiàn)部分可以用其它數(shù)據(jù)結(jié)構(gòu)代替嗎？

（11）LinkedHashMap是怎么實(shí)現(xiàn)的？

（12）LinkedHashMap是有序的嗎？怎么個(gè)有序法？

（13）LinkedHashMap如何實(shí)現(xiàn)LRU緩存淘汰策略？

（14）WeakHashMap使用的數(shù)據(jù)結(jié)構(gòu)？

（15）WeakHashMap具有什么特性？

（16）WeakHashMap通常用來(lái)做什么？

（17）WeakHashMap使用String作為key是需要注意些什么？為什么？

（18）什么是弱引用？

（19）紅黑樹具有哪些特性？

（20）TreeMap就有序的嗎？怎么個(gè)有序法？

（21）TreeMap是否需要擴(kuò)容？

（22）什么是左旋？什么是右旋？

（23）紅黑樹怎么插入元素？

（24）紅黑樹怎么刪除元素？

（25）為什么要進(jìn)行平衡？

（26）如何實(shí)現(xiàn)紅黑樹的遍歷？

（27）TreeMap中是怎么遍歷的？

（28）TreeMap插入、刪除、查詢?cè)氐臅r(shí)間復(fù)雜度各是多少？

（29）HashMap在多線程環(huán)境中什么時(shí)候會(huì)出現(xiàn)問(wèn)題？

（30）ConcurrentHashMap的存儲(chǔ)結(jié)構(gòu)？

（31）ConcurrentHashMap是怎么保證并發(fā)安全的？

（32）ConcurrentHashMap是怎么擴(kuò)容的？

（33）ConcurrentHashMap的size()方法的實(shí)現(xiàn)知多少？

（34）ConcurrentHashMap是強(qiáng)一致性的嗎？

（35）ConcurrentHashMap不能解決什么問(wèn)題？

（36）ConcurrentHashMap中哪些地方運(yùn)用到分段鎖的思想？

（37）什么是偽共享？怎么避免偽共享？

（38）什么是跳表？

（40）ConcurrentSkipList是有序的嗎？

（41）ConcurrentSkipList是如何保證線程安全的？

（42）ConcurrentSkipList插入、刪除、查詢?cè)氐臅r(shí)間復(fù)雜度各是多少？

（43）ConcurrentSkipList的索引具有什么特性？

（44）為什么Redis選擇使用跳表而不是紅黑樹來(lái)實(shí)現(xiàn)有序集合？

關(guān)于Map的問(wèn)題大概就這么多，你都能回答上來(lái)嗎？

點(diǎn)擊下面鏈接可以直接到相應(yīng)的章節(jié)查看：

死磕 java集合之HashMap源碼分析

死磕 java集合之LinkedHashMap源碼分析

死磕 java集合之WeakHashMap源碼分析

死磕 java集合之TreeMap源碼分析（一）

死磕 java集合之TreeMap源碼分析（二）

死磕 java集合之TreeMap源碼分析（三）

死磕 java集合之TreeMap源碼分析（四）

死磕 java集合之ConcurrentHashMap源碼分析（一）

死磕 java集合之ConcurrentHashMap源碼分析（二）

死磕 java集合之ConcurrentHashMap源碼分析（三）

死磕 java集合之ConcurrentSkipListMap源碼分析

Set

java里面的Set對(duì)應(yīng)于數(shù)學(xué)概念上的集合，里面的元素是不可重復(fù)的，通常使用Map或者List來(lái)實(shí)現(xiàn)。

java中提供的Set的實(shí)現(xiàn)主要有HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet、ConcurrentSkipSet。

關(guān)于Set的問(wèn)題主要有：

（1）HashSet怎么保證添加元素不重復(fù)？

（2）HashSet是有序的嗎？

（3）HashSet是否允許null元素？

（4）Set是否有g(shù)et()方法？

（5）LinkedHashSet是有序的嗎？怎么個(gè)有序法？

（6）LinkedHashSet支持按元素訪問(wèn)順序排序嗎？

（8）TreeSet真的是使用TreeMap來(lái)存儲(chǔ)元素的嗎？

（9）TreeSet是有序的嗎？怎么個(gè)有序法？

（10）TreeSet和LinkedHashSet有何不同？

（11）TreeSet和SortedSet有什么區(qū)別和聯(lián)系？

（12）CopyOnWriteArraySet是用Map實(shí)現(xiàn)的嗎？

（13）CopyOnWriteArraySet是有序的嗎？怎么個(gè)有序法？

（14）CopyOnWriteArraySet怎么保證并發(fā)安全？

（15）CopyOnWriteArraySet以何種方式保證元素不重復(fù)？

（16）如何比較兩個(gè)Set中的元素是否完全一致？

（17）ConcurrentSkipListSet的底層是ConcurrentSkipListMap嗎？

（18）ConcurrentSkipListSet是有序的嗎？怎么個(gè)有序法？

關(guān)于Set的問(wèn)題大概就這么多，你都能回答上來(lái)嗎？

點(diǎn)擊下面鏈接可以直接到相應(yīng)的章節(jié)查看：

死磕 java集合之HashSet源碼分析

死磕 java集合之LinkedHashSet源碼分析

死磕 java集合之TreeSet源碼分析

死磕 java集合之CopyOnWriteArraySet源碼分析

死磕 java集合之ConcurrentSkipListSet源碼分析

Queue

Queue是一種叫做隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列是遵循著一定原則的入隊(duì)出隊(duì)操作的集合，一般來(lái)說(shuō)，入隊(duì)是在隊(duì)列尾添加元素，出隊(duì)是在隊(duì)列頭刪除元素，但是，也不一定，比如優(yōu)先級(jí)隊(duì)列的原則就稍微有些不同。

java中提供的Queue的實(shí)現(xiàn)主要有PriorityQueue、ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、PriorityBlockingQueue、LinkedTransferQueue、DelayQueue、ConcurrentLinkedQueue。

關(guān)于Queue的問(wèn)題主要有：

（1）什么是堆？什么是堆化？

（2）什么是優(yōu)先級(jí)隊(duì)列？

（3）PriorityQueue是怎么實(shí)現(xiàn)的？

（4）PriorityQueue是有序的嗎？

（5）PriorityQueue入隊(duì)、出隊(duì)的時(shí)間復(fù)雜度各是多少？

（6）PriorityQueue是否需要擴(kuò)容？擴(kuò)容規(guī)則呢？

（7）ArrayBlockingQueue的實(shí)現(xiàn)方式？

（8）ArrayBlockingQueue是否需要擴(kuò)容？

（9）ArrayBlockingQueue怎么保證線程安全？

（9）ArrayBlockingQueue有什么缺點(diǎn)？

（10）LinkedBlockingQueue的實(shí)現(xiàn)方式？

（11）LinkedBlockingQueue是有界的還是×××的隊(duì)列？

（12）LinkedBlockingQueue怎么保證線程安全？

（13）LinkedBlockingQueue與ArrayBlockingQueue對(duì)比？

（14）SynchronousQueue的實(shí)現(xiàn)方式？

（15）SynchronousQueue真的是無(wú)緩沖的嗎？

（16）SynchronousQueue怎么保證線程安全？

（17）SynchronousQueue的公平模式和非公平模式有什么區(qū)別？

（18）SynchronousQueue在高并發(fā)情景下會(huì)有什么問(wèn)題？

（19）PriorityBlockingQueue的實(shí)現(xiàn)方式？

（20）PriorityBlockingQueue是否需要擴(kuò)容？

（21）PriorityBlockingQueue怎么保證線程安全？

（22）PriorityBlockingQueue為什么不需要notFull條件？

（23）什么是雙重隊(duì)列？

（24）LinkedTransferQueue是怎么實(shí)現(xiàn)阻塞隊(duì)列的？

（25）LinkedTransferQueue是怎么控制并發(fā)安全的？

（26）LinkedTransferQueue與SynchronousQueue有什么異同？

（27）ConcurrentLinkedQueue是阻塞隊(duì)列嗎？

（28）ConcurrentLinkedQueue如何保證并發(fā)安全？

（29）ConcurrentLinkedQueue能用于線程池嗎？

（30）DelayQueue是阻塞隊(duì)列嗎？

（31）DelayQueue的實(shí)現(xiàn)方式？

（32）DelayQueue主要用于什么場(chǎng)景？

關(guān)于Queue的問(wèn)題大概就這么多，你都能回答上來(lái)嗎？

點(diǎn)擊下面鏈接可以直接到相應(yīng)的章節(jié)查看：

死磕 java集合之PriorityQueue源碼分析

死磕 java集合之ArrayBlockingQueue源碼分析

死磕 java集合之LinkedBlockingQueue源碼分析

死磕 java集合之SynchronousQueue源碼分析

死磕 java集合之PriorityBlockingQueue源碼分析

死磕 java集合之LinkedTransferQueue源碼分析

死磕 java集合之ConcurrentLinkedQueue源碼分析

死磕 java集合之DelayQueue源碼分析

Deque

Deque是一種特殊的隊(duì)列，它的兩端都可以進(jìn)出元素，故而得名雙端隊(duì)列（Double Ended Queue）。

java中提供的Deque的實(shí)現(xiàn)主要有ArrayDeque、LinkedBlockingDeque、ConcurrentLinkedDeque、LinkedList。

關(guān)于Deque的問(wèn)題主要有：

（1）什么是雙端隊(duì)列？

（2）ArrayDeque是怎么實(shí)現(xiàn)雙端隊(duì)列的？

（3）ArrayDeque是有界的嗎？

（4）LinkedList與ArrayDeque的對(duì)比？

（5）雙端隊(duì)列是否可以作為棧使用？

（6）LinkedBlockingDeque是怎么實(shí)現(xiàn)雙端隊(duì)列的？

（7）LinkedBlockingDeque是怎么保證并發(fā)安全的？

（8）ConcurrentLinkedDeque是怎么實(shí)現(xiàn)雙端隊(duì)列的？

（9）ConcurrentLinkedDeque是怎么保證并發(fā)安全的？

（10）LinkedList是List和Deque的集合體？

關(guān)于Deque的問(wèn)題大概就這么多，你都能回答上來(lái)嗎？

點(diǎn)擊下面鏈接可以直接到相應(yīng)的章節(jié)查看（LinkedBlockingDeque和ConcurrentLinkedDeque跟相應(yīng)的Queue的實(shí)現(xiàn)方式基本一致，所以筆者沒(méi)寫這兩個(gè)類的源碼分析）：

死磕 java集合之ArrayDeque源碼分析

死磕 java集合之LinkedList源碼分析

總結(jié)

其實(shí)上面的問(wèn)題很多都具有共性，我覺(jué)得以下幾個(gè)問(wèn)題在看每個(gè)集合類的時(shí)候都要掌握清楚：

（1）使用的數(shù)據(jù)結(jié)構(gòu)？

（2）添加元素、刪除元素的基本邏輯？

（3）是否是fail-fast的？

（4）是否需要擴(kuò)容？擴(kuò)容規(guī)則？

（5）是否有序？是按插入順序還是自然順序還是訪問(wèn)順序？

（6）是否線程安全？

（7）使用的鎖？

（8）優(yōu)點(diǎn)？缺點(diǎn)？

（9）適用的場(chǎng)景？

（10）時(shí)間復(fù)雜度？

（11）空間復(fù)雜度？

（12）還有呢？

彩蛋

到這里整個(gè)集合的內(nèi)容就全部完畢了，其實(shí)看了這么多集合的源碼之后，筆者發(fā)現(xiàn)，基本上所有集合類使用的數(shù)據(jù)結(jié)構(gòu)都是數(shù)組和鏈表，包括樹和跳表也可以看成是鏈表的一種方式。

對(duì)于并發(fā)安全的集合，還要再加上相應(yīng)的鎖策略，要不就是重入鎖，要不就是CAS+自旋，偶爾也來(lái)個(gè)synchronized。

所以，掌握集合的源碼不算什么，數(shù)據(jù)結(jié)構(gòu)和鎖才是王道。

預(yù)告：下一個(gè)專題是java并發(fā)包，也就是著名的JUC，當(dāng)然這里是除了并發(fā)集合以外的內(nèi)容，也就是原子類、各種鎖、線程池三塊硬骨頭。

歡迎關(guān)注我的公眾號(hào)“彤哥讀源碼”，查看更多源碼系列文章, 與彤哥一起暢游源碼的海洋。