Java集合框架——ArrayList源碼

本文通過源碼來總結(jié)一下ArrayList

ArrayList

ArrayList 底層上是一個動態(tài)數(shù)組

屬性
// 默認(rèn)初始容量
private static final int DEFAULT_CAPACITY = 10;

// 指定容量為0時，數(shù)組為該值
private static final Object[] EMPTY_ELEMENTDATA = {};

// 調(diào)用無參構(gòu)造方法，數(shù)組為該值，初次add元素時擴(kuò)容為默認(rèn)10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 元素?cái)?shù)組，有transient關(guān)鍵字，不會被序列化
transient Object[] elementData; // non-private to simplify nested class access

// list的大小，就是elementData數(shù)組的長度
private int size;

可以看到這里有兩個空數(shù)組，具體區(qū)別下面會提到

構(gòu)造方法

提供了三個構(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);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_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;
    }
}

1、指定初始化容量

  • 大于0則初始化一個指定容量的數(shù)組
  • 等于0則將EMPTY_ELEMENTDATA空數(shù)組作為elementData

2、無參數(shù)構(gòu)造方法
將DEFAULTCAPACITY_EMPTY_ELEMENTDATA空數(shù)組作為elementData
默認(rèn)容量大小為10，但是這時候還沒有初始化

3、Collection參數(shù)
通過toArray方法獲取到的數(shù)組賦值給elementData，長度為0則用空數(shù)組代替
但是這里可以看到，如果長度不為0的話，進(jìn)行了類型的判斷，將非Object[]類型的復(fù)制為Object[]類型
注釋說明因?yàn)閏.toArray可能返回的不是Object[]類型，官網(wǎng)查找該bug描述


Arrays.asList構(gòu)建出來的List，如果創(chuàng)建的是String類型的，toArray方法返回的就是String[]類型的數(shù)組，如果之后在該List中再add其他類型的數(shù)據(jù)，會拋出ArrayStoreException異常
例如

List list = new ArrayList(Arrays.asList("one", "two", "three"));

所以此處為了避免這樣的情況，對非Object[]類型做了特殊處理

獲取元素

因?yàn)榈讓邮菙?shù)組，所以直接通過下標(biāo)獲取，時間復(fù)雜度為O(1)

public E get(int index) {
    // 范圍檢查，數(shù)組越界
    rangeCheck(index);

    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}
添加元素

因?yàn)槭莿討B(tài)數(shù)組，所以添加元素時會涉及到擴(kuò)容
1、通過calculateCapacity方法計(jì)算當(dāng)前所需容量大小
2、ensureExplicitCapacity方法確定是否執(zhí)行擴(kuò)容
3、grow方法執(zhí)行擴(kuò)容，進(jìn)行數(shù)組copy

public boolean add(E e) {
    // 確認(rèn)是否需要擴(kuò)容，所需最小容量傳遞當(dāng)前容量+1
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

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

// 計(jì)算當(dāng)前需要的容量大小
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是無參構(gòu)造方法初始化的數(shù)組，返回默認(rèn)大小10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 否則返回所需最小容量（當(dāng)前size + 1）
    return minCapacity;
}

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

    // 現(xiàn)在的數(shù)組容量小于所需最小容量，則擴(kuò)容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 進(jìn)行擴(kuò)容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 先擴(kuò)容為原來的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 1.5倍后還小于所需最小容量，則直接擴(kuò)容為所需最小容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果大于最大數(shù)組容量，則擴(kuò)容為Integer最大數(shù)值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 進(jìn)行數(shù)組copy
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

默認(rèn)容量為10，但是初始化的時候是個空數(shù)組，在第一次add元素的時候會擴(kuò)容到10

可以看到，擴(kuò)容需要進(jìn)行數(shù)組copy，所以如果是數(shù)據(jù)量很大又頻繁add數(shù)據(jù)的情況下，最好是初始化時能指定容量

更新元素

指定下標(biāo)，直接替換新值，返回舊的值

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
刪除元素

刪除指定下標(biāo)元素

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    // 通過下標(biāo)獲取到待刪除元素
    E oldValue = elementData(index);

    // 計(jì)算需要移動的元素?cái)?shù)量，被刪元素后面的都需要移動
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 數(shù)組copy移動
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

刪除某個元素

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

找到被刪除元素的下標(biāo)，刪除操作同指定下標(biāo)的刪除方法（數(shù)組copy），批量刪除的方法也是如此

迭代

ArrayList繼承自AbstractList，有個很重要的屬性modCount，它表示數(shù)據(jù)結(jié)構(gòu)被修改的次數(shù)
可以看到，只要是數(shù)據(jù)結(jié)構(gòu)發(fā)生變化的時候，都會對應(yīng)的變更modCount的值，如新增，刪除，清除等方法
作用就是為了防止在迭代遍歷的時候，其他線程對數(shù)據(jù)結(jié)構(gòu)進(jìn)行了修改
如果子類需要提供迭代時快速失敗機(jī)制，就需要在數(shù)據(jù)結(jié)構(gòu)性變化的方法記錄modCount

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    // 記錄modCount
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        // 每次遍歷前檢查modCount
        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];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        // 遍歷刪除元素前，判斷modCount
        checkForComodification();

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

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        // modCount有變更，說明有其他線程對數(shù)組結(jié)構(gòu)進(jìn)行了修改，拋出異常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
總結(jié)
  • ArrayList底層為動態(tài)數(shù)組
  • 默認(rèn)容量為10，在第一次添加元素時候會擴(kuò)容到10
  • 每次擴(kuò)容會變?yōu)橹暗?.5倍，會涉及到數(shù)組的拷貝
  • 獲取元素通過下標(biāo)直接獲取，速度快
  • 在尾部進(jìn)行元素的添加和刪除效率較高，在中間添加和刪除效率低，因?yàn)樯婕暗皆氐囊苿?/li>
  • 在大數(shù)據(jù)量的前提下，最好預(yù)估容量，初始化時候指定，避免擴(kuò)容時進(jìn)行的數(shù)組copy影響效率
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

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

  • 上一章分析了AbstractList抽樣類，這一章我們將全面分析最常用的集合ArrayList。 ArrayLis...
    wo883721閱讀 787評論 0贊 3
  • ArrayList是最常用的數(shù)組，這里我們分析一下源碼： ArrayList繼承了AbstractList<E> ...
    說dian什么好呢閱讀 838評論 0贊 0
  • Java Collection框架 - ArrayList 基于jdk1.8 簡介 ArrayList是基于數(shù)組實(shí)...
    xiedacon閱讀 854評論 0贊 1
  • 這本書是以程序員小強(qiáng)作為故事的主人公, 項(xiàng)目經(jīng)理老付帶著小強(qiáng)一步步走向效率達(dá)人的故事書.不同于其他枯燥乏味的時間管...
    359afe052eac閱讀 2,465評論 0贊 0
  • 藏在角落里的那雙眼 從來不曾為誰動容 與全世界的不贊同 看得到你眼里的笑容 謝謝你那么英勇 就算全世界都不贊同 也...
    小王爺小王爺閱讀 263評論 0贊 0

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