2018年12月3日 星期一

Java SE 入門教學 - 集合

更新時間:12/03/2018

前言

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 也有類別實作多種介面的特質,構造出需要多種需求組合的狀況。另外,有一些集合類別是專門要使用在多執行緒(多線程)上的。更多的觀念留在以後再說了!





沒有留言:

張貼留言