Java 集合框架，看这篇真的够了！
話不多說，直接上圖：
?
Java 集合，也稱作容器，主要是由兩大接口 (Interface)?派生出來的：
Collection 和 Map
顧名思義，容器就是用來存放數(shù)據(jù)的。
那么這兩大接口的不同之處在于：
-
Collection 存放單一元素；
-
Map 存放 key-value 鍵值對。
就是單身狗放 Collection 里面，couple 就放 Map 里。（所以你屬于哪里？
學習這些集合框架，我認為有 4 個目標：
明確每個接口和類的對應關系；
對每個接口和類，熟悉常用的 API；
對不同的場景，能夠選擇合適的數(shù)據(jù)結構并分析優(yōu)缺點；
學習源碼的設計，面試要會答啊。
關于 Map，之前那篇 HashMap 的文章已經(jīng)講的非常透徹詳盡了，所以本文不再贅述。如果還沒看過那篇文章的小伙伴，快去公眾號內(nèi)回復「Java」看文章吧～
Collection
先來看最上層的 Collection.
Collection 里還定義了很多方法，這些方法也都會繼承到各個子接口和實現(xiàn)類里，而這些 API 的使用也是日常工作和面試常見常考的，所以我們先來看下這些方法。
操作集合，無非就是「增刪改查」四大類，也叫?CRUD:
Create, Read, Update, and Delete.
那我也把這些 API 分為這四大類：
| 增 | add()/addAll() |
| 刪 | remove()/ removeAll() |
| 改 | Collection Interface 里沒有 |
| 查 | contains()/ containsAll() |
| 其他 | isEmpty()/size()/toArray() |
下面具體來看：
增：
boolean?add(E?e);add()?方法傳入的數(shù)據(jù)類型必須是 Object，所以當寫入基本數(shù)據(jù)類型的時候，會做自動裝箱 auto-boxing 和自動拆箱 unboxing。
還有另外一個方法?addAll()，可以把另一個集合里的元素加到此集合中。
boolean?addAll(Collection<??extends?E>?c);刪：
boolean?remove(Object?o);remove()是刪除的指定元素。
那和?addAll()?對應的，
自然就有removeAll()，就是把集合 B 中的所有元素都刪掉。
改：
Collection Interface 里并沒有直接改元素的操作，反正刪和增就可以完成改了嘛！
查：
-
查下集合中有沒有某個特定的元素：
-
查集合 A 是否包含了集合 B：
還有一些對集合整體的操作：
-
判斷集合是否為空：
-
集合的大小：
-
把集合轉(zhuǎn)成數(shù)組：
以上就是 Collection 中常用的 API 了。
在接口里都定義好了，子類不要也得要。
當然子類也會做一些自己的實現(xiàn)，這樣就有了不同的數(shù)據(jù)結構。
那我們一個個來看。
List
List 最大的特點就是：有序，可重復。
看官網(wǎng)說的：
An ordered collection (also known as a sequence).
Unlike sets, lists typically allow duplicate elements.
這一下把 Set 的特點也說出來了，和 List 完全相反，Set 是?無序，不重復的。
List 的實現(xiàn)方式有 LinkedList 和 ArrayList 兩種，那面試時最常問的就是這兩個數(shù)據(jù)結構如何選擇。
對于這類選擇問題：
一是考慮數(shù)據(jù)結構是否能完成需要的功能；
如果都能完成，二是考慮哪種更高效。
（萬事都是如此啊。
那具體來看這兩個 classes 的 API 和它們的時間復雜度：
| 增 | add(E e) | O(1) | O(1) |
| 增 | add(int index, E e) | O(n) | O(n) |
| 刪 | remove(int index) | O(n) | O(n) |
| 刪 | remove(E e) | O(n) | O(n) |
| 改 | set(int index, E e) | O(1) | O(n) |
| 查 | get(int index) | O(1) | O(n) |
稍微解釋幾個：
add(E e)?是在尾巴上加元素，雖然 ArrayList 可能會有擴容的情況出現(xiàn)，但是均攤復雜度（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 之后，后續(xù)元素都要往前移動一位，所以均攤復雜度是 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).
那造成時間復雜度的區(qū)別的原因是什么呢？
答：
-
因為 ArrayList 是用數(shù)組來實現(xiàn)的。
-
而數(shù)組和鏈表的最大區(qū)別就是數(shù)組是可以隨機訪問的（random access）。
這個特點造成了在數(shù)組里可以通過下標用 O(1) 的時間拿到任何位置的數(shù)，而鏈表則做不到，只能從頭開始逐個遍歷。
也就是說在「改查」這兩個功能上，因為數(shù)組能夠隨機訪問，所以 ArrayList 的效率高。
那「增刪」呢？
如果不考慮找到這個元素的時間，
數(shù)組因為物理上的連續(xù)性，當要增刪元素時，在尾部還好，但是其他地方就會導致后續(xù)元素都要移動，所以效率較低；而鏈表則可以輕松的斷開和下一個元素的連接，直接插入新元素或者移除舊元素。
但是呢，實際上你不能不考慮找到元素的時間啊。。。而且如果是在尾部操作，數(shù)據(jù)量大時 ArrayList 會更快的。
所以說：
改查選擇 ArrayList；
增刪在尾部的選擇 ArrayList；
其他情況下，如果時間復雜度一樣，推薦選擇 ArrayList，因為 overhead 更小，或者說內(nèi)存使用更有效率。
Vector
那作為 List 的最后一個知識點，我們來聊一下 Vector。這也是一個年齡暴露帖，用過的都是大佬。
那 Vector 和 ArrayList 一樣，也是繼承自 java.util.AbstractList，底層也是用數(shù)組來實現(xiàn)的。
但是現(xiàn)在已經(jīng)被棄用了，因為...它加了太多的 synchronized！
任何好處都是有代價的，線程安全的成本就是效率低，在某些系統(tǒng)里很容易成為瓶頸，所以現(xiàn)在大家不再在數(shù)據(jù)結構的層面加 synchronized，而是把這個任務轉(zhuǎn)移給我們程序員==
那么面試常問題：Vector 和 ArrayList 的區(qū)別是什么，只答出來這個還還不太全面。
來看 stack overflow 上的高票回答：
一是剛才已經(jīng)說過的線程安全問題；
二是擴容時擴多少的區(qū)別。
這個得看看源碼：
這是 ArrayList 的擴容實現(xiàn)，這個算術右移操作是把這個數(shù)的二進制往右移動一位，最左邊補符號位，但是因為容量沒有負數(shù)，所以還是補 0.
那右移一位的效果就是除以 2，那么定義的新容量就是原容量的?1.5 倍。
再來看 Vector 的：
因為通常 capacityIncrement 我們并不定義，所以默認情況下它是擴容兩倍。
答出來這兩點，就肯定沒問題了。
Queue & Deque
Queue 是一端進另一端出的線性數(shù)據(jù)結構；而 Deque 是兩端都可以進出的。
Queue
Java 中的 這個 Queue 接口稍微有點坑，一般來說隊列的語義都是先進先出（FIFO）的。
但是這里有個例外，就是 PriorityQueue，也叫 heap，并不按照進去的時間順序出來，而是按照規(guī)定的優(yōu)先級出去，并且它的操作并不是 O(1) 的，時間復雜度的計算稍微有點復雜，我們之后單獨開一篇來講。
那 Queue 的方法官網(wǎng)[1]都總結好了，它有兩組 API，基本功能是一樣的，但是呢：
-
一組是會拋異常的；
-
另一組會返回一個特殊值。
| 增 | add(e) | offer(e) |
| 刪 | remove() | poll() |
| 瞧 | element() | peek() |
為什么會拋異常呢？
-
比如隊列空了，那 remove() 就會拋異常，但是 poll() 就返回 null；element() 就會拋異常，而 peek() 就返回 null 就好了。
那 add(e) 怎么會拋異常呢？
有些 Queue 它會有容量的限制，比如?BlockingQueue，那如果已經(jīng)達到了它最大的容量且不會擴容的，就會拋異常；但如果 offer(e)，就會 return false.
那怎么選擇呢？：
-
首先，要用就用同一組 API，前后要統(tǒng)一；
-
其次，根據(jù)需求。如果你需要它拋異常，那就是用拋異常的；不過做算法題時基本不用，所以選那組返回特殊值的就好了。
Deque
Deque 是兩端都可以進出的，那自然是有針對 First 端的操作和對 Last 端的操作，那每端都有兩組，一組拋異常，一組返回特殊值：
| 增 | addFirst(e)/ addLast(e) | offerFirst(e)/ offerLast(e) |
| 刪 | removeFirst()/ removeLast() | pollFirst()/ pollLast() |
| 瞧 | getFirst()/ getLast() | peekFirst()/ peekLast() |
使用時同理，要用就用同一組。
Queue 和 Deque 的這些 API 都是 O(1) 的時間復雜度，準確來說是均攤時間復雜度。
實現(xiàn)類
它們的實現(xiàn)類有這三個：
所以說，
-
如果想實現(xiàn)「普通隊列 - 先進先出」的語義，就使用 LinkedList 或者 ArrayDeque 來實現(xiàn)；
-
如果想實現(xiàn)「優(yōu)先隊列」的語義，就使用 PriorityQueue；
-
如果想實現(xiàn)「棧」的語義，就使用 ArrayDeque。
我們一個個來看。
在實現(xiàn)普通隊列時，如何選擇用 LinkedList 還是 ArrayDeque 呢？
來看一下?StackOverflow[2]?上的高票回答：
總結來說就是推薦使用 ArrayDeque，因為效率高，而 LinkedList 還會有其他的額外開銷（overhead）。
那 ArrayDeque 和 LinkedList 的區(qū)別有哪些呢？
還是在剛才的同一個問題下，這是我認為總結的最好的：
ArrayDeque 是一個可擴容的數(shù)組，LinkedList 是鏈表結構；
ArrayDeque 里不可以存 null 值，但是 LinkedList 可以；
ArrayDeque 在操作頭尾端的增刪操作時更高效，但是 LinkedList 只有在當要移除中間某個元素且已經(jīng)找到了這個元素后的移除才是 O(1) 的；
ArrayDeque 在內(nèi)存使用方面更高效。
所以，只要不是必須要存 null 值，就選擇 ArrayDeque 吧！
那如果是一個很資深的面試官問你，什么情況下你要選擇用 LinkedList 呢？
-
答：Java 6 以前。。。因為 ArrayDeque 在 Java 6 之后才有的。。
為了版本兼容的問題，實際工作中我們不得不做一些妥協(xié)。。
那最后一個問題，就是關于 Stack 了。
Stack
Stack 在語義上是?后進先出（LIFO）?的線性數(shù)據(jù)結構。
有很多高頻面試題都是要用到棧的，比如接水問題，雖然最優(yōu)解是用雙指針，但是用棧是最直觀的解法也是需要了解的，之后有機會再專門寫吧。
那在 Java 中是怎么實現(xiàn)棧的呢？
雖然 Java 中有 Stack 這個類，但是呢，官方文檔都說不讓用了！
原因也很簡單，因為 Vector 已經(jīng)過被棄用了，而 Stack 是繼承 Vector 的。
那么想實現(xiàn) Stack 的語義，就用 ArrayDeque 吧：
Deque<Integer>?stack?=?new?ArrayDeque<>();Set
最后一個 Set，剛才已經(jīng)說過了 Set 的特定是無序，不重復的。
就和數(shù)學里學的「集合」的概念一致。
Set 的常用實現(xiàn)類有三個：
HashSet: 采用 Hashmap 的 key 來儲存元素，主要特點是無序的，基本操作都是 O(1) 的時間復雜度，很快。
LinkedHashSet: 這個是一個 HashSet + LinkedList 的結構，特點就是既擁有了 O(1) 的時間復雜度，又能夠保留插入的順序。
TreeSet: 采用紅黑樹結構，特點是可以有序，可以用自然排序或者自定義比較器來排序；缺點就是查詢速度沒有 HashSet 快。
那每個 Set 的底層實現(xiàn)其實就是對應的 Map：
數(shù)值放在 map 中的 key 上，value 上放了個 PRESENT，是一個靜態(tài)的 Object，相當于 place holder，每個 key 都指向這個 object。
那么具體的實現(xiàn)原理、增刪改查四種操作，以及哈希沖突、hashCode()/equals()?等問題都在 HashMap 那篇文章里講過了，這里就不贅述了，沒有看過的小伙伴可以在公眾號后臺回復「Java」獲取文章哦～
總結
再回到開篇的這張圖，有沒有清楚了一些呢？
每個數(shù)據(jù)結構下面其實都有很多內(nèi)容，比如 PriorityQueue 本文沒有細說，因為這家伙一說又要半天。。
如果你覺得文章不錯，文末的贊 👍 又回來啦，記得給我「點贊」和「在看」哦～
最后呢，很多讀者一直有問我交流群的問題，因為考慮到我有時差不方便管理，所以一直沒做。
但現(xiàn)在我找了一個專業(yè)的管理員和我一起管理，所以「秘密基地」正在籌備中，并且我會邀請國內(nèi)外的一些大佬入場，給大家?guī)聿灰粯拥囊暯恰?/p>
那么第一期交流群計劃于 7 月中上旬開放，到時候我會在朋友圈發(fā)邀請，大家敬請期待！
參考資料
[1] Queue:?https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html
[2] ArrayDeque vs LinkedList:?https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
總結
以上是生活随笔為你收集整理的Java 集合框架，看这篇真的够了！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 一篇来自前端同学对后端接口的吐槽：痛！
- 下一篇： 原创 | OpenAPI 标准规范