ArrayList

ArrayList
- 使用分析
  - 優點
    - 改查效率高
    - 自動擴容機制1.5倍
  - 缺點
    - 線程不安全，安全的可以用copyOnwritArrayList, synchronizedList,vector
    - 插入和刪除操作效率低
    - 底層時用Object[]數組實現，需要連續的內存空間
    - 遍歷的時候如果被修改會出現ConcurrentModificationException異常
  - 時間復雜度
    - 隨機訪問 Q（1）
    - 插入和刪除尾部 Q（1）
    - 插入和刪除指定非尾部位置 Q（n）
  - 適用場景：單線程情況下最常用的List就是
- 設計分析
  - 設計目標
    - 單線程下高效的改查的List
  - 設計思路
    - 解決問題的思路
      - 基于new Object[]數組解決隨機訪問
      - 通過自動擴容解決容量問題
  - 實現原理
    - 基于new Object[]數組解決隨機訪問，通過自動擴容解決容量問題
- 源碼分析
  - 繼承機制
    - public class ArrayList<E> extends AbstractList<E>
      implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
      
      }
  - 容量
    - 擴容方法
    - 擴容時機：增加元素時判斷容量是否有空余，沒有空余才擴容
    - 無參構造函數數組長度為0
    - 有參構造函數
      - 參數小于10則數組長度為10
      - 參數大于10則數組長度為參數大小
    - 自動擴容1.5倍
      - 單次擴容時，如果增加到1.5倍后還是小于期望的Size，則直接擴到Size長度
      - 擴容之后容量都會變為原來的 1.5 倍左右（oldCapacity 為偶數就是 1.5 倍，不是偶數責小于 1.5 倍）！奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇數的話會丟掉小數.
      - 擴容到1.5倍的原因
        
        位運算效率考慮：位運算方式都是2的倍數，要么2倍，要么0.5倍
        
        空間考慮：在1.5倍和2倍的情況下為了減少空間浪費選擇1.5倍
    - 當需要的大小大于Integer.MAX_VALUE - 8時，使用最大數組長度Integer.MAX_VALUE
    - 擴容方法
      - System.arraycopy()
      - Arrays.copyOf()
    - 不能自動縮容，只能手動縮容
    - 手動改容量
      - 減少內存消耗：手動將數組長度減到size大小 trimToSize（）
      - 減少重復擴容時間：手動將數組長度庫容到目標大小 ensureCapacity（int minCapacity）
  - 迭代器按照下標順序
  - 異常類型
    - ConcurrentModificationException 遍歷時修改異常
    - IndexOutOfBoundsException 下標越界異常
    - 當初始化長度為負數時非法參數異常 IllegalArgumentException
  - 快速失敗機制fail- fast
    - 在增加刪除操作時modcount增加
    - 在獲取迭代器遍歷時，迭代器保存了ArrayList當前modcoun值，在迭代器每次執行next時先比較保存的modcoun和ArrayList當前的modcoun不同時，拋出異常ConcurrentModificationException
    - http://www.rzrgm.cn/ldq2016/p/18751225
  - 可以存儲NULL
  - https://javaguide.cn/java/collection/arraylist-source-code.html#arraylist-%E7%AE%80%E4%BB%8B

posted @ 2025-04-18 11:38 一點點征服閱讀(28) 評論(0) 收藏舉報

刷新頁面返回頂部

一點點征服

ArrayList

公告