Java 容器的繼承關(guān)系圖

集合表示一組對(duì)象，稱為其元素。有些集合允許重復(fù)元素，而另一些則不允許。有些是有序的，有些是無(wú)序的。

JDK 沒有提供這個(gè)接口的任何直接實(shí)現(xiàn)：它提供了更具體的子接口（如 Set、List 和 Queue）的實(shí)現(xiàn)。

一、List

有序的元素序列,可以通過(guò)索引（即下標(biāo)）訪問元素。

1、ArrayList

基于索引的動(dòng)態(tài)數(shù)組

（1）實(shí)現(xiàn)了可變大小的數(shù)組，允許所有元素，包括 null 值，底層使用數(shù)組（array）保存所有元素，所以隨機(jī)訪問很快，可以直接通過(guò)元素的下標(biāo)值獲取元素的值（size、isEmpty、get、set、iterator、listIterator 這些方法的時(shí)間復(fù)雜度均為 O(1)），但插入和刪除較慢，因?yàn)樾枰苿?dòng) array 里的元素（即 add、remove 的時(shí)間復(fù)雜度為 O(n)），未實(shí)現(xiàn)同步。

（2）每一個(gè) ArrayList 實(shí)例都有一個(gè)容量（capacity），使用 Lists.newArrayList() 創(chuàng)建的是一個(gè) capacity = 0 的 List，當(dāng)在添加第一個(gè)元素的時(shí)候會(huì)擴(kuò)展到默認(rèn)的初始化容量（10），當(dāng)對(duì)其添加的數(shù)據(jù)大于它的 capacity 就必須改變 ArrayList 的 capacity（一般是原來(lái)大小的 1.5 倍），而這種 resize 操作是有開銷的，所以如果事先知道數(shù)組的大小為 actualSize，可以按照下面的方式初始化一個(gè)大小固定的 ArrayList，以減去 resize 的開銷：

int actualSize = 100;
List<Object> objectArrayList = Lists.newArrayListWithCapacity(actualSize);

（3）iterator() 和 listIterator(int) 返回的迭代器是快速失?。╢ail-fast）的：

如果在迭代器創(chuàng)建之后，原始的 List 被修改了，迭代器會(huì)拋一個(gè) ConcurrentModificationException，原因是 Iterator 里的 expectedModCount 和 List 的 modCount 不一致。在迭代的時(shí)候如果需要修改 List，只能通過(guò) Iterator 的 remove 方法修改。

（4）從 Array 創(chuàng)建 ArrayList 的坑：

Object[] array = new Object[10];
List<Object> arrayList1 = Lists.newArrayList(Arrays.asList(array));
List<Object> arrayList2 = Arrays.asList(array);
// 需要注意的是：Arrays.asList(array) 返回的是一個(gè) fixed size array（上面的arrayList2），如果不用 Lists.newArrayList(Arrays.asList(array))（上面的arrayList2）包裝起來(lái)的話，對(duì)它進(jìn)行 add 或 remove 操作就會(huì)報(bào) java.lang.UnsupportedOperationException

2、LinkedList

雙鏈表數(shù)據(jù)結(jié)構(gòu)

（1）實(shí)現(xiàn)了 List 接口，允許 null 值，底層使用鏈表保存所有元素（除了要存數(shù)據(jù)外，還需存 next 和 pre 兩個(gè)指針，因此占用的內(nèi)存比 ArrayList 多），因此，向 LinkedList 里面插入或移除元素時(shí)會(huì)特別快，但是對(duì)于隨機(jī)訪問方面相對(duì)較慢（需要遍歷鏈表，遍歷的時(shí)候會(huì)根據(jù) index 選擇從前往后或從后往前遍歷，如果 index < (size >> 1) 則從前往后），無(wú)同步，想要實(shí)現(xiàn)同步可以這樣：

List list = Collections.synchronizedList(new LinkedList(...)); 

（2）LinkedList 還擁有了可以使其用作堆棧（stack），隊(duì)列（queue）或者雙向隊(duì)列（deque）的方法（擁有 pop、push，從 LinkedList 的首部或尾部添加或刪除元素等方法）。

3、Vector

實(shí)現(xiàn)了同步的 ArrayList

和 ArrayList 幾乎一模一樣，除開以下兩點(diǎn)：

• 實(shí)現(xiàn)了同步，較 ArrayList 有輕微的性能上的差距（一般不用它，而是使用 ArrayList，在外部實(shí)現(xiàn)同步）；
• 二者的 resize 的大小不一樣：ArrayList 是變?yōu)樵瓉?lái)的 1.5 倍，而 Vector 為原來(lái)的 2 倍。

4、Stack

Java 的堆棧實(shí)現(xiàn)是糟糕的，它繼承了 Vector

Stack 表示后進(jìn)先出（LIFO）堆棧，繼承于 Vector ，新增了五個(gè)方法：

• push(E item) ：將 item 壓入棧；
• pop() ：remove 掉棧頂元素并返回 remove 掉的元素；
• peek() ：返回棧頂（Vector 的最后一個(gè)元素）的第一個(gè)元素（無(wú) remove 操作）；
• empty() ：判斷棧是否為空；
• search() ：返回查找到的離棧頂最近的元素的 position;
• javadoc 中建議：Deque 接口和它的實(shí)現(xiàn)提供了一個(gè)更完整、更一致的 LIFO 棧操作集，應(yīng)該優(yōu)先使用這個(gè)類。例如：

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

5、ArrayList、LinkedList 和 Vector 總結(jié)

（1）當(dāng)集合內(nèi)的元素需要頻繁插入，刪除操作時(shí)應(yīng)使用 LinkedList；當(dāng)需要頻繁查詢時(shí)，使用 ArrayList（大部分情況是使用 ArrayList）；

（2）ArrayList 和 LinkedList 都未實(shí)現(xiàn)同步，Vector 是在 ArrayList 的基礎(chǔ)上實(shí)現(xiàn)了同步，是線程安全的；

（3）相比而言，LinkedList 占的內(nèi)存要比 ArrayList 大（因?yàn)樗仨毦S護(hù)下一個(gè)和前一個(gè)節(jié)點(diǎn)的鏈接）。

二、Set

不包含重復(fù)元素的集合。

1、HashSet

• 由 HashMap 支持實(shí)現(xiàn)，無(wú)序，未實(shí)現(xiàn)同步，允許 null 值；
• add, remove, contains and size ：這些方法的時(shí)間復(fù)雜度為 O(1)，迭代 HashSet 的時(shí)間與實(shí)際 HashSet 的 size 和內(nèi)部支持實(shí)現(xiàn)的 HashMap 的 capacity 之和成線性關(guān)系。所以，如果對(duì)迭代性能敏感，就不要把 HashSet 的初始容量設(shè)置太高（或者負(fù)載因子太低）（實(shí)際上是減小 HashMap 的 capacity 值）。

2、LinkedHashSet

• 由 LinkedHashMap 支持實(shí)現(xiàn)，有序（保證了元素的插入順序），未實(shí)現(xiàn)同步，允許 null 值
• 與 HashSet 相比：需要多維護(hù)一個(gè) linked list ，所以總體上性能上會(huì)比 HashMap 稍微慢一點(diǎn)，但有一點(diǎn)例外：迭代 LinkedHashSet 的開銷比迭代 HashSet 要小，原因是迭代 LinkedHashSet 只與 size 相關(guān)，而迭代 HashSet 還與 capacity 相關(guān)。

3、SortedSet

• 元素有序（按照自然排序或 Comparator 排序）
• 內(nèi)部的元素都必須實(shí)現(xiàn) Comparable 接口，保證集合內(nèi)部任意兩個(gè)元素之間是可比較的
• subSet(E fromElement, E toElement) ：返回該集合部分元素（[from，to)）的視圖（view），操作該視圖會(huì)映射到原集合上，而且該視圖有限制：當(dāng)添加一個(gè)此范圍（[from，to)）之外的值會(huì)拋 IllegalArgumentException。
• headSet(E toElement):( < toElement) ：返回一個(gè)和 subSet 一樣的視圖（[lowestElement, toElement)）
• tailSet(E fromElement):( >= fromElement) ：返回一個(gè)和 subSet 一樣的視圖（[fromElement, highestElement]）

4、TreeSet（SortedSet 的實(shí)現(xiàn)）

• 基于 TreeMap 的 NavigableSet 實(shí)現(xiàn)；未實(shí)現(xiàn)同步。
• add, remove and contains ：時(shí)間復(fù)雜度為 log(n)

三、Queue

為在處理之前保存元素而設(shè)計(jì)的集合。

• 提供了額外的插入（offer）、提取（poll）和檢查（peek）操作，當(dāng)操作失敗時(shí)返回 null 或 false，而不是拋出異常。
• 一般來(lái)說(shuō)，隊(duì)列都是先進(jìn)先出（FIFO）的方式，但也有例外：如優(yōu)先級(jí)隊(duì)列（PriorityQueue）。
• 隊(duì)列實(shí)現(xiàn)通常不允許插入空元素，因?yàn)?null 被 poll 方法用作特殊返回值來(lái)指示隊(duì)列不包含任何元素。

1、PriorityQueue

• 基于優(yōu)先級(jí)堆（實(shí)際上是最小堆）實(shí)現(xiàn)，用數(shù)組存儲(chǔ)堆；
• 未實(shí)現(xiàn)同步（線程安全的優(yōu)先級(jí)隊(duì)列：PriorityBlockingQueue），是無(wú)界隊(duì)列，但有容量（capacity），添加元素時(shí)，如果容量不足，會(huì)自動(dòng)增長(zhǎng)。
• iterator() 方法不提供保證以特定的順序遍歷優(yōu)先級(jí)隊(duì)列中的元素。
• offer, poll, remove() and add 的時(shí)間復(fù)雜度為 O(log(n))：往堆里增刪元素
• remove(Object) 和 contains(Object) 為線性時(shí)間：Java 文檔上是寫的這兩個(gè)方法的復(fù)雜度都是線性時(shí)間，即 O(n) ，因?yàn)槭怯脭?shù)組存儲(chǔ)堆的，所以 contains 就是遍歷數(shù)組查找元素，因此，contains(Object) 的復(fù)雜度是 O(n) 是沒有問題的，但是我覺得 remove(Object) 操作的復(fù)雜度是 O(n) + O(log(n))，即從數(shù)組里面找到它 O(n)，然后從堆里面刪除它 O(log(n))。（還是我理解錯(cuò)了，希望有大佬能夠指導(dǎo)一下？）
• peek, element, and size 為 O(1)：因?yàn)槭侨《秧斣亍?/li>

2、Deque

雙向隊(duì)列，支持兩端元素的插入與刪除。Deque 也可以用作 LIFO（后進(jìn)先出）堆棧。這個(gè)接口應(yīng)優(yōu)先于傳統(tǒng)的 Stack 類使用。

不支持通過(guò)索引訪問元素。

雖然 Deque 實(shí)現(xiàn)不是嚴(yán)格要求禁止插入 null 值，強(qiáng)烈建議任何允許 null 元素的 Deque 實(shí)現(xiàn)的用戶不要利用插入空值的能力，因?yàn)閚ull被一些方法用作特殊返回值來(lái)指示該雙端隊(duì)列是空的。

3、ArrayDeque（Deque 的實(shí)現(xiàn)）

• 未實(shí)現(xiàn)同步，不允許 null 值。
• 當(dāng)用作堆棧時(shí)，該類可能比 Stack 快，并且在用作隊(duì)列時(shí)比 LinkedList 快。

到此這篇關(guān)于Java中的ArrayList、LinkedList、HashSet等容器詳解的文章就介紹到這了,更多相關(guān)Java中的容器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論