ArryaList源碼淺析

ArryaList源碼淺析

一 .繼承關系

​ ArrayList是java中常用的集合架構之一，其内部資料存儲為數組形式，其繼承關系如上圖所示。

二.屬性與方法

屬性

• private static final long serialVersionUID = 8683452581122892189L;
             

  序列化版本ID，用于反序列化進行版本比較，若反序列化時UID不一緻将會抛出java.io.InvalidClassException異常。

• private static final Object[] EMPTY_ELEMENTDATA = {};
             

  用于空清單的共享空對象數組，避免每次執行個體化時重新申請。

• private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
             

  同樣也是用于空清單的共享空對象數組，用于無參構造，和EMPTY_ELEMENTDATA的具體差別見注意事項。

• transient Object[] elementData;
             

  用于存放該清單的資料。

• private int size;
             

  該清單中元素的個數（指的是元素的個數，而非elementData數組的大小）。

• private static final int DEFAULT_CAPACITY = 10;
             

  預設的初始化數組大小。

• private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
             

  數組申請的最大大小，為什麼會是Integer.MAX_VALUE - 8？這是因為有些虛拟機會在數組頭部占用一定的空間，如果嘗試申請Integer.MAX_VALUE大小的數組，可能會導緻OutOfMemoryError: Requested array size exceeds VM limit。

方法

構造方法

• public ArrayList(int initialCapacity);
             

  有參構造方法，建立一個指定數組大小的空清單，如果initialCapacity為0，其elementData=EMPTY_ELEMENTDATA。

• public ArrayList();
             

  無參構造方法，elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

• public ArrayList(Collection<? extends E> c);
             

  有參構造方法，将傳入的集合轉換為數組存入elementData中，若集合為空，elementData=EMPTY_ELEMENTDATA。

清單核心方法

• public void ensureCapacity(int minCapacity);
             

  ArryaList的擴容方法，将對象數組的大小擴容為至少滿足minCapacity大小的程度。

  擴容規則：

  1. 計算minExpand，若elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA時為0，否則為DEFAULT_CAPACITY = 10。
  2. 若minCapacity <= minExpand時，不進行擴容。否則繼續進行擴容
  3. 計算minCapacity是否大于目前數組大小，大于時才進行擴容，防止資料丢失。
  4. 計算newCapacity（原數組大小的1.5倍）
  5. newCapacity取newCapacity與minCapacity的較大者
  6. 判斷newCapacity是否大于MAX_ARRAY_SIZE。大于時若minCapacity < 0 抛出OutOfMemoryError異常，minCapacity > MAX_ARRAY_SIZE時newCapacity取Integer.MAX_VALUE，否則取MAX_ARRAY_SIZE。
  7. 根據newCapacity建立新數組，并将原數組資料進行拷貝。

• public int size();
             

  傳回size的值，即清單中元素的個數。

• public boolean isEmpty();
             

  判斷清單是否為空，即size == 0？

• public boolean contains(Object o);
             

  查詢清單中是否包含對象o，若不包含對象o，傳回false。

  注意：這裡的o可以為null，此時比較直接使用==比較符，若o為對象，則調用該對象的equals方法。(内部實作為indexOf(Object o))。

• public int indexOf(Object o);
             

  從頭開始查詢清單，傳回對象o的數組下表，未查詢到時傳回-1。

  注意：這裡的o可以為null，此時比較直接使用==比較符，若o為對象，則調用該對象的equals方法。

• public int lastIndexOf(Object o);
             

  從末尾開始查詢清單，傳回對象o的數組下表，未查詢到時傳回-1。

• public E get(int index);
             

  根據索引值擷取指定位置的資料。

• public E set(int index, E element);
             

  根據索引值重新設定指定位置的資料，傳回舊值。

• public boolean add(E e);
             

  判斷數組是否能容納size+1個元素，不滿足則先進行擴容，最後添加元素至數組末尾。

• public void add(int index, E element);
             

  判斷數組是否能容納size+1個元素，不滿足則先進行擴容，最後添加元素至指定的索引位置。

• public E remove(int index);
             

  删除指定索引位置的資料，傳回删除元素的值。

• public boolean remove(Object o);
             

  删除指定的元素，o可以為null，從數組頭部開始配置，删除比對到的第一個元素。

• public void clear();
             

  将數組所有元素置為null，size=0。

• public boolean addAll(Collection<? extends E> c);
             

功能方法

• public void trimToSize();
             

  調整對象數組elementData的大小與size的值一緻，若size==0時将elementData的引用指向EMPTY_ELEMENTDATA。該方法主要用于減少清單的大小，釋放存儲空間。

• public Object clone();
             

  Object.clone()方法的實作，淺拷貝。

• public Object[] toArray();
             

  傳回該清單元素的一個新數組，注意同樣是淺拷貝。

• public <T> T[] toArray(T[] a);
             

  将清單中元素複制到數組a中。

  注意：當a.length<list.size時，原數組不會有任何變化，a.length=list.size時，原數組元素和清單中元素一緻，a.length>list.size, a[0]~a[size-1]為清單中元素，a[size]置為null。

• public boolean addAll(Collection<? extends E> c);
             

  将指定集合添加至數組末尾。

• public boolean addAll(int index, Collection<? extends E> c);
             

  将指定集合添加至指定索引處。

• public boolean removeAll(Collection<?> c);
             

  将既存在原清單中又存在集合c中的元素移除出清單，即兩集合的差集。

• public boolean retainAll(Collection<?> c);
             

  将既存在原清單中又存在集合c中的元素保留，即兩集合的交集。

• public List<E> subList(int fromIndex, int toIndex);
             

  根據指定的索引傳回一個新的清單。

  注意：該清單不是ArryaList，而是ArrayList的一個内部類SubList！

疊代器相關方法

• public ListIterator<E> listIterator(int index);
             

  從指定索引處傳回疊代器ListItr

• public ListIterator<E> listIterator();
             

  從數組起始處傳回疊代器ListItr

• public Iterator<E> iterator();
             

  傳回疊代器Itr

三.注意事項

1. EMPTY_ELEMENTDATA與DEFAULTCAPACITY_EMPTY_ELEMENTDATA

   ArryaList的無參構造函數會預設elementData為DEFAULTCAPACITY_EMPTY_ELEMENTDATA，在擴容時若需求大小小于DEFAULT_CAPACITY（10）時，擴容為10，防止在清單小的時候頻繁擴容。

2. ArrayList支援序列化為什麼elementData被transient修飾？

   在writeObject和readObject方法中進行了處理，隻序列化實際存儲的元素和size，而不是整個elementData數組。因為elementData數組的大小比size大，不需要序列化大于size的這部分數組。

3. 疊代器ListItr和Itr的差別