Learning Objectives
- 說明為什麼需要集合，以及 List、Set、Map 三種介面的差別
- 用 ArrayList 新增、讀取、修改、刪除元素，分辨 remove(int) 與 remove(Object)
- 用 HashSet、TreeSet 去除重複，用 HashMap 計數、查詢與走訪
- 依需求選用 HashMap、TreeMap、LinkedHashMap，並說明 HashMap 不保證順序
- 寫出 List<Integer> 這類泛型型別，並在走訪時用 Iterator.remove 或 removeIf 安全地移除元素
為什麼需要集合
第 06 課的陣列有一個限制：長度在建立時就固定了。如果你要記錄購物車裡的商品，事先不知道使用者會買幾樣； 陣列開太小會放不下，開太大又浪費，刪掉中間的元素還得自己把後面的往前搬。
Java 的集合框架（Collections Framework）在 java.util 套件裡提供了一整套現成的資料結構，會自動變大變小，常用操作都寫好了。
它們依用途分成三大類，每一類是一個介面（第 11 課），底下有幾種實作：
| 介面 | 特性 | 常用實作 | 生活例子 |
|---|---|---|---|
List |
有順序、可以重複、用索引存取 | ArrayList、LinkedList |
待辦清單、排隊名單 |
Set |
不放重複的元素 | HashSet、TreeSet、LinkedHashSet |
已選修的課程代碼、標籤 |
Map |
鍵（key）對應到值（value），鍵不重複 | HashMap、TreeMap、LinkedHashMap |
學號對應姓名、商品對應價格 |
List 和 Set 都繼承自 Collection 介面（一群元素）；Map 存的是「一對一對」的資料，自成一個介面，不屬於 Collection。
使用前要 import，例如 import java.util.ArrayList;、import java.util.List;（或用 import java.util.*; 一次匯入整個套件）。
角括號：告訴集合要裝什麼
建立集合時，要用角括號寫出它裝的元素型別，這叫做泛型（generics，第 14 課詳細介紹）：
List<String> names = new ArrayList<>(); // 裝 String 的串列
Map<String, Integer> price = new HashMap<>(); // 鍵是 String、值是 Integer
- 右邊的
<>可以留空，編譯器會依左邊推斷（俗稱「鑽石運算子」） - 變數的型別通常寫介面
List，右邊才寫實作ArrayList。之後想換成LinkedList，只要改右邊，其他程式都不用動（第 10 課的多型） - 寫了型別之後，放錯型別的元素會編譯錯誤，取出來也不必轉型
角括號裡只能放類別，不能放基本型別。 List<int> 無法編譯，要寫包裝類別（wrapper class）List<Integer>：
| 基本型別 | int |
double |
char |
boolean |
long |
|---|---|---|---|---|---|
| 包裝類別 | Integer |
Double |
Character |
Boolean |
Long |
不用擔心轉換：nums.add(5) 會自動把 int 包成 Integer（自動裝箱，autoboxing），int x = nums.get(0); 會自動拆回 int（自動拆箱）。
ArrayList 的基本操作
看右邊 ArrayList 的格子：每次 add 多一格；第 11 行 add(1, "回信") 插在中間，原本索引 1 以後的元素都往後移一格。字串的值直接顯示在格子裡。
remove 的陷阱、排序與不能修改的串列
ArrayList 常用方法：
| 方法 | 作用 |
|---|---|
add(e)／add(i, e) |
加到最後面／插在索引 i |
get(i)／set(i, e) |
讀取／替換索引 i 的元素 |
remove(i)／remove(obj) |
移除索引 i 的元素／移除第一個等於 obj 的元素 |
size()、isEmpty()、clear() |
個數、是否為空、清空 |
contains(obj)、indexOf(obj) |
是否包含、第一次出現的索引（找不到為 -1） |
remove 有兩個多載：remove(int index) 依索引移除，remove(Object o) 依值移除。List<String> 不會搞混，
但 List<Integer> 呼叫 nums.remove(1) 時，1 是 int，編譯器選的是 remove(int)，移除的是索引 1，不是值 1（第 10 課：多載看引數的型別）。
要依值移除，寫 nums.remove(Integer.valueOf(1))。
排序：Collections.sort(list) 由小到大排序（元素要能比較大小，第 11 課的 Comparable）。Collections 類別還有 reverse、max、min、frequency 等工具方法。
不能修改的串列：List.of(1, 2, 3)（Java 9 起）可以快速建立串列，但它不能修改，呼叫 add、remove、set 會拋出 UnsupportedOperationException。
需要修改時，把它複製成新的 ArrayList：new ArrayList<>(List.of(1, 2, 3))。
ArrayList 與 LinkedList：兩者都實作 List，用法幾乎一樣，差在內部結構。ArrayList 內部是陣列，get(i) 直接算出位置，很快；
但在前面插入或刪除時，後面的元素都要搬動。LinkedList 是一個接一個串起來的節點，在頭尾插入刪除很快，但 get(i) 要從頭一個一個數過去。
大多數情況用 ArrayList 就對了。
remove(int) 與 remove(Object)
串列一開始是 [30, 10, 20, 10]。第 9 行 remove(1) 移除的是索引 1（第一個 10）；第 11 行 remove(Integer.valueOf(10)) 移除的才是值為 10 的元素。
想一想：List
下面的程式會印出什麼？
import java.util.*;
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
list.remove(1);
list.remove(Integer.valueOf(1));
System.out.println(list);
}
}
下面的程式能不能編譯？
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<int> nums = new ArrayList<>();
nums.add(3);
System.out.println(nums);
}
}
下面的程式會怎樣？
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> week = List.of("一", "二", "三");
week.set(0, "日");
System.out.println(week);
}
}
Set：不重複的元素
Set 不放重複的元素：add 一個已經存在的元素，集合不會改變，add 回傳 false。它沒有索引，不能 get(i)，常用的是 add、remove、contains、size 與 for-each 走訪。
| 實作 | 走訪的順序 | 說明 |
|---|---|---|
HashSet |
不保證 | 用雜湊（hash）安排位置，contains 非常快 |
TreeSet |
由小到大排序 | 元素要能比較大小 |
LinkedHashSet |
加入的順序 | 去除重複，又保留原本的順序 |
HashSet 的「不保證順序」是指：元素的排列由雜湊值決定，跟加入的順序、大小都沒有關係，換一個 Java 版本也可能改變。
程式不應該依賴 HashSet、HashMap 走訪出來的順序；需要固定的順序時，改用 TreeSet 或 LinkedHashSet。
去除重複的標籤
同一組標籤分別加進三種 Set。重複的 "java"、"ai" 第二次加入時 add 回傳 false，三個集合都不會變大。最後比較 TreeSet（排序）與 LinkedHashSet（加入的順序）印出來的樣子。
Map：鍵與值
Map 存的是「鍵 → 值」的對應，像字典用單字查解釋。鍵不能重複，值可以重複。
| 方法 | 作用 |
|---|---|
put(k, v) |
放入一組；鍵已經存在時，用新的值覆蓋舊的值 |
get(k) |
取得鍵對應的值；鍵不存在時回傳 null |
getOrDefault(k, d) |
鍵不存在時回傳預設值 d |
containsKey(k)、remove(k)、size() |
是否有這個鍵、移除、組數 |
merge(k, 1, Integer::sum) |
鍵不存在就放 1，存在就把舊值加 1：計數的好幫手 |
keySet()、values()、entrySet() |
所有鍵、所有值、所有「鍵值對」 |
Integer::sum 是方法參照，意思是「用 Integer.sum(舊值, 1) 算出新值」，第 17 課會介紹。不用 merge 的寫法是
count.put(v, count.getOrDefault(v, 0) + 1);。
走訪 Map 最常用 entrySet()，每一個 Map.Entry 有 getKey() 與 getValue()：
for (Map.Entry<String, Integer> e : count.entrySet()) {
System.out.println(e.getKey() + "=" + e.getValue());
}
三種實作的差別和 Set 一樣：HashMap 不保證順序、TreeMap 依鍵排序、LinkedHashMap 保留放入的順序。
（小心：int x = map.get("沒有的鍵"); 會因為 null 無法拆箱成 int 而拋出 NullPointerException，不確定鍵在不在時用 getOrDefault。）
投票計數
右邊的 HashMap 以「鍵 = 值」表格顯示。迴圈每一圈用 merge 替一個飲料加 1 票，看表格裡的數字變化。第 13 行印出的順序是 HashMap 依雜湊安排的，不是投票順序，也不是排序結果。
想一想：Set 與 Map
下面的程式會印出什麼？
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<String> t = new TreeSet<>(List.of("b", "a", "c", "a"));
System.out.println(t.size() + " " + t);
}
}
下面的程式會印出什麼？
import java.util.*;
public class Main {
public static void main(String[] args) {
Map<String, Integer> m = new LinkedHashMap<>();
m.put("b", 1);
m.put("a", 2);
m.put("b", 3);
System.out.println(m);
}
}
下面的程式會印出什麼？
import java.util.*;
public class Main {
public static void main(String[] args) {
Map<String, Integer> stock = new TreeMap<>();
stock.put("pen", 5);
stock.merge("pen", 3, Integer::sum);
stock.merge("cup", 2, Integer::sum);
System.out.println(stock.getOrDefault("box", 0) + " " + stock);
}
}
要記錄「每位學生（學號）選了哪些課」，同一門課不能重複，而且印出時課程代碼要排好順序。哪個型別最合適？
走訪時移除元素
用 for-each 走訪串列時，不能直接呼叫串列的 remove 或 add。for-each 其實是靠一個 Iterator（走訪器）一格一格往前走，
串列在走訪途中被改變，Iterator 下一次取元素時會發現「串列被別人動過了」，拋出 ConcurrentModificationException。
（有時候剛好沒有拋出，例如移除的是倒數第二個元素，但那只是碰巧，結果也可能少檢查到元素。）
正確的做法有兩種：
Iterator<Integer> it = scores.iterator();
while (it.hasNext()) { // 還有下一個嗎？
int s = it.next(); // 取出下一個
if (s < 60) it.remove(); // 用 Iterator 自己的 remove，移除剛剛取出的那一個
}
scores.removeIf(s -> s < 60); // 更簡潔：移除所有符合條件的元素
s -> s < 60 是 Lambda 表示式，意思是「給我一個 s，回傳 s 是否小於 60」，第 17 課會詳細介紹。
安全地移除不及格的分數
第一段在 for-each 裡移除 45，下一圈取元素時拋出 ConcurrentModificationException，30 也沒有被檢查到。第二段改用 Iterator：next() 取出元素，it.remove() 移除它，走訪可以正常完成。
動手寫：統計單字出現次數
把一句英文拆成單字，用 TreeMap 統計每個單字出現幾次，依字母順序印出「單字=次數」；最後再印出有幾個不同的單字。
重點回顧
- 集合會自動調整大小；
List有順序可重複、Set不重複、Map存鍵值對且鍵不重複 - 角括號寫元素型別，只能放類別：
List<Integer>不能寫成List<int>；基本型別與包裝類別之間會自動裝箱、拆箱 ArrayList：add、get、set、remove、size、contains、indexOf；List<Integer>的remove(1)是移除索引 1，依值移除要寫remove(Integer.valueOf(1))Collections.sort排序；List.of建立的串列不能修改，要修改就複製成new ArrayList<>(…)HashSet／HashMap不保證順序，TreeSet／TreeMap自動排序，LinkedHashSet／LinkedHashMap保留加入的順序- Map 用
put（同鍵覆蓋）、get、getOrDefault、containsKey、merge計數，用entrySet()走訪 - 走訪時不要直接修改集合，否則會拋出
ConcurrentModificationException；改用Iterator.remove()或removeIf