ArrayList常用方法的原始碼詳解

　　我相信幾乎所有的同學在大大小小的筆試、面試過程中都會被問及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 ArrayListpublic 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的参数构造成ArrayListpublic ArrayList(Collection<? extends E> 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=6260652if (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<String> list = new ArrayList<String>();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<String> 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#addpublic boolean add(E e) {
    ensureCapacityInternal(size + 1);  //确保容量是否充足elementData[size++] = e;    //将元素添加至数组return true;
}

//ArrayList#ensureCapacityInternalprivate void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);     //如果此时还没有初始化列表容量大小，则对其初始化，默认容量为10    }
    ensureExplicitCapacity(minCapacity); //检查容量是否充足}

//ArrayList#ensureEcplicitCapacityprivate 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$Itrint expectedModCount = modCount;

　　在AbstractList$Itr#next中呼叫了checkForComodification方法。

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

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

//ArrayList#growprivate 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_VALUEnewCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

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

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

//ArrayList#removepublic 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，方便GCreturn oldValue;
}

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

以上是ArrayList常用方法的原始碼詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！