ArrayList源碼解析

ArrayList簡(jiǎn)介

ArrayList是一個(gè)實(shí)現(xiàn)了List接口的動(dòng)態(tài)數(shù)組，其容量能夠動(dòng)態(tài)增長(zhǎng)，其允許包括null在內(nèi)的所有元素。它繼承了AbstractList，實(shí)現(xiàn)了List、RandomAccess, Cloneable, java.io.Serializable。
因?yàn)槠浠跀?shù)組實(shí)現(xiàn)的特性，所以隨機(jī)訪問(wèn) get 和 set 效率較高，但是在于添加和刪除操作，由于要移動(dòng)數(shù)據(jù)，因此效率會(huì)低些。
需要注意的是，ArrayList中的操作不是線程安全的！如果多線程同時(shí)訪問(wèn) ArrayList ，而其中有個(gè)線程對(duì)表結(jié)構(gòu)做了修改，則它可能會(huì)拋出錯(cuò)誤。所以，建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList。下面我們就了解一下ArrayList一些常用的方法屬性，以及一些需要注意的地方。

本文轉(zhuǎn)自ArrayList源碼分析（基于JDK8），本人僅在自己的理解上做了些許的修改。

ArrayList屬性

屬性中比較重要的兩個(gè)就是用于記錄當(dāng)前數(shù)組長(zhǎng)度的 size，以及元素的緩存數(shù)組 elementData，除此之外還有一個(gè)經(jīng)常用到的屬性就是從AbstractList繼承過(guò)來(lái)的modCount屬性，代表ArrayList集合的修改次數(shù)。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {  
    // 序列化id  
    private static final long serialVersionUID = 8683452581122892189L;  
    // 默認(rèn)初始的容量  
    private static final int DEFAULT_CAPACITY = 10;  
    // 用于空實(shí)例的共享空數(shù)組實(shí)例
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 為默認(rèn)大小的空實(shí)例構(gòu)建的共享空數(shù)組實(shí)例。
    // 和 EMPTY_ELEMENTDATA 區(qū)別在于添加第一個(gè)元素需要膨脹多少
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 當(dāng)前數(shù)據(jù)對(duì)象存放地方，當(dāng)前對(duì)象不參與序列化  
    transient Object[] elementData;  
    // 當(dāng)前數(shù)組長(zhǎng)度  
    private int size;  
    // 數(shù)組最大長(zhǎng)度  
    private static final int MAX_ARRAY_SIZE = 2147483639;  

    // 省略方法。。  
}

ArrayList 構(gòu)造方法

無(wú)參構(gòu)造方法

如果不傳入?yún)?shù)，則使用默認(rèn)無(wú)參構(gòu)建方法創(chuàng)建ArrayList對(duì)象，如下：

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

注意：此時(shí)我們創(chuàng)建的ArrayList對(duì)象中的elementData中的長(zhǎng)度是1，size是0,當(dāng)進(jìn)行第一次add的時(shí)候，elementData將會(huì)變成默認(rèn)的長(zhǎng)度：10.

帶int類型的構(gòu)造函數(shù)

傳入的參數(shù)用于指定初始數(shù)組長(zhǎng)度，若參數(shù)大于等于0，則給elementData 賦予對(duì)應(yīng)長(zhǎng)度的Object數(shù)組，
若參數(shù)小于0，則拋出IllegalArgumentException異常，構(gòu)造方法如下：

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

帶Collection對(duì)象的構(gòu)造函數(shù)

構(gòu)造一個(gè)包含指定 Collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。
其內(nèi)部實(shí)現(xiàn)大致為：

  1. 將 Collection 對(duì)象轉(zhuǎn)為數(shù)組，然后將數(shù)組的地址的賦給elementData。
  2. 更新size的值，同時(shí)判斷size的大小，如果是size等于0，直接將空對(duì)象EMPTY_ELEMENTDATA的地址賦給elementData
  3. 如果size的值大于0，且 elementData 的 class 不等于 Object 數(shù)組的 class，則執(zhí)行Arrays.copyOf方法，把 Collection對(duì)象的內(nèi)容（可以理解為深拷貝）copy到 elementData 中。

注意：this.elementData = arg0.toArray(); 這里執(zhí)行的簡(jiǎn)單賦值時(shí)淺拷貝，所以要執(zhí)行Arrays,copy 做深拷貝

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;
    }
}

常用方法

add 方法

add(E e) 方法

此方法將指定的元素添加到列表的尾部中，內(nèi)部實(shí)現(xiàn)邏輯如下：

  1. 確保數(shù)組已使用長(zhǎng)度（size）加1之后足夠存入下一個(gè)數(shù)據(jù)
  2. 修改次數(shù)modCount 標(biāo)識(shí)自增1，如果當(dāng)前數(shù)組已使用長(zhǎng)度（size）加1后的大于當(dāng)前的數(shù)組長(zhǎng)度，則調(diào)用grow方法，增長(zhǎng)數(shù)組，grow方法會(huì)將當(dāng)前數(shù)組的長(zhǎng)度變?yōu)樵瓉?lái)容量的1.5倍。
  3. 確保新增的數(shù)據(jù)有地方存儲(chǔ)之后，則將新元素添加到位于size的位置上，size自增1
  4. 成功返回 true

添加元素方法入口：

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

確保添加的元素有地方存儲(chǔ)：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
    }

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

將修改次數(shù)（modCount）自增1，判斷是否需要擴(kuò)充數(shù)組長(zhǎng)度，判斷條件就是用當(dāng)前所需的數(shù)組最小長(zhǎng)度與數(shù)組的長(zhǎng)度對(duì)比，如果大于0，則增長(zhǎng)數(shù)組長(zhǎng)度。

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

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

如果當(dāng)前的數(shù)組已使用空間（size）加1之后大于數(shù)組長(zhǎng)度，則增大數(shù)組容量，擴(kuò)大為原來(lái)的1.5倍。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

add(int index, E element) 方法

這個(gè)方法其實(shí)和上面的add類似，該方法可以按照元素的位置，指定位置插入元素，其后的元素往后移動(dòng)一位，具體的執(zhí)行邏輯如下：

  1. 越界檢查，否則拋出異常
  2. 確保數(shù)組已使用長(zhǎng)度（size）加1之后足夠存入下一個(gè)數(shù)據(jù)
  3. 修改次數(shù)（modCount）標(biāo)識(shí)自增1，如果當(dāng)前數(shù)組已使用長(zhǎng)度（size）加1后的大于當(dāng)前的數(shù)組長(zhǎng)度，則調(diào)用grow方法，增長(zhǎng)數(shù)組
  4. grow方法會(huì)將當(dāng)前數(shù)組的長(zhǎng)度變?yōu)樵瓉?lái)容量的1.5倍。
  5. 確保有足夠的容量之后，使用System.arraycopy 將需要插入的位置（index）后面的元素統(tǒng)統(tǒng)往后移動(dòng)一位。
  6. 將新的數(shù)據(jù)內(nèi)容存放到數(shù)組的指定位置（index）上
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
    elementData[index] = element;
    size++;
}

注意：使用該方法的話將導(dǎo)致指定位置后面的數(shù)組元素全部重新移動(dòng)，即往后移動(dòng)一位。

get方法

返回此列表中指定位置上的元素

public E get(int index) {
    rangeCheck(index);  // 若 index >= size，則拋出異常

    return elementData(index);
}

set方法

public E set(int index, E element) {
    rangeCheck(index); 若 index >= size，則拋出異常

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
  }

contains方法

直接調(diào)用了 indexOf 方法，若返回小于 0 則返回 false。

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/**
 * 返回此列表中首次出現(xiàn)的指定元素的索引, 或如果此列表不包含元素，則返回 -1。
 */
public int indexOf(Object o) {
    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;
}

remove方法

根據(jù)索引remove

  1. 越界檢查，否則拋出異常
  2. modCount 自增1
  3. 將指定位置（index）上的元素保存到oldValue
  4. 將指定位置（index）上的元素都往前移動(dòng)一位
  5. 將最后面的一個(gè)元素置空，好讓垃圾回收器回收
  6. 將原來(lái)的值oldValue返回
/**
 * 移除此列表中指定位置上的元素。向左移動(dòng)所有后續(xù)元素（將其索引減 1）。
 */
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    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

    return oldValue;
}

注意：調(diào)用這個(gè)方法不會(huì)縮減數(shù)組的長(zhǎng)度，只是將最后一個(gè)數(shù)組元素置空而已。

根據(jù)對(duì)象remove

循環(huán)遍歷所有對(duì)象，得到對(duì)象所在索引位置，然后調(diào)用fastRemove方法，執(zhí)行remove操作

/**
* 移除此列表中首次出現(xiàn)的指定元素（如果存在）。如果列表不包含此元素，則列表不做改動(dòng)。
*/
public boolean remove(Object o) {
    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++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

定位到需要remove的元素索引，先將index后面的元素往前面移動(dòng)一位（調(diào)用System.arraycooy實(shí)現(xiàn)），然后將最后一個(gè)元素置空。

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方法

modCount 自增，當(dāng)前數(shù)組長(zhǎng)度內(nèi)的所有元素賦為 null，并把 size 置 0

/**
 * 移除此列表中的所有元素。此調(diào)用返回后，列表將為空。
 */
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

sublist方法

我們看到代碼中是創(chuàng)建了一個(gè)ArrayList 類里面的一個(gè)內(nèi)部類SubList對(duì)象，傳入的值中第一個(gè)參數(shù)時(shí)this參數(shù)，其實(shí)可以理解為返回當(dāng)前l(fā)ist的部分視圖，真實(shí)指向的存放數(shù)據(jù)內(nèi)容的地方還是同一個(gè)地方，如果修改了sublist返回的內(nèi)容的話，那么原來(lái)的list也會(huì)變動(dòng)。

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

trimToSize方法

  1. 修改次數(shù)加1
  2. 將elementData中空余的空間（包括null值）去除，例如：數(shù)組長(zhǎng)度為10，其中只有前三個(gè)元素有值，其他為空，那么調(diào)用該方法之后，數(shù)組的長(zhǎng)度變?yōu)?。Arrays.copyOf返回的是一個(gè)新數(shù)組，因此達(dá)到了節(jié)省空間的效果
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

iterator方法

interator方法返回的是一個(gè)內(nèi)部類，由于內(nèi)部類的創(chuàng)建默認(rèn)含有外部的this指針，所以這個(gè)內(nèi)部類可以調(diào)用到外部類的屬性。

public Iterator<E> iterator() {
    return new Itr();
}

Iterator 的 next方法

一般的話，調(diào)用完iterator之后，我們會(huì)使用iterator做遍歷，這里使用next做遍歷的時(shí)候有個(gè)需要注意的地方，就是調(diào)用next的時(shí)候，可能會(huì)引發(fā)ConcurrentModificationException，當(dāng)修改次數(shù)，與期望的修改次數(shù)（調(diào)用iterator方法時(shí)候的修改次數(shù)）不一致的時(shí)候，會(huì)發(fā)生該異常，詳細(xì)我們看一下代碼實(shí)現(xiàn)：

@SuppressWarnings("unchecked")
public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

expectedModCount這個(gè)值是在用戶調(diào)用ArrayList的iterator方法時(shí)候確定的，但是在這之后用戶add，或者remove了ArrayList的元素，那么modCount就會(huì)改變，那么這個(gè)值就會(huì)不相等，將會(huì)引發(fā)ConcurrentModificationException異常，這個(gè)是在多線程使用情況下，比較常見的一個(gè)異常。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

Iterator 的 remove方法

cursor 記錄了當(dāng)前元素索引，lastRet則記錄了上一元素的索引，調(diào)用迭代器自帶的remove方法，先調(diào)用了ArrayList的remove方法后，
會(huì)把操作次數(shù)modCount賦給expectedModCount，因此不會(huì)引發(fā)異常。

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

System.arraycopy 方法

參數(shù) 說(shuō)明
src 原數(shù)組
srcPos 原數(shù)組
dest 目標(biāo)數(shù)組
destPos 目標(biāo)數(shù)組的起始位置
length 要復(fù)制的數(shù)組元素的數(shù)目

Arrays.copyOf方法

original - 要復(fù)制的數(shù)組
newLength - 要返回的副本的長(zhǎng)度
newType - 要返回的副本的類型

其實(shí)Arrays.copyOf方法返回的是一個(gè)全新數(shù)組，其底層也是調(diào)用System.arraycopy實(shí)現(xiàn)的，源碼如下：

public static int[] copyOf(int[] original, int newLength) {   
   int[] copy = new int[newLength];   
   System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));   
   return copy;   
}

小結(jié)

ArrayList總體來(lái)說(shuō)比較簡(jiǎn)單，不過(guò)ArrayList還有以下一些特點(diǎn)：

  • ArrayList自己實(shí)現(xiàn)了序列化和反序列化的方法，因?yàn)樗约簩?shí)現(xiàn)了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法
  • ArrayList基于數(shù)組方式實(shí)現(xiàn)，無(wú)容量的限制（會(huì)擴(kuò)容）
    添加元素時(shí)可能要擴(kuò)容（所以最好預(yù)判一下），刪除元素時(shí)不會(huì)減少容量（若希望減少容量，trimToSize()），刪除元素時(shí)，將刪除掉的位置元素置為null，下次gc就會(huì)回收這些元素所占的內(nèi)存空間 。
  • 線程不安全
  • add(int index, E element)：添加元素到數(shù)組中指定位置的時(shí)候，需要將該位置及其后邊所有的元素都整塊向后復(fù)制一位
  • get(int index)：獲取指定位置上的元素時(shí)，可以通過(guò)索引直接獲?。∣(1)）
  • remove(Object o)需要遍歷數(shù)組
  • remove(int index)不需要遍歷數(shù)組，只需判斷index是否符合條件即可，效率比remove(Object o)高
  • contains(E)需要遍歷數(shù)組
  • 使用iterator遍歷可能會(huì)引發(fā)多線程異常
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容