Java集合之ArrayList

一、基礎

　　ArrayList不是線程安全的，多線程建議使用Vector或者CopyOnWriteArrayList;

　　底層實現是Object數組。預設容量DEFAULT_CAPACITY為10，最大數組大小MAX_ARRAY_SIZE為Integer.MAX_VALUE-8;

　　實現了RandomAccess介面，表明可以快速隨機訪問;

　　實現了Cloneable介面，表明能被克隆;

　　實現了Serializabble介面，表明能序列化之後傳輸;

二、源碼方法

　　構造函數：

　　無參構造函數ArrayList（），構造一個用於空實例的共用空數組實例

　　一個int類型參數的構造函數 ArrayList（int initialCapacity）構造一個具有指定初始容量的空列表

　　一個指定collection的構造函數ArrayList（Collection<？ extends E> c）構造一個包含指定collection的元素的列表，這些元素是按照該collection的迭代器返回它們的順序排列的

　　方法：

　　size()：返回數組大小

　　isEmpty()：返回數組是否為空

　　contains(Object o)：返回是否包含某對象

　　clear()：從此列表中刪除所有元素，並且將siz置為0

　　ensureCapacity(int minCapacity)：將數組容量擴容至指定大小

　　addAll(Collection<? extends E> c)：將指定集合的所有元素追加到list末尾

　　removeAll(Collection<?> c)：從此列表中刪除包含在其中的所有元素指定的集合

　　indexOf(Object o)：如果包含則返回指定元素首次出現的索引，不包含則返回-1

　　lastIndexOf(Object o)：如果包含則返回指定元素最後出現的索引，不包含則返回-1

　　removeRange(int fromIndex, int toIndex)：從該列表中刪除索引在之間的所有元素

　　trimToSize()：將elementData的數組設置為ArrayList實際的容量，刪除動態增長的多餘容量

　　remove(Object o)：從此列表中刪除第一次出現的指定元素，刪除成功返回true，否正返回false

　　addAll(int index, Collection<? extends E> c)：從指定位置開始，將指定集合中的所有元素插入到此列表

　　retainAll(Collection<?> c)：僅保留此列表中包含在指定的集合的元素， 換句話說，從此列表中刪除所有未包含在指定集合中的元素

　　get(int index)、set(int index, E element)、add(E e)、add(int index, E element)、remove(int index)、

三、擴容

　　ArrayList初始大小為0，在添加第一個元素的時候，調用add方法，進入add方法時，需要先確定容量足以放下這個元素

　　進入ensureCapacityInternal()方法，傳入值為（當前size+1），然後判斷當前數組是否為預設的空數組，滿足條件，則最小擴容需要值為（當前size+1）和預設容量中較大的一個值。不是預設的空數組，則最小擴容需要值為（當前size+1）大小

　　然後進入ensureExplicitCapacity()方法，傳入最小擴容需要值，然後判斷最小擴容需要值和當前對象數組的長度，如果最小擴容需要值大於當前的數組長度，則調用grow()方法進行擴容

　　擴容時，暫定擴容值大小為原大小+原大小右移一位（偶數的1.5倍，奇數-1的1.5倍），記為newCapacity，然後判斷暫定擴容值和最小容量需要值，擴容值兩者中較大值。然後再比較擴容值和數組容量最大值，如果超過了數組容量最大值，再進入hugeCapacity()進入特殊處理。

　　hugeCapacity()方法中，先判斷最小擴容需要值是否為負數，是的話，則拋出記憶體溢出錯誤。否則判斷最小擴容需要值和Integer的最大值-8比較，再確定最終的擴容值，減去的8位存放的是數組的長度

　　確定了擴容值之後，就進行擴容操作，根據擴容值新建數組，然後拷貝數組，數組拷貝時調用的是本地方法 System.arraycopy() ，在C語言方法中調用frenn()釋放了原數組。

總結：

　　自動擴容不易，在新建ArrayList時，可以指定大小，或者在新增大量元素之前，可以調用ensureCapacity(int minCapacity)方法先手動擴容