[Java] 集合框架

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

整體架構

Java Collection Framework 在 java.util 下，三大主幹加 Map：

Iterable
└── Collection
    ├── List       （有序、可重複）
    ├── Set        （不重複）
    └── Queue      （FIFO / 雙端）

Map                （key-value，獨立階層，不繼承 Collection）

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

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)。需要當 queue 或頻繁頭部操作才用，否則一律 ArrayList。

走訪

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

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

自訂物件放 Set 必須實作 equals + hashCode

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

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 產生）。

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 實作。

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 不存在就放 value，存在就用 remap 合併。

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（老舊、synchronized 拖速度），用 ArrayDeque。

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());

不可變集合（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)
);

add / put 會丟 UnsupportedOperationException。給「真的不會變」的常數用，建構快、執行緒安全。

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);    // 包裝成不可變視圖

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 泛型有「型別擦除」這個獨特包袱。