動态數組ArrayList源碼剖析

一、ArrayList是什麼

        ArrayList可以看成是一個動态的數組，它的内部是通過數組實作的。為什麼稱它為“動态”數組呢？因為ArrayList擁有“擴容”機制。當ArrayList的長度不夠的時候，它将會通過Arrays.copyof()方法，将其内部數組的長度進行增加操作。

二、ArrayList的特點

        為了記憶的友善，我的口訣是“序重步，資料結構”。

        順序：有序。原因是因為内部數組是有序的。

        重複：可重複。原因是數組的元素是可以重複的。

“快速失敗”的。

        資料結構：增删速度慢，查詢速度快。因為ArrayList内部是數組資料結構，是以它可以根據索引快速的定位到元素。增加和删除速度慢，原因是ArrayList需要将目前元素和它後面的所有元素向前或者向後移動一位。

        下面為上面的特點做一下簡單的解釋。

        快速失敗是：目前線程在疊代一個集合的時候，另外一個線程修改了你正在疊代的集合，這個時候會抛出異常。ArrayList是線程不安全的，是以可能會出現疊代ArrayList期間，另外一個線程修改了ArrayList集合中的元素，導緻異常發生。

        安全失敗是：準備疊代一個集合的時候，先将這個集合複制一個副本出來。目前線程疊代的是這個副本集合，另外一個線程修改的是原來的集合，是以不會産生沖突，不會抛出異常。java.util.concurrent包下的所有集合都是“安全失敗”的。

        ArrayList為什麼查詢速度比LinkedList塊？LinkedList它也是List集合的實作類，是以它也是有序的。但是LinkedList是連結清單資料結構，它的每個集合元素隻知道自己的前一個元素和後一個元素的位址，而ArrayList是數組資料結構，數組是一段連續的記憶體空間。舉個例子，假如有很多人，排成長隊，這個時候要找5号的人就非常簡單，問都不用問，直接定位。假如不排成長隊，隻是随機站在很大的廣場裡面，但是每個人隻知道自己的前一個人和後一個人的位置，而且你隻知道第一個人的位置，這個時候你要找第5個人的時候你就得從第一個人開始問後面的是誰，一直問下去才知道第5個人在哪裡。例子出自：​​為什麼ArrayList查詢速度比較快​​

三、屬性及構造函數分析

        底層使用數組實作。就是這個elementData數組，它就是ArrayList内部用來存放元素的數組。

transient Object[] elementData;      

        size是指的是ArrayList中内部數組elementData存放的實際元素個數，而不是此數組的長度。

private int size;      

        ArrayList預設長度是10。也就是說，我們通過空參構造函數建立的ArrayList它在第一次添加元素的時候，它的内部數組的長度将會被擴充為10。

private static final int DEFAULT_CAPACITY = 10;      

        ArrayList有三種構造函數。分别是空參的，指定初始化大小的，另外一個是傳入一個Collection接口的實作類。

        空參的是最常見的，将底層數組elementData數組初始化為一個沒有任何元素的數組。

public ArrayList() {
        this.elementData = EMPTY_ELEMENTDATA;// public static final Object[] EMPTY_ELEMENTDATA = {};
    }      

        下面的這個是初始化指定大小的數組。目的是把elementData初始化為一個指定大小的Object類型的數組。      

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = {};
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }      

        第三種用的不是很多。把另外一個集合的元素存放到ArrayList中，size是ArrayList中實際元素的個數。

/* 參數是Collection,證明數組中已經要存儲c.size個元素 */  
    public MyArrayList(Collection<? extends E> c) {  
        super();  
        elementData = c.toArray();  
        size = c.size();  
    }      

四、添加元素

        添加元素的源碼如下。我們看到方法的第一行執行了ensureCapacityInternal(size + 1); 這個方法。這個方法是什麼意思呢？我們之前就提到過，size是這個ArrayList集合的實際元素個數，現在為這個集合元素添加了一個元素，那麼這個ArrayList中的實際元素個數就是size+1個了。為了確定elementData數組的容量夠用，我們得去檢查一下elementData數組的長度是否能容的下 size+1 個元素。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size] = e;
        size++;    //實際個數 +1
        return true;
    }      

        size+1傳遞給了minCapacity。minCapacity代表為了目前操作能夠成功，elementData必須要達到的長度。比如，現在實際個數有12個，添加一個元素要求elementData數組至少要有13個元素位置。代碼中，如果目前elementData數組沒有元素，那麼此時elementData必須要求達到的長度是10。DEFAULT_CAPACITY 就是最初分析到的那個空參情況下，ArrayList預設要被擴容的長度。

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == {}) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }      

        為了目前操作能夠成功，最小要求ArrayList的内部數組elementData的長度達到minCapacity。如果内部數組elementData的長度不能夠達到此次操作的最小要求的minCapacity長度的話，那麼就需要為内部數組elementData擴容。擴容方法就是grow()方法。這裡的modCount是給ArrayList的疊代器使用的，在并發操作被修改時，提供快速失敗行為。modCount可以看成是一種标記。

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //如果為了能夠操作成功的長度 > 原來的數組的長度
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }      

        擴容方法是ArrayList的核心，可以看到ArrayList的神秘之處不過就是下面的寥寥幾行代碼。   

private void grow(int minCapacity) {    
        //先擷取到elementData内部數組的 舊長度    
        int oldCapacity = elementData.length;    
        //将舊長度修改為1.5倍的舊長度。>>是位運算符，二進制中向右左移一位就是除以2    
        int newCapacity = oldCapacity + (oldCapacity >> 1);    
        //如果擴容後的新長度，仍然不能滿足 此次操作的最小長度    
        if (newCapacity - minCapacity < 0)    
            //那麼把 此次操作的最小長度 當作擴容後的新長度    
            newCapacity = minCapacity;    
        //将内部數組elementData複制成指定的新長度    
        elementData = Arrays.copyOf(elementData, newCapacity);    
    }      

        如果是在指定位置添加元素的話，隻需要把指定位置的元素及其後面的元素向後移動一位，騰出指定的位置出來，給新添加的元素。關于System.arraycopy(Object src,int srcPos,Object dest, int destPos,int length) 方法的解釋。

src:源數組； srcPos:源數組要複制的起始位置；

dest:目的數組； destPos:目的數組放置的起始位置； length:複制的長度。

将源數組src從srcPos索引處，複制length個元素，覆寫目标數組dest。從目标數組dest的destPos處開始覆寫，覆寫目标數組length個元素。

/* 在指定位置添加 */  
    public void add(int index, E element) {  
        ensureCapacityInternal(size + 1); // 保證數組有充足的空間，不行的話進行擴容，請參考上面的代碼
        // 将指定索引位置右端元素右移  
        System.arraycopy(elementData, index, elementData, index + 1, size - index);  
        elementData[index] = element;// 将新添加的元素，添加到剛剛騰出來的索引處
        size++;  //實際個數加一
    }      

        删除操作，傳回被删除的元素。

/* 删除指定角标上的元素 */  
    public E remove(int index) {  
        
        E oldValue = this.get(index);// 擷取指定索引的值
        int numMoved = size - index - 1;// 右邊準備向左移動的元素的個數  
        // 從被删除的元素的角标後面的第一個元素開始，直到elementData數組的最後一個元素，它們全部向前移動一位
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);  
        elementData[--size] = null;// 實際個數減一，數組最後一位置空  
        return oldValue;  
    }      

            其餘方法的實作都簡單易懂，有興趣的話可以參考JDK源碼和API文檔。

五、要點

        ArrayList的特點，口訣是：“序重步，資料結構”。有序，可重複，不同步。因為是數組資料結構，增删慢，查詢塊。