教學目標

初步了解 Java 程式語言中集合框架之演算法的基本概念與應用。

重點概念

在 Java 平台中提供以 Collections 框架為基礎的演算法功能，所謂 Collections 框架又稱為容器是指多個元素組合成單一物件，主要應用於儲存、檢索、操作和溝通聚合資料。一般來說在 Java 平台中清單元素皆會搭配 Collections 框架進行演算法的實作，其中演算法可以分為六大類:

1. 排序
2. 洗牌
3. 搜尋
4. 組成
5. 例行性資料操作
6. 尋找最大最小值

首先排序演算法主要是重新排列清單，使得清單中的元素根據排序關係按遞增排序，排序操作，主要是使用 Collections 框架中的 sort 方法，其中排序方式為優化之後的合併排序演算法 (TimSort)，具有快速且穩定的特性，所謂快速是指保證在 nlog(n) 的時間內執行完成。所謂穩定是指不重新排列相等的元素，相等的元素排序之後會維持原先的先後順序。接著與排序相反的操作則是洗牌，洗牌演算法主要是破壞清單中可能存在的任何追蹤軌跡，一般來說其是基於隨機來源的輸入元素重新排列清單，主要是使用 Collections 框架中的 shuffle 方法應用於產生測試範例。

再來搜尋演算法主要在已排序的清單中搜尋指定的元素，主要是使用 Collections 框架中的 binarySearch 方法，其中搜尋方式為以二元搜尋演算法。若清單中包含該搜尋的值，則返回其索引，若不存在，則返回值為 (-1 × 插入點-1)，其中插入點是指值將新增至清單中的位置。

此外 Collections 框架中提供 frequency 方法了解清單組成的元素頻率，更進一步針對例行性資料操作提供演算法實作的方法，主要可以分為五種類型資料操作的方法，分別為:

1. 反向(reverse): 反轉清單中所有元素的順序。
2. 填充(fill): 覆蓋清單中具有指定值的每個元素。
3. 複製(copy): 將來源清單複製至目的清單。
4. 交換(swap): 交換清單中指定的元素位置。
5. 加入全部(addAll): 將所有指定的元素新增至清單中。

最後 Collections 框架針對尋找最大最小值則提供最小值和最大值的演算法，以利取得最大和最小的元素，此外我們亦可以透過實作 Comparator 介面解決特殊情境應用的排序方式。

範例程式碼

檔案名稱

ATM.java

情境說明

在現實生活中我們透過 ATM 進行轉帳作業時會需要點選轉帳帳戶所屬的銀行代碼，此時畫面就需要顯示銀行代碼清單，並且為了讓使用者方便點選，將會進行排序處理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
public class ATM {
   public static void main(String[] args) {
      String[] banks = {"004臺灣銀行"
          ,"008華南銀行"
          ,"005土地銀行"
          ,"006合庫商銀"
          ,"021花旗銀行"
          ,"009彰化銀行"
          ,"011上海銀行"
          ,"012台北富邦"
          ,"007第一銀行"
          ,"013國泰世華"
          ,"017兆豐商銀"};
      List<String> list = Arrays.asList(banks);
      Collections.sort(list);
      System.out.println("自動提款機畫面上顯示銀行代碼:\n" + list );
   }
}

執行結果

1
2

自動提款機畫面上顯示銀行代碼:
[004臺灣銀行, 005土地銀行, 006合庫商銀, 007第一銀行, 008華南銀行, 009彰化銀行, 011上海銀行, 012台北富邦, 013國泰世華, 017兆豐商銀, 021花旗銀行]

相關資源

• Lesson: Introduction to Collections
  https://docs.oracle.com/javase/tutorial/collections/intro/index.html
• Lesson: Algorithms
  https://docs.oracle.com/javase/tutorial/collections/algorithms/index.html#rdm
• Object Ordering
  https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html
• Class Collections
  https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html
• Optimistic sorting and information theoretic complexity
  http://dl.acm.org/citation.cfm?id=313859&dl=ACM&coll=DL&CFID=942481326&CFTOKEN=69887384

教學目標

初步了解 Java 程式語言中集合框架之資料結構的基本概念。

重點概念

在現實社會中我們永遠不會知道未來有多少相同類型的物件，也無法準確的知道物件的類型，為了解決上述問題，Java 程式語言則提供集合框架，又稱容器。主要常用的集和介面則為 List 、 Set 和 Map，並且根據不同的應用情境選擇適合的資料結構。

首先 List 主要有兩種資料結構進行實作，分別為:

1. ArrayList: 主要以陣列資料結構為主的序列，任何選取的元素皆可以在常數時間內容完成隨機的存取，此外其具有擴充機制，若沒有初始化長度則預設為 10，並且當增加元素超過原始容量時，則新容量為原始容量×3/2+1。
2. LinkedList: 主要以串列資料結構為主的序列，任何選取的元素皆需在串列上進行，若元素愈接近串列最後位置，則花費時間愈久。

接著 Set 主要有三種資料結構進行實作，分別為:

1. HashSet: 主要是將元素儲存至雜湊表中，效能最佳，但是對於迭代的順序無法確保。此外 HashSet 的雜湊值主要是由元素的值計算，且因為雜湊值會碰撞所以兩個物件可能會有相同的雜湊值，此時就會透過 equals() 方法判斷物件是否相等。
2. LinkedHashSet: 主要是將的元素儲存至鏈接的雜湊表中，效能良好，但是會根據被插入集合的順序確保迭代的順序。
3. TreeSet: 主要是將元素儲存至紅黑樹中，效能中等，但是對於元素的值會進行排序，若需要使用元素的值進行排序請採用 TreeSet，此外 TreeSet 可以搭配 Comparator 自定義針對值進行排序。

再來 Map 主要有三種資料結構進行實作，分別為:

1. HashMap: 主要是將元素中的索引 (Key) 和值 (Value) 儲存至雜湊表中，效能最佳，但是對於迭代的順序無法確保。接著 HashMap 基於雜湊的原理使用 put(key, value) 方法儲存物件至 HashMap 中，此時會介面先透過 hashCode() 方法取得雜湊值 ((h = key.hashCode()) ^ (h >>> 16))，以利計算 index 值找到正確 Bucket 位置儲存物件，物件內容包括索引和值，若當不同物件有相同雜湊值時則發生碰撞，此時會以Bucket 接串列的形式進行儲存，以及當串列的數量大於 TREEIFY_THRESHOLD 值 (預設為 8) 時就會將串列轉為紅黑樹，接著使用 get(key) 從 HashMap 中取得物件，但若是因為雜湊值相同則發生碰撞時，則會再透過 keys.equals() 方法從串列中找出正確的節點，因此物件內容必須包括索引和值才能夠進行比對索引。再來在 HashMap 有兩個重要的參數，分別為容量 (預設為 16 ) 和負載因子 (預設為 0.75)，所謂容量是指 Bucket 的大小，而負載因子則是 Bucket 允許填滿的最大程度，當 Bucket 中的物件數大於容量×負載因子時就會擴增兩位 Bucket 大小，此時還會執行 resize() 方法重新調整 Map 的大小，並且將原來的物件儲存至新的 Bucket 中的過程會執行 transfer() 方法，主要會將儲存在串列中的元素順序相反，直接將元素放在首位，為了避免 Tail Traversing 導致條件競爭發生造成死結。
2. LinkedHashMap: 主要是將的元素中的索引 (Key) 和值 (Value) 儲存至鏈接的雜湊表中，效能良好，但是會根據被插入集合的順序確保迭代的順序。
3. TreeMap: 主要是將元素儲存至紅黑樹中，效能中等，但是對於元素的值會進行排序，若需要使用元素的索引進行排序請採用 TreeMap，此外 TreeMap 可以搭配 Comparator 自定義針對索引進行排序。

最後要如何選擇適當集合介面搭配資料結構呢? 一開始最好的方式則是先以 ArrayList 為主，接著當發現效能問題的原因為在 List 中進行過多的插入和移除動作時，才使用 LinkedList，此外當時常進行隨機存取的方法 get() 和 set() 時則是 ArrayList 優於 LinkedList。接著 HashSet 效能優於 TreeSet ，尤其是插入和搜尋，除非需要維持元素的排序狀態，否則請採用 HashSet 即可。再來 HashMap 被設計應用於快速搜尋，其效能優於 TreeMap，除非需要維持元素索引的排序狀態，否則請採用 HashMap 即可，此外 HashMap 的實作主要使用雜湊表搭配陣列和串列的方式進行實作，若不當 hashCode() 方法不當使用則會被當成 LinkedList 使用。當然我們也可以參考不同資料結構的複雜度針對不同應用情境進行最適當的選擇。

相關資源

• Lesson: Introduction to Collections
  https://docs.oracle.com/javase/tutorial/collections/implementations/index.html

教學目標

初步了解 Java 程式語言中集合框架的基本概念。

重點概念

我們都曾聽過資料結構和演算法是程式語言的基礎，但是在 Java 程式語言是否有針對資料結構和演算法優化的框架能夠針對不同情境進行解決方案的應用呢? 事實上在 Java 程式語言中有提供 Collections 框架應用於表示和操作集合的架構，透過 Collections 框架就能夠讓程式設計師根據不同情境應用適當的資料結構和演算法之解決方案，Collections 框架主要包括三個部分，分別為:

1. 介面: 主要是表示集合的抽像資料類型，透過介面能夠使得集合獨立於不同表示集合的細節而被進行資料操作的應用。
2. 實作: 主要是專注於集合介面的實作，實作之後皆是可重用的資料結構。
3. 演算法: 主要是針對實作集合介面的物件進行實用的演算法。

首先 Collections 框架中核心的集合介面主要分為兩大類，第一類是以 Collection 類別為基礎的介面，第二類是以 Map 類別為基礎的介面，其中第一類主要有四種介面，分別為:

1. List: 可包含重複元素，並且有順序的集合。
2. Set: 不包含重複元素的集合。
3. Queue: 被使用於之前保存多個元素，會以先進先出 (FIFO) 的方式排序元素的集合。
4. Deque: 被使用於之前保存多個元素，會以先進先出 (FIFO) 或後進先出 (LIFO) 的方式排序元素的集合。

第二類則主要是以 Map 介面為主，主要是將索引值 (Key) 對應至值 (Value) 的集合，其中索引值不能重複，此外 Sort 和 Map 介面的集合是不進行排序，因此 Java 程式語言針對 Sort 和 Map 介面的集合提供 SortedSet 和 SortedMap 的介面進行元素和索引值的排序應用。

總結採用 Collections 框架主要有二大優點，分別為:

1. 減少程式開發的負擔，同時增加程式品質和效能: 透過 Collections 框架所提供實用的資料結構和演算法，同時實用的資料結構和演算法皆是以高品質與高效能的方式進行實作，同時每個介面的各種資料結構和演算法實作是可以互相切換。因此我們可以針對不同情境的問題立即轉換程式中的資料結構與演算法以利程式設計師更進一步改進程式的品質和效能。
2. 減少學習與設計新 API 的負擔，同時允許不相關的 API 之間進行協同合作: 透過 Collections 框架所提供標準介面的集合操作，就能夠減少程式設計師學習與設計新 API 所造成的負擔，同時集合所提供的資料結構與演算法是可以重複使用。

相關資源

• Lesson: Introduction to Collections
  https://docs.oracle.com/javase/tutorial/collections/intro/index.html

教學目標

初步了解 Java 程式語言中物件導向中類別、繼承、介面和套件的基本概念與應用。

重點概念

Java 程式語言中物件導向的基本概念主要包括物件、類別、繼承、介面和套件。所謂類別是一個軟體建構主要定義狀態和行為，它本身並不是一個物件，類別就像是一個藍圖，主要定義當物件從類別宣告的規範中建立物件的狀態和行為，透過實體化物件所定義的類別以取得具體的物件。因此我們可以從一個類別定義中實體化許多物件。若對應至現實生活中，則我們經常會發現許多單獨的物件都是一樣的。

然而不同種類的物件通常具有一定共同之處，此時若透過物件導向為主的程式設計則允許類別從其它類別繼承常用的狀態和行為，所有類別物件皆會繼承 Object 類別，此外在 Java 程式語言中一個類別只能繼承單一類別，也就是單一繼承模型。若我們要繼承多個類別時，則只能透過實作介面的方式解決，因為多重繼承會為程式設計師的混亂和膨脹，此時 Java 程式語言中透過介面以更優雅的方式解決問題。在 Java 程式語言中只是針對物件宣告將會實作的方法規範，並不包括實體變數或實體方式，只會以常數和方法宣告的方式實作，簡單來說物件透過公開的方法定義與外部溝通的方式，此時方法就是物件與外部溝通的介面。

範例程式碼

檔案名稱

MRT.java

情境說明

在現實生活中台北捷運站每一站皆有自動提款機，此時我們就能用 Java 物件導向的概念進行初步實作在台北捷運站中啟動和關閉自動提款機。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.lang.*;
public class MRT {
   public static void main(String[] argv) {
      ATM atm1 = new ATM();
      ATM atm2 = new ATM();
      atm1.on();
      atm2.on();
      atm1.off();
      atm2.off();
   }
}
interface Machine {
   void on();
   void off();
}
class ATM extends Object implements Machine{
   private String bank = "國泰世華銀行";
   public void on() {
      System.out.println(bank + "的自動提款機啟動。");
   }
   public void off() {
      System.out.println(bank + "的自動提款機停止。");
   }
}

執行結果

1
2
3
4

國泰世華銀行的自動提款機啟動。
國泰世華銀行的自動提款機啟動。
國泰世華銀行的自動提款機停止。
國泰世華銀行的自動提款機停止。

此外在 Java 程式語言中宣告一個類別、方法和資料時，則可以設定四種等級的存取方式，分別為公開、保護、私有和友好，首先公開為可以隨時隨地的使用，接著保護為只能在該類別和繼承類別中存取，再來私有為只能在該類別中存取，至於友好則是沒有指定存取等級，則代表在同一個套件中所有的物件皆可存取。

最後在 Java 程式語言中的套件則是指命名空間，其主要是組織一組相關的類別和介面，概念上有點類似資料夾，由於在 Java 程式語言開發軟體的過程中主要是由數百或數千個單獨的類別所組成，所以透過將相關的類別和介面打包為套件是有意義的一件事，當然在 Java 平台中也提供龐大的類別庫，這種類別庫被稱為 API，其代表通用開發最相關的任務，例如: String 物件包括字串的狀態和行為，File 物件允許程式設計師輕鬆地建立，刪除，檢查，比較或修改文件，…，等，因此對於程式設計師來說主要專注於特定應用程式的設計，而不是針對工作所需的基礎架構進行設計。總結與其說 Java 是個程式語言，還不如說 Java 是個平台更為適當。

相關資源

• The Java Language Environment
  http://www.oracle.com/technetwork/java/object-142541.html
• Lesson: Object-Oriented Programming Concepts
  https://docs.oracle.com/javase/tutorial/java/concepts/index.html
• Java™ Platform, Standard Edition 8 API Specification
  https://docs.oracle.com/javase/8/docs/api/index.html

教學目標

初步了解 Java 程式語言中物件導向中物件的基本概念。

重點概念

Java 程式語言中物件導向的基本概念主要包括物件、類別、繼承、介面和套件。所謂物件通常被使用於建立現實生活中的物件，現實生活中的物件皆有兩個特性，分別為狀態和行為。此時軟體物件概念類似於現實生活中的物件，主要會透過方法公開其行為，以及透過方法針對物件中的狀態進行操作，其中會儲存狀態的資料，同時物件導向的應用非常適合分散式客戶端與伺服器的軟體需求。

接著將程式碼以物件導向的方式實作時則有下述四大好處:

1. 模組化: 物件彼此之間的程式碼可以獨立撰寫和維護，同時物件一旦建立之後，物件就能很容易地傳遞至系統內部。
2. 資訊隱藏: 透過物件的方法進行互動，此時物件內部的細節資訊將會被隱藏起來。
3. 程式碼重用: 若物件已經存在時，則可以直接在程式中使用該物件。
4. 容易除錯: 若特定的物件若存在問題，則可以直接將該物件從應用程序中刪除，以其它物件進行更換。

然而要如何進行實作，此時我們就必須了解物件導向程式語言的四大特性:

1. 封裝: 實現模組化和資訊隱藏。
2. 多態: 相同的訊息會傳送至不同物件中時會根據訊息和物件的特性導致不同的行動。
3. 繼承: 根據現有的類別定義新的類別和行為，以利重用和組織程式碼。
4. 動態綁定: 物件可以來自於任何地方，當撰寫程式碼時只需要將訊息傳送到物件，此時對於程式執行時提供最大的靈活性。

總結物件技術主要是分析、設計和程式設計方法的集合，其設計專注於針對現實生活中物件的狀態和行為進行建模。例如: 當我們透過 ATM 自動提款機進行提款時，則就會有 ATM 自動提款機的物件建模，一台自動提款機會有狀態 (現金) 和行為 (提款)。

相關資源

• The Java Language Environment
  http://www.oracle.com/technetwork/java/object-142541.html
• Lesson: Object-Oriented Programming Concepts
  https://docs.oracle.com/javase/tutorial/java/concepts/index.html