ArrayList源碼解析

前言：在前面我們提到資料結構的線性表表。 那麼今天我們詳細看下Java源碼是如何實現線性表的， 這一篇主要講解順序表ArrayList鏈式表下一篇在提及。

1：ArrayList結構圖

2：關於Collection和List的區別

最好的比對就是查看他們的源碼我們先看Collection的所有介面

public interface Collection extends Iterable { int size; boolean contains(Object o); Iterator iterator; Object toArray; T toArray(T[] a); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection c); boolean addAll(Collection c); boolean retainAll(Collection c); void clear; boolean equals(Object o); int hashCode; }

在看List介面

public interface List extends Collection { int size; boolean isEmpty; Iterator iterator; Object toArray; T toArray(T[] a); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection c); boolean addAll(Collection c); boolean addAll(int index, Collection c); boolean removeAll(Collection c); boolean retainAll(Collection c); void clear; boolean equals(Object o); int hashCode; E get(int index); E set(int index, E element); void add(int index, E element); E remove(int index); int indexOf(Object o); int lastIndexOf(Object o); ListIterator listIterator; ListIterator listIterator(int index); List subList(int fromIndex, int toIndex); }

由於List是繼承Collection， 所有具有Collection所有的功能， 從Collection介面中我們也可以看出， Collection不具有索引， 不可以取元素的值， 而List取可以， List是具有索引的， 這樣一來在獲取元素方面遠遠好於Collection。

3：Iterable介面

從ArrayList中我們可以看出， 最頂端的介面就是Iterable這個介面， 這個是一個反覆運算器， 介面如下

public interface Iterable { Iterator iterator; }

這個介面主要是返回一個物件， 這個物件是Iterator， 那麼我們在看看Iterator介面裡面的方法

public interface Iterator { boolean hasNext; E next; void remove; }

那麼我們主要看ArrayList是如何實現反覆運算器Iterator的。 Iterator的實現在AbstractList這個抽象類別中的一個私有類Itr中。 我們看看具體實現

private class Itr implements Iterator { int cursor = 0; int lastRet = -1; int expectedModCount = modCount; public boolean hasNext { return cursor != size; }cursor：記錄即將調用索引的位置lastRet：最後一個元素的索引int expectedModCount = modCount;目的是為了驗證modCount後面會單獨說下。
public E next { checkForComodification; try { E next = get(cursor); lastRet = cursor++; return next; } catch (IndexOutOfBoundsException e) { checkForComodification; throw new NoSuchElementException; } }final void checkForComodification { if (modCount != expectedModCount) throw new ConcurrentModificationException; }

modCount：記錄所有陣列資料結構變動的次數， 包括添加、刪除、更改等， 為了避免併發時候， 當多個執行緒同時操作時候， 某個執行緒修改了陣列結構， 而另一個執行緒恰恰讀取這個陣列， 這樣一來就會產生錯誤。 所以在這段代碼中加入了modCount != expectedModCount， 比如A執行緒對資料結構修改一次， 那麼modCount比如+1， 而expectedModCount並沒有發生變化， 所以這樣就會拋出異常。

public void remove { if (lastRet == -1) throw new IllegalStateException; checkForComodification; try { AbstractList.this.remove(lastRet); if (lastRet

我們剛剛說了lastRet記錄的是最後一個元素， 所以刪除的時候直接按照索引刪除即可， 因為modCount會減一， 所以重新對expectedModCount 進行賦值， 避免遍歷時候產生錯誤。 而且把lastRed在次賦初始值。

4：分析ArrayList

剛剛目的是為了更加連接ArrayList做個鋪墊， ArrayList和我們以前資料結構中提到的順序表一樣， 採用Object 陣列進行存儲元素， 用size來記錄元素的元素的個數。

/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. */ private transient Object elementData; /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;

關於transient， 一旦變數被transient修飾， 變數將不再是物件持久化的一部分， 那麼為啥採用transient修飾呢， 由於elementData本身是一個緩存陣列， 通常會預留一些容量， 當容量不夠時然後進行擴充， 比如現在elementData容量是10， 但是只有5個元素， 陣列中的最後五個元素是沒有實際意義的， 不需要儲存， 所以ArrayList的設計者將elementData設計為transient， 然後在writeObject方法中手動將其序列化， 並且只序列化了實際存儲的那些元素， 而不是整個陣列。 我們看下writeObject方法

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject; // Write out array length s.writeInt(elementData.length); // Write out all elements in the proper order. for (int i=0; i

關於ArrayList的初始化。 ArrayList的設計者採用3種方式初始化。 （預設陣列容量是10）

public ArrayList(int initialCapacity) { super; if (initialCapacity < 0)="" throw="" new="" illegalargumentexception("illegal="" capacity:="" "+="" initialcapacity);="" this.elementdata="new" object[initialcapacity];="" }="" public="" arraylist="" {="" this(10);="" }="" public="" arraylist(collection="" c)="" {="" elementdata="c.toArray;" size="elementData.length;" c.toarray="" might="" (incorrectly)="" not="" return="" object="" (see="" 6260652)="" if="" (elementdata.getclass="" !="Object.class)" elementdata="Arrays.copyOf(elementData," size,="" object[].class);="">trimToSize方法， 這個方法可能我們好多人用的少， 其實意義蠻大的， 它主要把沒用的容量去除掉， 這樣一來可以減少記憶體的開銷 public void trimToSize { modCount++; int oldCapacity = elementData.length; if (size ensureCapacity方法， 我們知道陣列如果滿了就會進行擴容， 這個方法就是擴容的。 public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity

modCount就是增加因數， 記錄運算元組結構的次數， 首先和容量進行比對， 如果不夠了進行擴容。 這是Java1.6版本的就是在原來的基礎上擴容1.5倍。 1.7採用>>1也就是所有元素像右邊移動一位元然後加上原來的容量。 其中

indexOf方法， 這個方法是獲取元素索引。 通過索引然後進行查詢元素

public int indexOf(Object o) { if (o == null) { for (int i = 0; i

從中我們也可以看出ArrayList是支持null的插入的。 同樣採用的是迴圈遍歷來進行查找， 時間複雜的為n。

contains方法， 驗證陣列是否包含某元素， 直接通過indexOf驗證返回值即可

public boolean contains(Object o) { return indexOf(o) >= 0; }lastIndexOf方法， 和indexOf相對， indexOf是從前往後， lastIndexOf是從後面往前查找如下public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }

toArray方法， 就是把List轉換成陣列形式

public Object toArray { return Arrays.copyOf(elementData, size); }

get和set方法， 這個就很簡單了大家看下就行

public E get(int index) { RangeCheck(index); return (E) elementData[index]; } public E set(int index, E element) { RangeCheck(index); E oldValue = (E) elementData[index]; elementData[index] = element; return oldValue; }RangeCheck方法是進行驗證的， 查詢的索引不可以超過陣列的長度如下
private void RangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); }

add(E e)添加一個元素，

這個採用尾插入， 先驗證容量， size+1是加入1個元素後長度， 看原來陣列容量是否夠。

public boolean add(E e) { ensureCapacity(size + 1); // Increments modCount!! elementData[size++] = e; return true; }add(int index, E element)按照索引進行插入， 第一個還是一樣進行擴容， 然後把索引index後面的元素全部向後面移一位元。 System.arraycopy(elementData, index, elementData, index + 1, size - index);的意思就是將public void add(int index, E element) { if (index > size || index addAll(Collection c)public boolean addAll(Collection c) { Object a = c.toArray; int numNew = a.length; ensureCapacity(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }

首先把集合c轉換成a陣列， 然後計算要進行添加的陣列長度， 其它的基本和添加元素一致。 arraycopy(Object src, int srcPos,Object dest, int destPos,int length)

參數次數依次 源陣列， 源陣列起始位置， 目標陣列， 目標陣列起始位置， 複製陣列元素數目。

addAll(int index, Collection c)把陣列插入到指定位置public boolean addAll(int index, Collection c) { if (index > size || index 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }

首先判斷是是否越界， 然後和上面的基本一樣， 就是進行擴容判斷， 然後index後面的值進行後移包括index， 然後留下的空間插入集合a。 所以2次進行複製元素。

E remove(int index)和add相對， 刪除這個元素然後把index後面的元素往前面移一位元size - index - 1其中-1是因為index這個元素會被刪除， 會少一位元元素。public E remove(int index) { RangeCheck(index); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; }remove(Object o)這個就需要先進性驗證然後找到這個元素的位置最後進行刪除public boolean remove(Object o) { if (o == null) { for (int index = 0; index private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work }clear就是把所有的原素置空public void clear { modCount++; // Let gc do its work for (int i = 0; i

subList方法，我們知道ArrayList是有這個方法，在ArrayList源碼並不存在，因為是繼承AbstractList而來的

public List subList(int fromIndex, int toIndex) { return (this instanceof RandomAccess ? new RandomAccessSubList(this, fromIndex, toIndex) : new SubList(this, fromIndex, toIndex)); }class SubList extends AbstractList { private AbstractList l; private int offset; private int size; private int expectedModCount; SubList(AbstractList list, int fromIndex, int toIndex) { if (fromIndex list.size) throw new IndexOutOfBoundsException("toIndex = " + toIndex); if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); l = list; offset = fromIndex; size = toIndex - fromIndex; expectedModCount = l.modCount; }

從代碼中我們可以看出這個一個基本內部類的實現，subList只是去List中的一段資料。但是關於subList我們要注意幾個事項。

第一：如果我們改變了List的數值，那麼你獲取的subList中的值也隨之改變，原因如下

public E get(int index) { rangeCheck(index); checkForComodification; return l.get(index+offset); }

因為獲取的還是以前List中的資料。同樣如果修改subList獲取的數值，List同樣改變，

第二：如果改變了List結構，可能導致subList的不可用，因為這些修改已然基於原來的list，他們共同用一個list陣列。

public void add(int index, E element) { if (indexsize) throw new IndexOutOfBoundsException; checkForComodification; l.add(index+offset, element); expectedModCount = l.modCount; size++; modCount++; }

5：關於list刪除錯誤分析

list在採用迴圈刪除的時候會報ConcurrentModificationException異常，那麼我們來看看具體原因，先看一段代碼

List list = new ArrayList; list.add("a"); list.add("b"); list.add("c"); list.add("d"); list.add("e"); for (String str:list){ list.remove(str); }

由於foreach遍歷最終會for (Iterator it=iterator;iterators.hasNext;)模式那麼所以獲取元素的時候必然會用到反覆運算器中的next方法，next方法我們前面說了會有if(modCount!= expectedModCount)throw new ConcurrentModificationException驗證。因為調用remove(T x)方法時候modCount會+1,所以2次比較就會出現不一致。

正確寫法如下

Iterator iterator=list.iterator; while (iterator.hasNext){ iterator.next; iterator.remove; }

為啥反覆運算器中remove就可以呢，是由於在remove代碼中有expectedModCount = modCount這句代碼。

6：ArrayList是執行緒安全嗎

執行緒不安全就是指多個執行緒同時操作造成髒讀，錯讀情況，很明顯ArrayList是非執行緒安全的，比如說ArrayList現在只有一個值後，如果A，B2個執行緒同時刪除這個值，A執行緒判斷得到size=1,而此時時間片段到，CPU調用B執行緒執行發現size也是1，開始刪除操作，然後A繼續進行發現ArrayList已經空了就會報異常。或者添加等等。但是Vector是執行緒安全的，因為裡面所有方法都加入了synchronized，這樣造成的結果就是所有執行緒執行ArrayList方法都必須等待，直到獲取同步鎖才可以繼續進行，這樣一來性能大大降低。

會少一位元元素。public E remove(int index) { RangeCheck(index); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; }remove(Object o)這個就需要先進性驗證然後找到這個元素的位置最後進行刪除public boolean remove(Object o) { if (o == null) { for (int index = 0; index private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work }clear就是把所有的原素置空public void clear { modCount++; // Let gc do its work for (int i = 0; i

subList方法，我們知道ArrayList是有這個方法，在ArrayList源碼並不存在，因為是繼承AbstractList而來的

public List subList(int fromIndex, int toIndex) { return (this instanceof RandomAccess ? new RandomAccessSubList(this, fromIndex, toIndex) : new SubList(this, fromIndex, toIndex)); }class SubList extends AbstractList { private AbstractList l; private int offset; private int size; private int expectedModCount; SubList(AbstractList list, int fromIndex, int toIndex) { if (fromIndex list.size) throw new IndexOutOfBoundsException("toIndex = " + toIndex); if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); l = list; offset = fromIndex; size = toIndex - fromIndex; expectedModCount = l.modCount; }

從代碼中我們可以看出這個一個基本內部類的實現，subList只是去List中的一段資料。但是關於subList我們要注意幾個事項。

第一：如果我們改變了List的數值，那麼你獲取的subList中的值也隨之改變，原因如下

public E get(int index) { rangeCheck(index); checkForComodification; return l.get(index+offset); }

因為獲取的還是以前List中的資料。同樣如果修改subList獲取的數值，List同樣改變，

第二：如果改變了List結構，可能導致subList的不可用，因為這些修改已然基於原來的list，他們共同用一個list陣列。

public void add(int index, E element) { if (indexsize) throw new IndexOutOfBoundsException; checkForComodification; l.add(index+offset, element); expectedModCount = l.modCount; size++; modCount++; }

5：關於list刪除錯誤分析

list在採用迴圈刪除的時候會報ConcurrentModificationException異常，那麼我們來看看具體原因，先看一段代碼

List list = new ArrayList; list.add("a"); list.add("b"); list.add("c"); list.add("d"); list.add("e"); for (String str:list){ list.remove(str); }

由於foreach遍歷最終會for (Iterator it=iterator;iterators.hasNext;)模式那麼所以獲取元素的時候必然會用到反覆運算器中的next方法，next方法我們前面說了會有if(modCount!= expectedModCount)throw new ConcurrentModificationException驗證。因為調用remove(T x)方法時候modCount會+1,所以2次比較就會出現不一致。

正確寫法如下

Iterator iterator=list.iterator; while (iterator.hasNext){ iterator.next; iterator.remove; }

為啥反覆運算器中remove就可以呢，是由於在remove代碼中有expectedModCount = modCount這句代碼。

6：ArrayList是執行緒安全嗎

執行緒不安全就是指多個執行緒同時操作造成髒讀，錯讀情況，很明顯ArrayList是非執行緒安全的，比如說ArrayList現在只有一個值後，如果A，B2個執行緒同時刪除這個值，A執行緒判斷得到size=1,而此時時間片段到，CPU調用B執行緒執行發現size也是1，開始刪除操作，然後A繼續進行發現ArrayList已經空了就會報異常。或者添加等等。但是Vector是執行緒安全的，因為裡面所有方法都加入了synchronized，這樣造成的結果就是所有執行緒執行ArrayList方法都必須等待，直到獲取同步鎖才可以繼續進行，這樣一來性能大大降低。