有關ArrayList常用方法的源碼解析

jdk1.7.0_79

我相信幾乎所有的同學在大大小小的筆試、面試過程中都會被問及ArrayList與LinkedList之間的異同點。稍有準備的人這些問題早已爛熟於心，前者基於數組實現，後者基於鏈表實現；前者隨機方法速度快刪除和插入指定位置速度慢，後者隨機訪問速度慢刪除和插入指定位置速度快；兩者都是線程不安全的；列表與數組之間的區別等等。

列表與數組之間很大的一個區別就是：數組在其初始化就需要給它確定大小不能動態擴容，而列表則可以動態擴容。ArrayList是基於數組實現的，那麼它是如何實現的動態擴容呢？

對於ArrayList的初始化有三種方式：

對於第一種默認的構造方法，ArrayList並沒有初始化容量大小，而是將列表的元素數據引用指向了一個空數組。

private transient Object elementData;
private static final Object EMPTY_ELEMENTDATA = {};

//1.ArrayList默認構造方法
public ArrayList {
super;
this.elementData = EMPTY_ELEMENTDATA;
}

與JDK1.6不同的是，JDK1.6即時是在調用默認的構造方法時，也會初始化容量大小，JDK1.7當然會帶來一定的好處，如果初始化而不使用就白白浪費了存儲空間，等到添加的時候再初始化容量大小即可。

//JDK1.6 ArrayList
public ArrayList {
this(10);
}

對於第二種構造方法，則直接創建一個指定大小的數組，將列表的元素數組引用指向它。

//2.ArrayList帶有初始化大小的構造方法
public ArrayList(int initialCapacity) {
super;
if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; }

第三種構造方法，能將一個集合作為參數傳遞，但集合中的元素必須繼承自ArrayList中的元素。

//3.可將一個集合作為ArrayList的參數構造成ArrayList
public ArrayList(Collection c) {
elementData = c.toArray; //將集合轉換為數組
size = elementData.length; //集合中的元素大小
// c.toArray might (incorrectly) not return Object (see 6260652) 這裡是個bug，參考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
if (elementData.getClass != Object.class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}

上面提到了一個bug，也就是說將一個集合轉換為數組的時候可能錯誤地不會返回Object，舉例說明。

1 package com.algorithm.sort;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5 import java.util.List;
6
7 /**
8 * bug編號:6260652。toArray有可能不會返回Object
9 * Created by yulinfeng on 2017/6/26.
10 */
11 public class Test {
12 public static void main(String[] args) {
13 correctly;
14 incorrectly;
15 }
16
17 /**
18 * 返回Object
19 */
20 private static void correctly {
21 List list = new ArrayList;
22 list.add("test");
23 System.out.println(list.getClass);
24 Object objArray = list.toArray;
25 System.out.println(objArray.getClass);
26 }
27 /**
28 * 不返回Object
29 */
30 private static void incorrectly {
31 List list = Arrays.asList("test");
32 System.out.println(list.getClass);
33 Object objArray = list.toArray;
34 System.out.println(objArray.getClass);
35 }
36 }

運行結果：

上面的這個例子就說明了toArray並不一定總是返回Object，返回的Object時，Object元素就不能插入，故JDK在「6260652」中修復了這個bug。

接下來看元素插入以及刪除等其它方法。

//ArrayList#add
public boolean add(E e) {
ensureCapacityInternal(size + 1); //確保容量是否充足
elementData[size++] = e; //將元素添加至數組
return true;
}

//ArrayList#ensureCapacityInternal
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //如果此時還沒有初始化列表容量大小，則對其初始化，默認容量為10
}
ensureExplicitCapacity(minCapacity); //檢查容量是否充足
}

//ArrayList#ensureEcplicitCapacity
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //注意此變數
if (minCapacity - elementData.length > 0)
grow(minCapacity); //容量不夠則進行擴容
}

在ensureEcplicitCapacity方法中有一個modCount（modify count）變數進行了自增。

protected transient int modCount = 0;

這個變數不僅在add方法中會自增，只要是在增加或者刪除等對ArrayList結構產生了變化都會記錄加1，這樣做的原因和多線程下Iterator迭代器遍歷有關。在AbstractList$Itr中也有一個變數與之對應。

//AbstractList$Itr
int expectedModCount = modCount;

在AbstractList$Itr#next中調用了checkForComodification方法。

//AbstractList$Itr#checkForComodification
final void checkForComodification {
if (modCount != expectedModCount)
throw new ConcurrentModificationException;
}

如果當前運行環境是單線程，不論對列表進行何種操作何時增加、修改、刪除等，excpectedModCount總是會等於modCount，但是如果當前運行環境是多線程，很有可能一個線程在迭代遍歷，而另一個線程在對其進行新增或者修改等，JDK則不允許這麼做，此時則會拋出ConcurrentModificationException異常，這就是modCount變數在此起的作用。 回到ArrayList#add方法，當列表容量不足時，此時會調用grow方法進行擴容。

//ArrayList#grow
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //擴容策略為，每次新增容量的大小為舊容量的一半。也就是說如果默認容量為10，則第一次擴容大小為10 / 2 = 5，第二次擴容大小為15 / 2 = 7。
if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //擴容策略擴得太小 if (newCapacity - MAX_ARRAY_SIZE > 0) //擴容策略擴得太大，大於最大數組大小時，最多等於Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);

elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList獲取指定索引位置的元素get方法。

public E get(int index) {
rangeCheck(index); //檢查索引是否越界
return elementData(index);
}

由於ArrayList是由基於數組實現，故此方法較為簡單，判斷是否越界，沒有則根據數組下標來索引返回元素即可。remove方法刪除指定位置的元素。

//ArrayList#remove
public E remove(int index) {
rangeCheck(index); //檢查索引是否越界
modCount++; //記錄modCount，上面已提及
E oldValue = elementData(index); //取出指定索引元素
int numMoved = size - index - 1; //移動的元素個數
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; //將最後一個數組元素置為null，方便GC

return oldValue;
}

代碼比較簡單，同樣也體現了基於數組實習的ArrayList在刪除指定元素時的效率問題。有關Arrays. copyOf和System.arraycopy方法可參考《System.arraycopy(src, srcPos, dest, destPos, length) 與 Arrays.copyOf(original, newLength)區別》

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！