0x00 前言

大家好，我是 ArrayList拄衰， 應該是大家都耳熟能詳?shù)娜萜髦涣烁蛏荨W習一下內(nèi)中原理鬼癣，還是很有必要的陶贼。至于為什么叫淺析呢，因為本文不會分析 Arrays 的相關(guān)方法待秃。為什么不分析 Arrays 的相關(guān)方法骇窍，就是淺析了呢？那就接著往下看~（本文分析源碼基于jdk1.8锥余。本文基于第一人稱描述腹纳，我 == ArrayList。）

0x01 一句話介紹

我實際上就是一個可以自動擴容的數(shù)組驱犹，并可以進行增刪改查等操作嘲恍。

0x02 概述

我是list接口的一個可擴容實現(xiàn)。通過 Java 的泛型機制雄驹，我可以容納任何類型的對象佃牛。我和 Vector 非常像，但我是線程不安全的医舆，而他是線程安全的俘侠，其他地方的差異很小。

我所有方法中蔬将，時間復雜度為O(1)的有：

• size
• get
• isEmpty
• set
• iterator
• listIterator
  而add方法是O(n)的爷速。

我的每個實例，都有一個capacity變量霞怀。那么這個變量是干嘛的呢惫东？這個變量用于衡量我內(nèi)在的數(shù)組用來裝變量的長度，他總是大于等于 size 毙石。當添加一個元素到我這里廉沮，他會自動的增長，以滿足需要徐矩。

如果一個應用他需要往我這里放置很多的元素滞时，那最好一開始就設置我的 ensureCapacity 變量，這樣我一開始就申請很多的空間滤灯，而不用我一次次擴容浪費時間了坪稽。

請注意，我不是線程安全的力喷！如果多個線程同時修改我刽漂，一個要設置同步，否則會出現(xiàn)數(shù)據(jù)錯誤的情況弟孟，這個鍋贝咙，我是不背的。簡單的方式就是用Collections#synchronizedList來包裝一下我拂募，我就變成一個同步的容器了庭猩。

我同樣擁有fail-fast機制窟她，如果你迭代我，同時又修改我蔼水，我就會拋出ConcurrentModificationException異常震糖，讓你承受。多線程同時修改迭代趴腋，也會出現(xiàn)這個問題吊说。

0x03 解釋幾個變量

private static final int DEFAULT_CAPACITY = 10

默認的數(shù)組大小。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}

如果構(gòu)造我時优炬，采用的是默認的 capacity 颁井，就使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 來當做默認的空數(shù)組。

private static final Object[] EMPTY_ELEMENTDATA = {}

capacity == 0 蠢护，則使用 EMPTY_ELEMENTDATA 來當做默認的空數(shù)組雅宾。此時，產(chǎn)生了一個疑問葵硕，為什么要弄兩個這樣的變量呢眉抬？后面我們在擴容的時候可以看到，他們是用來區(qū)分到底是被設置了 capacity 是 0 懈凹，還是使用了默認的 capacity蜀变。那區(qū)分這個干嘛呢？那就往下看看擴容是怎么擴的蘸劈。

transient Object[] elementData

先解釋一下 transient 這個昏苏，這個主要是讓此變量不進行序列化。更多的可以谷歌一下威沫，看看詳解，此處就略過了洼专。這個就是我的核心部件棒掠，我所有的元素都放在他里面！實質(zhì)就是一個 Object 數(shù)組屁商！

private int size

想要知道我里面到底有多少個元素烟很？喏，size 就是我所擁有的元素數(shù)量蜡镶。

0x04 方法分析

構(gòu)造函數(shù)分析

// 擁有設置 capacity 參數(shù)的構(gòu)造函數(shù)
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {  // 如果設置的 initialCapacity 初始值大于0雾袱，那我的數(shù)組就初始相應的長度
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) { 
        // 如果設置了 0 ，那就用 EMPTY_ELEMENTDATA 來初始化我的數(shù)組官还。
        this.elementData = EMPTY_ELEMENTDATA;
    } else { // 小于 0 芹橡，拋出異常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 無參構(gòu)造
public ArrayList() {
    // 直接用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 來初始化我的數(shù)組。
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 還有其他構(gòu)造函數(shù)望伦，此處略去不講林说。

size()

此方法用于查看我有多少個元素煎殷，來看看實現(xiàn)。

public int size() {
    // 非常簡單腿箩，就是返回 size 變量豪直。
    return size;
}

get(int index)

get 方法用來返回指定索引處的元素。

public E get(int index) {
    // 檢查索引是否越界
    rangeCheck(index);
    // 直接根據(jù)索引返回元素
    return elementData(index);
}

private void rangeCheck(int index) {
    // 可以看到珠移，如果索引大于等于 size弓乙，將會拋出異常。所以在使用時一定要注意不能傳入錯誤的索引钧惧，導致程序異常唆貌。
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

set(int index, E element)

這個方法相當于修改操作。

public E set(int index, E element) {
    // 檢查邊界
    rangeCheck(index);
    // 先拿到老的元素
    E oldValue = elementData(index);
    // 對應位置附上新元素
    elementData[index] = element;
    // 返回老元素垢乙。所以 set 方法的返回是對應的舊元素锨咙。
    return oldValue;
}

add(E e)

這個方法相當于增加操作。

public boolean add(E e) {
    // 確保數(shù)組空間充足
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 將元素放到原數(shù)組長度后面一位追逮。
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    // 這里使用了 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 酪刀。
    // 這個變量是在我初始化時，使用了默認的 capacity 的時候钮孵，用來初始化數(shù)組的骂倘。
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 在這種情況下， 將入?yún)⒑?默認 capacity 進行比較巴席，取其較大大者历涝。
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 根據(jù)上面的操作，決定了使用什么長度來擴容漾唉。下面來進行擴容荧库。
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // 如果會執(zhí)行這個操作，就代表會改變數(shù)組赵刑，則將改變標志位+1.
    modCount++;

    // 原文注釋這里說可能會有內(nèi)存溢出
    if (minCapacity - elementData.length > 0) // 如果大于數(shù)組長度分衫，則進行擴容。
        grow(minCapacity);
}

// 我內(nèi)部的數(shù)組最大可以這么大般此，為什么減了個8呢蚪战？因為有些VM底層實現(xiàn)，保留了一些內(nèi)部字段铐懊，致使留給用戶的長度就變小了邀桑。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // 要注意是否會溢出。
    // 先保存數(shù)組的原長度科乎。
    int oldCapacity = elementData.length;
    // 新長度是原長度的1.5倍壁畸。（右移相當于除以2，所以加起來是1.5倍）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0) // 如果新長度小于入?yún)㈤L度喜喂，則新長度賦值為入?yún)㈤L度瓤摧。
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新長度大于數(shù)組最大長度竿裂，則調(diào)用 hugeCapacity 方法獲取長度。
        newCapacity = hugeCapacity(minCapacity);
    // 調(diào)用了 Arrays 的方法照弥，對數(shù)組進行了一個復制腻异。
    // 底層就不解釋了，可以簡單理解為把原 elementData 數(shù)組中的值这揣，一個個都搬移到了新的長度為 newCapacity 的數(shù)組中悔常，然后讓 elementData 指向新數(shù)組。
    //（由于沒有解析 Arrays.copy 方法给赞，所以本文只能算淺析机打，后面相關(guān)操作，也不會進行解析片迅。要解析的話残邀，一篇文章可能就放不下了。以后專開文章介紹這些工具類柑蛇。）
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 如果 傳遞進來的參數(shù)小于0芥挣，則直接拋異常，此時數(shù)組已經(jīng)放不下了耻台。
        // 什么時候會小于0呢空免？可以看到參數(shù)是通過 index + 1 傳遞進來的，當index 已經(jīng)到達了 Integer.MAX_VALUE盆耽，則會出現(xiàn)此情況蹋砚。
        throw new OutOfMemoryError();
    // 發(fā)現(xiàn)參數(shù)比設置的最大長度還要大，那行吧摄杂，那就返回最大值坝咐，不然就直接返回最大的數(shù)組長度。
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

add(int index, E element)

這個方法實際上是一個插入操作匙姜。

public void add(int index, E element) {
    // 范圍檢查
    rangeCheckForAdd(index);

    // 容量檢查
    ensureCapacityInternal(size + 1);  // modCount增加了
    // 直接調(diào)用了 System.arraycopy 方法畅厢。
    // 這里也不去分析他底層的源碼，去分析也不太容易氮昧，他實際上是一個 native 方法，要看只能去看 jni 層的代碼了浦楣。
    // 解釋一下現(xiàn)在參數(shù)所表示的意思：就是將數(shù)組根據(jù)傳入的 index 分成兩部分袖肥，然后把后面一部分往后面整體移動一個位置，index位置留出空位振劳。
    // 第一個參數(shù)表示源數(shù)組
    // 第二個參數(shù)表示從哪個位置開始復制
    // 第三個參數(shù)表示復制到哪個數(shù)組中
    // 第四個參數(shù)表示復制從哪里開始
    // 第五個參數(shù)表示復制多少位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 將 index 位置進行填充
    elementData[index] = element;
    // 長度自增
    size++;
}
舉個??解釋一下 System.arraycopy 的操作椎组。
有一個數(shù)組如下：
[0,1,2,3,4,5,6,null,null,null]
現(xiàn)在如果要在第二位插入一個數(shù)字7.
第一步：找到第2個位置，是2历恐；
第二步：把第二位開始的字段整體往后遷移一位寸癌，變成：[0,1,2,2,3,4,5,6,null,null]
此時數(shù)組已經(jīng)移動完畢专筷，再進行賦值即可。

通過源碼的分析蒸苇，可以看到插入實際上是先對數(shù)組進行復制移動磷蛹，耗費巨大。所以應當避免此操作溪烤。

remove(int index)

此即刪除操作味咳。

public E remove(int index) {
    // 邊界檢查
    rangeCheck(index);
    // 修改計數(shù)
    modCount++;
    // 找到舊值
    E oldValue = elementData(index);
    // 計算需要移動多少個元素。
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 和 上面的 add 操作調(diào)用檬嘀，如出一轍槽驶。
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // 利于內(nèi)存回收
    // 返回舊值
    return oldValue;
}

可以發(fā)現(xiàn)，刪除操作也比較費勁鸳兽，除非是最后一個元素掂铐。

remove(Object o)

刪除指定元素，可以想象揍异，肯定是一個個的遍歷然后對比全陨，再執(zhí)行刪除操作。

public boolean remove(Object o) {
    // null 和 非 null 分開處理蒿秦，私以為烤镐，直接使用 Objects.equals 方法不就好了么。
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            // 可以看到他調(diào)用的是 equals 方法棍鳖，然而沒有調(diào)用 == 來判斷是否是同一個對象炮叶。
            // 所以此處要注意，如果重寫了 equals 方法渡处，則同一個對象未必相等镜悉。這里可能就識別不到。
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
// 這個方法和 remove 的上一個方法里面的內(nèi)容一模一樣医瘫，不知道上個 remove 方法不用侣肄。
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

clear()

清空此 list。

public void clear() {
    modCount++;

    // 挨個賦值 null
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

contains(Object o) && indexOf(Object o)

為什么這兩個方法放在一起呢醇份，因為他們之間是好基友的關(guān)系稼锅。

public boolean contains(Object o) {
    // 可以看到，直接調(diào)用的 indexOf 方法僚纷。
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // 還是將 null 和 非 null 進行了區(qū)分處理矩距。是不是似曾相識的代碼！remove 不也這么做的么怖竭！
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

所以可以看到锥债， contains 和 indexOf 實際上都是對數(shù)組進行一個遍歷操作，所以使用一定要謹慎。而 Set 方法的 contains 方法是直接用的 hash 計算的哮肚，復雜度是 O(1).所以盡量用 Set 進行類似操作登夫。

subList(int fromIndex, int toIndex)

從字面上看，他就是返回一個我的孩子 list允趟。

public List<E> subList(int fromIndex, int toIndex) {
    // 邊界檢查
    subListRangeCheck(fromIndex, toIndex, size);
    // 返回一個 SubList 類恼策！竟然不是 ArrayList
    return new SubList(this, 0, fromIndex, toIndex);
}

看看內(nèi)部類 SubList 的聲明：
private class SubList extends AbstractList<E> implements RandomAccess
和 ArrayList 竟然不一樣。
那就看看構(gòu)造函數(shù)吧：

SubList(AbstractList<E> parent,
        int offset, int fromIndex, int toIndex) {
    // parent 當然就是我咯拼窥，ArrayList
    this.parent = parent;
    // 相對我的偏移量戏蔑，就是孩子是從哪開始截取的
    this.parentOffset = fromIndex;
    // 如果兒子也要生兒子，就是產(chǎn)生SubList鲁纠，則要計算相對爺爺?shù)钠屏孔芸茫酥稻褪菫榱藖碛嬎氵@個。
    // 如果要生重孫子改含，那就要計算相對于祖爺爺?shù)钠屏壳榱洹Ｗ幼訉O孫無窮盡也。
    this.offset = offset + fromIndex;
    // 計算孩子有多長捍壤。
    this.size = toIndex - fromIndex;
    // 繼承父親的更改計數(shù)骤视。
    this.modCount = ArrayList.this.modCount;
}
看一下 SubList 方法的 get 方法。
public E get(int index) {
    // 檢查邊界
    rangeCheck(index);
    // 檢查是否已經(jīng)被修改
    checkForComodification();
    // 吃驚嗎鹃觉？竟然直接修改的是父親的數(shù)組专酗。
    return ArrayList.this.elementData(offset + index);
}
private void checkForComodification() {
    // 和父親的修改計數(shù)進行一個對比，如果父親變了盗扇，則拋出異常祷肯。
    if (ArrayList.this.modCount != this.modCount)
        throw new ConcurrentModificationException();
}
......

可以看到，SubList 實際上并不是拿到了一個和原數(shù)組完全分離的數(shù)組疗隶，對于 SubList 的修改佑笋，全都會作用于父親這里。這就好比兒子惹得禍斑鼻，父親都要來背蒋纬。所以使用此方法一定要注意。同理坚弱，生兒子也要慎重蜀备！哈哈。

其他方法就先略過了

0x05 喝口水荒叶，來個總結(jié)

ArrayList 相對來說簡單些琼掠，但是其中也不乏 contains subList 這種需要注意的方法。知己知彼停撞，方能百戰(zhàn)不殆！

文中如有錯誤，請大家不吝賜教戈毒！感激不盡艰猬，與君共勉。