ArrayList原始碼分析
總覽
- 底層:ArrayList是List介面的大小可變陣列的實現。
- 是否允許null:ArrayList允許null元素。
- 時間複雜度:size、isEmpty、get、set、iterator和listIterator方法都以固定時間執行,時間複雜度為O(1)。add和remove方法需要O(n)時間。與用於LinkedList實現的常數因子相比,此實現的常數因子較低。
- 容量:ArrayList的容量可以自動增長。
- 是否同步:ArrayList不是同步的。
- 迭代器:ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的。
定義
public class ArrayList<E> extends AbstractList<E>
- ArrayList<E>:說明ArrayList支援泛型。
- extends AbstractList<E>:繼承了AbstractList。AbstractList提供List介面的骨幹實現,以最大限度地減少“隨機訪問”資料儲存(如ArrayList)實現Llist所需的工作。
-
implements
- List<E>:實現了List。實現了所有可選列表操作。
- RandomAccess:表明ArrayList支援快速(通常是固定時間)隨機訪問。此介面的主要目的是允許一般的演算法更改其行為,從而在將其應用到隨機或連續訪問列表時能提供良好的效能。
- Cloneable:表明其可以呼叫clone()方法來返回例項的field-for-field拷貝。
- java.io.Serializable:表明該類具有序列化功能。
域
/** * 預設初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; /** * 指定該ArrayList容量為0時,返回該空陣列。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 當呼叫無參構造方法,返回的是該陣列。剛建立一個ArrayList 時,其內資料量為0。 * 它與EMPTY_ELEMENTDATA的區別就是:該陣列是預設返回的,而後者是在使用者指定容量為0時返回。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 儲存ArrayList資料的陣列 * 該值為DEFAULTCAPACITY_EMPTY_ELEMENTDATA 時,當第一次新增元素進入ArrayList中時,陣列將擴容值DEFAULT_CAPACITY。 */ transient Object[] elementData; /** * ArrayList 所包含的元素個數 */ private int size;
問題:elementData被標記為transient,那麼它的序列化和反序列化是如何實現的呢?
ArrayList自定義了它的序列化和反序列化方式。詳情請檢視writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectOutputStream s)方法。
構造方法
ArrayList提供了三種構造方法。
- ArrayList(int initialCapacity):構造一個指定容量為capacity的空ArrayList。
- ArrayList():構造一個初始容量為 10 的空列表。
- ArrayList(Collection<? extends E> c):構造一個包含指定 collection 的元素的列表,這些元素是按照該 collection 的迭代器返回它們的順序排列的。
/** * 帶初始容量引數的建構函式。(使用者自己指定容量) */ public ArrayList(int initialCapacity) { //初始容量大於0 if (initialCapacity > 0) { //建立initialCapacity大小的陣列 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //建立空陣列 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 預設建構函式,DEFAULTCAPACITY_EMPTY_ELEMENTDATA 為0.初始化為10, * 也就是說初始其實是空陣列 當新增第一個元素的時候陣列容量才變成10 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 構造一個包含指定集合的元素的列表,按照它們由集合的迭代器返回的順序。 * 如果指定的集合為null,throws NullPointerException。 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); //如果指定集合元素個數不為0 if ((size = elementData.length) != 0) { // c.toArray 可能返回的不是Object型別的陣列所以加上下面的語句用於判斷, if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); //【2】Arrays包含用來運算元組(比如排序和搜尋)的各種方法。 //copyOf(U[] original, int newLength, Class<? extends T[]> newType) // 複製指定的陣列,擷取或用 null 填充(如有必要),以使副本具有指定的長度。 } else { this.elementData = EMPTY_ELEMENTDATA; } }
核心方法
/** * 返回此列表中指定位置的元素。 * * @paramindex 需要返回的元素的索引 * @return list中索引為index的元素 * @throws IndexOutOfBoundsException 如果索引超出size */ public E get(int index) { //越界檢查 rangeCheck(index); return elementData(index); } /** * 檢查給定的索引是否在範圍內。 */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 返回索引為index的元素 */ @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }
從程式碼中可以看到,因為ArrayList底層是陣列,所以它的get方法非常簡單,先是判斷一下有沒有越界,之後就直接通過陣列下標來獲取元素。get方法的時間複雜度是O(1)。
/** * 將指定的元素追加到此列表的末尾。 */ public boolean add(E e) { //確認list容量,如果不夠,容量加1。注意:只加1,保證資源不被浪費 ensureCapacityInternal(size + 1); //這裡看到ArrayList新增元素的實質就相當於為陣列賦值 elementData[size++] = e; return true; }
從原始碼中可以看到,add(E e)有兩個步驟:
空間檢查,如果有需要進行擴容
插入元素
擴容
/** * ArrayList的擴容機制 * ArrayList的擴容機制提高了效能,如果每次只擴充一個, * 那麼頻繁的插入會導致頻繁的拷貝,降低效能,而ArrayList的擴容機制避免了這種情況。 * 如有必要,增加此ArrayList例項的容量,以確保它至少能容納元素的數量 * @paramminCapacity所需的最小容量 */ public void ensureCapacity(int minCapacity) { // 如果elementData等於DEFAULTCAPACITY_EMPTY_ELEMENTDATA,最小擴容量為DEFAULT_CAPACITY,否則為0 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } /** * 陣列容量檢查,不夠時則進行擴容。 * * @param minCapacity想要的最小容量 */ private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA, // 則取minCapacity為DEFAULT_CAPACITY和引數minCapacity之間的最大值 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } //得到最小擴容量 private void ensureCapacityInternal(int minCapacity) { // 獲取預設的容量和傳入引數的較大值 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } //判斷是否需要擴容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 確保指定的最小容量 > 陣列緩衝區當前的長度 if (minCapacity - elementData.length > 0) //擴容 grow(minCapacity); } /** * 要分配的最大陣列大小 * 為什麼要減去8呢? * 因為某些VM會在陣列中保留一些頭字,嘗試分配這個最大儲存容量,可能會導致array容量大於VM的limit,最終導致OutOfMemoryError。 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * ArrayList擴容的核心方法 * * 第一次擴容,邏輯為newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基礎上增加一半。 * 第一次擴容後,如果容量還是小於minCapacity,就將容量擴充為minCapacity。 */ private void grow(int minCapacity) { // oldCapacity為舊容量,newCapacity為新容量 int oldCapacity = elementData.length; //將oldCapacity 右移一位,其效果相當於oldCapacity /2, //我們知道位運算的速度遠遠快於整除運算,整句運算式的結果就是將新容量更新為舊容量的1.5倍, int newCapacity = oldCapacity + (oldCapacity >> 1); //然後檢查新容量是否大於最小需要容量,若還是小於最小需要容量,那麼就把最小需要容量當作陣列的新容量, if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //再檢查新容量是否超出了ArrayList所定義的最大容量, //若超出了,則呼叫hugeCapacity()來比較minCapacity和 MAX_ARRAY_SIZE, //如果minCapacity大於MAX_ARRAY_SIZE,則新容量則為Interger.MAX_VALUE,否則,新容量大小則為 MAX_ARRAY_SIZE。 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } //比較minCapacity和 MAX_ARRAY_SIZE private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
看完了程式碼,可以對擴容方法總結如下:
進行空間檢查,決定是否進行擴容,以及確定最少需要的容量
如果確定擴容,就執行grow(int minCapacity),minCapacity為最少需要的容量
第一次擴容,邏輯為newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基礎上增加一半。
第一次擴容後,如果容量還是小於minCapacity,就將容量擴充為minCapacity。
對擴容後的容量進行判斷,如果大於允許的最大容量MAX_ARRAY_SIZE,則將容量再次調整為MAX_ARRAY_SIZE。至此擴容操作結束。
add(int index, E element)
/** * 在此列表中的指定位置插入指定的元素。 * 先呼叫 rangeCheckForAdd 對index進行界限檢查;然後呼叫 ensureCapacityInternal 方法保證capacity足夠大; * 再將從index開始之後的所有成員後移一個位置;將element插入index位置;最後size加1。 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); //arraycopy()這個實現陣列之間複製的方法一定要看一下,下面就用到了arraycopy()方法實現陣列自己複製自己 //實現讓index開始之後的所有元素後移一個位置: //elementData:源陣列;index:源陣列中的起始位置;elementData:目標陣列;index + 1:目標陣列中的起始位置; size - index:要複製的陣列元素的數量; System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
從原始碼中可以看到,add(E e)有三個步驟:
1、越界檢查
2、空間檢查,如果有需要進行擴容
3、插入元素
add(int index, E e)需要先對元素進行移動,然後完成插入操作,也就意味著該方法有著線性的時間複雜度,即O(n)
remove(int index)
/** * 刪除該列表中指定位置的元素。 將任何後續元素移動到左側(從其索引中減去一個元素)。 */ public E remove(int index) { //檢查索引是否越界 rangeCheck(index); //結構性修改次數+1【1】 modCount++; E oldValue = elementData(index); // 刪除指定元素後,需要左移的元素個數 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // size減一,然後將索引為size-1處的元素置為null。為了讓GC起作用,必須顯式的為最後一個位置賦null值 elementData[--size] = null; //從列表中刪除的元素 return oldValue; }
看完程式碼後,可以將ArrayList刪除指定索引的元素的步驟總結為
- 檢查索引是否越界。如果引數指定索引index>=size,丟擲一個越界異常
- 將索引大於index的元素左移一位(左移後,該刪除的元素就被覆蓋了,相當於被刪除了)。
- 將索引為size-1處的元素置為null(為了讓GC起作用)。
注意:為了讓GC起作用,必須顯式的為最後一個位置賦null值。上面程式碼中如果不手動賦null值,除非對應的位置被其他元素覆蓋,否則原來的物件就一直不會被回收。
set( int index, E element)
/** * 用指定的元素替換此列表中指定索引的元素。 */ public E set(int index, E element) { //對index進行界限檢查 rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; //返回原來在這個位置的元素 return oldValue; }