有哪些Java集合框架

這篇文章主要介紹“有哪些Java集合框架”，在日常操作中，相信很多人在有哪些Java集合框架問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”有哪些Java集合框架”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

話不多說(shuō)，直接上圖：

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

Collection 和 Map

顧名思義，容器就是用來(lái)存放數(shù)據(jù)的。

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

• Collection 存放單一元素;

• Map 存放 key-value 鍵值對(duì)。

就是單身狗放 Collection 里面，couple 就放 Map 里。(所以你屬于哪里?

學(xué)習(xí)這些集合框架，我認(rèn)為有 4 個(gè)目標(biāo)：

1. 明確每個(gè)接口和類(lèi)的對(duì)應(yīng)關(guān)系;

2. 對(duì)每個(gè)接口和類(lèi)，熟悉常用的 API;

3. 對(duì)不同的場(chǎng)景，能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)并分析優(yōu)缺點(diǎn);

4. 學(xué)習(xí)源碼的設(shè)計(jì)，面試要會(huì)答啊。

關(guān)于 Map，之前那篇 HashMap  的文章已經(jīng)講的非常透徹詳盡了，所以本文不再贅述。如果還沒(méi)看過(guò)那篇文章的小伙伴，快去公眾號(hào)內(nèi)回復(fù)「HashMap」看文章吧～

Collection

先來(lái)看最上層的 Collection.

Collection 里還定義了很多方法，這些方法也都會(huì)繼承到各個(gè)子接口和實(shí)現(xiàn)類(lèi)里，而這些 API  的使用也是日常工作和面試常見(jiàn)?？嫉?，所以我們先來(lái)看下這些方法。

操作集合，無(wú)非就是「增刪改查」四大類(lèi)，也叫 CRUD:

• Create, Read, Update, and Delete.

那我也把這些 API 分為這四大類(lèi)：

下面具體來(lái)看：

增：

boolean add(E e);

add() 方法傳入的數(shù)據(jù)類(lèi)型必須是 Object，所以當(dāng)寫(xiě)入基本數(shù)據(jù)類(lèi)型的時(shí)候，會(huì)做自動(dòng)裝箱 auto-boxing 和自動(dòng)拆箱  unboxing。

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

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

刪：

boolean remove(Object o);

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

那和 addAll() 對(duì)應(yīng)的，

自然就有removeAll()，就是把集合 B 中的所有元素都刪掉。

boolean removeAll(Collection<?> c);

改：

Collection Interface 里并沒(méi)有直接改元素的操作，反正刪和增就可以完成改了嘛!

查：

查下集合中有沒(méi)有某個(gè)特定的元素：

boolean contains(Object o);

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

boolean containsAll(Collection<?> c);

還有一些對(duì)集合整體的操作：

• 判斷集合是否為空：

boolean isEmpty();

• 集合的大?。?/p>

int size();

• 把集合轉(zhuǎn)成數(shù)組：

Object[] toArray();

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

在接口里都定義好了，子類(lèi)不要也得要。

當(dāng)然子類(lèi)也會(huì)做一些自己的實(shí)現(xiàn)，這樣就有了不同的數(shù)據(jù)結(jié)構(gòu)。

那我們一個(gè)個(gè)來(lái)看。

List

List 最大的特點(diǎn)就是：有序，可重復(fù)。

看官網(wǎng)說(shuō)的：

• An ordered collection (also known as a sequence).

• Unlike sets, lists typically allow duplicate elements.

這一下把 Set 的特點(diǎn)也說(shuō)出來(lái)了，和 List 完全相反，Set 是 無(wú)序，不重復(fù)的。

List 的實(shí)現(xiàn)方式有 LinkedList 和 ArrayList 兩種，那面試時(shí)最常問(wèn)的就是這兩個(gè)數(shù)據(jù)結(jié)構(gòu)如何選擇。

對(duì)于這類(lèi)選擇問(wèn)題：

一是考慮數(shù)據(jù)結(jié)構(gòu)是否能完成需要的功能;

如果都能完成，二是考慮哪種更高效。

(萬(wàn)事都是如此啊。

那具體來(lái)看這兩個(gè) classes 的 API 和它們的時(shí)間復(fù)雜度：

稍微解釋幾個(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è)元素的過(guò)程是 O(1)，但是 remove 之后，后續(xù)元素都要往前移動(dòng)一位，所以均攤復(fù)雜度是 O(n);

• LinkedList 也是要先找到這個(gè) index，這個(gè)過(guò)程是 O(n) 的，所以整體也是 O(n)。

remove(E e)是 remove 見(jiàn)到的第一個(gè)這個(gè)元素，那么

• ArrayList 要先找到這個(gè)元素，這個(gè)過(guò)程是 O(n)，然后移除后還要往前移一位，這個(gè)更是 O(n)，總的還是 O(n);

• LinkedList 也是要先找，這個(gè)過(guò)程是 O(n)，然后移走，這個(gè)過(guò)程是 O(1)，總的是 O(n).

那造成時(shí)間復(fù)雜度的區(qū)別的原因是什么呢?

答：

• 因?yàn)?ArrayList 是用數(shù)組來(lái)實(shí)現(xiàn)的。

• 而數(shù)組和鏈表的最大區(qū)別就是數(shù)組是可以隨機(jī)訪問(wèn)的(random access)。

這個(gè)特點(diǎn)造成了在數(shù)組里可以通過(guò)下標(biāo)用 O(1) 的時(shí)間拿到任何位置的數(shù)，而鏈表則做不到，只能從頭開(kāi)始逐個(gè)遍歷。

也就是說(shuō)在「改查」這兩個(gè)功能上，因?yàn)閿?shù)組能夠隨機(jī)訪問(wèn)，所以 ArrayList 的效率高。

那「增刪」呢?

如果不考慮找到這個(gè)元素的時(shí)間，

數(shù)組因?yàn)槲锢砩系倪B續(xù)性，當(dāng)要增刪元素時(shí)，在尾部還好，但是其他地方就會(huì)導(dǎo)致后續(xù)元素都要移動(dòng)，所以效率較低;而鏈表則可以輕松的斷開(kāi)和下一個(gè)元素的連接，直接插入新元素或者移除舊元素。

但是呢，實(shí)際上你不能不考慮找到元素的時(shí)間啊。。。而且如果是在尾部操作，數(shù)據(jù)量大時(shí) ArrayList 會(huì)更快的。

所以說(shuō)：

• 改查選擇 ArrayList;

• 增刪在尾部的選擇 ArrayList;

• 其他情況下，如果時(shí)間復(fù)雜度一樣，推薦選擇 ArrayList，因?yàn)?overhead 更小，或者說(shuō)內(nèi)存使用更有效率。

Vector

那作為 List 的最后一個(gè)知識(shí)點(diǎn)，我們來(lái)聊一下 Vector。這也是一個(gè)年齡暴露帖，用過(guò)的都是大佬。

那 Vector 和 ArrayList 一樣，也是繼承自 java.util.AbstractList，底層也是用數(shù)組來(lái)實(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)移給我們程序員==

那么面試常問(wèn)題：Vector 和 ArrayList 的區(qū)別是什么，只答出來(lái)這個(gè)還還不太全面。

來(lái)看 stack overflow 上的高票回答：

一是剛才已經(jīng)說(shuō)過(guò)的線程安全問(wèn)題;

二是擴(kuò)容時(shí)擴(kuò)多少的區(qū)別。

這個(gè)得看看源碼：

這是 ArrayList 的擴(kuò)容實(shí)現(xiàn)，這個(gè)算術(shù)右移操作是把這個(gè)數(shù)的二進(jìn)制往右移動(dòng)一位，最左邊補(bǔ)符號(hào)位，但是因?yàn)槿萘繘](méi)有負(fù)數(shù)，所以還是補(bǔ) 0.

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

再來(lái)看 Vector 的：

因?yàn)橥ǔ?capacityIncrement 我們并不定義，所以默認(rèn)情況下它是擴(kuò)容兩倍。

答出來(lái)這兩點(diǎn)，就肯定沒(méi)問(wèn)題了。

Queue & Deque

Queue 是一端進(jìn)另一端出的線性數(shù)據(jù)結(jié)構(gòu);而 Deque 是兩端都可以進(jìn)出的。

Queue

Java 中的 這個(gè) Queue 接口稍微有點(diǎn)坑，一般來(lái)說(shuō)隊(duì)列的語(yǔ)義都是先進(jìn)先出(FIFO)的。

但是這里有個(gè)例外，就是 PriorityQueue，也叫 heap，并不按照進(jìn)去的時(shí)間順序出來(lái)，而是按照規(guī)定的優(yōu)先級(jí)出去，并且它的操作并不是 O(1)  的，時(shí)間復(fù)雜度的計(jì)算稍微有點(diǎn)復(fù)雜，我們之后單獨(dú)開(kāi)一篇來(lái)講。

那 Queue 的方法官網(wǎng)[1]都總結(jié)好了，它有兩組 API，基本功能是一樣的，但是呢：

• 一組是會(huì)拋異常的;

• 另一組會(huì)返回一個(gè)特殊值。

為什么會(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ù)需求。如果你需要它拋異常，那就是用拋異常的;不過(guò)做算法題時(shí)基本不用，所以選那組返回特殊值的就好了。

Deque

Deque 是兩端都可以進(jìn)出的，那自然是有針對(duì) First 端的操作和對(duì) Last 端的操作，那每端都有兩組，一組拋異常，一組返回特殊值：

使用時(shí)同理，要用就用同一組。

Queue 和 Deque 的這些 API 都是 O(1) 的時(shí)間復(fù)雜度，準(zhǔn)確來(lái)說(shuō)是均攤時(shí)間復(fù)雜度。

實(shí)現(xiàn)類(lèi)

它們的實(shí)現(xiàn)類(lèi)有這三個(gè)：

所以說(shuō)，

• 如果想實(shí)現(xiàn)「普通隊(duì)列 - 先進(jìn)先出」的語(yǔ)義，就使用 LinkedList 或者 ArrayDeque 來(lái)實(shí)現(xiàn);

• 如果想實(shí)現(xiàn)「優(yōu)先隊(duì)列」的語(yǔ)義，就使用 PriorityQueue;

• 如果想實(shí)現(xiàn)「?！沟恼Z(yǔ)義，就使用 ArrayDeque。

我們一個(gè)個(gè)來(lái)看。

在實(shí)現(xiàn)普通隊(duì)列時(shí)，如何選擇用 LinkedList 還是 ArrayDeque 呢?

來(lái)看一下 StackOverflow[2] 上的高票回答：

總結(jié)來(lái)說(shuō)就是推薦使用 ArrayDeque，因?yàn)樾矢?，?LinkedList 還會(huì)有其他的額外開(kāi)銷(xiāo)(overhead)。

那 ArrayDeque 和 LinkedList 的區(qū)別有哪些呢?

還是在剛才的同一個(gè)問(wèn)題下，這是我認(rèn)為總結(jié)的最好的：

1. ArrayDeque 是一個(gè)可擴(kuò)容的數(shù)組，LinkedList 是鏈表結(jié)構(gòu);

2. ArrayDeque 里不可以存 null 值，但是 LinkedList 可以;

3. ArrayDeque 在操作頭尾端的增刪操作時(shí)更高效，但是 LinkedList 只有在當(dāng)要移除中間某個(gè)元素且已經(jīng)找到了這個(gè)元素后的移除才是 O(1)  的;

4. ArrayDeque 在內(nèi)存使用方面更高效。

所以，只要不是必須要存 null 值，就選擇 ArrayDeque 吧!

那如果是一個(gè)很資深的面試官問(wèn)你，什么情況下你要選擇用 LinkedList 呢?

答：Java 6 以前。。。因?yàn)?ArrayDeque 在 Java 6 之后才有的。。

為了版本兼容的問(wèn)題，實(shí)際工作中我們不得不做一些妥協(xié)。。

那最后一個(gè)問(wèn)題，就是關(guān)于 Stack 了。

Stack

Stack 在語(yǔ)義上是 后進(jìn)先出(LIFO) 的線性數(shù)據(jù)結(jié)構(gòu)。

有很多高頻面試題都是要用到棧的，比如接水問(wèn)題，雖然最優(yōu)解是用雙指針，但是用棧是最直觀的解法也是需要了解的，之后有機(jī)會(huì)再專(zhuān)門(mén)寫(xiě)吧。

那在 Java 中是怎么實(shí)現(xiàn)棧的呢?

雖然 Java 中有 Stack 這個(gè)類(lèi)，但是呢，官方文檔都說(shuō)不讓用了!

原因也很簡(jiǎn)單，因?yàn)?Vector 已經(jīng)過(guò)被棄用了，而 Stack 是繼承 Vector 的。

那么想實(shí)現(xiàn) Stack 的語(yǔ)義，就用 ArrayDeque 吧：

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

Set

最后一個(gè) Set，剛才已經(jīng)說(shuō)過(guò)了 Set 的特定是無(wú)序，不重復(fù)的。

就和數(shù)學(xué)里學(xué)的「集合」的概念一致。

Set 的常用實(shí)現(xiàn)類(lèi)有三個(gè)：

HashSet: 采用 Hashmap 的 key 來(lái)儲(chǔ)存元素，主要特點(diǎn)是無(wú)序的，基本操作都是 O(1) 的時(shí)間復(fù)雜度，很快。

LinkedHashSet: 這個(gè)是一個(gè) HashSet + LinkedList 的結(jié)構(gòu)，特點(diǎn)就是既擁有了 O(1)  的時(shí)間復(fù)雜度，又能夠保留插入的順序。

TreeSet: 采用紅黑樹(shù)結(jié)構(gòu)，特點(diǎn)是可以有序，可以用自然排序或者自定義比較器來(lái)排序;缺點(diǎn)就是查詢(xún)速度沒(méi)有 HashSet 快。

那每個(gè) Set 的底層實(shí)現(xiàn)其實(shí)就是對(duì)應(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() 等問(wèn)題都在 HashMap  那篇文章里講過(guò)了，這里就不贅述了，沒(méi)有看過(guò)的小伙伴可以在公眾號(hào)后臺(tái)回復(fù)「HashMap」獲取文章哦～

總結(jié)

到此，關(guān)于“有哪些Java集合框架”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！