ArrayList源碼解讀

ArrayList

  • 介紹

    ArrayList是基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)

    ArrayList 隨機(jī)訪問速度快，中間插入與刪除速度慢，尾部插入與刪除速度也快。

  • 重要屬性

//存儲(chǔ)元素的數(shù)組緩沖區(qū)
transient Object[] elementData;
//List的大小
private int size;
  • 構(gòu)造函數(shù)一
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);
    }
}

此構(gòu)造需要傳入一個(gè)初始化容量initialCapacity；

如果大于0，則創(chuàng)建此大小的數(shù)組緩沖區(qū)，等于0，則直接使用一個(gè)空數(shù)組EMPTY_ELEMENTDATA

因此，使用ArrayList的時(shí)候如果預(yù)先知道其容量，使用此構(gòu)造方法傳入容量，避免內(nèi)存浪費(fèi)與add時(shí)觸發(fā)無必要的擴(kuò)容。

  • 構(gòu)造函數(shù)二
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

此構(gòu)造直接使用一個(gè)空數(shù)組DEFAULTCAPACITY_EMPTY_ELEMENTDATA作為數(shù)據(jù)緩沖區(qū)，add時(shí)才擴(kuò)容。

  • 構(gòu)造函數(shù)三
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

此構(gòu)造直接使用傳入集合c數(shù)組數(shù)據(jù)作為數(shù)據(jù)緩沖區(qū)。

  • get方法
public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    return (E) elementData[index];
}

通過index直接從數(shù)組緩沖區(qū)中獲取數(shù)據(jù)，根據(jù)下標(biāo)取數(shù)據(jù)快。

  • set方法
public E set(int index, E element) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;
}

直接從數(shù)組緩沖區(qū)替換指定index的數(shù)據(jù)，速度快。

  • add方法
public boolean add(E e) {
    //確保內(nèi)部容量夠用
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //DEFAULT_CAPACITY = 10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//真正擴(kuò)容數(shù)組緩沖區(qū)
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // a >> 1 相當(dāng)于 a / 2^1 取整
    // a >> 2 相當(dāng)于 a / 2^2 取整
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    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);
}

舉例說明一下擴(kuò)容：

`假設(shè)當(dāng)前數(shù)組緩沖區(qū)大小為10，ArrayList.size也為10，`

`=> add(ele)`

    `=> ensureCapacityInternal(11) // size+1 = 11`

        `=> ensureExplicitCapacity(11)`

            `=> grow(minCapacity = 11)`

                `=> oldCapacity = elementData.length = 10`

                     `newCapacity = oldCapacity + (oldCapacity >> 1) = 15`

                     `...這塊未影響newCapacity的值`

                     `elementData = Arrays.copyOf(elementData, newCapacity)，此時(shí)elementData.length = newCapacity = 15了`

`=>elementData[10] = ele;// size++ 先使后加`

add如果不觸發(fā)擴(kuò)容的話速度非常快，觸發(fā)擴(kuò)容需要數(shù)組copy，速度會(huì)受到影響

  • add方法(從指定index add)
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //確保數(shù)組容量夠用
    ensureCapacityInternal(size + 1);
    //將數(shù)組緩沖區(qū)中index之后的數(shù)據(jù)，向后移動(dòng)一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

此方法相比在上一add方法，多一步數(shù)組拷貝過程。

  • remove方法(通過index)，返回舊的數(shù)據(jù)
public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    modCount++;
    //取出當(dāng)前index之前的值，下面作為方法返回值
    E oldValue = (E) elementData[index];
    int numMoved = size - index - 1;
    //大于0，說明不是移除最后一個(gè)元素，需要將index之后的數(shù)據(jù)往前移一位
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //最后一個(gè)一定沒用了，置為空，讓gc去管
    elementData[--size] = null;
    return oldValue;
}

如果是移除最后一個(gè)元素的話，不涉及數(shù)組copy，速度很快；

如果移除非最后一個(gè)元素，需要數(shù)組copy，速度會(huì)受影響。

  • remove方法(通過元素)，返回是否移除前是否包含該元素
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;
}
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
}

遍歷元素，找到與傳入元素相等的元素的index，然后移除(過程與上面通過index remove的過程相同)；

注意：如果元素中包含重復(fù)的元素，則僅移除前面的那個(gè)元素(因?yàn)槭菑那巴笳襥ndex的);

  • addAll方法
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

addAll 跟上面add方法基本一樣。

  • removeAll方法
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            //complement=false
            //如果c不包含elementData[r],把elementData[r]保留
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 看上面的for循環(huán)，沒有多線程并發(fā)問題的話，r一定是等于size的，
        // 這個(gè)if不會(huì)命中
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        //如果不是全部移除，w肯定不等于size，
        //這個(gè)if命中，把多余的元素置空
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

舉例分析以下代碼：

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
List<Integer> c = new ArrayList<>(Arrays.asList(1, 3, 5));
list.removeAll(c);
System.out.println(list);// 輸出[2, 4, 6, 7]

1.原始數(shù)據(jù)

1 2 3 4 5 6 7 _ _ _

2.batchRemove == for循環(huán)完后=>

2 4 6 7 5 6 7 _ _ _

3.置空多余元素

2 4 6 7 _ _ _ _ _ _
  • subList(int fromIndex, int toIndex)
public List<E> subList(int fromIndex, int toIndex) {
    //檢查index是否異常
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}
private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

    public E set(int index, E e) {
        //......
        ArrayList.this.elementData[offset + index] = e;
        //......
    }

    public E get(int index) {
        //......
        return (E) ArrayList.this.elementData[offset + index];
    }

    public void add(int index, E e) {
        //......
        parent.add(parentOffset + index, e);
        //......
    }

    public E remove(int index) {
        //......
        E result = parent.remove(parentOffset + index);
        //......
    }

    protected void removeRange(int fromIndex, int toIndex) {
        //......
        parent.removeRange(parentOffset + fromIndex, parentOffset + toIndex);
        //......
    }

    public boolean addAll(Collection<? extends E> c) {
        return addAll(this.size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        //......
        parent.addAll(parentOffset + index, c);
        //......
    }
    
    //......
}

該方法返回的不是ArrayList，而是SubList;

SubList相當(dāng)于是原ArrayList的一個(gè)映射，[fromIndex, toIndex);

子list實(shí)際上是修改的父ArrayList。

父list操作后，子list再操作會(huì)拋出異常 ConcurrentModificationException，是因?yàn)楦竘ist操作后不會(huì)把modCount同步給子list。

  • clear方法
public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}

遍歷將數(shù)組緩沖區(qū)全部置空，size置0。

?著作權(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)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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

  • 1、ArrayList簡介 ArrayList屬于java.util的類，底層是基于數(shù)組實(shí)現(xiàn)的，其實(shí)就是一個(gè)動(dòng)態(tài)數(shù)...
    月悠揚(yáng)閱讀 451評(píng)論 0贊 0
  • 整體架構(gòu) ArrayList整體架構(gòu)比較簡單,就是一個(gè)數(shù)組結(jié)構(gòu),比較簡單,如下圖: 圖中展示是長度為10的數(shù)組,從...
    Shaw_Young閱讀 186評(píng)論 0贊 0
  • java jdk是如何實(shí)現(xiàn)ArrayList的？ ArrayList的實(shí)現(xiàn)很簡單，總的來說，就是arraylist...
    差得很遠(yuǎn)呢閱讀 319評(píng)論 0贊 0
  • ArrayList特點(diǎn)總結(jié) ArrayList實(shí)現(xiàn)List接口，底層是使用數(shù)組實(shí)現(xiàn)的，可以根據(jù)元素的個(gè)數(shù)進(jìn)行動(dòng)態(tài)擴(kuò)...
    西土城小羊閱讀 108評(píng)論 0贊 0
  • ArrayList 的應(yīng)用場(chǎng)景 ArrayList的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，也就是說它滿足數(shù)組的特點(diǎn)，數(shù)組的優(yōu)勢(shì)在于：...
    明月清風(fēng)被占用閱讀 209評(píng)論 0贊 0

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