2007年7月29日 星期日

Java 學習筆記 (7) - Container

在程式運作中,有時候會需要有地方可以暫時儲存產生出來的物件,我們稱之為 Container(容器)。

而根據目的的不同,在 container 的選擇上也有所不同,例如:
  • List:循序索引的串列結構
  • Set:不允許相同物件存在的集合結構
  • Map:使用 Key-Value(鍵-值) 方式儲存的結構

Collection

在 Java SE 中,Collection 包含了 List 以及 Set。

首先先認識一下 List ,其為 java.util.Collection interface 的 sub interface,而 Collection interface 則是擴充了 Iterable interface,因此其關係如下:
Iterable --> Colllection --> List
而在 J2 SE 5.0 之後,由於增加了 Generic 的功能,因此許多這一類的 Class 都使用 Generic 的功能重新改寫了,因此在查詢 API 時常常會發現 Generic 的使用。

而 List 的特性在於:每個 List 中的元素都是循序加入的,並可透過 index 來存取元素。

然而,List 可使用 Array(java.util.ArrayList) 或是 Linked List(java.util.LinkedList) 來進行實作。而每一種不同的資料結構,適用的情況也不同:
  • ArrayList:處理循序加入以及存取元素方面,效率較佳
  • Linked List:處理經常變動元素排列順序時,效率較佳

接著以下針對由 List 所衍生出來的 container 進行說明:

ArrayList
使用 Array 結構實作 List,而其特性為 index 的應用,因此對於快速取得隨機 object 上效率叫好,但在新增或刪除 object 上,速度就會比 Linked List 慢上許多。

以下使用範例介紹 ArrayList 的使用:
package net.twcic;

import java.util.*;

public class ArrayListDemo {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);

List<String> list = new ArrayList<String>();
System.out.println("輸入名稱(使用 quit 結束:)");

while(true) {
System.out.print("# ");
String input = scanner.next();
if(input.equals("quit"))
break;
list.add(input);
}

System.out.println("顯示輸入:");

//使用 List interface 中所提供的方法列出所有元素
for(int i = 0 ; i < list.size() ; i++)
System.out.print(list.get(i) + " ");
System.out.println();

//使用 for each 列出所有元素
for(String s : list)
System.out.print(s + " ");
System.out.println();

//使用 iterator 列出所有元素
Iterator iterator = list.iterator();
while(iterator.hasNext())
System.out.print(iterator.next() + " ");
System.out.println();
}
}
【註】ArrayList 較為適合用在不常新增刪除、且隨機存取元素的情況。

LinkedList

使用 Linked List 來實作 List,其特性是在新增修改元素,效率優於 ArrayList 很多,若有經常針對 container 中的元素進行新增刪除的需求時,LinkedList 是一個很好的選擇,因此常常被拿來實作於 stack(堆疊) 以及 queue(佇列) 上。

以下用範例程式碼,說明如何利用 LinkedList 實作 stack

StringStack.java
package net.twcic;

import java.util.LinkedList;

public class StringStack {

// 以下方法在 List interface 沒有提供
// 因此必須將型態宣告為 LinkedList
private LinkedList<String> linkedList;

public StringStack() {
linkedList = new LinkedList<String>();
}

public void push(String name) {
linkedList.addFirst(name);
}

public String top() {
return linkedList.getFirst();
}

public String pop() {
return linkedList.removeFirst();
}

public boolean isEmpty() {
return linkedList.isEmpty();
}
}
StringStackDemo.java
package net.twcic;

import java.util.Scanner;

public class StringStackDemo {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);

StringStack stack = new StringStack();
System.out.println("輸入名稱(使用 quit 結束):");

while(true) {
System.out.print("# ");
String input = scanner.next();
if(input.equals("quit"))
break;
stack.push(input);
}

System.out.print("顯示輸入:");
while(!stack.isEmpty())
System.out.print(stack.pop() + " "); //利用 pop將元素印出來
System.out.println();
}
}

以下用範例程式碼,說明如何利用 LinkedList 實作 queue

StringQueue.java
package net.twcic;

import java.util.LinkedList;

public class StringQueue {

// 以下方法在 List interface 沒有提供
// 因此必須將型態宣告為 LinkedList
private LinkedList<String> linkedList;

public StringQueue() {
linkedList = new LinkedList<String>();
}

public void put(String name) {
linkedList.addFirst(name);
}

public String get() {
return linkedList.removeLast();
}

public boolean isEmpty() {
return linkedList.isEmpty();
}
}
StringQueueDemo.java
package net.twcic;

import java.util.Scanner;

public class StringQueueDemo {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);

StringQueue queue = new StringQueue();

System.out.println("輸入名稱(使用 quit 結束):");
while(true) {
System.out.print("# ");
String input = scanner.next();

if(input.equals("quit"))
break;
queue.put(input);
}

while(!queue.isEmpty())
System.out.print(queue.get() + " "); //利用 get() 將元素印出
System.out.println();
}
}
其實,LinkedList class 也是有實作 java.util.Queue interface 啦;因此若要使用 Queue 的特性,倒也不用使用類似上面的方式,直接使用 polymorphism 的方式透過 Queue interface 去控制 LinkedList object 即可囉!


接著要介紹的是 Set,跟 List 相同為 java.util.Collection interface 的 sub interface,但在 Set 中,每個 object 都必須是唯一的,而排序的方式開發者則不需要操心,因為他有其自成一格的排序方式。而實作 Set 的 class 有 HashSetTreeSet 以及 EnumSet 三種,以下分別逐一介紹:

HashSet
其實作的方式,是利用 hash code 產生並規劃出多個 hash can,而 HashSet 則根據 hash code 來確定 object 是存在於哪一個 hash can 中,也可以根據 hash code 快速的找到特定的 object;而若要判斷 HashSet 中的兩個 object 是否相同,除了使用 hashCode() method 來確定傳回值是否相同,還要使用 equals() method 來比較兩 object 是否相同。

以下有個簡單範例,說明 HashSet 的使用方式:
package net.twcic;

import java.util.Iterator;
import java.util.Set;
import java.util.HashSet;

public class HashSetDemo {
public static void main(String args[]) {
Set<String> set = new HashSet<String>();

set.add("bad");
set.add("godleon");
set.add("good");
set.add("godleon"); //重複的元素,在 Set 中不會存兩份

// 請注意,實際上元素印出來的順序並非當初元素加入的順序
// 那是因為 Set 有自己一套的排序方式
Iterator iterator = set.iterator();
while(iterator.hasNext())
System.out.print(iterator.next() + " ");
System.out.println();

//也是可以利用 for each 的方式將元素印出
set.remove("good");
for(String s : set)
System.out.print(s + " ");
System.out.println();
}
}

TreeSet
TreeSet 不僅有實作了 Set interface,亦是唯一實作了 SortedSet interface 的 class,因此可針對 Set 中的元素進行排序,而其排序的方式是以 Red-black tree(紅黑樹) 的方式進行排序,詳細方法可參考以下兩篇文章:
以下有個簡單範例,說明 TreeSet 的使用方式:
package net.twcic;

import java.util.Set;
import java.util.TreeSet;

public class TreeSetDemo {
public static void main(String args[]) {
Set<String> set = new TreeSet<String>();

set.add("godleon");
set.add("good");
set.add("bad");

// 由於存入字串,因此元素會以字典的順序加以排序
// 若要修改排序方式,可實作 java.util.Comparator interface 後
// 在 new TreeSet 時當作其 Constructor 的參數帶入
for(String s : set)
System.out.print(s + " ");
System.out.println();
}
}
排序的方式預設是以紅黑樹的方式,當然也可以自訂囉! 只要透過實作 java.util.Comparator interface,並在 new TreeSet 時作為 constructor 的參數代入即可。

EnumSet
EnumSet 是一直到 J2SE 5.0 後才提供的 class,提供了許多 static method,協助建立 Set 中的元素,以下直接用範例來說明:
package net.twcic;

import java.util.EnumSet;

enum FontConstant { Plain, Bold, Italic };

public class EnumSetDemo {
public static void main(String args[]) {
// 建立 EnumSet 並設定其元素內容
EnumSet<FontConstant> enumSet = EnumSet.of(FontConstant.Plain, FontConstant.Bold);
//顯示 Set 中內容
showEnumSet(enumSet);
// 顯示 Set 中 Enumerate 的互補內容
showEnumSet(EnumSet.complementOf(enumSet));

// 建立空的 EnumSet 再一一加入元素
EnumSet<FontConstant> enumSetEmpty = EnumSet.noneOf(FontConstant.class);
enumSetEmpty.add(FontConstant.Bold);
enumSetEmpty.add(FontConstant.Italic);
showEnumSet(enumSetEmpty);
}

public static void showEnumSet(EnumSet<FontConstant> enumSet) {
for(FontConstant constant : enumSet)
System.out.print(constant + " ");
System.out.println();
}
}


Map

實作了 Map interface 的 container,儲存在裡面的 object 都會以 key-value 的方式存在,也就是說,存入每一個 object 後,都要給定一個唯一的 key,如此一來才可以用 key 去取得相對應的 object。

而在 J2SE 中,實作了 Map interface 的有許多 class,不過這邊挑比較常用的 HashMapTreeMapEnumMap 來說明,以下就分別介紹其使用方式:

HashMap
HashMap 在內部實作中使用了 hash,因此可以在很快的時間內搜尋到 key-value,以下給個例子:
package net.twcic;

import java.util.Map;
import java.util.HashMap;

public class HashMapDemo {
public static void main(String args[]) {
Map<String, String> map = new HashMap<String, String>();

// 宣告 key
String key1 = "leon";
String key2 = "godleon";

// 使用 put() 將資料存入 Map container 中
map.put(key1, "leon 的資料");
map.put(key2, "godleon 的資料");

// 使用 get() 將資料從 Map container 取出
System.out.println(map.get(key1));
System.out.println(map.get(key2));
}
}
另外,由於 Map interface 並沒有擴充 Collection interface 或是其 sub interface,加上本身並沒有定義用來取得全部 key-value 的 method。但若是要取得列出 Map container 中所有的 key-value,可透過 value() method 取得 Collection 來達到此目的,以下用範例程式碼來說明:
package net.twcic;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class HashMapDemo2 {
public static void main(String args[]) {
Map<String, String> map = new HashMap<String, String>();
map.put("leon", "leon 的資料");
map.put("godleon", "godleon 的資料");
map.put("bill", "bill 的資料");

// 透過 values() 取得 Collection
// 再由 Collection 變出 Iterator
// 最後由 Iterator 列出所有元素
Collection collection = map.values();
Iterator iterator = collection.iterator();
while(iterator.hasNext())
System.out.println(iterator.next());
System.out.println();

// 透過 for each 也是可以的
for(String s : map.values())
System.out.println(s);
System.out.println();
}
}

TreeMap
TreeMap 是唯一同時實作 java.util.Map interface 以及 java.util.SortedMap interface 的 class,跟 TreeSet 相同,也是利用紅黑樹的方式針對 container 中的元素進行排序,以下看一個簡單的例子:
package net.twcic;

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo {
public static void main(String args[]) {
Map<String, String> map = new TreeMap<String, String>();
map.put("godleon", "godleon 的資料");
map.put("leon", "leon 的資料");
map.put("bill", "bill 的資料");

for(String s : map.values())
System.out.println(s);
System.out.println();
}
}

EnumMap
EnumMap 則是專門為 Enumerated Type 與 Map 搭配所設計的 class,以下直接來個範例:
package net.twcic;

import java.util.Map;
import java.util.EnumMap;

public class EnumMapDemo {
// 內部定義的 Enumerated Type
private enum Action {TURN_LEFT, TURN_RIGHT, SHOOT};

public static void main(String args[]) {
// 加入的元素僅限於 Enumerated Type 中所限定的
Map<Action, String> map = new EnumMap<Action, String>(Action.class);
map.put(Action.TURN_LEFT, "向左轉");
map.put(Action.TURN_RIGHT, "向右轉");
map.put(Action.SHOOT, "射擊");

for(Action action : Action.values())
System.out.println(map.get(action));
}
}
【註】在 EnumMap 中元素的排序順序,是依照 Enumerated Type 中元素的順序所排序。

最後,開發者在撰寫程式時,選擇合適的 container,不論是在開發的便利上,或是在程式運作的效率上,相信都會很有幫助的!

6 則留言:

  1. 您的blog是我在搜尋data structure in java的時候找到的,寫得很詳細也很清楚.謝謝您無私的分享.

    回覆刪除
  2. 讚!!您寫的真好,對我這新手來說,無疑是天降甘霖。

    回覆刪除
  3. This is a great tutorial!!! Thank you very much!

    回覆刪除
  4. 非常有用,感谢博主。

    回覆刪除
  5. 寫的超好的~可以引用您的例子做教學嗎?

    回覆刪除