• 1 概述
• 2 底層資料結構
• 3 建構式
• 4 自動擴容
• 5 set() get() remove()
• 6 Fail-Fast機制

1 概述

1. ArrayList實作了List介面，是 順序容器，允許放入null元素
2. 有一個容量(capacity)，表示底層陣列的實際大小，如果容量不足，容器會 自動增大底層陣列的大小
3. 支持泛型，泛型擦除后，容器的元素都是 Object型別
4. ArrayList沒有實作同步(synchronized)，因此它是 執行緒不安全的，（vector執行緒安全）
5. 關于陣列：一旦陣列初始化完成，則長度不可改變 因此ArrayList擴容時會涉及陣列的拷貝

2 底層資料結構

兩個重要成員變數

1. Object[] elementData：

存盤串列元素的陣列；該陣列的長度就是串列的容量
串列的容量是指它所能存盤元素的最大個數

2. size：

串列的大小，指當前串列包含的元素個數，跟容量不是一個概念

size 跟 elementData陣列長度是不一樣的，elementData 允許長度大于元素的個數

    transient Object[] elementData; //存盤串列元素的陣列
    private int size;//元素的數量
    protected transient int modCount = 0; //list的修改次數

3 建構式

有三個建構式：

• 指定初始容量大小時，創建一個容量為引數的Object陣列，并賦值給資料陣列
• 不指定初始容量大小時，資料陣列賦值為一個無限容量的空陣列
• 構造引數為集合型別，將引數轉換成Object型別陣列，并賦值給資料陣列
• 注意，只有當第一次add元素時，才會指定陣列的長度

參照原始碼：

    //指定初始容量大小時，創建一個容量為引數的Object陣列，并賦值給資料陣列
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = https://www.cnblogs.com/knowledgeispower/p/new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
// 不指定初始容量大小時，資料陣列賦值為一個無限容量的空陣列
    public ArrayList() {
        this.elementData = https://www.cnblogs.com/knowledgeispower/p/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
// 構造引數為集合型別，將引數轉換成Object型別陣列，并賦值給資料陣列
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

4 自動擴容

1. 添加元素時，會判斷添加后是否超出當前陣列長度，超出則會執行陣列擴容；
2. 陣列擴容時，會將老陣列中的元素重新 拷貝一份到新的陣列中，（因為陣列長度不可變，因此需要創建新陣列）
3. 陣列執行擴容，擴容后的容量為擴容前的 1.5倍
4. 盡可能評估所需要容量的大小，避免擴容，（因為擴容占用更多的記憶體）

參考原始碼:

重點！！！！！：添加前，都判斷是否需要擴容：（如果size+1后，超過elementData的長度，則執行擴容，擴容為原來的1.5倍）

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // size 初始化時是0，
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//計算所需容量:第一次添加時，容量為10；反則，容量為當前長度+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData =https://www.cnblogs.com/knowledgeispower/p/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10,即第一次添加時，陣列長度變為10
    }
    return minCapacity;//如果陣列不為空時，最小長度是當前長度+1
}

//再次計算陣列所需容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//串列修改次數遞增
    //所需容量大于陣列的長度,則執行擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//擴容，陣列的記憶體狀態已經發生變化了
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//  新的長度為舊長度的1.5倍  【右移1位（除以2）】
    if (newCapacity - minCapacity < 0)  // 如果擴容后的長度小于所需要的最小長度，則使用最小長度(基本不會發生)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)  //這里是極限的情況，即逼近陣列分配的最大記憶體空間
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);  // 執行陣列拷貝
}

5 set() get() remove()

• set()方法也就變得非常簡單，直接對陣列的指定位置賦值即可，

public E set(int index, E element) {
    rangeCheck(index);//下標越界檢查
    E oldValue = https://www.cnblogs.com/knowledgeispower/p/elementData(index);
    elementData[index] = element;//賦值到指定位置，復制的僅僅是參考
    return oldValue;//回傳原先位置上的元素
}

• get()方法同樣很簡單，唯一要注意的是由于底層陣列是Object[]，得到元素后需要進行型別轉換，

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意型別轉換
}

• remove()方法也有兩個版本，一個是remove(int index)洗掉指定位置的元素，另一個是remove(Object o)洗掉第一個滿足o.equals(elementData[index])的元素，洗掉操作是add()操作的逆程序，需要將洗掉點之后的元素向前移動一個位置，需要注意的是為了讓GC起作用，必須顯式的為最后一個位置賦null值，

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = https://www.cnblogs.com/knowledgeispower/p/elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //清除該位置的參考，讓GC起作用
    return oldValue;
}

6 Fail-Fast機制

ArrayList也采用了快速失敗的機制，通過記錄 modCount 引數來實作，在面對并發的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發生任意不確定行為的風險，

標籤：Java

上一篇：資料脫敏的 3 種常見方案，好用到爆！

下一篇：設計模式之單例設計模式