話不多說弟头，直接上圖：
?
Java 集合易桃，也稱作容器亥鸠，主要是由兩大接口 (Interface) 派生出來的：
Collection 和 Map
顧名思義捆姜，容器就是用來存放數(shù)據(jù)的传趾。
那么這兩大接口的不同之處在于：
Collection 存放單一元素；
Map 存放 key-value 鍵值對娇未。
就是單身狗放 Collection 里面墨缘，couple 就放 Map 里。（所以你屬于哪里零抬？
學(xué)習(xí)這些集合框架，我認(rèn)為有 4 個(gè)目標(biāo)：
明確每個(gè)接口和類的對應(yīng)關(guān)系宽涌；
對每個(gè)接口和類平夜，熟悉常用的 API；
對不同的場景卸亮，能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)并分析優(yōu)缺點(diǎn)忽妒；
學(xué)習(xí)源碼的設(shè)計(jì)，面試要會(huì)答啊兼贸。
福利 福利 福利 免費(fèi)領(lǐng)取Java架構(gòu)技能地圖 注意了是免費(fèi)送
?
Collection
先來看最上層的 Collection.
?
Collection 里還定義了很多方法段直，這些方法也都會(huì)繼承到各個(gè)子接口和實(shí)現(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，所以當(dāng)寫入基本數(shù)據(jù)類型的時(shí)候枉圃，會(huì)做自動(dòng)裝箱 auto-boxing 和自動(dòng)拆箱 unboxing功茴。
還有另外一個(gè)方法 addAll()，可以把另一個(gè)集合里的元素加到此集合中孽亲。
boolean addAll(Collection<? extends E> c);
復(fù)制代碼
刪：
boolean remove(Object o);
復(fù)制代碼
remove()是刪除的指定元素坎穿。
那和 addAll() 對應(yīng)的，
自然就有removeAll()，就是把集合 B 中的所有元素都刪掉玲昧。
boolean removeAll(Collection<?> c);
復(fù)制代碼
改：
Collection Interface 里并沒有直接改元素的操作栖茉，反正刪和增就可以完成改了嘛！
查：
查下集合中有沒有某個(gè)特定的元素：
boolean contains(Object o);
復(fù)制代碼
查集合 A 是否包含了集合 B：
boolean containsAll(Collection<?> c);
復(fù)制代碼
還有一些對集合整體的操作：
判斷集合是否為空：
boolean isEmpty();
復(fù)制代碼
集合的大凶么簟：
int size();
復(fù)制代碼
把集合轉(zhuǎn)成數(shù)組：
Object[] toArray();
復(fù)制代碼
以上就是 Collection 中常用的 API 了衡载。
在接口里都定義好了，子類不要也得要隙袁。
當(dāng)然子類也會(huì)做一些自己的實(shí)現(xiàn)痰娱，這樣就有了不同的數(shù)據(jù)結(jié)構(gòu)。
那我們一個(gè)個(gè)來看菩收。
List
?
List 最大的特點(diǎn)就是：有序梨睁，可重復(fù)。
看官網(wǎng)說的：
An ordered collection (also known as a sequence).
Unlike sets, lists typically allow duplicate elements.
這一下把 Set 的特點(diǎn)也說出來了娜饵，和 List 完全相反坡贺，Set 是 無序，不重復(fù)的箱舞。
List 的實(shí)現(xiàn)方式有 LinkedList 和 ArrayList 兩種遍坟，那面試時(shí)最常問的就是這兩個(gè)數(shù)據(jù)結(jié)構(gòu)如何選擇。
對于這類選擇問題：
一是考慮數(shù)據(jù)結(jié)構(gòu)是否能完成需要的功能晴股；
如果都能完成愿伴，二是考慮哪種更高效。
（萬事都是如此啊电湘。
那具體來看這兩個(gè) classes 的 API 和它們的時(shí)間復(fù)雜度：
功能方法ArrayListLinkedList增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)
稍微解釋幾個(gè)：
add(E e) 是在尾巴上加元素隔节，雖然 ArrayList 可能會(huì)有擴(kuò)容的情況出現(xiàn)，但是均攤復(fù)雜度（amortized time complexity）還是 O(1) 的寂呛。
add(int index, E e)是在特定的位置上加元素怎诫，LinkedList 需要先找到這個(gè)位置，再加上這個(gè)元素贷痪，雖然單純的「加」這個(gè)動(dòng)作是 O(1) 的幻妓，但是要找到這個(gè)位置還是 O(n) 的。（這個(gè)有的人就認(rèn)為是 O(1)呢诬，和面試官解釋清楚就行了涌哲，拒絕扛精。
remove(int index)是 remove 這個(gè) index 上的元素尚镰，所以
ArrayList 找到這個(gè)元素的過程是 O(1)阀圾，但是 remove 之后，后續(xù)元素都要往前移動(dòng)一位狗唉，所以均攤復(fù)雜度是 O(n)初烘；
LinkedList 也是要先找到這個(gè) index，這個(gè)過程是 O(n) 的，所以整體也是 O(n)肾筐。
remove(E e)是 remove 見到的第一個(gè)這個(gè)元素哆料，那么
ArrayList 要先找到這個(gè)元素，這個(gè)過程是 O(n)吗铐，然后移除后還要往前移一位东亦，這個(gè)更是 O(n)，總的還是 O(n)唬渗；
LinkedList 也是要先找典阵，這個(gè)過程是 O(n)，然后移走镊逝，這個(gè)過程是 O(1)壮啊，總的是 O(n).
那造成時(shí)間復(fù)雜度的區(qū)別的原因是什么呢？
答：
因?yàn)?ArrayList 是用數(shù)組來實(shí)現(xiàn)的撑蒜。
而數(shù)組和鏈表的最大區(qū)別就是數(shù)組是可以隨機(jī)訪問的（random access）歹啼。
這個(gè)特點(diǎn)造成了在數(shù)組里可以通過下標(biāo)用 O(1) 的時(shí)間拿到任何位置的數(shù)，而鏈表則做不到座菠，只能從頭開始逐個(gè)遍歷狸眼。
也就是說在「改查」這兩個(gè)功能上，因?yàn)閿?shù)組能夠隨機(jī)訪問浴滴，所以 ArrayList 的效率高份企。
那「增刪」呢？
如果不考慮找到這個(gè)元素的時(shí)間，
數(shù)組因?yàn)槲锢砩系倪B續(xù)性成畦，當(dāng)要增刪元素時(shí)钝鸽，在尾部還好，但是其他地方就會(huì)導(dǎo)致后續(xù)元素都要移動(dòng)驹尼，所以效率較低；而鏈表則可以輕松的斷開和下一個(gè)元素的連接，直接插入新元素或者移除舊元素腰根。
但是呢，實(shí)際上你不能不考慮找到元素的時(shí)間啊拓型。额嘿。。而且如果是在尾部操作劣挫，數(shù)據(jù)量大時(shí) ArrayList 會(huì)更快的册养。
所以說：
改查選擇 ArrayList；
增刪在尾部的選擇 ArrayList压固；
其他情況下球拦，如果時(shí)間復(fù)雜度一樣，推薦選擇 ArrayList，因?yàn)?overhead 更小坎炼，或者說內(nèi)存使用更有效率愧膀。
Vector
那作為 List 的最后一個(gè)知識點(diǎn)，我們來聊一下 Vector谣光。這也是一個(gè)年齡暴露帖檩淋，用過的都是大佬。
那 Vector 和 ArrayList 一樣萄金，也是繼承自 java.util.AbstractList蟀悦，底層也是用數(shù)組來實(shí)現(xiàn)的。
但是現(xiàn)在已經(jīng)被棄用了捡絮，因?yàn)?..它加了太多的 synchronized熬芜！
任何好處都是有代價(jià)的，線程安全的成本就是效率低福稳，在某些系統(tǒng)里很容易成為瓶頸涎拉，所以現(xiàn)在大家不再在數(shù)據(jù)結(jié)構(gòu)的層面加 synchronized，而是把這個(gè)任務(wù)轉(zhuǎn)移給我們程序員==
那么面試常問題：Vector 和 ArrayList 的區(qū)別是什么的圆，只答出來這個(gè)還還不太全面鼓拧。
來看 stack overflow 上的高票回答：
?
一是剛才已經(jīng)說過的線程安全問題；
二是擴(kuò)容時(shí)擴(kuò)多少的區(qū)別越妈。
這個(gè)得看看源碼：
?
這是 ArrayList 的擴(kuò)容實(shí)現(xiàn)季俩，這個(gè)算術(shù)右移操作是把這個(gè)數(shù)的二進(jìn)制往右移動(dòng)一位，最左邊補(bǔ)符號位梅掠，但是因?yàn)槿萘繘]有負(fù)數(shù)酌住，所以還是補(bǔ) 0.
那右移一位的效果就是除以 2，那么定義的新容量就是原容量的1.5 倍阎抒。
不了解這個(gè)右移操作符的小伙伴酪我，公眾號內(nèi)回復(fù)「二進(jìn)制」快復(fù)習(xí)一下吧～
再來看 Vector 的：
?
因?yàn)橥ǔ?capacityIncrement 我們并不定義，所以默認(rèn)情況下它是擴(kuò)容兩倍且叁。
答出來這兩點(diǎn)都哭，就肯定沒問題了。
Queue & Deque
Queue 是一端進(jìn)另一端出的線性數(shù)據(jù)結(jié)構(gòu)逞带；而 Deque 是兩端都可以進(jìn)出的欺矫。
?
Queue
Java 中的 這個(gè) Queue 接口稍微有點(diǎn)坑，一般來說隊(duì)列的語義都是先進(jìn)先出（FIFO）的展氓。
但是這里有個(gè)例外穆趴，就是 PriorityQueue，也叫 heap带饱，并不按照進(jìn)去的時(shí)間順序出來毡代，而是按照規(guī)定的優(yōu)先級出去阅羹，并且它的操作并不是 O(1) 的，時(shí)間復(fù)雜度的計(jì)算稍微有點(diǎn)復(fù)雜教寂，我們之后單獨(dú)開一篇來講捏鱼。
那 Queue 的方法官網(wǎng)都總結(jié)好了，它有兩組 API酪耕，基本功能是一樣的导梆，但是呢：
一組是會(huì)拋異常的；
另一組會(huì)返回一個(gè)特殊值迂烁。
功能拋異常返回值增add(e)offer(e)刪remove()poll()瞧element()peek()
為什么會(huì)拋異常呢看尼？
比如隊(duì)列空了，那 remove() 就會(huì)拋異常盟步，但是 poll() 就返回 null藏斩；element() 就會(huì)拋異常，而 peek() 就返回 null 就好了却盘。
那 add(e) 怎么會(huì)拋異常呢狰域？
有些 Queue 它會(huì)有容量的限制，比如BlockingQueue黄橘，那如果已經(jīng)達(dá)到了它最大的容量且不會(huì)擴(kuò)容的兆览，就會(huì)拋異常；但如果 offer(e)塞关，就會(huì) return false.
那怎么選擇呢抬探？：
首先，要用就用同一組 API帆赢，前后要統(tǒng)一小压；
其次，根據(jù)需求椰于。如果你需要它拋異常场航，那就是用拋異常的；不過做算法題時(shí)基本不用廉羔，所以選那組返回特殊值的就好了。
Deque
Deque 是兩端都可以進(jìn)出的僻造，那自然是有針對 First 端的操作和對 Last 端的操作憋他，那每端都有兩組，一組拋異常髓削，一組返回特殊值：
功能拋異常返回值增addFirst(e)/ addLast(e)offerFirst(e)/ offerLast(e)刪removeFirst()/ removeLast()pollFirst()/ pollLast()瞧getFirst()/ getLast()peekFirst()/ peekLast()
使用時(shí)同理竹挡，要用就用同一組。
Queue 和 Deque 的這些 API 都是 O(1) 的時(shí)間復(fù)雜度立膛，準(zhǔn)確來說是均攤時(shí)間復(fù)雜度揪罕。
實(shí)現(xiàn)類
它們的實(shí)現(xiàn)類有這三個(gè)：
?
所以說梯码，
如果想實(shí)現(xiàn)「普通隊(duì)列 - 先進(jìn)先出」的語義，就使用 LinkedList 或者 ArrayDeque 來實(shí)現(xiàn)好啰；
如果想實(shí)現(xiàn)「優(yōu)先隊(duì)列」的語義轩娶，就使用 PriorityQueue；
如果想實(shí)現(xiàn)「椏蛲」的語義鳄抒，就使用 ArrayDeque。
我們一個(gè)個(gè)來看椰弊。
在實(shí)現(xiàn)普通隊(duì)列時(shí)许溅，如何選擇用 LinkedList 還是 ArrayDeque 呢？
來看一下 StackOverflow 上的高票回答：
?
總結(jié)來說就是推薦使用 ArrayDeque秉版，因?yàn)樾矢呦椭兀?LinkedList 還會(huì)有其他的額外開銷（overhead）。
那 ArrayDeque 和 LinkedList 的區(qū)別有哪些呢清焕？
?
還是在剛才的同一個(gè)問題下并蝗，這是我認(rèn)為總結(jié)的最好的：
ArrayDeque 是一個(gè)可擴(kuò)容的數(shù)組，LinkedList 是鏈表結(jié)構(gòu)耐朴；
ArrayDeque 里不可以存 null 值借卧，但是 LinkedList 可以；
ArrayDeque 在操作頭尾端的增刪操作時(shí)更高效筛峭，但是 LinkedList 只有在當(dāng)要移除中間某個(gè)元素且已經(jīng)找到了這個(gè)元素后的移除才是 O(1) 的铐刘；
ArrayDeque 在內(nèi)存使用方面更高效。
所以影晓，只要不是必須要存 null 值镰吵，就選擇 ArrayDeque 吧！
那如果是一個(gè)很資深的面試官問你挂签，什么情況下你要選擇用 LinkedList 呢疤祭？
答：Java 6 以前。饵婆。勺馆。因?yàn)?ArrayDeque 在 Java 6 之后才有的。侨核。
為了版本兼容的問題草穆，實(shí)際工作中我們不得不做一些妥協(xié)。搓译。
那最后一個(gè)問題悲柱，就是關(guān)于 Stack 了。
Stack
Stack 在語義上是先進(jìn)先出（LIFO）的線性數(shù)據(jù)結(jié)構(gòu)些己。
有很多高頻面試題都是要用到棧的豌鸡，比如接水問題嘿般，雖然最優(yōu)解是用雙指針，但是用棧是最直觀的解法也是需要了解的涯冠，之后有機(jī)會(huì)再專門寫吧炉奴。
那在 Java 中是怎么實(shí)現(xiàn)棧的呢？
雖然 Java 中有 Stack 這個(gè)類功偿，但是呢盆佣，官方文檔都說不讓用了！
?
原因也很簡單械荷，因?yàn)?Vector 已經(jīng)過被棄用了共耍，而 Stack 是繼承 Vector 的。
那么想實(shí)現(xiàn) Stack 的語義吨瞎，就用 ArrayDeque 吧：
Deque<Integer> stack = new ArrayDeque<>();
復(fù)制代碼
Set
最后一個(gè) Set痹兜，剛才已經(jīng)說過了 Set 的特定是無序，不重復(fù)的颤诀。
就和數(shù)學(xué)里學(xué)的「集合」的概念一致字旭。
?
Set 的常用實(shí)現(xiàn)類有三個(gè)：
HashSet: 采用 Hashmap 的 key 來儲存元素，主要特點(diǎn)是無序的崖叫，基本操作都是 O(1) 的時(shí)間復(fù)雜度遗淳，很快。
LinkedHashSet: 這個(gè)是一個(gè) HashSet + LinkedList 的結(jié)構(gòu)心傀，特點(diǎn)就是既擁有了 O(1) 的時(shí)間復(fù)雜度屈暗，又能夠保留插入的順序。
TreeSet: 采用紅黑樹結(jié)構(gòu)脂男，特點(diǎn)是可以有序养叛，可以用自然排序或者自定義比較器來排序；缺點(diǎn)就是查詢速度沒有 HashSet 快宰翅。
那每個(gè) Set 的底層實(shí)現(xiàn)其實(shí)就是對應(yīng)的 Map：
數(shù)值放在 map 中的 key 上弃甥，value 上放了個(gè) PRESENT，是一個(gè)靜態(tài)的 Object汁讼，相當(dāng)于 place holder淆攻，每個(gè) key 都指向這個(gè) object。
那么具體的實(shí)現(xiàn)原理嘿架、增刪改查四種操作卜录，以及哈希沖突、hashCode()/equals()等問題都在 HashMap 那篇文章里講過了
總結(jié)
再回到開篇的這張圖眶明，有沒有清楚了一些呢？
?
每個(gè)數(shù)據(jù)結(jié)構(gòu)下面其實(shí)都有很多內(nèi)容筐高，比如 PriorityQueue也就是堆搜囱，齊姐之前也專門寫過文章講解它的相關(guān)操作丑瞧，比如很有名的 heapify() 的過程為什么是 O(n) 的等面試常問題
