Java 集合框架核心總結：List、Set、Map 實現原理與選型指南

前言

集合框架是 Java 開發最高頻的基礎設施。許多開發者長期只用 ArrayList，對 HashMap、HashSet、TreeMap 等底層原理理解不足，導致性能隱患或面試失利。本文從源碼視角，系統梳理三大核心接口及其主流實現類的結構特點、擴容機制、線程安全性與選型建議。

一、List 接口：有序、可重複、支援下標訪問

1. ArrayList —— 動態數組，查詢快，增刪慢

• 底層結構：Object[] elementData，默認初始容量 10（延遲初始化為空數組，首次添加擴容為 10）。
• 擴容機制（grow()）：newCapacity = oldCapacity + (oldCapacity >> 1)，即 1.5 倍。超過 MAX_ARRAY_SIZE (Integer.MAX_VALUE - 8) 則分配 Integer.MAX_VALUE。
• 核心操作：
  • get(index)：O(1) 直接下標訪問。
  • add(E e)：均攤 O(1)，觸發擴容時 O(n) 需 Arrays.copyOf。
  • remove(index)：O(n) 需 System.arraycopy 移動後續元素。
• 適用場景：讀多寫少、頻繁隨機訪問、作為堆棧/隊列輔助。
• 避坑指南：預知大致數據量時，構造函數指定 initialCapacity 避免多次擴容拷貝；多線程環境用 Collections.synchronizedList 或 CopyOnWriteArrayList。

2. LinkedList —— 雙向鏈表，增刪快，查詢慢

• 底層結構：靜態內部類 Node，含 item、next、prev；維護 first/last 指針及 size。
• 核心操作：
  • addFirst/addLast：O(1) 僅調整指針。
  • get(index)：O(n) 需從頭/尾遍歷（源碼優化：index < size/2 從頭，否則從尾）。
  • remove(Object)：O(n) 先查找再斷鏈。
• 額外身份：實現 Deque 接口，可直接作為棧、隊列、雙端隊列使用（push/pop、offer/poll）。
• 適用場景：頻繁頭尾增刪、實現隊列/棧、數據量大且少隨機訪問。

二、Map 接口：鍵值映射、鍵唯一

1. HashMap (JDK 1.8) —— 數組 + 鏈表/紅黑樹，高性能非線程安全

• 核心字段：Node[] table、size、threshold、loadFactor (默認 0.75)。
• 存儲流程 (putVal)：
  1. 計算 hash：hash(key) = key.hashCode() ^ (key.hashCode() >>> 16)，高低位混合減少碰撞。
  2. 定位桶索引：index = (n - 1) & hash（n 為 2 的冪）。
  3. 桶為空 → 直接新建節點放入。
  4. 桶非空 → 遍歷鏈表/樹：equals 命中則覆蓋值；否則尾插。
  5. 樹化閾值：鏈表長度 ≥ 8 且數組長度 ≥ 64 → 轉為紅黑樹（TreeNode），查詢從 O(n) 降為 O(log n)。
  6. 退化閾值：樹節點 ≤ 6 → 退化為鏈表。
• 擴容：resize() 2 倍擴容，重新計算索引（JDK 1.8 優化：節點要么留原位，要么移至 oldCap + index，避免全量 rehash）。
• 線程不安全表現：多線程 put 導致鏈表成環（JDK 1.7）、數據丟失、CPU 100%。並發場景必用 ConcurrentHashMap。

2. Hashtable —— 老牌線程安全，性能差，已被 ConcurrentHashMap 取代

• 所有 public 方法 synchronized，粗粒度鎖，並發度極低。
• 不允許 null key/value。

3. TreeMap —— 紅黑樹，有序 Map

• 底層：紅黑樹（自平衡二叉搜索樹），實現 NavigableMap。
• 排序方式：自然順序（Key 實現 Comparable）或構造傳入 Comparator。
• 核心操作 O(log n)：put/get/remove/firstKey/lastKey/lowerKey/higherKey 等範圍查詢極其高效。
• 適用場景：需要有序遍歷、範圍查找、最近鍵查詢的場景。

三、Set 接口：無序、不可重複

1. HashSet —— 基於 HashMap 實現，值存作 Key，Value 固定為 PRESENT 單例

private transient HashMap map;
public boolean add(E e) { return map.put(e, PRESENT) == null; }

• 特性同 HashMap：非線程安全、允許一個 null、無序、查找/添加/刪除均攤 O(1)。

2. TreeSet —— 基於 TreeMap 實現，天然有序、去重

public TreeSet() { this(new TreeMap()); }
public boolean add(E e) { return m.put(e, PRESENT) == null; }

• 特性同 TreeMap：紅黑樹、O(log n)、支援 first()/last()/lower()/higher()/subSet() 等導航操作。
• 適用場景：去重 + 排序 + 範圍查詢（如排名榜、區間統計）。

3. LinkedHashSet —— 維護插入順序的 HashSet（內部用 LinkedHashMap）

• 兼具 HashSet 高性能與插入順序遍歷，LRU 緩存常用結構。

四、選型決策表（收藏備用）

五、總結

• ArrayList = 動態數組，查快改慢；LinkedList = 雙向鏈表，改快查慢。
• HashMap 1.8 引入紅黑樹解決極端碰撞性能退化，擴容優化避免全量 rehash。
• TreeMap/TreeSet 靠紅黑樹實現有序，適合範圍查詢。
• HashSet/TreeSet 本質是 Map 的 Key 視圖，去重邏輯極簡高效。
• 並發場景堅決不用 HashMap/ArrayList/HashSet，轉用 java.util.concurrent 包對應實現。

吃透底層原理，才能在業務開發中做最優選型，在面試中游刃有餘。