[Java] 集合框架

寫真實程式幾乎一定會用到集合。Java 集合框架（JCF）的關鍵不是「會用 ArrayList」，而是「面對需求挑對實作」——ArrayList vs LinkedList、HashMap vs TreeMap、何時該用 ArrayDeque 取代 Stack。這篇把整個階層、慣用法、選型都串完。

整體架構

Java Collections Framework 在 java.util 下，主要介面與關係如下：

宣告時用介面、實例化時用具體類別：

List<String> names = new ArrayList<>();
Set<Integer> ids = new HashSet<>();
Map<String, Integer> counts = new HashMap<>();

List

ArrayList（最常用）

底層陣列。隨機存取 O(1)，尾端 add O(1) 攤銷，中間插入刪除 O(n)。

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add(1, "c");        // 在 index 1 插入
list.get(0);             // "a"
list.set(0, "z");        // 取代
list.remove(0);          // 移除 index
list.remove("b");        // 移除值
list.size();
list.contains("z");
list.indexOf("z");
list.isEmpty();

LinkedList

雙向鏈結。頭尾 add/remove O(1)，隨機存取 O(n)。一般 List 可先選 ArrayList；單純的 queue／stack 通常也可先考慮 ArrayDeque。LinkedList 的優勢要連同走訪方式評估，不能只看到「插入 O(1)」就忽略找位置的成本。

走訪

for (String s : list) { ... }                  // for-each
for (int i = 0; i < list.size(); i++) { ... }  // 傳統
list.forEach(s -> System.out.println(s));      // lambda

對 LinkedList 反覆用 get(i) 走訪，整輪可能變成 O(n²)；for-each／iterator 不需要每次從頭找位置。

Set

HashSet

雜湊表，O(1) 平均，無序：

Set<Integer> s = new HashSet<>();
s.add(1); s.add(2); s.add(1);
s.size();        // 2
s.contains(1);   // true

LinkedHashSet

保留插入順序。比 HashSet 略慢，但走訪順序可預測。

TreeSet

紅黑樹，自動排序（自然順序或自訂 Comparator）。O(log n)：

TreeSet<Integer> t = new TreeSet<>();
t.add(3); t.add(1); t.add(2);
t.first();    // 1
t.last();     // 3

HashSet／LinkedHashSet 的相等規則

否則兩個內容相同的物件會被當成不同東西：

record Point(int x, int y) {}     // record 自動實作 equals/hashCode
Set<Point> set = new HashSet<>();
set.add(new Point(1, 2));
set.contains(new Point(1, 2));    // ✅ true

非 record 的 class 要手動實作（或用 IDE 產生）。

TreeSet 則依 compareTo／Comparator 的結果判斷兩個元素是否相同，回傳 0 就視為同一個元素；排序規則應與 equals 一致，才符合 Set 的一般契約。

Map

HashMap

Map<String, Integer> m = new HashMap<>();
m.put("a", 1);
m.put("b", 2);
m.get("a");            // 1
m.getOrDefault("z", 0);// 0
m.containsKey("a");
m.remove("a");
m.size();

// 走訪
for (Map.Entry<String, Integer> e : m.entrySet()) {
    System.out.println(e.getKey() + "=" + e.getValue());
}
m.forEach((k, v) -> System.out.println(k + "=" + v));

LinkedHashMap

預設保留插入順序。若用來實作 LRU cache，通常要用 accessOrder=true 的建構方式，並另外處理容量與淘汰；單純換成 LinkedHashMap 還不會自動變成 LRU。

TreeMap

按 key 排序，O(log n)：

TreeMap<String, Integer> t = new TreeMap<>();
t.put("b", 1); t.put("a", 2);
t.firstKey();   // "a"

計數慣用法

Map<String, Integer> count = new HashMap<>();
for (String w : words) {
    count.merge(w, 1, Integer::sum);
}

merge(key, value, remap)：key 不存在或目前對應 null 時放入 value；已有非 null 值才呼叫 remap 合併。若 remap 回傳 null，該 key 會被移除。

computeIfAbsent

群組分類常用：

record Item(String category, int value) {}
List<Item> data = List.of(
    new Item("A", 1),
    new Item("B", 2),
    new Item("A", 3)
);

Map<String, List<Integer>> groups = new HashMap<>();
data.forEach(d ->
    groups.computeIfAbsent(d.category(), k -> new ArrayList<>()).add(d.value())
);

Queue / Deque

ArrayDeque：當 stack 或 queue 都好用

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
stack.pop();        // 2

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
queue.poll();       // 1

一般單執行緒 stack／queue 可先選 ArrayDeque，避免沿用歷史較久的 Stack。ArrayDeque 不接受 null，也不是執行緒安全的容器；多執行緒需求要另選並行容器或同步方式。

PriorityQueue

最小堆，poll 取最小：

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3); pq.offer(1); pq.offer(2);
pq.poll();    // 1

// 自訂比較：最大堆
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());

優先順序保證的是 peek／poll 的頭部元素，並不保證 iterator 或直接印出的整個佇列已排序。

不可修改的集合（Java 9+）

List<Integer> nums = List.of(1, 2, 3);
Set<String> tags = Set.of("a", "b");
Map<String, Integer> m = Map.of("a", 1, "b", 2);
Map<String, Integer> big = Map.ofEntries(
    Map.entry("a", 1),
    Map.entry("b", 2)
);

這些 factory 產生的集合不能 add／put，否則會丟 UnsupportedOperationException；也不接受 null。這是集合結構不可修改，不代表元素本身深度不可變，不能因此就宣稱任何內容都能安全地跨執行緒共享。

Collections 工具類

Collections.sort(list);
Collections.sort(list, Comparator.reverseOrder());
Collections.reverse(list);
Collections.shuffle(list);
Collections.max(list);
Collections.min(list);
Collections.frequency(list, x);

List<Integer> readOnly = Collections.unmodifiableList(list);    // 包裝成不可修改的視圖

視圖仍會反映原本 list 的變化，不是快照；若要獨立的不可修改結果，可依需求使用 List.copyOf(list)（Java 10+），但元素依然只是淺層複製。

Comparator

record Person(String name, int age) {}

List<Person> people = ...;

people.sort(Comparator.comparingInt(Person::age));                       // 升冪
people.sort(Comparator.comparingInt(Person::age).reversed());            // 降冪
people.sort(Comparator.comparingInt(Person::age)
                      .thenComparing(Person::name));                     // 多鍵

怎麼選

集合 API 上面的 <T> 角括號就是泛型。下一篇正式進泛型——萬用字元 ?、extends / super 上下界、為什麼 Java 泛型有「型別擦除」這個獨特包袱。

參考

• Java 21：List 的不可修改集合
• Java 21：TreeSet 的相等與排序契約
• Java 21：LinkedHashMap 的 access-order
• Java 21：ArrayDeque