Java 集合，也稱作容器，主要是由兩大接口 (Interface) 派生出來的：

　　Collection 和 Map

　　顧名思義，容器就是用來存放數據的。

　　那么這兩大接口的不同之處在于：

　　Collection 存放單一元素;

　　Map 存放 key-value 鍵值對。

　　就是單身狗放 Collection 里面，couple 就放 Map 里。

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

　　1. 明確每個接口和類的對應關系;

　　2. 對每個接口和類，熟悉常用的 API;

　　3. 對不同的場景，能夠選擇合適的數據結構并分析優缺點;

　　4. 學習源碼的設計，面試要會答啊。

　　Collection

　　先來看最上層的 Collection.

　　Collection 里還定義了很多方法，這些方法也都會繼承到各個子接口和實現類里，而這些 API 的使用也是日常工作和面試常見常考的，所以我們先來看下這些方法。

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

　　Create, Read, Update, and Delete.

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

　　下面具體來看：

　　增：

　　boolean add(E e);復制代碼

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

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

　　boolean addAll(Collection 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 會更快的。

　　所以說：

　　改查選擇 ArrayList;

　　增刪在尾部的選擇 ArrayList;

　　其他情況下，如果時間復雜度一樣，推薦選擇 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 是兩端都可以進出的，那自然是有針對 First 端的操作和對 Last 端的操作，那每端都有兩組，一組拋異常，一組返回特殊值：

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

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

　　實現類

　　它們的實現類有這三個：

　　所以說，如果想實現「普通隊列 - 先進先出」的語義，就使用 LinkedList 或者 ArrayDeque 來實現;

　　· 如果想實現「優先隊列」的語義，就使用 PriorityQueue;

　　· 如果想實現「棧」的語義，就使用 ArrayDeque。

　　我們一個個來看。

　　在實現普通隊列時，如何選擇用 LinkedList 還是 ArrayDeque 呢?

　　來看一下 StackOverflow[2] 上的高票回答：

　　總結來說就是推薦使用 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 吧：

　　Dequestack = 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。

　　.Map接口存取元素：

　　Map存放鍵值對，鍵不能重復。

　　存元素：用put方法，put(obj key,obj value)。每次存儲，要存儲一對key,value，不能存放重復的key，判斷是否重復，按equals來比較。

　　取元素：可以用get(Object key)根據key獲得相應的value;也可以獲得所有的key的集合;也可以獲得所有的value的集合;也可以獲得key和value組合成的Map.Entry對象的集合。

　　那么具體的實現原理、增刪改查四種操作，以及哈希沖突、hashCode()/equals() 等問題我們在這里不具體說了。

　　更多關于“Java培訓”的問題，歡迎咨詢千鋒教育在線名師。千鋒已有十余年的培訓經驗，課程大綱更科學更專業，有針對零基礎的就業班，有針對想提升技術的好程序員班，高品質課程助理你實現java程序員夢想。