全網最硬核的原始碼分析之——ArrayList原始碼分析

一.ArrayList 資料結構

ArrayList 資料結構，就是一個陣列結構，如下圖：

圖中展示是長度為 10 的陣列，從 1 開始計數，index 表示陣列的下標，從 0 開始計數，elementData 表示陣列本身

1.1 重要變數

/**
 * 表示陣列的初始大小，默認是 10;
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 統計當前陣列被修改的版本次數，陣列結構有變動，就會 +1，
 * 該變數在AbstractList中
*/
protected transient int modCount = 0;

/**
 * 表示當前陣列的大小，型別 int，沒有使用 volatile 修飾，非執行緒安全的
 */
private int size;

二.原始碼分析

2.1 ArrayList 類注釋決議

• 允許 put null 值，會自動擴容；
• size、isEmpty、get、set、add 等方法時間復雜度都是 O (1)；
• 是非執行緒安全的，多執行緒情況下，推薦使用執行緒安全類：Collections#synchronizedList；
• 增強 for 回圈，或者使用迭代器迭代程序中，如果陣列大小被改變，會快速失敗，拋出例外，

2.2 初始化實作

原始碼決議：

ArrayList 有三種初始化辦法：無引數直接初始化、指定大小初始化、指定初始資料初始化，原始碼如下：

/**
 * 無引數直接初始化，陣列大小為空
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
  /**
     * 指定引數初始化
     */
    public ArrayList(Collection<? extends E> c) {
        //elementData 保存陣列的容器，默認為null
        elementData = c.toArray();
        //如果給定的集合有值
        if ((size = elementData.length) != 0) {
            // 如果集合元素不是Object,會轉換成Object
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 給定集合無值，則默認空陣列
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

注意事項：

• ArrayList 無參構造器初始化時，默認大小是空陣列，并不是大家常說的 10，10 是在第一次 add 的時候擴容的陣列值，

2.3 新增和擴容實作

原始碼決議：

新增就是往陣列中添加元素，主要分成兩步：

• 判斷是否需要擴容，如果需要執行擴容操作；
• 直接賦值，

新增：

public boolean add(E e) {
   //確保陣列大小是否足夠，不過則進行擴容，size為當前陣列大小
    ensureCapacityInternal(size + 1); 
    // 直接復制執行緒不安全
    elementData[size++] = e;
    return true;
}

擴容：

private void ensureCapacityInternal(int minCapacity) {
  //如果初始化陣列大小時，有給定初始值，以給定的大小為準，不走 if 邏輯
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //確保容積足夠
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {  
    //記錄陣列被修改
    modCount++;
    // 如果我們期望的最小容量大于目前陣列的長度，那么就擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//擴容，并把現有資料拷貝到新的陣列里面去
private void grow(int minCapacity) {
     int oldCapacity = elementData.length;
    // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果擴容后的值 < 我們的期望值，擴容后的值就等于我們的期望值
    if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    // 如果擴容后的值 > jvm 所能分配的陣列的最大值，那么就用 Integer 的最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
     // 通過復制進行擴容
     elementData = Arrays.copyOf(elementData, newCapacity);
    }

擴容的本質：

? 擴容是通過： Arrays.copyOf(elementData, newCapacity); 這行代碼實作的，這行代碼描述的本質是陣列之間的拷貝，擴容是會先新建一個符合我們預期容量的新陣列，然后把老陣列的資料拷貝過去，我們通過 System.arraycopy 方法進行拷貝，此方法是 native 的方法，原始碼如下:

/**
*@param src 被拷貝的陣列
*@param srcPos 從陣列那里開始
*@param dest 目標陣列
*@param destPos 從目標陣列那個索引位置開始拷貝
*@param length 拷貝的長度
*此方法是沒有回傳值的，通過 dest 的參考進行傳值
 */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

注意事項：

• 擴容的規則并不是翻倍，是原來容量大小 + 容量大小的一半，擴容后的大小是原來容量的 1.5 倍；

• ArrayList 中的陣列的最大值是 Integer.MAX_VALUE，超過這個值，JVM 就不會給陣列分配記憶體空間了，新增時，并沒有對值進行嚴格的校驗，所以 ArrayList 是允許 null 值的，

• 原始碼在擴容的時候，有陣列大小溢位，就是說擴容后陣列的大小下界不能小于 0，上界不能大于 Integer 的最大值，

• 擴容完成之后，賦值是非常簡單的，直接往陣列上添加元素即可：elementData [size++] = e，這種簡單賦值，沒有任何鎖控制，所以這里的操作是執行緒不安全的：

2.4 洗掉實作

原始碼決議：

ArrayList 洗掉元素有很多種方式，比如根據陣列索引洗掉、根據值洗掉或批量洗掉等等，我們選取根據值洗掉方式來進行原始碼說明：

public boolean remove(Object o) {
    // 如果要洗掉的值是 null，找到第一個值是 null 的洗掉
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
      // 如果要洗掉的值不為 null，找到第一個和要洗掉的值相等的洗掉
        for (int index = 0; index < size; index++)
        // 根據 equals 來判斷值相等，相等后再根據索引位置進行洗掉
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

上面代碼已經找到要洗掉元素的索引位置了，下面代碼是根據索引位置進行元素的洗掉：

private void fastRemove(int index) {
    // 記錄陣列的結構發生變動
    modCount++;
    // numMoved 表示洗掉 index 位置的元素后，需要從 index 后移動多少個元素到前面去
    // 減 1 的原因，是因為 size 從 1 開始算起，index 從 0開始算起
    int numMoved = size - index - 1;
    if (numMoved > 0)
    // 從 index +1 位置開始被拷貝，拷貝的起始位置是 index，長度是 numMoved 
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
   //陣列最后一個位置賦值 null，幫助 GC 
    elementData[--size] = null; 
}

注意事項：

• 新增的時候是沒有對 null 進行校驗的，所以洗掉的時候也是允許洗掉 null 值的；
• 找到值在陣列中的索引位置，是通過 equals 來判斷的，如果陣列元素不是基本型別，需要我們關注 equals 的具體實作，
• 某一個元素被洗掉后，為了維護陣列結構，我們都會把陣列后面的元素往前移動

三.時間復雜度

經過新增或洗掉方法的原始碼決議，對陣列元素的操作，只需要根據陣列索引，直接新增和洗掉，所以時間復雜度是 O (1)，

四.執行緒安全

4.1 出現執行緒安全原因

只有當 ArrayList 作為共享變數時，才會有執行緒安全問題，當 ArrayList 是方法內的區域變數時，是沒有執行緒安全的問題的，

ArrayList 有執行緒安全問題的原因，是因為 ArrayList 自身的 elementData、size、modConut 在進行各種操作時，都沒有加鎖，而且這些變數的型別并非是可見（volatile）的，所以如果多個執行緒對這些變數進行操作時，可能會有值被覆寫的情況，

類注釋中推薦我們使用 Collections#synchronizedList 來保證執行緒安全，SynchronizedList 是通過在每個方法上面加上鎖來實作，雖然實作了執行緒安全，但是性能大大降低，具體實作原始碼：

public boolean add(E e) {
    synchronized (mutex) {return c.add(e);}
}

我們也可以使用CopyOnWriteArrayList來保證執行緒安全 具體對比可以參考以下表格

4.2 保證執行緒安全方式的對比：

五.總結

ArrayList 底層是陣列結構， API 都是對陣列的操作進行封裝，讓使用者無需感知底層實作，只需關注如何使用即可，

推薦閱讀

全網最硬核的原始碼分析之——String原始碼分析

Spring Boot 自動化配置原理帶圖全面講解

MySQL 3大日志的作用

如果感覺對您有幫助，希望大家可關注一下，點個贊再走，感謝您的閱讀，