萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

Java 陣列與集合深度對比:靜態陣列 vs ArrayList/Vector/LinkedList

核心差異總覽

特性靜態陣列ArrayListVectorLinkedList
大小固定,宣告時決定動態擴容動態擴容動態,鏈式結構
元素類型基本型別或具體引用型別Object(泛型擦除後)ObjectObject
同步/線程安全否否是(方法級 synchronized)否
隨機訪問 get(i)O(1)O(1)O(1)O(n)
尾部增刪不可變O(1) 攤還O(1) 攤還O(1)
中間增刪不可變O(n) 需搬移O(n) 需搬移O(1) 僅改指針
記憶體開銷最小預留空間 1.5 倍預留空間 2 倍每節點額外 2 指針

原理深度剖析

ArrayList / Vector:動態陣列

  • 底層 Object[] elementData
  • 擴容機制:
    • ArrayList:newCapacity = oldCapacity + (oldCapacity >> 1)(1.5 倍)
    • Vector:newCapacity = oldCapacity * 2(2 倍),可指定增量
  • 插入/刪除需 System.arraycopy 搬移後續元素

LinkedList:雙向鏈表

  • 節點結構:Node { E item; Node next; Node prev; }
  • 頭尾指針 first/last,尾部增刪極快
  • 索引訪問需從頭/尾遍歷,index < size/2 從頭,否則從尾

同步性選擇指南

// 單執行緒 / 手動同步:ArrayList(效能最佳)
List list = new ArrayList<>();

// 多執行緒讀多寫少:Collections.synchronizedList(new ArrayList<>())
// 或 CopyOnWriteArrayList(寫入複製,讀取無鎖)

// 多執行緒寫入頻繁:Vector(舊 API)或 ConcurrentLinkedQueue / CopyOnWriteArrayList
// 注意:Vector 方法級同步無法保證複合操作原子性(如 check-then-act)
List syncList = Collections.synchronizedList(new ArrayList<>());
synchronized(syncList) { // 複合操作需額外同步
    if (!syncList.contains("x")) syncList.add("x");
}

效能基準參考(百萬級數據)

操作ArrayListLinkedListVector
順序添加 100 萬~15ms~25ms~30ms
隨機訪問 100 萬次~5ms~2500ms~5ms
頭部插入 1 萬次~800ms~2ms~900ms
中間插入 1 萬次~400ms~1200ms~450ms
記憶體佔用 (100 萬 Integer)~16 MB~40 MB~18 MB

數據僅供參考,實際受 JVM、GC、硬體影響。

選型決策樹

需要固定大小、極致效能、基本型別? → 陣列 (int[], byte[] 等)
需要動態大小、頻繁隨機訪問、尾部增刪? → ArrayList
需要頻繁頭部/中間增刪、不需隨機訪問? → LinkedList
多執行緒環境、簡單同步需求? → Collections.synchronizedList / Concurrent 包
舊版 API 相容、不介意效能? → Vector

避坑指南

  1. 指定初始容量:new ArrayList<>(10000) 避免多次擴容拷貝
  2. 勿在循環中刪除 ArrayList 元素:用 Iterator.remove() 或反向循環
  3. LinkedList 不適合隨機訪問:for (int i=0; i<list.size(); i++) list.get(i) 是 O(n²) 災難
  4. Vector 已過時:新代碼優先用 ArrayList + 顯式同步或 java.util.concurrent
copyright © 萬盛學電腦網 all rights reserved