您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 集合框架核心：Set、List、Map 深度解析與選型指南

編輯：Java 相關知識

Java 集合框架是日常開發最高頻使用的 API。Set、List、Map 三大接口各有千秋，掌握其底層數據結構、性能特徵、線程安全性與適用場景，能讓代碼更簡潔、高效、健壯。本文從原理、源碼視角、實戰選型三個維度深度解析。

一、核心體系全景圖

Collection (接口)
 ├── List (有序、可重複)
 │    ├── ArrayList  (動態數組，隨機訪問快)
 │    ├── LinkedList (雙向鏈表，首尾增刪快)
 │    └── Vector     (同步，歷史遺留)
 │
 └── Set (無序、不可重複)
      ├── HashSet   (HashMap 底層，O(1) 查找)
      ├── LinkedHashSet (鏈表維護插入序)
      └── TreeSet   (紅黑樹，有序、O(log n))

Map (接口，鍵值對)
 ├── HashMap       (數組+鏈表/紅黑樹，JDK8 優化)
 ├── LinkedHashMap (維護插入/訪問序)
 ├── TreeMap       (紅黑樹，鍵有序)
 ├── Hashtable     (同步，歷史遺留)
 └── ConcurrentHashMap (分段鎖/CAS，高併發)

二、List 族群：有序可重複的序列

實現類	底層結構	隨機訪問	頭尾增刪	中間增刪	線程安全	典型場景
ArrayList	動態數組	O(1) ✅	O(1) 尾部 / O(n) 頭部	O(n) 需移動數組	❌	大多數場景首選，頻繁讀、少量寫
LinkedList	雙向鏈表	O(n) ❌	O(1) ✅	O(1) 定位後	❌	隊列、棧、頻繁頭尾操作
Vector	動態數組	O(1)	O(1)/O(n)	O(n)	✅ 同步方法	避免使用，性能差

核心源碼洞察

ArrayList 擴容機制：grow() -> newCapacity = oldCapacity + (oldCapacity >> 1) 1.5 倍擴容，Arrays.copyOf 複製數組。
LinkedList 無容量限制：節點對象 Node { E item; Node next; Node prev; }，適合未知大小、頻繁增刪。
隨機訪問接口：RandomAccess 標記接口，Collections.binarySearch 等會判斷優化算法。

遍歷方式性能對比

// 1. for 循環 + get(i) - ArrayList 快，LinkedList 慢 (O(n²))
for (int i = 0; i < list.size(); i++) { process(list.get(i)); }

// 2. 增強 for / 迭代器 - 統一 O(n)，推薦通用
for (E e : list) { process(e); }

// 3. ListIterator - 雙向遍歷、支持增刪改，LinkedList 專用優勢
ListIterator it = list.listIterator();
while (it.hasNext()) { process(it.next()); }

三、Set 族群：唯一性的守門員

實現類	底層結構	有序性	查找/增刪	null 支持	典型場景
HashSet	HashMap (key=元素, value=PRESENT)	無序	O(1)	允許 1 個 null	去重、快速存在性判斷
LinkedHashSet	HashMap + 雙向鏈表	插入序	O(1)	允許 1 個 null	去重且保持輸入順序
TreeSet	TreeMap (紅黑樹)	自然序/比較器序	O(log n)	不允許 null	排序去重、區間查詢

關鍵點：equals() 與 hashCode() 契約


public class User {
    private Long id;
    private String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return Objects.equals(id, user.id); // 業務主鍵決定唯一性
    }

    @Override
    public int hashCode() {
        return Objects.hash(id); // 必須與 equals 一致
    }
}

// 現在可以正確去重
Set set = new HashSet<>();
set.add(new User(1L, "A"));
set.add(new User(1L, "B")); // 不會添加，id 相同視為重複

四、Map 族群：鍵值映射的藝術

實現類	底層結構	有序性	線程安全	null 鍵/值	典型場景
HashMap	數組+鏈表/紅黑樹 (JDK8)	無序	❌	允許 1 null key, 多 null value	通用緩存、計數、索引
LinkedHashMap	HashMap + 雙向鏈表	插入序/訪問序	❌	允許	LRU 緩存、保持順序配置
TreeMap	紅黑樹	鍵自然序/比較器序	❌	不允許 null key	排序映射、範圍查詢
ConcurrentHashMap	Node[] + CAS/synchronized (JDK8)	無序	✅ 高併發	不允許 null	多線程緩存、計數器
Hashtable	數組+鏈表	無序	✅ 粗粒度鎖	不允許 null	避免使用

HashMap JDK 8 核心優化

鏈表樹化：鏈表長度 > 8 且數組長度 ≥ 64 時轉為紅黑樹，查找從 O(n) 降為 O(log n)。
樹化還原：擴容時節點數 ≤ 6 退回鏈表。
擴容機制：resize() 使用高位掩碼重新分佈，避免重新計算 hash。

ConcurrentHashMap 進化史


// JDK 7: 分段鎖 Segment[] (繼承 ReentrantLock)
// JDK 8: 放棄 Segment，採用 Node[] + CAS + synchronized (頭節點)
//        putVal: 
//          1. CAS 設置頭節點
//          2. 否則 synchronized 鎖頭節點操作鏈表/樹
//        size(): LongAdder 累加器

五、實戰選型決策表

業務需求	推薦集合	關鍵理由
頻繁隨機訪問、尾部增刪、單線程	ArrayList	底層數組，CPU 緩存友好，get/set O(1)
頻繁頭尾增刪、實現隊列/棧	LinkedList	雙向鏈表，首尾 O(1)，實現 Deque 接口
去重、快速判斷存在、無序	HashSet	HashMap 底層，O(1) 含有性檢查
去重、保持插入順序	LinkedHashSet	鏈表維護順序，O(1) 操作
去重、自動排序、範圍查詢	TreeSet	紅黑樹，有序性、subSet/headSet/tailSet
鍵值映射、高頻讀寫、單線程	HashMap	JDK8 樹化防退化，通用首選
鍵值映射、保持插入/訪問順序	LinkedHashMap	LRU 緩存實現利器
鍵值映射、鍵有序、範圍查詢	TreeMap	紅黑樹，navigableMap 接口豐富
高併發鍵值映射	ConcurrentHashMap	CAS + 細粒度鎖，吞吐量極高
線程安全 List/Set/Map (舊代碼)	Collections.synchronizedXxx	全鎖，性能差，僅兼容舊代碼

六、避坑指南與最佳實踐

指定初始容量：new ArrayList<>(expectedSize)、new HashMap<>(expectedSize / 0.75f + 1) 減少擴容開銷。
遍歷時修改：使用 Iterator.remove() 或 ListIterator，避免 ConcurrentModificationException。
Map 鍵不可變：鍵對象一旦放入 Map，絕不修改其 hashCode/equals 相關字段，否則導致數據「丟失」。
避免在循環中創建集合：移到循環外複用，或用 Stream API 收集器。
並發場景選 ConcurrentHashMap，不要用 Collections.synchronizedMap 或 Hashtable。
善用 Stream API：list.stream().filter(...).collect(Collectors.toSet()) 替代手工循環，更聲明式。

七、總結

List：有序、可重複、按索引訪問 → ArrayList 通用首選，LinkedList 專用隊列/棧。
Set：無重複、存在性檢查 → HashSet 通用首選，LinkedHashSet 保序，TreeSet 排序。
Map：鍵值映射、按鍵查找 → HashMap 通用首選，LinkedHashMap 保序/LRU，TreeMap 排序，ConcurrentHashMap 並發。
核心原理：數組(隨機訪問) vs 鏈表(增刪) vs 雜湊(O(1)查找) vs 紅黑樹(有序+O(log n))。