Java 集合框架看這篇就夠了

話不多說，直接上圖：

Java 集合，也稱為容器，主要是由兩大介面(Interface) 衍生出來的：
Collection 和Map

顧名思義，容器就是用來存放資料的。

那麼這兩大介面的不同之處在於：

• Collection 存放單一元素；
• Map 存放key- value 鍵值對。

就是單身狗放 Collection 裡面，couple 就放 Map 裡。 （所以你屬於哪裡？

學習這些集合框架，我認為有4 個目標：

1. 明確每個介面和類別的對應關係；
2. 對每個介面和類別，熟悉常用的API；
3. 對不同的場景，能夠選擇合適的資料結構並分析優缺點；
4. 學習原始碼的設計，面試要會答啊。

#關於Map，之前那篇HashMap 的文章已經講的非常透徹詳盡了，所以本文不再贅述。如果還沒看過那篇文章的夥伴，快去公眾號內回覆「HashMap」看文章吧～

##Collection

Collection 裡也定義了許多方法，這些方法也會繼承到各個子介面和實作類別裡，而這些API 的使用也是日常工作和麵試常見常考的，所以我們先來看下這些方法。

操作集合，無非是「增刪改查」四大類，也叫CRUD:

Create, Read, Update, and Delete.

那我也把這些API 分成這四大類：

下面具體來看：

增：

boolean add(E e);

add() 方法傳入的資料型別必須是Object，所以當寫入基本資料型別的時候，會做自動裝箱auto-boxing 和自動拆箱unboxing。

還有另一個方法 addAll()，可以把另一個集合裡的元素加到此集合中。

boolean addAll(Collection<? extends E> c);

刪除：

boolean remove(Object o);

#remove()是刪除的指定元素。

那和 addAll() 對應的，
自然就有removeAll()，就是把集合 B 中的所有元素都刪除。

boolean removeAll(Collection<?> c);

改：

Collection Interface 裡並沒有直接改元素的操作，反正刪和增就可以完成改了嘛！

查：

• 查下集合中有没有某个特定的元素：

boolean contains(Object o);

• 查集合 A 是否包含了集合 B：

boolean containsAll(Collection<?> c);

还有一些对集合整体的操作：

• 判断集合是否为空：

boolean isEmpty();

• 集合的大小：

int size();

• 把集合转成数组：

Object[] toArray();

以上就是 Collection 中常用的 API 了。

在接口里都定义好了，子类不要也得要。

当然子类也会做一些自己的实现，这样就有了不同的数据结构。

那我们一个个来看。

List

List 最大的特点就是：有序，可重复。

看官网说的：

An ordered collection (also known as a sequence).

Unlike sets, lists typically allow duplicate elements.

這一下把 Set 的特點也說出來了，跟 List 完全相反，Set 是 無序，不重複的。

List 的實作方式有 LinkedList 和 ArrayList 兩種，那面試時最常問的就是這兩個資料結構如何選擇。

對於這類選擇問題：
一是考慮資料結構是否能完成需要的功能；
如果都能完成，二是考慮哪一個更高效。

（萬事都是如此啊。

那具體來看這兩個 classes 的 API 和它們的時間複雜度：

稍微解釋幾個：

add(E e) 是在尾巴上加元素，雖然ArrayList 可能會有擴容的情況出現，但是均攤複雜度（amortized time complexity ）還是O(1) 的。

add(int index, E e)是在特定的位置上加元素，LinkedList 需要先找到這個位置，再加上這個元素，雖然單純的「加上」這個動作是O(1) 的，但是要找出這個位置還是O(n) 的。 （這個有的人就認為是O(1)，和麵試官解釋清楚就行了，拒絕扛精。

remove(int index)是remove 這個index 上的元素，所以

• ArrayList 找到這個元素的過程是O(1)，但是remove 之後，後續元素都要往前移動一位，所以均攤複雜度是O(n)；
• LinkedList 也是要先找這個index，這個過程是O(n) 的，所以整體也是O(n)。

remove(E e)是remove 見到的第一個這個元素，那麼

• #ArrayList 要先找出這個元素，這個過程是O(n)，然後移除後還要往前移一位，這個更是O(n)，總的還是O(n)；
• #LinkedList 也是要先找，這個過程是O(n )，然後移走，這個過程是O(1)，總的是O(n).

那造成時間複雜度的區別的原因是什麼呢？

答案：

• 因為ArrayList 是用陣列來實作的。

• ##而陣列和鍊錶的最大差別就是

  陣列是可以隨機存取的（random access）。

那「增刪」呢？

如果不考慮找到這個元素的時間，

數組因為物理上的連續性，當要增刪元素時，在尾部還好，但是其他地方就會導致後續元素都要移動，所以效率較低；而鍊錶則可以輕鬆的斷開和下一個元素的連接，直接插入新元素或移除舊元素。

但是呢，其實你不能不考慮找到元素的時間。 。 。而且如果是在尾部操作，資料量大時 ArrayList 會更快的。

所以說：

1. 改查選擇ArrayList；
2. 增刪在尾部的選擇ArrayList；
3. 其他情況下，如果時間複雜度一樣，推薦選擇ArrayList，因為overhead 更小，或者說內存使用更有效率。

Vector

#那作為 List 的最後一個知識點，我們來聊聊 Vector。這也是一個年齡暴露帖，用過的都是大佬。

那 Vector 和 ArrayList 一樣，也是繼承自 java.util.AbstractList#，底層也是用陣列來實現的。

但現在已經被棄用了，因為...它加了太多的 synchronized！

任何好處都是有代價的，線程安全的成本就是效率低，在某些系統裡很容易成為瓶頸，所以現在大家不再在資料結構的層面加synchronized，而是把這個任務轉移給我們程式設計師==

那麼面試常問題：Vector 和ArrayList 的差別是什麼，只回答這個還不太全面。

來看stack overflow 上的高票回答：

#一是剛才已經說過的線程安全問題；
二是擴容時擴多少的差別。

這個得看看原始碼：

這是ArrayList 的擴容實現，這個算術右移操作是把這個數的二進位往右移動一位，最左邊補符號位，但是因為容量沒有負數，所以還是補0.

那右移一位的效果就是除以2 ，那麼定義的新容量就是原容量的1.5 倍。

再來看 Vector 的：

因為通常 capacityIncrement 我們不會定義，所以預設情況下它是擴容兩倍。

答出來這兩點，就肯定沒問題了。

Queue & Deque

#Queue 是一端進另一端出的線性資料結構；而Deque 是兩端都可以進出的。

Queue

#Java 中的這個Queue 介面稍微有點坑，一般來說佇列的語義都是先進先出（FIFO）的。

但這裡有個例外，就是PriorityQueue，也叫heap，並不按照進去的時間順序出來，而是按照規定的優先級出去，並且它的操作並不是O(1) 的，時間複雜度的計算稍微有點複雜，我們之後再單獨開一篇來講。

那 Queue 的方法官網^[1]都總結好了，它有兩組 API，基本功能是一樣的，但是呢：

• 一組是會拋異常的；
• 另一組會回傳一個特殊值。

為什麼會拋異常呢？

• 例如佇列空了，那remove() 就會拋異常，但是poll() 就回傳null；element() 就會拋異常，而peek() 就返回null 就好了。

那 add(e) 怎麼會拋異常呢？

有些Queue 它會有容量的限制，例如BlockingQueue，那如果已經達到了它最大的容量且不會擴容的，就會拋異常；但如果offer (e)，就會return false.

那要怎麼選擇呢？ ：

• 首先，要用就用同一組API，前後要統一；

• 其次，根據需求。如果你需要它拋異常，那就是用拋異常的；不過做算法題時基本上不用，所以選那組回傳特殊值的就好了。

Deque

#Deque 是兩端都可以進出的，那自然是有針對First 端的操作和對Last 端的操作，那每端都有兩組，一組拋異常，一組傳回特殊值：

使用時同理，要用就用同一組。

Queue 和 Deque 的這些 API 都是 O(1) 的時間複雜度，準確來說是均攤時間複雜度。

實作類別

它們的實作類別有這三個：

所以說，

• 如果想實作「普通佇列- 先進先出」的語義，就使用LinkedList 或ArrayDeque 來實作;
• 如果想實作「優先佇列」的語義，就使用PriorityQueue;
• 如果想實作「堆疊」的語義，就使用ArrayDeque。

我們一個個來看。

在實作普通佇列時，如何選擇用 LinkedList 還是 ArrayDeque 呢？

來看看StackOverflow^[2] 上的高票答案：

那 ArrayDeque 和 LinkedList 的差別有哪些呢？

1. ArrayDeque是一個可擴容的數組，LinkedList 是鍊錶結構；
2. ArrayDeque 裡不可以存null 值，但是LinkedList 可以；
3. #ArrayDeque 在操作頭尾端的增刪操作時更有效率，但是LinkedList 只有在當要移除中間某個元素且已經找到了這個元素後的移除才是O(1) 的；
4. ArrayDeque 在記憶體使用方面更有效率。

那如果是很資深的面試官問你，什麼情況下你要選擇用 LinkedList 呢？

• 答：Java 6 以前。。。因为 ArrayDeque 在 Java 6 之后才有的。。

为了版本兼容的问题，实际工作中我们不得不做一些妥协。。

那最后一个问题，就是关于 Stack 了。

Stack

Stack 在语义上是 后进先出（LIFO） 的线性数据结构。

有很多高频面试题都是要用到栈的，比如接水问题，虽然最优解是用双指针，但是用栈是最直观的解法也是需要了解的，之后有机会再专门写吧。

那在 Java 中是怎么实现栈的呢？

虽然 Java 中有 Stack 这个类，但是呢，官方文档都说不让用了！

原因也很简单，因为 Vector 已经过被弃用了，而 Stack 是继承 Vector 的。

那么想实现 Stack 的语义，就用 ArrayDeque 吧：

Deque<Integer> stack = new ArrayDeque<>();

Set

最后一个 Set，刚才已经说过了 Set 的特定是无序，不重复的。

就和数学里学的「集合」的概念一致。

Set 的常用实现类有三个：

HashSet: 采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。

LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。

TreeSet: 采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。

那每个 Set 的底层实现其实就是对应的 Map：

數值放在 map 中的 key 上，value 上放了個 PRESENT，是靜態的 Object，相當於 place holder，每個 key 都指向這個 object。

那麼具體的實作原理、增刪改查四種操作，以及雜湊衝突、hashCode( )/equals() 等問題都在HashMap 那篇文章裡講過了，這裡就不贅述了，沒有看過的小伙伴可以在公眾號後台回复“HashMap”獲取文章哦～

總結

#再回到開篇的這張圖，有沒有清楚了一些呢？

每個資料結構下面其實都有很多內容，像是 PriorityQueue 本文沒有細說，因為這傢伙一說又要半天。 。

如果你覺得文章不錯，文末的讚? 又回來啦，記得給我「讚」和「在看」喔～

最後呢，很多讀者一直有問我交流群的問題，因為考慮到我有時差不方便管理，所以一直沒做。

但現在我找了一個專業的管理員和我一起管理，所以「齊姐的秘密基地」正在籌備中，並且我會邀請國內外的一些大佬入場，給大家帶來不一樣的視角。

那麼第一期交流群組計畫於 7 月初開放，到時候我會在朋友圈發邀請，大家敬請期待！