JDK Collections 框架提供了 List、Set、Map 三大核心介面及其多種實現。本文結合 JDK 8 源碼，從底層數據結構、核心方法實現、性能特徵及優化建議四個維度進行系統剖析。
header 哨兵節點，first/last 指向首尾實際節點。
| 操作 | ArrayList | LinkedList | 結論 |
|---|---|---|---|
尾部插入 add(E) | 擴容時需 Arrays.copyOf，均攤 O(1) | 新建 Node + 指針調整，O(1) | ArrayList 略優（連續內存、擴容快） |
任意位置插入 add(index, E) | System.arraycopy 移動元素，O(n) | 定位 O(n) + 指針調整 O(1) | 中前端插入 LinkedList 優；尾部 ArrayList 優 |
任意位置刪除 remove(index) | 數組移動 + 置 null，O(n) | 定位 O(n) + 指針調整 O(1) | 同插入邏輯 |
隨機訪問 get(index) | O(1) | O(n) 需遍歷 | ArrayList 完勝 |
| 遍歷 | for 循環/迭代器極快 | for 循環極慢（隨機訪問），迭代器/forEach 尚可 | ArrayList 首選 for 循環 |
ArrayList(int initialCapacity) 可減少擴容次數。Vector 同步開銷大，非線程安全場景首選 ArrayList。
標識支援快速隨機訪問的 List 實現。遍歷時可判斷：
if (list instanceof RandomAccess) {
for (int i=0; iNode[] table （JDK 8 引入紅黑樹化）。next 指針串聯 Entry。put 流程：計算 hash → 索引 → 遍歷鏈表/樹覆蓋或插入 → 擴容檢查。
| 特性 | HashMap | Hashtable |
|---|---|---|
| 線程安全 | 否 | 是（全方法 synchronized） |
| Null Key/Value | 允許 | 不允許 |
| 哈希算法 | 擾動函數 + 位運算 | 直接取模 |
| 推薦替代 | ConcurrentHashMap | 已淘汰 |
new HashMap(initialCapacity, loadFactor)，threshold = capacity * loadFactor。預估數據量時預設容量可避免頻繁擴容。
繼承 HashMap，內部維護雙向鏈表記錄插入順序或訪問順序（accessOrder 參數）。適合 LRU 快取實現。
基於紅黑樹，按 Comparable 或 Comparator 排序。查找/插入/刪除均為 O(log n)。
本質上是 Map 的鍵集合封裝：
HashSet → HashMap（value 為共享 PRESENT 對象）。LinkedHashSet → LinkedHashMap。TreeSet → TreeMap。
int size = list.size(); for (int i=0; i。 理解底層數據結構是寫出高性能 Java 代碼的前提。ArrayList 適合「讀多寫少、尾部操作」；LinkedList 適合「頻繁頭尾增刪、順序遍歷」；HashMap 是通用鍵值存儲首選；TreeMap 解決有序需求；ConcurrentHashMap 解決高併發寫入。實際開發中，結合 RandomAccess 判斷、預設容量、負載因子調優，可顯著提升吞吐量。
