Java集合物件

  • 集合物件的概念

Java物集合物件,指的是一群相同形態的物件集合,集合物件中所存放的資料稱為元素(Elements)。依不同的資料結構與存取特性,而有許多不同的集合物件,有的允許重複資料存放,有的會對元件進行建立索引表。Java 針對不同類型的集合物件定義了一套集合介面,目的是讓所有的集合物件都具有一致性的存取操作方式,例如Collection、Map、List、Set…。 下圖為Java的集合介面的繼承關係圖:

圖 1Java集合元件類別繼承圖

由上圖可以發現Map並不是Collection的子介面,而是一個獨立的特別集合介面。所儲存的資料是組對應的元素,由Key與Value組成。在Map中的Values函式可將MAP中的Data轉換成Colloection物件傳回。

下表為Collection常用的函式

函式 回傳值 功能
add(Object o) boolean 加入元素進集合中,加入成功回傳true
addAll(Collection c) boolean 將Collection c中所有的元素加入集合中,加入成功回傳true
Clear() void 清除集合中的所有元素
contains(Object o) boolean 判斷指定的物件是否己被包含在集合物件中,若有則回傳true
containsAll(Collection c) boolean 判斷指定的Collection c中所有的元素是否皆被包含在集合中,若是則回傳true
isEmpty() boolean 判斷此集合是否為空的,若為空的回傳true
remove(Object o) boolean 從集合中移除指定的物件o
removeAll(Collection c) boolean 從集合中移除指定的Collection c中所有包含的元素
retainAll(Collection c) void 從集合中留下指定的Collection c元件,其餘的元素全部移除
size() int 傳回此集合所有的元素數量
iterator() Iterator 取得此集合的一個Iterator物件,可使用Iterator去尋集合中的元素
  • List介面

List實作了Collection介面,因此自然會包含所有Collection中的所有方法。List中的資料允許重覆,元素之間具有順序性,另外List的容量長度為可變動的。一般常用的List實作元件有Vector、LinkList、Vector。

下表為List常用的函式

函式 回傳值 功能
add(int index, E element) void 在index的位置中插入element元件
set(int index,E element) E 將index位置的元素換成element
addAll(int index ,Collection<? Extends E> c) boolean 從index的位置插入Collection中的所有元素,成功將回傳true
get(int index) E 從集合中取得指定索引位置的元素
remove (int index) E 移除指定index位置的元素
indexOf(Object o) int 搜尋集合中是否有與o相同的元素,若有則回傳第一個找到的索引位置,若找不到則回傳-1
lastIndexOf(Object o) int 搜尋集合中是否有與o相同的元素,若有則回傳最後一個找到的索引位置,若找不到則回傳-1
iterator() Iterator 取得集合物件尋訪器
listIterator() ListIterator 取得ListIterator<E> ,尋訪的位置從0開始
listIterator(int index) ListIterator 取得ListIterator<E>,尋訪的位置從指定的index開始
  • Vector、LinkList與ArrayList

Vectory與ArrayList在開發使用上相當的類似,其內部的資料存放都是採用Array來實作完成,因此隨機存取資料的效能很高。Vectory與ArrayList主要的不同處有二個:

    1. 在於Vector提供的函式皆為同步(Synchronized)的而且是執行緒安全的(Thread-Safe),而ArrayList則為非同步的,相對的也就是執行緒不安全的函式。所謂的同步存取代表的是當一個Thread在Put資料進Vectory的同時其它的Thread將無法進行Get資料的動作(會被Block住),然而同步資料存取將會影響到存取的效能,因此ArrayList的存取效能較Vectory好。若你的應用程式不會有多執行緒同時去對一個資料做存取的動作,那麼建議使用ArrayList可以帶來較高的存取效能。
    2. 另一個Vector與ArrayList處在於資料結構的增長方式,當你加入的元件數量超過Vectory或ArrayList的初始大小,Vectory會先行擴充自身一倍的容量,而ArrayList則只會廣充相對於自身的50%容量。因此ArrayList有利於節省記憶體儲存空間。

LinkList與ArrayList主要差異在所採用的資料儲存結構不同,其大致區別如下列三項:

    1. ArrayList使用Array儲存資料,LinkList使用LinkList資料結構
    2. 對於隨機存取get與put,ArrayList效能優於LinkList,因為LinkLit需要移動指標去尋訪每個元素。
    3. 對於新增與刪除操作add與remove,LinkList效能優於ArrayList,因為每次的插入或移除元素,ArrayList就必須重整Array,元素必須全部往上搬移以填補刪除的元素,或者全部往下搬移以空出空間插入元素。

【範例程式】

import java.util.ArrayList;

【運行結果】

實際應用上,若你使用的是ArrayList,只要盡量都從資料的最尾端去進行資料的add與remove的動作,就不會造成Array搬移重整的動作。相對的若採用的是LinkList則只需盡量的從資料的頂端做get與put的動作則可以省下資料尋訪的次數。因此兩者皆有所適合使用的場所,取決於應用程式的需求,一般而言Linklist大多應用在需要做Queue應用的地方,例如一個Client-Server應用程式,每個要求建立連線的Client物件可將其先串在LinkLikst的底端,Server應用程式不斷的從LinkList的頂端去取出目前待建立連線的Client物件。像這類的應用使用LinkList的效能將會大於ArrayList。

  • HashSet元件應用

HashSet繼承了AbstractSet並且同時實作了Set介面,而Set介面中所存放的元素是不具有順序性的,每個元素存放的位置根據資料的hashCode而定,同時不允許放置相同的資料。因此Set具有資料唯一性但無順序性 。要放置於HashSet中的物件皆必須定義一個hashCode,因此HashSet在搜尋資料上具有相當高的效率,但由於每個存放資料的hashCode不見得會連號,因此相較於Array,HashSet在記憶體空間的利用率上比較差。

一般HashSet在實際應用上可以拿來做為快速資料過濾器,列如一個聊天室的內容過濾器,你可以利用HashSet將想要過濾掉的單子填入Set中,接著將收到的每個單字字串丟進Set判斷是否己存在,藉此可達到快速資料比對的功能。另外也可以利用HashSet資料不可重覆的特性,協助你過濾出互相交集的資料,例如現在有兩個Set,Set內存分別存放的是兩天的手機通聯號碼。若你想找出同時連續兩天你都有連絡過的朋友電號,那麼只要利用retainAll函式,將兩者之間相同的Set留下來,就可以取出交集的資料。另外若你想找出兩天之內只要有打過一次的電話通聯,那麼只要直接將兩個set資料相加,由於set的特性相同的資料只會留下一份,因此可以很方便的取得兩天的聯集內容並自動去除了重覆的部份。

【範例程式】

import java.util.HashSet;

【運行結果】

  • Map介面

Map本身並無繼承Collection集合介面,廣義的說Map為集合物件架構中的一部份,實作的類別分別有HashTable與HashMap。Map中利用Key鍵值來決定元素要存放的位置,Key不得重覆,每個Key只對應一個元素資料。元素資料可以重覆,可以使用不同的Key去對應多組重覆的資料。下表為Map中常用的函式:

函式 回傳值 功能
put(Object key,Object value) Object 將指定的Key Values物件放入到MAP中
putAll(Map t) void 複製Map t物件中所有的元素到Map中
get(Object key) Object 取得指定Key存放在Map中的元素物件
remove(Object key) Object 移除指定key的資料
values() Collection 將Map中的value資枓以Collection型態取出
size() int Map中目前存放的元素數量
clear() void 除非所有的元素
containsKey(Object key) boolean 判斷Map中是否有包含指定的key物件,若有則回傳true
containsValues(Object values) boolean 判斷Map中是否有包含指定Value的物件資料存在,若有則回傳true
entrySet() Set 將Map中的values資料部份以Set的型態傳回
isEmpty() boolean 判斷Map是否為空的
keyset() Set 將Map的keys部份以Set型態傳回
  • HashTable與HashMap 的差別

HashMap對資料的存取是非同步的(非執行緒安全),且可以允許放置null key與null value,反之Hashtable對資料存取是同步的,且不允許null。在多執行緒的應用程式上使用HashMap若有同時兩個thread對HashMap進行get與put動作,則系統有可能會發出concurrentModificationException例外,此外還有可能會讓你的程式進入deadlock。為避免上述的狀況,在多執行緒情況下應用HashMap建立改用ConcurrentHashMap類別。ConcurrentHashMap可同時提供,同步與非同步資料存取(讀可以同時多個Trhead,但寫只能一次一個),同時又提供了Thread-safe的解決方案。下表為使用ConcurrentHashMap與使用Hashtable在多執行緒環境下的效能評比(數字愈小愈好):

Thread數量 ConcurrentHashMap Hashtable
1 1.00 1.03
2 2.59 32.40
4 5.58 78.23
8 13.21 163.48
16 27.58 341.21
32 57.27 778.41

【範例程式】

import java.io.BufferedReader;

【運行結果】

  • Collections(Collect的外包工具類別)

Collections提供了許多靜態函式,可供Collection集合物件做內部的資料處理。例如:資料排序、尋找最大與最小值。下表列出了幾個常用的函式:

static void sort(List<T> list) 排序
static int binarySearch(List< T> list, T key) 二分法搜尋
static void reverse(List<?> list) 反轉
static void shuffle(List<?> list,Random rnd) 打亂
static void swap(List<?> list,int i,int j) 交換
static <T> void fill(List<? super T> list, T obj) 填補
static <T> void copy(List<? super T> dest,List<? extends T> src) 複製
static <T> boolean replaceAll(List<T> list, T oldVal,T newVal) 取代
static > T min(Collection<? extends T> coll) 取最大值
static > T max(Collection<? extends T> coll) 取最小值