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 有 HashSet、TreeSet 以及 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，不過這邊挑比較常用的 HashMap、TreeMap、EnumMap 來說明，以下就分別介紹其使用方式：

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. ashokayang2009年4月26日 上午8:34

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

    回覆刪除
  2. Lazy.Jay2012年1月10日 上午11:48

    超棒

    回覆刪除
  3. Unknown2013年2月8日 下午4:54

    讚！！您寫的真好，對我這新手來說，無疑是天降甘霖。

    回覆刪除
  4. 匿名2014年4月10日 下午3:35

    This is a great tutorial!!! Thank you very much!

    回覆刪除
  5. 匿名2016年9月23日 凌晨4:49

    非常有用，感谢博主。

    回覆刪除
  6. 匿名2016年12月3日 晚上9:06

    寫的超好的~可以引用您的例子做教學嗎?

    回覆刪除

訂閱： 張貼留言 (Atom)