Java集合

JAVA Collection的Set，List，Map，Stack，Queue介紹

如上圖，Java的集合物件源自Collection這個介面。Set，List，Queue皆是實作於它。

*註* Collection內的元素必須是物件，不可為基本資料型態

Set介面

Set介面的特性是，在其內的物件沒有特定的順序，也因為這樣，所以不允許有重複的物件，也就是在Set內找不到一對元素是e1.equals(e2)，並且最多只能有一個null元素。

Set不允許其元素中包含自己。

有些實作Set的類別有限制其元素性質，當嘗試添加一些不合格的元素時將會拋出unchecked exception，像是NullPointerException or ClassCastException。當嘗試去查詢一些不合格的元素的存在時，將會拋出一個Exception，或者只是簡單的傳回一個false值，某些實作Set介面的類別是使用前者，某些使用後者。

實作Set介面的有

• HashSet類別
  元素排列沒有順序，沒有排列性，先加入未必是排在第一個。
  元素有唯一性，也就是不能重複，加入相同的一個物件進去，會被當作是同一個。
  Hashset是以「雜湊表(Hash Table)」的方法來儲存集合元素的一種Collection，元素儲存時是運用特殊的演算法來計算儲存hash table中的位置，其優點是存取每個元素的時間是相同的。
  其利用hashCode()來搜尋指定的元素，所謂的hashCode是一個經過數學公式計算所得的數值，每個物件都可以計算出適合自己的數值，並透過雜湊表的查找提供給外界尋找物件。
  可以透過next()方法來取出目前所指向的集合元素內容，但是因為next()方法的回傳值是Object型態，所以要轉型。
  除了透過iterator來走訪，也可以透過toArray()方法來將集合內容轉換成Object[]陣列，透過for來依序取出。
  HashSet是一種nonthread-safe的集合。
• TreeSet類別(元素排列)
  元素不能重複出現，而且會由小到大做自然排序。既然它會做排序那麼它就一定會比較它所擁有的元素，所以它的元素必須是相同的型態，才能比較。元素不能為null。TreeSet內部運作是基於紅黑樹的資料結構所實作。
• SortedSet介面
  做自然排序，也就是按照字母順序做遞增排列。
• LinkedHashSet類別
  元素內容擺放是有順序性的，其依照加入的順序insertion order排放。在使用上可以透過LinkedHashSet來讓HashSet的內容透過當初加入的順序依序取出。

List介面

List介面的特性是，元素會依照特定的順序做排列，而且元素具有索引值。因為它的元素有做排序，而且有索引，所以它的元素是可以重複存在的。和TreeSet不一樣，TreeSet的元素是依據元素內容做排序，而List的排序是依據元素的索引值。

List的使用者可以精準的控制新增元素所插入到的位置。讀取元素時，是按照其索引值或是直接搜尋元素值。List的元素可以重複存在，也就是說它允許e1.equals(e2)的狀況，而且也可以有一個以上的null值。List介面提供4種方式來取得其元素，而它相似於java陣列一般，是從索引0開始，並且它的位置就在第0的索引。

List提供2種方法去搜尋特定的元素，而且也提供2種方法來高效能的去插入以及移除多個元素於List中的任一點。

List允許元素中包含自己，但這務必要非常小心的使用。這樣的狀況下，equals和hashCode方法都沒有良好的定義。

有些實作List的類別有限制其元素性質，當嘗試添加一些不合格的元素時將會拋出unchecked exception，像是NullPointerException or ClassCastException。當嘗試去查詢一些不合格的元素的存在時，將會拋出一個Exception，或者只是簡單的傳回一個false值，某些實作List介面的類別是使用前者，某些使用後者。

實作List介面的有

• LinkedList類別
  就像一節一節的車廂串接在一起，每個車廂稱為節點(node)，node由兩部分所組成，分別是資料部分和鏈結部分。資料部分所儲存的就是所需要的資料，而鏈結部分則是儲存下一個node的位址。LinkedList最後的一個node會指向null，表示後面已經沒有節點了。
  對應到Java的LinkedList類別，node中的資料欄位所儲存的是需要的資料，而鏈結欄位部分則是儲存索引(index)值，也就是紀錄元素在集合中的排列順序，索引值和陣列的索引值一樣由0開始，當我們在此集合中刪除了其中一個元素或是新增一個新的元素，元素間的索引值會自動重新排列，而最後一個元素的鏈結欄位則會儲存-1，表示後面已經沒有節點了。
  LinkedList和LinkedHashSet一樣，元素間會使用doubly-linked相互鏈結。LinkedList在走訪元素的效率上比ArrayList來得差(因為ArrayList是按照第一個元素的所在位置的偏移量去讀取其他元素位置，如果預設的連續空間滿了，就會去找記憶體中更大的一塊連續空間，通常是有個單位量，一次增加一個單位量的空間做搬移的動作，然後包含之前的元素，整塊都搬到新的更大的記憶體空間)，但是在新增或刪除元素的機制上會比ArrayList好。
  LinkedList有實作Queue介面，所以可以當作一般List使用，也可以當作具有Queue特性的集合來使用。
• ArrayList類別
  其實就是一種伸縮自如的Array，擁有較優的隨機存取機制(fast iteration and access)。
  元素加入ArrayList時也是用索引值依序儲存，先加入的元素index就在前面。它類似陣列一樣，但是不同的是我們不需要先知道它的元素數量，所以就像是一個動態的陣列。
  ArrayList是按照第一個元素的所在位置的偏移量去讀取其他元素位置，如果預設的連續空間滿了，就會去找記憶體中更大的一塊連續空間，通常是有個單位量，一次增加一個單位量的空間做搬移的動作，然後包含之前的元素，整塊都搬到新的更大的記憶體空間
• Vector類別
  是Java的三個原始集合之一，其中有所方法都加上synchronized。
  Vector特性與ArrayList相同，唯一不同的是在多執行續的機制下，Vector在同步維護上是tread-safe的，Vector原始碼中所有對外的public方法都加上了synchronized，也因為這樣讓Vector的效率比ArrayList差。如果在單執行續的環境下，不建議使用Vector。

Map介面

Map並不是Collection介面的子介面，它是一個獨立的架構。

List及Set物件是以add()方法來將元素加入，而Map物件則是以put()方法新增元素。

Map要以一個key儲存，透過key會對應到指定的資料，也就是對應值(value)，這個value是一種object。Map中key是不能重複的(重複就會覆蓋上一個)，且一個key對應到一個value。像是身分證字號一樣，有了這個號碼就可以找到對應的人。最大的好處就是可以個別操作keys與values。

Map介面可以以三種觀點來檢視：

第一是讓Map的key元素看作是一種Set，

第二是讓Map的value元素看作是一種集合collection，

第三是讓Map的key和value看作是相對映的一種集合。

Map用Map<K,V>來表示，其中K就是key值，V就是對應值value。

比較特別的是，因為Map的key值和Set集合物件的元素都是不可以重複存在的，因此可以利用keySet()這個方法將Map物件轉換成Set介面的物件。而Map的value值因為允許重複，所以可以用values()這個方法將Map物件轉換成其它的Collection物件元素。

當將可變對象用作Map的key時要十分注意。

Map不允許它的key值包含自己，但是value值包含自己是被允許的，但是若這麼做的話要格外當心，這種情況下的Map的equals和hashCode方法將沒有良好的定義。

一般繼承自Map介面的類別提供2個標準的建構方式，分別是空的參數建構子(它將建立一個沒有元素的集合物件)，以及帶有單一Map型別參數的建構子(它將建立一個具有與參數相同的key-value對映的元素)，利用第二種方式將可以複製任何的Map。

有一種'破壞性'的方法，該方法將拋出(但不是必須的)UnsupportedOperationException當它嘗試在自己所在的map去修改這個map(如果該map不支援這種操作)。

有些實作Map的類別有限制其key或value的性質，像是key或value不能有null值，或是限制key值的型別，當嘗試添加一些不合格的key或value時將會拋出unchecked exception，像是NullPointerException or ClassCastException。當嘗試去查詢一些不合格的key或value的存在時，將會拋出一個Exception，或者只是簡單的傳回一個false值，某些實作List介面的類別是使用前者，某些使用後者。

Map介面是Java Collections Framework中的其中一員。

實作Map介面的類別有

• HashMap類別
  元素的key值不可重複，元素也不會依據key值來排序，HashMap是非同步(synchronize)存取的類別。無順序性，無排序性的集合，其key和value皆可為null。用get()去取key時，如果該key不在集合中，執行時不會拋Exception，而是回傳null。
• TreeMap類別
  元素的key值不可重複，但是元素會依照key值有小到大來排序。
• HashTable類別
  是Java的三個原始集合之一，其中有所方法都加上synchronized。
  其為 無順序性，無排序性的集合。與HashMap不同的是，HashTable是thread-safe，以及其key和value都不可為null。
• SortedMap介面
  根據元素的key做自然排序，其key不得重複也不可以為null，但其velue允許重複。
• TreeMap類別
  實作SortedMap介面，具有排序性(自然排序)。其和TreeSet一樣是基於紅黑樹演算法所實作出來的集合。TreeMap所置入的key必須是相同的資料型別。
• LinkedHashMap類別
  元素內容擺放是有順序性的，其依照加入的順序insertion order排放。除了順序性之外，大致上和HashMap相同。
  效能上，走訪元素(iteration)，LinkedHashMap優於HashMap，但是新增或刪除元素時，HashMap會較優。

stack類別

是Java的三個原始集合之一，其中有所方法都加上synchronized。其為Vector的子類別。Stack類別描述了後進先出(LIFO)的堆疊物件。它繼承自Vector類別，並有5個操作以讓一個vector物件被視為一個堆疊。

正常的push and pop操作它都有提供，還有像是檢視最上層物件的方法，測試stack是否為空的方法，還有搜尋一個stack內元素和得出它距離最頂層有多遠的方法。

取得元素可用peek()或pop()方法，它們之間的差別在於pop()在取得元素之後會將元素刪除。

一個stack剛開始建立的時候，它是沒有任何元素的。

Deque介面或是實作該介面的類別，擁有更完整和一致性的LIFO堆疊操作。

Queue介面

繼承自Collection介面，用來在元素處理之前持有元素。除了Collection所提供的基本的操作之外，Queue提供了額外的插入，提取和檢視的操作。這些操作以2種格式存在，第一是萬一操作失敗則拋出一個例外，第二是萬一操作失敗則回傳一個特定值(可以是null或false之類的)，後者是有容量限制的Queue的實作類別所採用的方式。這兩種格式所使用的方法如下：

Queue一般排序元素的方式是先進先出FIFO的方式，但這並非一定，就像priority queues，它會以它提供的comparator方式去排序元素，或是按照自然排序法來排序元素，此外還有像是LIFO queues，它是以後進先出LIFO的方式來排序元素，但不管是用何種排序的方式，當時用remove()方法或是poll()方法時都是移除Queue的第一個元素。

如果是先進先出FIFO的queue，新增的元素都將插入在最尾部。以其他方式排序的queue則將使用各自定義的排序方式。

offer()方法將插入一個元素，失敗時則回傳false，這點它和Collection.add()方法在插入元素失敗時拋出例外的作法不同。offer()方法是設計於那些在插入元素時經常會失敗的queue(比如固定容量或有界限的queue)，而不是那些不常插入元素失敗的queue。

remove()和poll()方法，用來提取並移除queue的第一個元素。而第一個元素是甚麼則是要看該queue是根據甚麼排序方式了。這兩個方法的差別只在於當queue是空的時候，remove()會拋出例外，而poll()則是回傳一個null值。

element()和peek()方法讀取queue中的第一個元素，但是並不把它從queue中移除。

Queue介面並沒有定義在同步編程中很常見的blocking queue方法。blocking queue方法會去等待元素沒有被其他執行續使用時才允許存取，它被定義在BlockingQueue介面中。

雖然一些實作Queue的類別(像是LinkedList)並沒有限制插入null到元素中，但是通常一些實作Queue的類別會不允許這麼做。就算實作Queue的類別允許這麼做，null也不應該被插入到Queue中，因為null在poll()方法被用來當作一個特定的回傳值以表示該queue是空的。

實作Queue的類別通常不會定義基本版本的equals()和hashCode()方法，而是用繼承自Object類別的這些方法，因為基本版本的"相等"定義在那些相同元素但是不同排序法的queues中並非是良好的定義。

Queue介面是Java Collections Framework中的其中一員。

實作Queue介面的類別：

• PriorityQueue類別
  PriorityQueue集合讓程式開發人員可以撰寫自己想要的排序規則，只要實作Comparator這個interface以及裡面所提供的compare()抽象方法，最後將物件放到PriorityQueue建構子中，所建立的PriorityQueue集合就會依照compare()方法的邏輯排序元素內容。預設的PriorityQueue是以自然法則來排序。

整理後得出，JAVA集合有4大特性：

1. 排序性(Sorted)：利用實作equals()方法將集合的元素做遞增排序(也就是自然排序)的動作。

2. 順序性(Ordered)：也叫做次序性，其元素排列方式是依照某一特性順序排列(像是加入元素的順序，元素的index，或是最後的存取次序等)，而取出時也會依照特定順序依序取出。

3. 重複性(Duplicates)：集合中是否允許出現重複的元素。

3. 鍵值(Key)：使用Key來參考到真正物件所存放的位置。每一個元素所存放的物件都有相對應的Key，而一個Key最多只能對應一個元素。Key是唯一性的，但是元素所存放的物件則可以重複。

依據上面所提到的各介面和類別，去檢視集合的這四大特性，整理如下：

介面與類別名稱	排序性	順序性	允許重複	使用key值
<<interface>> Set
<<interface>> SortedSet	*
HashSet
TreeSet	*
LinkedHashSet		*
<<interface>> List		*	*
ArrayList		*	*
LinkedList		*	*
Vector		*	*
Stack		*	*
<<interface>> Queue		*	*
<<interface>> Map			*(value)	*
<<interface>> SortedMap	*		*	*
HashMap			*	*
Hashtable			*	*
TreeMap	*		*	*
LinkedHashMap		*	*	*

走訪Collection方法

Iterator與ListIterator介面，都可以用來走訪或是刪除集合物件的元素，但是現在大多數都是使用ForEach來走訪集合物件，如下。

ForEach：

List<Integer> list = new LinkedList<Integer>();

list.add(2);

…

for(Integer i : list){

...

}

Iterator：

除了Map族群之外，所有的Collection都會產生Iterator。

其中Iterator介面提供走訪集合元素及刪除元素的方法，List和Set都已經實作了Iterator介面，所以只要利用iterator()方法，就可以取得Iterator<E>介面的物件。像是

Iterator<String> itr = 實作Iterator介面的集合物件名稱.iterator();

利用iterator()方法是將集合物件的元素轉換成Iterator<E>介面的物件，轉換之後就可以利用Iterator的物件走訪與刪除集合物件的元素了。利用Iterator物件刪除集合中的元素，原先產生它的集合物件裡的元素，也會跟著刪除，因為它們指向的集合是同一個。

Iterator是單向單次性的，也就是說Iterator物件的讀取是單向的且只能讀取一次，只能向下走訪，從頭走到尾，不能往回讀取，所以當Iterator物件的hasNext()方法傳回值為false時，該Iterator物件也就沒有用處了。要再讀取的話要重新用iterator()方法取得Iterator物件。

ListIterator：

Iterator物件可以用在Set和List物件，但是ListIterator物件就只能用在List物件。ListIterator物件的走訪方式是雙向的，可以往前或往後走訪。利用listIterator()方法，就可以得到ListIterator的物件。像是

ListIterator<Integer> litr = 實作ListIterator介面的List集合物件名稱.listIterator();

利用listIterator()方法是將List集合物件的元素轉換成ListIterator<E>介面的物件，再利用它走訪或是刪除集合物件裡的元素。

無論是Iterator或ListIterator的物件，都必須要在集合物件已宣告好並加入元素之後才可以宣告與建立Iterator或ListIterator的物件，建好之後如果集合元素再加入新的元素，剛已經宣告好的Iterator或ListIterator物件。就讀不到它了。

Enumeration：

Enumeration 是使用在Map族群的走訪。

和Iterator一樣，Enumeration 亦只能向下走訪。

使用Enumeration，透過其nextElement()方法可以逐次存取元素內容值，亦可利用hasMoreElements()方法測試是否還有下一個元素，有則回傳true，反之則回傳false。

利用Enumeration所取出元素內容值是各自獨立，沒有順序性的。