集合(Collections)

以往要將原生資料或物件放入陣列中，陣列的長度需先宣告，一宣告就不能變更長度。若事先不知道長度或者要隨時可以變更長度，就必需使用集合。可以把集合想成是多啦A夢的百寶袋，要裝多少物件都可以，只要記憶体足夠即可。

集合中的每個物件被稱為元素(elements)，每個元素的型態可以不一樣，因為都會被轉換成 Object (未使用泛型時)，不過原生資料不允許被在集合之中。

集合的重點在於如何新增移除元素，如何找到並取出元件，以及走訪整個集合。集合重度依靠泛型而寫成的，所以就不再限定只會轉成 Object 。

Collection Type

集合的類型如下圖所示

Map Type

Map 的類型如下圖所示

Collection 介面有三個子類別，分別是 LIst，Queue 及 Set。

Map 是另一個獨立的介面，跟 Collection 無關，它類似 Python 的字典。Collection 介面定義了add，addAll，clear，contains，wquals，remove，removeAll，size，iterator 等相關方法。

Iterator 介面

Iterator 為 Collection 的走訪器，有hasNext()，next()，remove() 等方法，只能由上往下走。若要能往上讀取就要使用ListIterator。

ListIterator 繼承 Iterator，可作新增修改刪除動作，每個元素間都有 index，可用 index 取得元素，有 add，hasNext，hasPrevious，next，nextIndex，previous，previousIndex，remove，set 等方法。

Enumeration 介面

為 Map 的走訪器，有 hasMoreElements，nextElement 等方法。

集合的四特性

了解每一個集合時, 需記住每個集合是否有如下四個特性 :

排序性 : 遞增或遞減的特性。
順序性 : 是否有依加入的順序排列。有順序就無排序, 有排序就無順序。
重複性 : 是否允許出現重複的物件。
鍵值 (Key/value) : 使用鍵值存放物件，只有 Map 使用此法。

集合介面	排序性	順序性	不允許重複	使用鍵值
ArrayList		v
LinkedList		v
Vector		v
HashSet			v
LinkedHashSet		v	v
TreeSet	v		v
HaspMap				v
LinkedHashMap		v		v
HashTable				v
TreeMap	v			v

最像陣列的集合，每個集合都有 index，除了可動態擴充長度外，其他都跟陣列一樣。

所有的 List 都是有順序性、無排序、可重複，可使用如下的方法新增、插入、刪除

add("Apple") //在最後新增資料
add(2,"Banana") //在索引2 插入新資料
get(index) //取得 index 索引的資料
remove(index) //移除 index 索引的資料
indexOf("Apple") //取得第一個 "Apple 的索引編號

ArrayList

最簡易使用的 List 就屬 ArrayList，使用 add 新增、get(index) 取出、remove(index) 刪除。ArrayList 底層其實是一個陣列，並不是雙向連結。當元素超出目前陣列容量時，ArrayList 會自動擴充容量(通常是原來容量的 1.5 倍到 2 倍)，並複制資料到新的陣列中，在效能上其實還不錯。

非泛型ArrayList

非泛型會產生 Runtime error，且必需要強制轉型。泛型會產生 Compiler error，不需強制轉型。

初始化

new ArrayList<>() 是產生一個空的 List，如果要給定初始值，可以使用如下二種方式。

傳入 List.of()。List.of() 是不可變更的 List，但加上 new ArrayList 後，此 List 即可變更。

Listages=new ArrayList<>(List.of(10,20,30,40,50));

另也傳入 Array.asList()

Listages=new ArrayList<>(Arrays.asList(10,20,30,40,50));

LinkedList

LinkedList 採用雙向鏈結，所以在新增刪除的效能比 ArrayList 快很多，但走訪的效能比 ArrayList 差。LinkedList 比 ArrayList 多了一個 addLast，其功能同 add。

排序

如果要排序的資料是 Integer、String 等簡易的資料型態，可以使用 List 裏的 sort、Collection.sort 及 stream 的三種方式排序，如下代碼所示。

如果要排序的資料是自訂資料結構，也有如下二種方式。

Vector

Vector 是最原始的集合，特性同 ArrayList。但 Vector 是 Thread-safe，效能遠比 ArrayList 差，建議能不要用就不用。

Stack

繼承 Vector，具後進先出原則，使用 push 加入，pop 取出(並刪除)，peek取出(但不刪除)。

Set 介面的特性為裏面的物件不會重複。

HastSet

HastSet 使用 HashCode 來判斷物件是否相同，如果相同則新物件會覆蓋舊物件，所以 HashSet 裏的物件不會重複，且無順序性，無排序性。

HashCode (雜湊碼) 是一種數學演算法，HashSet 使用 HashCode 決定物件要存放的位置。所以在大量的資料中要查找某個物件，使用 HashSet 是個效能非常高的方式。

LinkedHashSet

LinkedHashSet 也是使用 HashCode 決定物件存放的位置，但多了雙向連結記錄上下物件，所以具順序性，無排序，不允許重複，新增修改的效能略遜於 HashSet (因為要加雙向連結)。

若要將 HashSet 依加入的順序取出的話，可轉為 LinkedHashSet 類型，如下所示。

HashSet hs=new HashSet();
LinkedHashSet lhs=new LinkedHashSet(hs);

TreeSet

TreeSet 不是使用 HashCode 來判斷物件是否重覆，它是繼承 SortedSet，使用二元樹排序，一樣重複的物件會覆蓋舊物件，具排序性，無順序性，不可重複，新增修改的效能是最差的。

Queue 具先進先出原則，但不要使用 add、remove 方法，因為會丟出例外。需改採 offer、poll、peek 三個方法。

LinkedList

LinkedList 除了實作 List 介面外，還實作了 Queue 介面，所以 LinkedList 除了可以當作 List 來使用，也可以當成 Queue。

Queue q=new LinkedList();
q.offer("First");
q.poll();

PriorityQueue

是一個可以自訂排序方式的類別，排序時先實作 Comparator 裏的 compare()方法，再將產生的物件放入PriorityQueue 建構子。

注意, String s=”abcd”;
s.compare(“defg”); 先一個字一個字比, 若前面比較小, 傳回負數, 前面比較大, 傳回正數, 二個都一樣, 傳回 0

Iterator

 for-each 遍訪所有元素比較簡潔，但無法在迴圈中刪除資料，否則會發生 ConcurrentModificationException 例外。

使用 Iterator 遍訪所有元素時，可以在迴圈中安全的刪除修改元素，比較適合邊走邊修改的需求。

Map在其他的語言如Python, C#中, 稱為字典, 是一個包含key及value的袋子. key必需是唯一, 值為物件. Map不繼承Collection介面. 使用put/putAll加入元素, get(key)取回元素

HashMap

無順序, 無排序, 可允許key及value都是null

LinkedHashMap

同HashMap, 但因為加了雙向鏈結, 所以走訪效能快, 新增刪除效能差

HashTable

同HashMap, 但這是thread-safe的, 鍵值不可為null

SortedMap

根據key值作自然排序, key不得重複也不可能null

TreeMap

實作SortedMap, 採二元樹排序, 裏面的鍵值必需是同一種資料型態

Deque 介面

Deque是Collection的子介面, 可同時作為queue及stack
queue : FIFO, add, remove
stack : LIFO, push, pop

  Deque stack=new ArrayDeque<>();
  stack.push("one");
  stack.push("two");

Collections集合工具

Collections.synchronizedMap(map) : 變成thread-safe
Collections.sort(list, sort); 依sort方式來排序, 見下面說明

排序集合(Ordering Collections)

Comparable 介面 : 需實作compareTo(), 僅提供一個排序的方式
返回值需包含0, 1, -1三個, 加入Collection的物件, 會依此排序取出

Comparator介面 : 需實作compare(), 可建立多個排序方式
List<Student> list=new ArrayList<>();
Compartor<Student> sortName=new StudentSortName();
Comparator<Student>sortGpa=new StudentSortGpa();
Colloections.sort(list, sortName); <==依sortName排序
Colloections.sort(list, sortGpa); <==依sortGpa序

NavigableSet/NavigableMap

此二個會根據內容作自然排序

NavigableSet 為SortedSet, 只可用在TreeSet;
NavigableSet<Integer> ns1=new TreeSet<>();

NavigableMap為SortedMap, 只可用在TreeMap;
NavigableMap<Integer, Integer> ns2=new TreeMap<>();

並行集合

常見的有
ConcurrentHashMap : 同步HashMap實作
ConcurrentSkipListMap : 同步TreeMap實作
CopyOnWriteArrayList : 同步ArrayList實作