Java Collection Framework 深度掌握（下）：Set/Queue/Map 全體系、實現類選型、Arrays/Collections 算法工具箱
接續上篇 List 體系，本文系統講解 Set（去重、集合運算）、Queue（FIFO/雙端/優先級）、Map（鍵值映射、有序/線程安全）三大接口體系、核心實現類對比、典型用法與 java.util.Arrays/java.util.Collections 算法工具類完全指南。
一、Set<E> 接口：數學集合、去重、集合運算
核心實現類對比
| 實現 | 底層結構 | 有序性 | 線程安全 | Null 支援 | 典型場景 |
|---|
| HashSet | HashMap (散列表) | 無序 | ❌ | 1 個 | 高性能去重、成員資格測試 |
| LinkedHashSet | HashMap + 雙向鏈表 | **插入序** | ❌ | 1 個 | 需保持插入順序的去重 |
| TreeSet | 紅黑樹 (NavigableMap) | **自然序/定製序** | ❌ | ❌ | 範圍查詢、有序遍歷、最近鄰 |
HashSet 關鍵：正確重寫 equals() + hashCode()
public class Book {
private int id; private String title;
// 構造器、getter、toString...
@Override public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Book)) return false;
return id == ((Book) o).id; // 僅按 id 判等
}
@Override public int hashCode() { return Integer.hashCode(id); } // 與 equals 一致
}
// 使用
Set set = new HashSet<>();
set.add(new Book(1, "Java")); // 加入
set.add(new Book(1, "Java EE")); // 重複 id，不加入
set.add(null); // 允許 1 個 null
set.add(null); // 忽略
LinkedHashSet：插入順序 = 遍歷順序
Set lhs = new LinkedHashSet<>();
lhs.add(new Book(3, "C"));
lhs.add(new Book(1, "A"));
lhs.add(new Book(2, "B"));
System.out.println(lhs); // [3:C, 1:A, 2:B] 保持插入序
TreeSet + Comparable / Comparator 定製排序
// 方式 1：實現 Comparable（自然序）
class Address implements Comparable {
String name;
@Override public int compareTo(Address o) { return name.compareToIgnoreCase(o.name); }
// equals/hashCode 保持一致...
}
TreeSet ts1 = new TreeSet<>();
ts1.add(new Address("peter"));
ts1.add(new Address("PAUL"));
ts1.add(new Address("Patrick"));
System.out.println(ts1); // [Patrick, PAUL, peter] 忽略大小寫升序
// 方式 2：外部 Comparator（靈活、不侵入實體）
class PhoneEntry { String name; }
Comparator descByName = (a, b) -> b.name.compareToIgnoreCase(a.name);
TreeSet ts2 = new TreeSet<>(descByName);
ts2.add(new PhoneEntry("peter"));
ts2.add(new PhoneEntry("PAUL"));
System.out.println(ts2); // [peter, PAUL] 降序
// NavigableSet 進階查詢
ts1.floor(new Address("PAUL")); // ≤ PAUL 最大元素 → PAUL
ts1.lower(new Address("PAUL")); // < PAUL 最大元素 → Patrick
ts1.headSet(new Address("PAUL")); // 所有 < PAUL
ts1.tailSet(new Address("PAUL")); // 所有 ≥ PAUL
二、Queue<E> & Deque<E>：FIFO、雙端、優先級、阻塞
核心實現類
| 類 | 接口 | 底層 | 特點 | 典型場景 |
|---|
| PriorityQueue | Queue | 堆 (數組) | 最小堆、O(log n) 入/出、非阻塞 | 任務調度、Top-K、事件驅動 |
| ArrayDeque | Deque | 循環數組 | 雙端 O(1)、無容量上限、非線程安全 | 棧、隊列、滑動窗口 |
| LinkedList | List + Deque | 雙向鏈表 | 雙端 O(1)、實現 List/Queue/Deque 三接口 | 頻繁頭尾增刪、棧/隊列 |
| BlockingQueue 實現 | BlockingQueue | 數組/鏈表 | **阻塞 put/take**、有界/無界、線程安全 | 生產消費、線程池工作隊列 |
關鍵方法分組（異常 vs 返回值）
// 入隊
q.add(e); // 滿拋 IllegalStateException
q.offer(e); // 滿返回 false
// 出隊
q.remove(); // 空拋 NoSuchElementException
q.poll(); // 空返回 null
// 查看
q.element(); // 空拋異常
q.peek(); // 空返回 null
Deque 雙端操作
Deque dq = new ArrayDeque<>();
dq.addFirst("A"); dq.addLast("Z");
dq.offerFirst("0"); dq.offerLast("9");
dq.removeFirst(); dq.removeLast();
dq.pollFirst(); dq.pollLast();
dq.getFirst(); dq.getLast(); dq.peekFirst(); dq.peekLast();
// 作為棧 (LIFO)
dq.push("top"); dq.pop(); dq.peek();
// 作為隊列 (FIFO)
dq.add("tail"); dq.remove(); dq.element();
三、Map<K,V>：鍵值映射、唯一鍵、多樣實現
核心實現類全景
| 實現 | 底層 | 有序性 | 線程安全 | Null Key/Value | 典型場景 |
|---|
| HashMap | 散列表 (數組+鏈表/紅黑樹) | 無序 | ❌ | 1 個 null key、多 null value | 通用高性能映射 |
| LinkedHashMap | HashMap + 雙向鏈表 | **插入序/訪問序** | ❌ | 同 HashMap | LRU 緩存、保持順序映射 |
| TreeMap | 紅黑樹 | **自然序/定製序** | ❌ | ❌ null key | 範圍查詢、有序遍歷 |
| Hashtable | 散列表 (同步) | 無序 | ✅ (synchronized) | ❌ null key/value | **舊代碼兼容**，新代碼用 ConcurrentHashMap |
| ConcurrentHashMap | CAS + synchronized + 節點鎖 | 無序 | ✅ (高併發) | ❌ null key/value | **多線程映射首選** |
HashMap 基本用法與詞頻統計
Map freq = new HashMap<>();
try (Scanner in = new Scanner(new File("words.txt"))) {
while (in.hasNext()) {
String w = in.next().toLowerCase();
freq.merge(w, 1, Integer::sum); // JDK 8+ 合併語法
}
}
System.out.println(freq); // {java=10, python=8, ...}
四、Arrays 工具類：數組排序、查找、複製、填充、轉 List
| 功能 | 核心方法 | 備註 |
|---|
| 排序 | sort(int[]), sort(T[], Comparator), parallelSort | 基本類型雙軸快排，對象 TimSort，JDK 8+ 並行排序 |
| 二分查找 | binarySearch(int[], key), binarySearch(T[], key, Comparator) | **前提：已排序** |
| 比較 | equals(int[], int[]), deepEquals(Object[], Object[]) | deepEquals 遞歸比較嵌套數組 |
| 複製 | copyOf(int[], newLen), copyOfRange(int[], from, to), copyOf(U[], len, T[].class) | 支援類型轉換複製 |
| 填充 | fill(int[], val), fill(int[], from, to, val) | 基本類型、對象均支援 |
| 轉字符串 | toString(int[]), deepToString(Object[]) | 調試神器 |
| 轉 List | asList(T...) | **返回固定長度 List**，修改寫回數組，不可增刪 |
五、Collections 工具類：集合排序、查找、極值、同步包裝、不可變視圖
| 功能 | 核心方法 | 備註 |
|---|
| 排序 | sort(List), sort(List, Comparator) | **僅支援 List**，Set/Queue 用 TreeSet/PriorityQueue 自動有序 |
| 二分查找 | binarySearch(List, key), binarySearch(List, key, Comparator) | List 必須已排序 |
| 極值 | max(Collection), min(Collection), max(Collection, Comparator) | 元素需實現 Comparable 或提供 Comparator |
| 同步包裝 | synchronizedList(List), synchronizedSet(Set), synchronizedMap(Map), synchronizedSortedMap(SortedMap) | **遍歷時必須手動 synchronized(包裝對象)** |
| 不可變視圖 | unmodifiableList(List), unmodifiableSet(Set), unmodifiableMap(Map) | 任何修改操作拋 UnsupportedOperationException |
| 單例集合 | singleton(T), singletonList(T), singletonMap(K,V) | 不可變、極省內存 |
| 反轉/打亂 | reverse(List), shuffle(List), rotate(List, distance) | 原地修改 |
| 填充/複製 | fill(List, obj), copy(List dest, List src) | dest 長度 ≥ src |
| 頻率/不相交 | frequency(Collection, obj), disjoint(Collection, Collection) | 統計工具 |
同步包裝遍歷鐵律
List syncList = Collections.synchronizedList(new ArrayList<>());
// 多線程添加安全
syncList.add("A");
// 遍歷**必須**手動加鎖
synchronized (syncList) {
for (String s : syncList) { // 或 Iterator
System.out.println(s);
}
}
六、總結：選型決策速查表
需要去重、成員測試
├─ 無序、高性能 → HashSet
├─ 保持插入序 → LinkedHashSet
└─ 有序、範圍查詢 → TreeSet (Comparable/Comparator)
需要隊列
├─ FIFO、雙端 → ArrayDeque (首選) / LinkedList
├─ 優先級 → PriorityQueue
└─ 多線程阻塞 → BlockingQueue (ArrayBlockingQueue/LinkedBlockingQueue)
需要鍵值映射
├─ 通用高性能 → HashMap
├─ 保持插入/訪問序 → LinkedHashMap
├─ 有序、範圍查詢 → TreeMap
└─ 多線程 → ConcurrentHashMap (首選) / Collections.synchronizedMap
需要算法
├─ 數組 → Arrays
└─ 集合 → Collections
