集合體系速覽
Collection (介面)
├── List (有序、可重複) → ArrayList, LinkedList, Vector
└── Set (無序、唯一) → HashSet, LinkedHashSet, TreeSet
List 實作詳解
| 實作類別 | 底層結構 | 隨機存取 | 頭尾插入/刪除 | 中間插入/刪除 | 適用場景 |
|---|
| ArrayList | 動態陣列 | O(1) ✅ | O(1) 擴容攤銷 | O(n) 需搬移元素 | 頻繁讀取、偶爾尾端新增 |
| LinkedList | 雙向鏈結串列 | O(n) ❌ | O(1) ✅ | O(1) 定位後 | 頻繁頭尾/中間增刪、佇列/堆疊 |
| Vector | 同步化動態陣列 | O(1) | O(1) | O(n) | 舊版 API、需執行緒安全時 (建議用 Collections.synchronizedList 或 CopyOnWriteArrayList) |
ListIterator：雙向游標，支援 add()/set()/previous()，僅 LinkedList 高效使用。
Set 實作詳解
| 實作類別 | 底層結構 | 查詢/插入/刪除 | 順序保證 | 元素需實作 | 適用場景 |
|---|
| HashSet | HashMap (雜湊表) | O(1) 平均 | 無序 | hashCode()、equals() | 高效去重、查找、不需排序 |
| LinkedHashSet | HashMap + 雙向鏈結 | O(1) 平均 | 插入順序 | hashCode()、equals() | 需保留插入順序的去重集合 |
| TreeSet | 紅黑樹 (NavigableMap) | O(log n) | 自然排序 / Comparator | Comparable 或 提供 Comparator | 需排序、範圍查詢 (headSet/tailSet) |
選型決策樹
- 需要 保留插入順序 且 唯一 →
LinkedHashSet
- 需要 排序/範圍查詢 且 唯一 →
TreeSet
- 單純 高效去重/查找 →
HashSet
- 需要 索引隨機存取、以讀為主 →
ArrayList
- 需要 頻繁頭尾/中間增刪、實作 Queue/Deque →
LinkedList
- 多執行緒環境 → 考慮
CopyOnWriteArrayList、ConcurrentHashMap.newKeySet() 等並發集合。
常見誤區提醒
- Set 判斷唯一性依賴
equals() + hashCode()，**必須雙方一致覆寫**，否則會出現「邏輯相等但雜湊碼不同」導致重複元素。
ArrayList 擴容會複製陣列，大量資料預知規模時用 new ArrayList<>(capacity) 減少擴容開銷。LinkedList 實作 Deque，push/pop、offer/poll 皆為 O(1)，勿自行造輪子。
