認識 Collection 架構

針對收集物件的需求，Java SE 提供了Collection API，而 Lambda 新特性的加入，對 Collection API 在運用時增添不少幫助，瞭解 Collection API，是瞭解 Lambda 應用時不錯的起點。

API 架構

Collection API 架構設計如下：

認識 Collection 架構

收集物件的行為，像是新增物件的 add 方法，移除物件的 remove 方法等，都是定義在 java.util.Collection。既然可以收集物件，也要能逐一取得物件，這就是 java.lang.Iterable 定義的行為，它定義了 iterator 方法傳回 java.util.Iterator 實作物件，可以讓你逐一取得收集之物件。

收集物件的共同行為定義在 Collection，然而收集物件會有不同的需求。如果希望收集時記錄每個物件的索引順序，並可依索引取回物件，這樣的行為定義在 java.util.List 介面。如果希望收集的物件不重複，具有集合的行為，由 java.util.Set 定義。如果希望收集物件時可以佇列方式，收集的物件加入至尾端，取得物件時可以從前端，可以使用 java.util.Queue。如果希望可以對Queue的兩端進行加入、移除等操作，則可以使用 java.util.Deque。

收集物件時，會依需求使用不同的介面實作物件，舉例來說，如果想收集時具有索引順序，實作方式之一就是使用陣列，而以陣列實作 List 的就是 java.util.ArrayList，如果查看 API 文件，會發現有以下繼承與實作架構：

認識 Collection 架構

Java SE API 不僅提供許多已實作類別，也考慮到自行擴充 API 的需求，以收集物件的基本行為來說，提供 java.util.AbstractCollection 實作了 Collection 基本行為，java.util.AbstractList 實作了 List 基本行為，必要時可以繼承 AbstractCollection 實作自己的 Collection，繼承 AbstractList 實作自己的 List，這會比直接實作 Collection 或 List 介面方便許多。

有時為了只表示我們感興趣的介面或類別，會簡化繼承與實作架構圖。例如：

認識 Collection 架構

這樣的表示方式，可以更清楚地明瞭哪些類別實作了哪個介面、繼承了哪個類別，或哪些介面又繼承自哪個介面，至於詳細的繼承與實作架構，可在 API 文件上查詢。

具有索引的 List

List 是一種 Collection，作用是收集物件，並以索引方式保留收集的物件順序，其實作類別之一是 java.util.ArrayList，其實作原理大致如〈定義與使用泛型〉的 ArrayList 範例。

例如可用 java.util.ArrayList 改寫〈final／Object／instanceof〉的 Guest 類別，而作用相同：

package cc.openhome;

import java.util.*;
import static java.lang.System.out;

public class Guest {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        collectNameTo(names);
        out.println("訪客名單：");
        printUpperCase(names);
    }

    static void collectNameTo(List<String> names) {
        Scanner scanner = new Scanner(System.in);
        String name;
        while(true) {
            out.print("訪客名稱：");
            name = scanner.nextLine();
            if(name.equals("quit")) {
                break;
            }
            names.add(name);
        }
    }

    static void printUpperCase(List<String> names) {
        for(int i = 0; i < names.size(); i++) {
            String name = names.get(i);
            out.println(name.toUpperCase());
        }        
    }
}

你可以查看API文件，可發現 List 介面定義了 add、remove、set 等許多依索引操作的方法。java.util.LinkedList 也實作了 List 介面，可以將上面的範例中 ArrayList 換為 LinkedList 而結果不變，什麼時候該用 ArrayList？何時該用 LinkedList 呢？

java.util.ArrayList 實作時，內部就是使用陣列來保存收集之物件，考慮是否使用 ArrayList，就等於考慮是否要使用到陣列的特性。

陣列在記憶體中會是連續的線性空間，根據索引隨機存取時速度快，如果操作上有這類需求時，像是排序，就可使用 ArrayList，可得到較好的速度表現。

陣列在記憶體中會是連續的線性空間，如果需要調整索引順序時，會有較差的表現。例如若在已收集 100 物件的 ArrayList，使用可指定索引的 add 方法，將物件新增到索引 0 位置，那麼原先索引 0 的物件必須調整至索引 1、索引 1 的物件必須調整至索引 2、索引 2 的物件必須調整至索引 3…依此類推，使用 ArrayList 做這類的操作並不經濟。

陣列的長度固定也是要考量的問題，在 ArrayList 內部陣列長度不夠時，會建立新陣列，並將舊陣列的參考指定給新陣列，這也是必需耗費時間與記憶體的操作，為此，ArrayList 有個可指定容量（Capacity）的建構式，如果大致知道將收集的物件範圍，事先建立足夠長度的內部陣列，可以節省以上所描述之成本。

LinkedList 在實作 List 介面時，採用了鏈結（Link）結構，若你不是很瞭解何謂鏈結，可參考底下的 SimpleLinkedList 範例：

package cc.openhome;

public class SimpleLinkedList<E> {
    private class Node {
        Node(E elem) {
            this.elem = elem;
        }
        E elem;
        Node next;
    }
    
    private Node first;

    public void add(E elem) {
        Node node = new Node(elem);        
        if(first == null) {
            first = node;
        }
        else {
            append(node);
        }
    }

    private void append(Node node) {
        Node last = first;
        while(last.next != null) {
            last = last.next;
        }
        last.next = node;
    }
    
    public int size() {
        int count = 0;
        Node last = first;
        while(last != null) {
            last = last.next;
            count++;
        }
        return count;
    }
    
    public E get(int index) {
        checkSize(index);
        return findElemOf(index);        
    }

    private void checkSize(int index) throws IndexOutOfBoundsException {
        int size = size();
        if(index >= size) {
            throw new IndexOutOfBoundsException(
                    String.format("Index: %d, Size: %d", index, size));
        }
    }

    private E findElemOf(int index) {
        int count = 0;
        Node last = first;
        while(count < index) {
            last = last.next;
            count++;
        }
        return last.elem;
    }
}

在 SimpleLinkedList 內部使用 Node 封裝新增的物件，每次 add 新增物件之後，將會形成以下的鏈狀結構：

認識 Collection 架構

每次 add 物件時，才會建立新的 Node 來保存物件，不會事先耗費記憶體，若呼叫 size，則從第一個物件，逐一參考下一個物件並計數，則可取得收集的物件長度。若想呼叫 get 指定索引取得物件，從第一個物件，逐一參考下一個物件並計數，則可取得指定索引之物件。

可以看出，想要指定索引隨機存取物件時，鏈結方式都得使用從第一個元素開始查找下一個元素的方式，會比較沒有效率，像排序就不適合使用鏈結實作的 List，想像一下，如果排序時，剛好必須將索引 0 與索引 10000 的元素調換，效率會不會好呢？

鏈結的每個元素會參考下一個元素，這有利於調整索引順序，例如，若在已收集 100 物件的 SimpleLinkedList，實作可指定索引的 add 方法，將物件新增到索引 0 位置，則概念上如下圖：

認識 Collection 架構

新增的物件將建立 Node 實例封裝，而 first（或上一節點的 next）重新參考至新建的 Node 物件，新建 Node 的 next 參考至下一 Node 物件。因此，若你收集的物件經常會有變動索引的情況，也許考慮鏈結方式實作的 List 會比較好，像是隨時會有客戶端登入或登出的客戶端 List，使用 LinkedList 會有比較好的效率。

內容不重複的 Set

同樣是收集物件，在收集過程中若有相同物件，則不再重複收集，若你有這類需求，可以使用 Set 介面的實作物件。例如，若有一個字串，當中有許多的英文單字，你希望知道不重複的單字有幾個，那麼可以如下撰寫程式：

package cc.openhome;

import java.util.*;

public class WordCount {
    public static void main(String[] args) {
        String line = input("請輸入英文：");
        Set<String> words = tokens(line);
        System.out.printf("不重複單字有 %d 個：%s%n",
                words.size(), words);
    }

    static String input(String prompt) {
        System.out.print(prompt);
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        return line;
    }
    
    static Set<String> tokens(String line) {
        String[] tokens = line.split(" ");
        Set<String> words = new HashSet<>();
        for(String token : tokens) {
            words.add(token);
        }
        return words;
    }
}

String 的 split 方法，可以指定切割字串的方式，在這邊指定以空白切割，split 會傳回 String[]，包括切割的每個字串，接著將 String[] 的每個字串加入 Set 的實作 HashSet 中，由於 Set 的特性是不重複，因此若有相同單字，則不會再重複加入，最後只要呼叫Set的size()方法，就可以知道收集的字串個數，HashSet 的 toString 實作，則會包括收集的字串。一個執行的範例如下：

請輸入英文：This is a dog that is a cat where is the student
不重複單字有 9 個：[that, cat, is, student, a, the, where, dog, This]

再來看以下的範例：

package cc.openhome;

import java.util.*;

class Student {
    private String name;
    private String number;
    Student(String name, String number) {
        this.name = name;
        this.number = number;
    }
    
    @Override
    public String toString()  {
        return String.format("(%s, %s)", name, number);
    }
}

public class Students {
    public static void main(String[] args) {
        Set<Student> set = new HashSet<>();
        set.add(new Student("Justin", "B835031"));
        set.add(new Student("Monica", "B835032"));
        set.add(new Student("Justin", "B835031"));
        System.out.println(set);
    }
}

程式中使用 Set 收集了 Student 物件，其中故意重複加入了相同的學生資料，然而在執行結果中看到，Set 並沒有將重複的學生資料排除：

[(Monica, B835032), (Justin, B835031), (Justin, B835031)]

這是理所當然的結果，因為你並沒有告訴 Set，什麼樣的 Student 實例才算是重複，以 HashSet 為例，會使用物件的 hashCode 與 equals 來判斷物件是否相同，HashSet 的實作概念是，在記憶體中開設空間，每個空間會有個雜湊編碼（Hash code）：

認識 Collection 架構

這些空間稱為雜湊桶（Hash bucket），如果物件要加入 HashSet，會呼叫物件的 hashCode 取得雜湊碼，並嘗試放入對應號碼的雜湊桶中，如果雜湊桶中沒物件，則直接放入，如上圖所示；如果雜湊桶中有物件呢？會再呼叫物件的 equals 進行比較：

認識 Collection 架構

如果同一個雜湊桶中已有物件，呼叫該物件 equals 與要加入的物件比較結果為 false，表示兩個物件非重複物件，可以收集，如果是 true，表示兩個物件是重複物件，則不予收集。

事實上不只有 HashSet，Java 許多場合要判斷物件是否重複時，都會呼叫 hashCode 與 equals 方法，因此規格書中建議，兩個方法必須同時實作。以先前範例而言，若實作了 hashCode 與 equals 方法，重複的 Student 將不會被收集：

package cc.openhome;

import java.util.*;

class Student {
    private String name;
    private String number;
    Student(String name, String number) {
        this.name = name;
        this.number = number;
    }

    @Override
    public int hashCode() {
        // Objects 有 hash 方法可以使用
        // 以下可以簡化為 return Objects.hash(name, number);
        int hash = 7;
        hash = 47 * hash + Objects.hashCode(this.name);
        hash = 47 * hash + Objects.hashCode(this.number);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Student other = (Student) obj;
        if (!Objects.equals(this.name, other.name)) {
            return false;
        }
        if (!Objects.equals(this.number, other.number)) {
            return false;
        }
        return true;
    }
    
    @Override
    public String toString()  {
        return String.format("(%s, %s)", name, number);
    }
}

public class Students {
    public static void main(String[] args) {
        Set<Student> set = new HashSet<>();
        set.add(new Student("Justin", "B835031"));
        set.add(new Student("Monica", "B835032"));
        set.add(new Student("Justin", "B835031"));
        System.out.println(set);
    }
}

在這邊定義學生的姓名與學號相同，表示為相同 Student 物件，hashCode 則直接利用 Objects 的 hashCode 再作運算。執行結果如下，可看出不再收集重複的 Student 物件：

[(Justin, B835031), (Monica, B835032)]

如果 Student 會作為純綷的資料載體，可以使用 record 來定義，編譯器能自動生成 hashCode、equals 以及 toString 等方法：

package cc.openhome;

import java.util.*;

record Student(String name, String number) {} 

public class Students {
    public static void main(String[] args) {
        var students = new HashSet();
        students.add(new Student("Justin", "B835031"));
        students.add(new Student("Monica", "B835032"));
        students.add(new Student("Justin", "B835031"));
        System.out.println(students);
    }
}

以上範例執行結果如下，可看出沒有重複的物件，也使用了預設的 toString 作為顯示之用：

[Student[name=Justin, number=B835031], Student[name=Monica, number=B835032]]

支援佇列操作的 Queue

如果希望收集物件時可以佇列方式，收集的物件加入至尾端，取得物件時可以從前端，則可以使用 Queue 介面的實作物件。Queue 繼承自 Collection，也具有 Collection 的 add、remove、element 等方法，然而 Queue 定義了自己的 offer、poll 與 peek 等方法，最主要的差別之一在於，add、remove、element 等方法操作失敗時會拋出例外，而 offer、poll 與 peek 等方法操作失敗時會傳回特定值。

如果物件有實作 Queue，並打算以佇列方式使用，且佇列長度受限，通常建議使用 offer、poll 與 peek 等方法。offer 方法用來在佇列後端加入物件，成功會傳回 true，失敗則傳回 false。poll 方法用來取出佇列前端物件，若佇列為空則傳回 null。peek 用來取得（但不取出）佇列前端物件，若佇列為空則傳回 null。

先前提過 LinkedList，它不僅實作了 List 介面，也實作了 Queue 的行為，可將 LinkedList 當作佇列來使用。例如：

package cc.openhome;

import java.util.*;

interface Request {
    void execute();
}

public class RequestQueue {

    public static void main(String[] args) {
        Queue<Request> requests = new LinkedList<>();
        offerRequestTo(requests);
        process(requests);
    }

    static void offerRequestTo(Queue<Request> requests) {
        // 模擬將請求加入佇列
        for (int i = 1; i < 6; i++) {
            requests.offer(
                    () -> System.out.printf("處理資料 %f%n", Math.random())
            );
        }
    }
    // 處理佇列中的請求
    static void process(Queue<Request> requests) {
        while(requests.peek() != null) {
            Request request = requests.poll();
            request.execute();
        }
    }
}

一個執行結果如下：

處理資料 0.302919
處理資料 0.616828
處理資料 0.589967
處理資料 0.475854
處理資料 0.274380

經常地，你也會想對佇列的前端與尾端進行操作，在前端加入物件與取出物件，在尾端加入物件與取出物件，Queue 的子介面 Deque 就定義了這類行為，Deque 定義 addFirst、removeFirst、getFirst、addLast、removeLast、getLast 等方法，操作失敗時會拋出例外，而 offerFirst、pollFirst、peekFirst、offerLast、pollLast、peekLast 等方法，操作失敗時會傳回特定值。

Queue 的行為與 Deque 的行為有所重複，有幾個操作是等義的：

`Queue` 方法	`Deque` 等義方法
`add`	`addLast`
`offer`	`offerLast`
`remove`	`removeFirst`
`poll`	`pollFirst`
`element`	`getFirst`
`peek`	`peekFirst`

java.util.ArrayDeque 實作了 Deque 介面，以下範例是使用 ArrayDeque 來實作容量有限的堆疊：

package cc.openhome;

import java.util.*;
import static java.lang.System.out;

public class Stack<E> {
    private Deque<E> deque = new ArrayDeque<>();
    private int capacity;
    
    public Stack(int capacity) {
        this.capacity = capacity;
    }
    
    public boolean push(E elem) {
        if(isFull()) {
            return false;
        }
        return deque.offerLast(elem);
    }

    private boolean isFull() {
        return deque.size() + 1 > capacity;
    }
    
    public E pop() {
        return deque.pollLast();
    }
    
    public E peek() {
        return deque.peekLast();
    }
    
    public int size() {
        return deque.size();
    }
    
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>(5);
        stack.push("Justin");
        stack.push("Monica");
        stack.push("Irene");
        out.println(stack.pop());
        out.println(stack.pop());
        out.println(stack.pop());
    }
}

堆疊結構是先進後出，執行結果最後才顯示 Justin：

Irene
Monica
Justin