Java 集合看這一篇就夠了

大家好，這里是《齊姐聊資料結構》系列之大集合，

話不多說，直接上圖：

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

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

那么這兩大介面的不同之處在于：

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

就是單身狗放 Collection 里面，couple 就放 Map 里，（所以你屬于哪里？

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

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

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

Collection

先來看最上層的 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），

這個特點造成了在陣列里可以通過下標用 O(1) 的時間拿到任何位置的數，而鏈表則做不到，只能從頭開始逐個遍歷，

也就是說在「改查」這兩個功能上，因為陣列能夠隨機訪問，所以 ArrayList 的效率高，

那「增刪」呢？

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

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

但是呢，實際上你不能不考慮找到元素的時間啊，，，而且如果是在尾部操作，資料量大時 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 的方法官網都總結好了，它有兩組 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 上的高票回答：

總結來說就是推薦使用 ArrayDeque，因為效率高，而 LinkedList 還會有其他的額外開銷（overhead），

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

還是在剛才的同一個問題下，這是我認為總結的最好的：

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

所以，只要不是必須要存 null 值，就選擇 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 也就是堆，齊姐之前也專門寫過文章講解它的相關操作，比如很有名的 heapify() 的程序為什么是 O(n) 的等面試常問題，感興趣的小伙伴在公眾號后臺回復「堆」獲取文章吧～

如果你喜歡這篇文章，記得給我點贊留言哦～你們的支持和認可，就是我創作的最大動力，我們下篇文章見！

我是小齊，紐約程式媛，終生學習者，每天晚上 9 點，云自習室里不見不散！

更多干貨文章見我的 Github: https://github.com/xiaoqi6666/NYCSDE

標籤：其他

上一篇：「下載王APP」批量保存視頻號視頻、免費短視頻去水印、4K高清視頻下載

下一篇：K8S節點例外怎么辦？TKE"節點健康檢查和自愈"來幫忙