前言
Java 中的集合是一個框架,它提供了一個存儲和操作物件組的體系結構。能夠有系統的操作資料,是處理資料的好幫手。Java Collections 可以實現您對數據執行的所有操作,例如搜索,排序,插入,操作和刪除。
早在 Java 2 中之前,Java 就提供了特殊類別。比如:Dictionary, Vector, Stack, 和 Properties 這些類別用來存儲和操作物件組。雖然這些類別都非常有用,但是它們缺少一個核心的,統一的主題。由於這個原因,使用 Vector 類別的方式和使用 Properties 類別的方式有著很大不同。
集合框架被設計成要滿足以下幾個目標。
- 該框架必須是高性能的。基本集合(動態數組,鍊錶,樹,哈希表)的實現也必須是高效的。
- 該框架允許不同類型的集合,以類似的方式工作,具有高度的互操作性。
- 對一個集合的擴展和適應必須是簡單的。
為此,整個集合框架就圍繞一組標準介面而設計。你可以直接使用這些介面的標準實現,諸如:LinkedList、HashSet 和 TreeSet 等,除此之外你也可以通過這些介面實現自己的集合。
此篇針對如何使用集合框架做個拋磚引玉,重點在於如何簡單的使用這些類別,更深入的瞭解集合框架不在此篇的討論範圍。
一、集合框架介紹
從集合框架圖可以看到,Java 集合框架主要包括兩種型態的容器,一種是集合(Collection),存儲一個元素集合。另一種是圖(Map),存儲鍵/值對映射。 Collection 介面又有 3 種子類型,List、Set 和 Queue,再下面是一些抽像類別,最後是具體實現類別,常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。
集合框架是一個用來代表和操縱集合的統一架構。所有的集合框架都包含如下內容:
- 介面:是代表集合的抽像數據類型。例如 Collection、List、Set、Map 等。之所以定義多個介面,是為了以不同的方式操作集合物件。
- 實現(類別):是集合介面的具體實現。從本質上講,它們是可重複使用的數據結構,例如:ArrayList、LinkedList、HashSet、HashMap。
- 算法:是實現集合介面的物件裡的方法執行的一些有用的計算,例如:搜索和排序。這些算法被稱為多型,那是因為相同的方法可以在相似的介面上有著不同的實現。
除了集合,該框架也定義了幾個 Map 介面和類別。 Map 裡存儲的是鍵/值對。儘管 Map 不是集合,但是它們完全整合在集合中。
Java 的集合框架使用 泛型(Generic) 的概念下去設計,集合框架的根介面為 Iterable<T>,可以依照傳入的型態儲存 Java 物件。
二、集合介面
Collection 介面中定義了所有集合最基本的存取方式 (看 Collection API 說明)。Collection 介面並未定義集合中資料之間的順序性或重複性。
- 順序性:表示將物件加入集合時,依加入先後設定順序關係;因此可以依據順序的索引值來取出物件。
- 重複性:表示集合是否允許加入重複的物件值,而所謂的重覆是指呼叫該物件的 equals 及 hashCode 比較時其值為 true,即表示加入集合中的物件值重覆。
- 排序性:可以依照人為的邏輯,將集合內的元素做排序。
致於各類集合的順序性、重覆性要由 Collection 介面的子類別或孫類別中實作。
介面名稱 | 介面描述 |
---|---|
Collection 介面 | Collection 是最基本的集合介面,一個 Collection 代表一組 Object,即 Collection 的元素,Java 不提供直接繼承自 Collection 的類別,只提供繼承於的子介面(如 List 和 set )。 |
List 介面 | List 介面是一個有序的 Collection,使用此介面能夠精確的控制每個元素插入的位置,能夠通過索引(元素在 List 中位置,類似於數組的索引)來訪問 List 中的元素,第一個元素的索引為 0,而且允許有相同的元素。 List 介面存儲一組不唯一,有序(插入順序)的物件。 |
Set 介面 | Set 具有與 Collection 完全一樣的介面,只是行為上不同,Set 不保存重複的元素。 Set 介面存儲一組唯一,無序的對象。 |
SortedSet 介面 | 繼承於 Set 保存有序的集合。 |
Map 介面 | Map 介面存儲一組鍵值對象,提供 key(鍵) 到 value(值) 的映射。 |
Map.Entry 介面 | 描述在一個 Map 中的一個元素( 鍵/值 對)。是一個 Map 的內部類別。 |
SortedMap 介面 | 繼承於 Map,使 Key 保持在升序排列。 |
Enumeration 介面 | 這是一個傳統的介面和定義的方法,通過它可以枚舉(一次獲得一個)物件集合中的元素。這個傳統介面已被迭代器(Iterator)取代。 |
Set 和 List 的區別:
- 1. Set 介面儲存的是無序的,不重複的數據。
List 介面儲存的是有序的,可以重複的元素。 - 2. Set 檢索效率低下,刪除和插入效率高,插入和刪除不會引起元素位置改變,實現的類別有 HashSet、TreeSet。
- 3. List 和數組類似,可以動態增長,根據實際存儲的數據的長度自動增長 List 的長度。查找元素效率較高,插入刪除效率低,因為會引起其他元素位置改變,實現的類別有 ArrayList、LinkedList、Vector。
三、List 介面
List 介面最有的特點是有順序性,亦表示,加入物件至 List 集合時是可指定位置。
3.1 ArrayList 類別
- 有順序性,其順序是以加入的先後順序為其元素的順序,而加入的元素物件允許重覆。
- 可以透過索引值隨機存集合中的元素。
- 可以指定加入的物件,插入在集合中的那一個位置。
- 其操作方式有點類示陣列。
- 但若要對 ArrayList 索引值在中間的元素進行安插和移除,其效能略差(與 LinkedList 比)。
範例 1:
3.2 LinkedList 類別
- 除了實作 List 介面外,也實作 Queue 介面。
- LinkedList 卻是以鏈結依序串連 List 中的元素。
- 若要找出集合中的某一物件值,則必需從集合的第一個元素開始搜尋到最後一個元素,所以不適合以索引值直接隨機存取其中的元素。
- 但若時常需要在集合中插入物件或刪除物件,其效能比 ArrayList 好。
範例 2:
3.3 Vector 類別
- Vector 是 Java 的原始集合,其特性基本上與 ArrayList 相同,唯一不同處,在多執行緒的機制下,Vector 在同步維護上是 thread-safe 的,而 ArrayList 不是。
- Vector 的原始碼中所有對外的 public 方法都加上了 synchronized 修飾子。
- Vector 在效率上就比 ArrayList 差。
範例 3:
3.4 Stack 類別
- Stack 類別是 Vector 的子類別,它支援後進先出的原則(Last in first out)(first in last out先進後出)。
- 可利用 push() 方法加入原素內容。
- 利用 peek() 與 pop() 取得集合內元素的資料。
- pop() 在取得元素內容後會將該元素刪除,而 peek() 不會。
範例 4:
3.5 List 集合中元素的排序問題
- 陣列中的元素值排序,可以用 Arrays.sort()。
- List 集合中元素排序,可以使用 Collections.sort()。
- 如果是 Set 集合中元素要做排序,有兩處理方式:
(i) 可以先使用 ArrayList 或 LinkedList 將 Set 物件轉換為 List 物件,再使用 Collections.sort() 處理。
(ii) 使用 TreeSet。 - 不論陣列或 List,若需要排序元素值,前提這些元素物件所宣告的類別必需實作 Comparable 介面,且要實作其指定的 compareTo() 方法,並把自己的排序邏輯寫在 compareTo() 方法中。
- 若是原先定義的排序邏輯不敷使用,可以實作另一個 Comparator 介面的 compare() 方法。
四、Set 介面
Set 是不允許重複元素值的集合。每個加入 Set 集合的物件必需做值重覆性的檢查(檢查方式可透過該元素類別中的 equals() 及 hashCode() 方法)。而 Set 的 add() 方法會用加入物件的 equals() 及 hashCode() 方式處理元素值重覆的問題。若當兩個物件的 equals 等於 true,而 hashCode 的值又相等時,表示這個物件已重覆出現。
Set 最大的特色是不允許重覆,也無法指定順序。
4.1 HashSet 類別
- HashSet 是典型的 Set 實作類別,其特性是沒有次序性,不允許值重覆。
- 加入的順序與輸出的順序不一定會相同。
範例 5:
4.2 LinkedHashSet 類別
- LinkedHashSet 仍有 Set 不允值重覆的特性,但元素集合中的排列順序跟安插順序一樣。
- 就算重覆加入相同物件值,亦無法加入集合,也不影響原有順序。
範例 6:
五、SortedSet 與 NavigableSet 介面
SortedSet 介面 繼承 Set 介面,擁有排序功能。
具排序性,當物件加入集合時,不但會做重複性的檢查,加入後還會排序。其排序方式是以物件 compareTo 方法,和已經存在的元素相比較,並執行 QuickSort 演算法,將元素由小排到大。因此加入 SortedSet 的物件類別要實作 compareTo 方法,否則會產生執行時期錯誤。
NavigableSet 介面 繼承 SortedSet 介面,是 JDK 6.0 增加的新介面。
NavigableSet 除了會做重複性的檢查,能自動排序,還提供可以在已排序集合中前後操控的方法,方便在已排序的集合中往前往後瀏覽物件。
5.1 TreeSet 類別
- TreeSet 是 NagiableSet 的實作類別,所以也是 SortedSet 實作類別。
- 物件加入 TreeSet 的集合,除了做重複性檢查外,一旦物件加入 TreeSet 集合,就會執行物件的 compareTo 方法來排序。
- 因此要加入 TreeSet 集合的物件必須是同一類別或其子孫類別的物件,而且該類別要實作 Comparable 介面,並實作其指定的 compareTo() 方法。
- 若將 null 加入 TreeSet 集合中,在執行時期呼叫物件的 compareTo() 方法將發生 NullPointException。
- 若將不同類別物件加入 TreeSet 集合中,也會在執行物件的 compareTo() 方法時產生 ClassCastException。
範例 7:
六、Queue 與 Deque 介面
從 JDK 5.0 之後,Collection 介面又擴充出 Queue 介面。Queue 是有順序的集合,其提供先進先出(first in first out)的原則控制元素的存取。
最常用來處理排程、排隊系統。
從 JDK 6.0 之後,Queue 介面又擴充出 Deque 介面,支持兩端插入和移除元素。名稱 Deque 是「雙端佇列」的縮寫,通常發音為「deck」。
6.1 PriorityQueue 類別
- 它實作了 Queue 介面。
- 元素會依先進先出原則排列其位置。
- 利用自然排序法調整排列順序,也就是用元素本身實作的 compareTo() 來執行排序。
- PriorityQueue 集合中的物件不允許 null 元素值。
範例 8:
6.2 ArrayDeque 類別
- 從 JDK 1.6 之後,擴充的類別,實作 Deque 介面。
- 提供了插入,移除和檢查元素的方法。這些方法中的每一種都以兩種形式存在:一種在操作失敗時拋出異常,另一種返回特殊值(null或false,具體取決於操作)。
- 既具有 FIFO 特點又具有 LIFO 特點,即是佇列又是棧。
- 不推薦插入 null 元素,null 作為特定返回值表示佇列為空。
範例 9:
七、Map 介面
Map 中的一組元素有兩個部分
(i) 鍵值(key)
(ii) 對應的資料物件值(value)
Map 中的每個元素的鍵值都不相同。每個鍵值對應到一個而且只有一個資料物件值。Key值不可重覆。但是要成為有意的鍵值物件,該類別應該要覆蓋 equals() 及 hashCode() 方法,否則鍵值的重覆檢查會有問題。Value 值可重覆。
7.1 HashMap 類別
- 元素加入的順序與鍵值排列順序可能不同。
範例 10:
7.2 LinkedHashMap 類別
- 元素加入的順序與鍵值排列順序相同。
範例 11:
7.3 TreeMap 類別
- 鍵值會依自然順序排序。
範例 12:
7.4 HashTable 類別
- 功能與 HashMap 一樣,但其具 Thead-safe。
範例 13:
八、簡單 Generic 與 Comparable 範例
Java 語言中,有許多類別可以依據某種條件進行排序的動作,例如 Integer、Double、String 等。事實上,我們也可以把自己開發的類別(尤其是資料類別)加上這個功能,只要我們實作 Comparable 介面 中的 compareTo() 方法。compareTo() 傳回值為返回負整數、零或正整數,代表此物件小於、等於或大於指定物件。也就是說返回正整數,將會排在前面;如果返回負整數,就會排在後面。
底下範例構造一個 Student 類別並實作 Comparable 介面,依據 GPA 分數高的排在前面,分數低的排在後面。並使用兩種容器 TreeSet 和 ArrayList 做排序。
輸出的結果您會發現 TreeSet 集合中少了一個學生「Kan」,為什麼會這樣呢?
因為 TreeSet 是一個排序的集合,但會依據排序所使用的比較值當作重不重複的判斷,在加入學生 John 之後,就有 GPA = 3.9 的值,所以當要再加入學生 Kan 時,因為分數相同(元素重複),故無法加入。
九、總結
Java 集合框架包含了許多的資料結構,因應不同的狀況,而使用不同的集合物件。
如果需要順序性的(依插入的順序),可以考慮使用實作 List 介面的類別。
如果需要收集不重複的元素,可以考慮使用實作 Set 介面的類別。
如果需要類似排隊的情況,可以考慮使用實作 Queue 介面的類別。
如果需要儲存映射對的資料,可以考慮使用實作 Map 介面的類別。
當然會有複合需求的時候,所以 Java 也有類別實作多種介面的特質,構造出需要多種需求組合的狀況。另外,有一些集合類別是專門要使用在多執行緒(多線程)上的。更多的觀念留在以後再說了!
沒有留言:
張貼留言