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

Java 集合框架深度解析：從介面設計到底層資料結構

集合是 Java 開發最高頻 API。本文系統梳理 Collection 體系（List/Set）核心實現類的底層資料結構、效能特徵、適用場景與原始碼關鍵點，並附贈「隊列/堆疊模擬」、「自定義物件存入 HashSet/TreeSet 必讀」實戰指南。

一、Collection 體系架構圖譜

Collection (介面)
├── List (有序、可重複、有索引)
│   ├── ArrayList  (動態陣列)          → 查詢快、增刪慢、非執行緒安全
│   ├── LinkedList (雙向鏈表)          → 增刪快、查詢慢、可模擬隊列/堆疊
│   └── Vector   (舊版動態陣列，同步)  → 已被 ArrayList 取代，僅維護相容
└── Set (無序、不可重複)
    ├── HashSet   (雜湊表)             → 存取無序、O(1) 查找、非安全
    ├── LinkedHashSet (鏈表+雜湊表)    → 維護插入順序/存取順序
    └── TreeSet   (紅黑樹)             → 自然排序/定製排序、O(log N)

二、List 族群深度剖析

ArrayList

• 底層：Object[] elementData，擴容 1.5 倍。
• 隨機存取 O(1)，尾部新增均攤 O(1)，中間插入/刪除 O(N)（需陣列複製）。
• 允許 null 元素。

LinkedList

• 底層：雙向鏈表，節點含 prev/next/item。
• 頭/尾操作 O(1)：addFirst/Last、removeFirst/Last、getFirst/Last。
• 支援 ListIterator 雙向遍歷與增刪改查。
• 經典應用：模擬隊列（addLast + removeFirst）與堆疊（addLast + removeLast）。

Vector

• 所有方法 synchronized，效能差，僅為相容舊代碼保留。
• 早期迭代器 Enumeration 已被 Iterator 取代。

三、Set 族群深度剖析

HashSet / LinkedHashSet

• 底層包裝 HashMap<E, Object>，PRESENT 為固定 value。
• 核心規則：存入物件必須覆寫 hashCode() 與 equals()，否則無法保證唯一性（預設比較記憶體位址）。
• LinkedHashSet 額外維護雙向鏈表，迭代順序 = 插入順序（或存取順序）。

自定義物件存入 HashSet 範例

public class Person {
    private String name; private int age;
    // getter/setter/toString 省略

    @Override public int hashCode() {
        return Objects.hash(name, age);
    }
    @Override public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person p = (Person) o;
        return age == p.age && Objects.equals(name, p.name);
    }
}

未覆寫時：同名同年齡的不同實例視為不同元素 → 重複存入。覆寫後：內容相同視為同一元素 → 去重生效。

TreeSet

• 底層：紅黑樹（自平衡二叉搜尋樹），元素必須實作 Comparable 或提供 Comparator。
• 插入時按比較結果決定左/右子樹，重複元素（compareTo == 0）捨棄。
• 迭代輸出為自然升序。

Comparable 實作範例

public class Person implements Comparable<Person> {
    // ...
    @Override public int compareTo(Person o) {
        int ageDiff = this.age - o.age;
        return ageDiff != 0 ? ageDiff : this.name.compareTo(o.name);
    }
}

若未實作 Comparable 直接存入 TreeSet，拋 ClassCastException。

四、效能選型速查表

五、常見面試題與坑點

1. ArrayList vs LinkedList 插入效能：僅尾部插入 ArrayList 勝出；中間插入 LinkedList 理論較優，但實際因記憶體不連續、快取未命中，小數據量 ArrayList 往往更快。
2. HashSet 存入自定義物件重複：忘記覆寫 hashCode/equals。
3. TreeSet 拋 ClassCastException：物件未實作 Comparable 且無 Comparator。
4. 迭代中修改集合：直接 list.remove() 拋 ConcurrentModificationException，需用 Iterator.remove() 或 CopyOnWriteArrayList。
5. Vector 同步鎖粒度過大：高併發建議用 Collections.synchronizedList 或 CopyOnWriteArrayList。

掌握底層結構，才能在海量數據、高併發場景下做出正確集合選型，避免效能陷阱。