ArrayList詳解

ArrayList是Java集合框架中最常用的List實現(xiàn)類，基于動態(tài)數(shù)組實現(xiàn)。

1. 類繼承關(guān)系

                   ┌────────────────────────┐
                   │        List<E>        │
                   └──────────┬─────────────┘
                              │
                   ┌──────────▼─────────────┐
                   │     AbstractList<E>    │
                   └─────┬───────────┬──────┘
                         │           │
              ┌──────────▼───┐   ┌───▼──────────┐
              │ ArrayList<E> │   │  Vector<E>   │
              └──────────────┘   └──────────────┘

2. 核心特性

• 動態(tài)擴容：默認初始容量10，擴容時增加50%
• 隨機訪問：通過索引訪問元素時間復雜度O(1)
• 非線程安全：多線程環(huán)境下需要外部同步
• 允許null元素：可以存儲null值
• 快速失敗(Fail-Fast)：迭代時檢測到并發(fā)修改會拋出ConcurrentModificationException

3. 內(nèi)部結(jié)構(gòu)

transient Object[] elementData;  // 存儲元素的數(shù)組
private int size;                // 實際元素數(shù)量
private static final int DEFAULT_CAPACITY = 10;

4. 常用方法

5. 性能分析

• 優(yōu)點：

  • 隨機訪問速度快
  • 尾部添加元素效率高
  • 內(nèi)存占用比LinkedList少

• 缺點：

  • 中間插入/刪除元素效率低
  • 擴容時會產(chǎn)生額外開銷：
    • 創(chuàng)建新數(shù)組：需要分配更大的內(nèi)存空間
    • 數(shù)組拷貝：使用System.arraycopy()復制原數(shù)組元素
    • 舊數(shù)組GC：舊數(shù)組成為垃圾等待回收
    • 擴容時機：添加元素時發(fā)現(xiàn)容量不足才會觸發(fā)
    • 實踐中的坑：
      • 頻繁擴容導致性能下降（特別是大數(shù)據(jù)量時）
      • 預估容量不準確導致內(nèi)存浪費
      • 擴容期間可能引發(fā)OOM異常

6. 使用示例

// 創(chuàng)建ArrayList
List<String> list = new ArrayList<>();

// 添加元素
list.add("Java");
list.add("Python");
list.add(1, "C++");  // 在索引1處插入

// 訪問元素
String first = list.get(0);

// 遍歷
for (String lang : list) {
    System.out.println(lang);
}

// 刪除元素
list.remove("Python");
list.remove(0);

7. 線程安全替代方案

• 使用Collections.synchronizedList包裝：

  List<String> syncList = Collections.synchronizedList(new ArrayList<>());
  

• 使用CopyOnWriteArrayList(適合讀多寫少場景)

8. 最佳實踐

1. 預估容量避免頻繁擴容：

   new ArrayList<>(100);  // 指定初始容量
   

2. 批量操作使用addAll：

   list.addAll(anotherList);
   

3. 遍歷時避免結(jié)構(gòu)性修改

9. 面試常見問題

1. ArrayList和LinkedList的區(qū)別？

   • 底層結(jié)構(gòu)：數(shù)組 vs 雙向鏈表
   • 訪問效率：O(1) vs O(n)
   • 插入刪除：尾部O(1)，中間O(n) vs 頭尾O(1)，中間O(n)
   • 內(nèi)存占用：連續(xù)內(nèi)存 vs 節(jié)點額外內(nèi)存

2. ArrayList的擴容機制？

   • 默認初始容量10
   • 擴容公式：newCapacity = oldCapacity + (oldCapacity >> 1)
   • 最大容量Integer.MAX_VALUE - 8：

     // JDK源碼片段
     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
     
     private void grow(int minCapacity) {
         int oldCapacity = elementData.length;
         int newCapacity = oldCapacity + (oldCapacity >> 1);
         if (newCapacity - minCapacity < 0)
             newCapacity = minCapacity;
         if (newCapacity - MAX_ARRAY_SIZE > 0)
             newCapacity = hugeCapacity(minCapacity);
         elementData = Arrays.copyOf(elementData, newCapacity);
     }
     

     • 減8是因為某些JVM實現(xiàn)會在數(shù)組頭部存儲元數(shù)據(jù)
     • 超過此限制會拋出OutOfMemoryError
       java.lang.OutOfMemoryError: Requested array size exceeds VM limit
       這是為了避免在某些 JVM 上數(shù)組對象頭占用內(nèi)存導致的溢出問題。

什么是對象頭
[ Mark Word ][ Class Pointer ][ Array Length ][ Array Elements ... ]

• 擴容時數(shù)組拷貝使用System.arraycopy()

3. 線程安全相關(guān)

   • ArrayList線程安全：

     • 非線程安全
     • 解決方案：

       // 方法1：Collections.synchronizedList
       List<String> syncList = Collections.synchronizedList(new ArrayList<>());
       
       // 方法2：CopyOnWriteArrayList
       List<String> cowList = new CopyOnWriteArrayList<>();
       

     • 需要手動同步的場景：

       synchronized(list) {
           list.add(item);
       }
       

   • Vector的區(qū)別：

     // Vector的同步方法示例
     public synchronized boolean add(E e) {
         modCount++;
         ensureCapacityHelper(elementCount + 1);
         elementData[elementCount++] = e;
         return true;
     }
     

     • Java 1.2后被標記為"legacy"，原因：
       • 同步粒度太粗(方法級)，性能差
       • 現(xiàn)代應用更傾向于細粒度同步控制
     • 推薦替代方案：
       • ArrayList + 外部同步
       • CopyOnWriteArrayList
     • 擴容策略不同：Vector增長100%，ArrayList增長50%

4. 快速失敗(Fail-Fast)機制？

   // ArrayList中的modCount聲明
   protected transient int modCount = 0;
   
   // 迭代器檢查實現(xiàn)
   final void checkForComodification() {
       if (modCount != expectedModCount)
           throw new ConcurrentModificationException();
   }
   

   • 實現(xiàn)原理：
     • modCount記錄結(jié)構(gòu)修改次數(shù)(add/remove等操作會遞增)
     • 創(chuàng)建迭代器時記錄expectedModCount=modCount
     • 每次迭代前調(diào)用checkForComodification()檢查
   • 注意：
     • 非原子操作，不能完全保證線程安全
     • 僅用于檢測單線程下的并發(fā)修改

5. ArrayList的toArray()方法？

   // toArray(T[] a)源碼關(guān)鍵部分
   if (a.length < size)
       return (T[]) Arrays.copyOf(elementData, size, a.getClass());
   System.arraycopy(elementData, 0, a, 0, size);
   if (a.length > size)
       a[size] = null;
   

   • 行為說明：
     • 數(shù)組大小充足時：拷貝元素到該數(shù)組，剩余位置保持原內(nèi)容
     • 數(shù)組大小不足時：創(chuàng)建新數(shù)組
     • 最佳實踐：list.toArray(new String[0])

6. ArrayList的subList()方法注意事項？

   // SubList構(gòu)造方法
   SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {
       this.parent = parent;
       this.parentOffset = fromIndex;
       this.modCount = ArrayList.this.modCount;
       // ...
   }
   

   • 實現(xiàn)原理：
     • 基于原列表的視圖(存儲偏移量，不拷貝數(shù)據(jù))
     • 共享原列表的modCount
   • 異常原因：
     • 任何結(jié)構(gòu)性修改都會改變原列表modCount
     • 子列表操作時會檢查modCount是否一致
   • 解決方案：

     new ArrayList<>(list.subList(from, to))