ArrayList核心源碼解析

一、基本方法解析

1、構(gòu)造器

ArrayList有三種創(chuàng)建方式

ArrayList的底層實(shí)現(xiàn)方式為數(shù)組，在創(chuàng)建ArrayList時(shí)，底層會(huì)創(chuàng)建數(shù)組對(duì)象Object[]

1.1 無參構(gòu)造器


private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

通過這種方式創(chuàng)建ArrayList，底層對(duì)創(chuàng)建一個(gè)空的數(shù)據(jù)，這個(gè)數(shù)組對(duì)象是 static final 類型的，即該數(shù)組對(duì)象在初始化的是否就會(huì)被創(chuàng)建，并且不能夠被改變。

1.2 自帶數(shù)組長(zhǎng)度的的構(gòu)造方式

private static final Object[] EMPTY_ELEMENTDATA = {};

transient Object[] elementData;

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

不難看出，這種方式在創(chuàng)建ArrayList對(duì)象時(shí)，會(huì)進(jìn)行一系列的判斷，根據(jù)你傳入的參數(shù)不同，進(jìn)行不同的構(gòu)造方式。

  • ① 當(dāng)傳入的數(shù)組長(zhǎng)度值大于0時(shí)，會(huì)創(chuàng)建一個(gè)特定長(zhǎng)度的數(shù)組對(duì)象。
  • ② 當(dāng)傳入的數(shù)組長(zhǎng)度值等于0時(shí)，會(huì)創(chuàng)建一個(gè)空的Object數(shù)組對(duì)象，基本上跟無參的構(gòu)造方法是一樣。
  • ③ 第三種情況就是你傳入的參數(shù)是非法參數(shù)，那么，會(huì)拋出異常“Illegal Capacity: initialCapacity”。

這里要特別注意的是，elementData數(shù)組對(duì)象被transient所描述，因?yàn)锳rraylist實(shí)現(xiàn)了java.io.Serializable接口，即在序列化的時(shí)候，Arraylist會(huì)使用Serializable的默認(rèn)序列化方式，而被transient關(guān)鍵字修飾的屬性會(huì)在序列化時(shí)被忽略，不進(jìn)行序列化。

1.3 傳入一個(gè)集合Collection對(duì)象，構(gòu)造ArrayList對(duì)象

transient Object[] elementData; 

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

2、元素的添加：add()、addAll()

Arraylist提供了四種的添加新增元素的方式，兩種add()，以及兩種addAll()。

2.1 直接在集合的結(jié)尾添加元素：add(E e)

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

在這個(gè)過程中，會(huì)做一下的操作：

  • ① 判斷當(dāng)前ArrayList對(duì)象的 elementData 屬性是否為空，如果為空，則判斷當(dāng)前你要傳入的集合長(zhǎng)度 size+1 和會(huì)提供的默認(rèn)集合長(zhǎng)度10的大小，拿較大的一個(gè)值作為集合長(zhǎng)度。如果 elementData 不為空，則直接拿傳入時(shí)的 size+1 作為當(dāng)前集合的長(zhǎng)度（size是在添加當(dāng)前數(shù)據(jù)之前集合的長(zhǎng)度）.

核心代碼1：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 判斷當(dāng)前集合的屬性elementData是否為空
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // DEFAULT_CAPACITY 默認(rèn)為 10，取較大的一個(gè)值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

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

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

    // 判斷新的集合長(zhǎng)度與數(shù)組長(zhǎng)度的大小
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
  • ② 把獲取到的集合的長(zhǎng)度與當(dāng)前數(shù)組elementData的長(zhǎng)度進(jìn)行比較，如果當(dāng)前集合的長(zhǎng)度小于其屬性對(duì)象elementData的長(zhǎng)度，則直接在當(dāng)前數(shù)組中數(shù)據(jù)的后面添加數(shù)據(jù)；如果當(dāng)前集合的長(zhǎng)度大于其屬性數(shù)組對(duì)象elementData的長(zhǎng)度，則需要增加數(shù)組的長(zhǎng)度（添加規(guī)則：在原有的數(shù)組長(zhǎng)度的基礎(chǔ)上在增加一半，作為一個(gè)新的數(shù)組長(zhǎng)度，在判斷新的長(zhǎng)度與當(dāng)前集合的長(zhǎng)度大小，如果新的數(shù)組長(zhǎng)度依然比集合長(zhǎng)度小，則直接把集合長(zhǎng)度作為數(shù)組長(zhǎng)度，否則，用新的數(shù)組長(zhǎng)度。然后再把這個(gè)新的數(shù)組長(zhǎng)度與可分配的數(shù)組的最大大小進(jìn)行比較，得到最終的新的數(shù)組大?。?，然后根據(jù)得到最新的數(shù)組長(zhǎng)度創(chuàng)建一個(gè)新的數(shù)組，把elementData中的數(shù)組copy到其中，再將這個(gè)新的數(shù)組賦值給elementData，然后把要添加的元素添加進(jìn)去。

核心代碼2：

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    // 獲取當(dāng)前的數(shù)組長(zhǎng)度
    int oldCapacity = elementData.length;
    // 新的數(shù)組長(zhǎng)度為：原來的數(shù)組長(zhǎng)度 + 原來數(shù)組長(zhǎng)度的1/2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 比較新的數(shù)組長(zhǎng)度與新的集合長(zhǎng)度的大小
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 比較新的數(shù)組長(zhǎng)度與jvm所允許的最大數(shù)組長(zhǎng)度    
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 創(chuàng)建一個(gè)新的數(shù)組，將原來的數(shù)組信息添加進(jìn)去，然后再賦值給elementData
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2.2 將某個(gè)元素添加到集合的指定位置

public void add(int index, E element) {
    // 首先判斷當(dāng)前傳入的位置是否合法，即在0-size之間
    rangeCheckForAdd(index);

    // 判斷是否需要添加數(shù)組長(zhǎng)度，此處的操作同上add()中的操作
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 用System.arraycopy()方法將數(shù)組index-1之后的所有數(shù)據(jù)往后移動(dòng)一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 在index的位置加入新的元素
    elementData[index] = element;
    // 更新size
    size++;
}

private void rangeCheckForAdd(int index) {
     if (index > size || index < 0)
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

基本錯(cuò)作流程如下：

  • ① 首先判斷當(dāng)前傳入的位置是否合法，即在0-size之間
  • ② 判斷是否需要添加數(shù)組長(zhǎng)度，此處的操作同上add()中的操作
  • ③ 用System.arraycopy()方法將數(shù)組index-1之后的所有數(shù)據(jù)往后移動(dòng)一位
  • ④ 在index的位置加入新的元素
  • ⑤ 更新size

2.3 將整個(gè)Collection對(duì)象中所有的元素添加到ArrayList中

public boolean addAll(Collection<? extends E> c) {
    // 通過toArray()方法將Collection轉(zhuǎn)化為數(shù)組a
    Object[] a = c.toArray();
    // 獲取傳入的集合的長(zhǎng)度
    int numNew = a.length;
    // 把 size + numNew 作為新的集合長(zhǎng)度，進(jìn)行數(shù)組的處理，同add()方法中的操作
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 使用System.arraycopy()方法將傳入的數(shù)據(jù)信息copy到 elementData 中
    System.arraycopy(a, 0, elementData, size, numNew);
    // 更新size
    size += numNew;
    return numNew != 0;
}

基本操作流程如下：

  • ① 通過toArray()方法將Collection轉(zhuǎn)化為數(shù)組a
  • ② 獲取傳入的集合的長(zhǎng)度
  • ③ 把 size + numNew 作為新的集合長(zhǎng)度，進(jìn)行數(shù)組的處理，同add()方法中的操作
  • ④ 使用System.arraycopy()方法將傳入的數(shù)據(jù)信息copy到 elementData 中
  • ⑤ 更新size

2.4 將整個(gè)Collection對(duì)性中的元素從特定位置開始全部加入到Arraylist

public boolean addAll(int index, Collection<? extends E> c) {
    // 首先判斷當(dāng)前傳入的位置是否合法，即在0-size之間
    rangeCheckForAdd(index);
    // 通過toArray()方法將Collection轉(zhuǎn)化為數(shù)組a
    Object[] a = c.toArray();
    // 獲取傳入的集合的長(zhǎng)度
    int numNew = a.length;
    // 把 size + numNew 作為新的集合長(zhǎng)度，進(jìn)行數(shù)組的處理，同add()方法中的操作
    ensureCapacityInternal(size + numNew);  // Increments modCount

    // 通過System.arraycopy()方法將原本elementData中index-1之后的所有元素向后移動(dòng) numNew位
    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    // 通過System.arraycopy()方法將傳入數(shù)組中的數(shù)據(jù)添加到elementData中
    System.arraycopy(a, 0, elementData, index, numNew);
    // 跟新size的值
    size += numNew;
    return numNew != 0;
}

基本操作流程如下：

  • ① 首先判斷當(dāng)前傳入的位置是否合法，即在0-size之間
  • ② 通過toArray()方法將Collection轉(zhuǎn)化為數(shù)組a
  • ③ 獲取傳入的集合的長(zhǎng)度
  • ④ 把 size + numNew 作為新的集合長(zhǎng)度，進(jìn)行數(shù)組的處理，同add()方法中的操作
  • ⑤ 通過System.arraycopy()方法將原本elementData中index-1之后的所有元素向后移動(dòng) numNew位
  • ⑥ 使用System.arraycopy()方法將傳入的數(shù)據(jù)信息copy到 elementData 中
  • ⑦ 更新size
?著作權(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)容