Java總結之容器家族--Collection

摘要： 零、前言 Collection是[收集品]的意思,這裡稱[容器],是java中的一個介面，位於 java.util 包下 Collection下有三大介面： List(列表) 、 Set(集合) 、 Queue(佇列) Collection...

零、前言

Collection是[收集品]的意思,這裡稱[容器],是java中的一個介面，位於 java.util 包下

Collection下有三大介面： List(列表) 、 Set(集合) 、 Queue(佇列)

第一節：List介面

List：列表，顧名思義是一種表結構，核心方法：

按索引插入元素 void add(int var1, E var2)

按索引刪除元素 E remove(int var1);

按索引修改元素 E set(int var1, E var2)

按索引查詢元素 E get(int var1)

特點：
1.增刪改查操作都可以按照索引進行精確的控制，所以是元素的有序排列
2.允許相同元素

List是java中使用頻率非常高的一個介面，最要的子類：ArrayList、Vector、LinkedList

1.其中ArrayList、Vector是AbstractList-->AbstractCollection-->Collection 路線

2.LinkedList不止實現了List，還實現了Deque，就像得到兩個師傅的真傳，招式(方法)更多一些

Queue介面是佇列(先進先出)，Deque介面(雙端佇列)是Queue的弟子，兩頭都能隨意進出

所以根據需求即可當棧也可當佇列，LinkedList得到了Deque的真傳，所以也可以

關於抽象類：

抽象類一般是先實現介面，或者拓展一些子類公用方法，總之就是把能做的先做了。

有種天下父母心的感覺，就像AbstractList對ArrayList說：我能幫你做的儘量都做了，接下來就看你的了

public abstract class AbstractCollection<E> implements Collection<E>
public abstract class AbstractSequentialList<E> extends AbstractList<E> 
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

1.ArrayList:陣列列表

2.Vector：載體

3.LinkedList：鏈式列表

4.Vector、ArrayList與 LinkedList的比較

可以說Vector、ArrayList是親兄弟,LinkedList算個堂兄

專案	執行緒安全?	實現	擴容	定點新增/刪除	尾新增/刪除	查詢	修改
ArrayList	否	陣列	50%	O(n)	O(1)	O(1)	O(1)
Vector	是	陣列	100%	O(n)	O(1)	O(1)	O(1)
LinkedList	否	雙鏈表	--	O(n)	O(1)	O(n)	O(n)

尾新增測試[add(E)]

----	複雜度	1000	10000	10W	100W	1000W
ArrayList	O(1)	0.0004秒	0.0016秒	0.0063秒	0.0297秒	0.6704秒
LinkedList	O(1)	0.0004秒	0.0017秒	0.0098秒	0.2384秒	2.4285秒

運算元opCount=1000W:插入的位置與耗時比較

----	1/9	3/9	5/9	7/9	8/9
ArrayList	0.1496秒	0.1136秒	0.0821秒	0.0297秒	0.0012秒
LinkedList	0.0150秒	0.0251秒	0.0386秒	0.0176秒	0.0102秒

可見ArrayList越往後插入越快，因為要變動的元素越少

LinkedList從兩頭到中間速度變慢，取決於連結串列的查詢機制，總的來說，

隨機新增LinkedList比較有優勢些,只是末尾新增ArrayList較好

陣列和雙鏈表兩種資料結構：

陣列：定點新增，後面元素都要往後挪個位，O(n)-------雙鏈表：耗時在找到那個定點，新增很快，綜合O(n)
陣列：定點刪除，後面元素都要往前挪個位，O(n)-------雙鏈表：耗時在找到那個定點，刪除很快，綜合O(n)
陣列：定點查詢，陣列自帶索引光環，O(1)-------雙鏈表：一個一個挨著找 O(n)
陣列：定點修改，陣列自帶索引光環，O(1)-------雙鏈表：耗時在找到那個定點，修改很快，綜合O(n)

綜上所屬：

隨機訪問、修改效能：Vector、ArrayList>LinkedList
考慮到Vector、ArrayList新增或刪除時：
1.可能伴隨擴容/縮容，
2.當元素個數巨大時，可能造成大量空閒空間
3.陣列連續開闢空間，會造成儲存空間的碎片化
的這些問題，在大量新增或刪除操作使用LinkedList是更好的選擇

因為雙鏈表：
1.雙鏈表的新增/刪除耗時在查詢工作，而雙鏈表查詢時會檢視索引在前半還是後半
來決定從頭查詢或從尾查詢，從而最差情況只需size/2,而陣列最差情況為size
2.連結串列不需要開闢連續空間，從而避免儲存空間的碎片化

另外在資料非常巨大的時候：
LinkedList基於雙鏈表，需要new 巨大數量的節點(Node),
Vector、ArrayList只是開闢空間，所以更好一些，所以根據需求酌情處理

關於 Vector

Vector類對集合的元素操作時都加了synchronized，保證執行緒安全。但使得效率下降：如

public synchronized boolean add(E e) {
modCount++;
add(e, elementData, elementCount);
return true;
}

所謂同步：即當一個Iterator被正在被使用，另一個執行緒對Vector新增或刪除元素，這時呼叫Iterator的方法時將丟擲異常
public synchronized void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final Object[] es = elementData;
final int size = elementCount;
for (int i = 0; modCount == expectedModCount && i < size; i++)
es[i] = operator.apply(elementAt(es, i));
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
modCount++;
}

可以看到很多關於修改的方法當:modCount != expectedModCount時都會扔一個ConcurrentModificationException異常
也就是期望的修改次數與真實的修改次數不一致時

第二節：Set介面

集合：數學上的集合性質：

確定性：給定一個集合，任給一個元素，該元素或者屬於或者不屬於該集合
互異性：一個集合中，任何兩個元素都認為是不相同的，即每個元素只能出現一次。
無序性：一個集合中，每個元素的地位都是相同的，元素之間是無序的。

Set的操作比較少，基本上也就是Collection傳下來的方法

Set一般基於Map來實現：HashSet、LinkedHashSet、TreeSet的特性，根本上是HashMap、LinkedHashMap、TreeMap的特性

1.HashSet

HashSet內部有一個HashMap<E,Object> map成員變數，增刪實際上是使用map的方法

按照雜湊的順序:hashCode()，equals(Object obj)

底層實現：HashMap

private transient HashMap<E,Object> map;

public HashSet() {
map = new HashMap<>();
}

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}

2.LinkedHashSet

LinkedHashSet是HashSet的子類，原始碼少得可憐,基本上都是呼叫父類(HashSet)的構造方法

基於一個由連結串列實現的雜湊表，保留了元素插入順序

底層實現：LinkedHashMap

LinkedHashSet中：

public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}

HashSet中的三參構造

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

3.TreeSet---有序集合

實現NavigableSet：使用元素的compareTo對元素進行排序,也可使用Comparator自定義比較器

TreeSet多拜了一個師傅：NavigableSet-->SortedSet 使用方法也多幾個

底層實現：TreeMap

public TreeSet() {
this(new TreeMap<>());
}

插入元素順序比較

HashSet<String> hashSet = new HashSet<>();
hashSet.add("趙");
hashSet.add("錢");
hashSet.add("孫");
hashSet.add("李");

//按照雜湊的順序:hashCode()，equals(Object obj)
System.out.println(hashSet);//[錢, 趙, 孫, 李]

LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("趙");
linkedHashSet.add("錢");
linkedHashSet.add("孫");
linkedHashSet.add("李");
//基於連結串列實現了插入的順序
System.out.println(linkedHashSet);//[趙, 錢, 孫, 李]

TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("趙");
treeSet.add("錢");
treeSet.add("孫");
treeSet.add("李");
//按照compareTo()的排序
System.out.println(treeSet);//[孫, 李, 趙, 錢]

專案	執行緒安全?	實現	add	remove	contains
HashSet	否	HashMap	O(1)	O(1)	O(1)
LinkedHashSet	否	LinkedHashMap	O(1)	O(1)	O(1)
TreeSet	否	TreeMap	O(log(n))	O(log(n))	O(log(n))

第三節：Queue

關於佇列，是一直先進先出的線性資料結構，使用場合比較狹窄

子類常見的有PriorityQueue(優先佇列)和上文提到的LinkedList。

PriorityQueue

PriorityQueue優先佇列，是基於陣列實現的二叉堆來實現的特殊佇列，具有完全二叉樹的性質。

每次從優先佇列中取出來的元素要麼是最大值或最小值（最大堆/最小堆）

Collection的簡單總結就醬紫

後記、

1.宣告：

1----本文由張風捷特烈原創,轉載請註明

2----歡迎廣大程式設計愛好者共同交流

3---個人能力有限，如有不正之處歡迎大家批評指證，必定虛心改正

4----你的喜歡與支援將是我最大的動力

2.連線傳送門：