ArrayList類源碼筆記

ArrayList類是一個繼承自AbstractList類的變長數(shù)組，其長度可以隨著元素數(shù)量的變化而變化。它同時實現(xiàn)了List、RandomAccess、Cloneable和Serializable接口。此外，ArrayList允許插入的元素為null，是一個線程不安全版本的Vector。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

所在路徑：\java\util\ArrayList.java

ArrayList類繼承關系圖

一、成員變量

ArrayList類的成員變量共7個，大概可以分為四類。1是默認容量（長度）和最大長度；2是空數(shù)組實例；3是當前數(shù)組的值和長度；最后是常規(guī)的UID。各變量具體的描述如下所示。

/** 默認容量為10（List的長度） */
private static final int DEFAULT_CAPACITY = 10;
/** List的最大長度（因為有些虛擬機為head word保留了空間，所以這個值減了8） */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/** 空數(shù)組實例，適用于有參數(shù)的構造器（容量傳入為0） */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** 默認容量的空數(shù)組，適用于無參數(shù)的構造器（沒有傳入容量） */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** 存儲List元素的數(shù)組 */
transient Object[] elementData;
/** elementData的長度 */
private int size;

/** serialVersionUID */
private static final long serialVersionUID = 8683452581122892189L;

EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的區(qū)別主要是供不同的構造器使用，ArrayList類的創(chuàng)造者認為這是一種規(guī)范：https://blog.csdn.net/weixin_43390562/article/details/101236833

transient關鍵字修飾elementData是為了在序列化時不將數(shù)組尾部的空元素也輸入進去，而是采取實現(xiàn)writeObject()方法的方式，只序列化有值的數(shù)組部分：https://www.cnblogs.com/vinozly/p/5171227.html

二、構造器

1、無參構造器

直接將一個空的數(shù)組賦值給elementData。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2、入?yún)槌跏既萘?/h5>

初始化一個長度為initialCapacity的數(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);
    }
}
3、入?yún)镃ollection接口的實現(xiàn)類或其子類

當入?yún)橐粋€集合接口的實現(xiàn)類或其子類時，使用toArray()方法進行初始化。例如：List<String> stringList = new ArrayList<>(Arrays.asList("1", "2"));

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()和addAll()

1、add()

add()方法是ArrayList類的核心方法，它可以將元素添加到數(shù)組的尾部或指定位置。用戶在使用add()方法不需要關心elementData的長度，只要不超過之前定義的最大長度，ArrayList會自動對elementData進行擴容。

/** 默認添加至尾部 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/** 添加至指定位置 */
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++;
}

每次插入數(shù)據(jù)前，ArrayList都會計算當前elementData是否需要擴容。擴容的具體過程如下：

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

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

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

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

擴容的動作最終由Arrays.copyOf()方法完成（這個方法我們之前介紹過，它最終調(diào)用的是System.arraycopy()方法，實際上就是數(shù)組元素的逐一拷貝），數(shù)組的實際長度會增加為原來的1.5倍。

modCount表示被修改次數(shù)，在ArrayList的所有涉及結構變化的方法中都增加modCount的值，包括：add()、remove()、addAll()、removeRange()及clear()方法。這些方法每調(diào)用一次，modCount的值就加1。當線程對ArrayList進行遍歷時，通過比較modCount和expectModCount的值來確保循環(huán)不會因多線程的不安全操作而出錯。

https://blog.csdn.net/qq_24235325/article/details/52450331

當newCapacity大于MAX_ARRAY_SIZE時，會調(diào)用hugeCapacity()方法，最多返回一個Integer.MAX_VALUE。

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

addAll()方法可以將一個集合中的每個元素的都加入到數(shù)組中，具體的實現(xiàn)方法基本與add()一致。在copy前，ArrayList會先調(diào)用目標集合的toArray()方法，將其轉換為一個Object類型的數(shù)組。

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) {
    rangeCheckForAdd(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;
}

四、remove()和removeAll()

1、remove()

remove()方法被用來從ArrayList中移除一個元素，移除元素的空當會被其他元素有序補齊。如果輸入的參數(shù)是元素的index，ArrayList會直接用System.arraycopy()對其進行覆蓋。如果入?yún)⑹且粋€Object類對象，ArrayList會在遍歷數(shù)組后調(diào)用fastRemove()方法。

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

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

入?yún)镺bject類對象的remove()方法會在第一次遍歷到該對象時移除并返回，此時ArrayList調(diào)用的是對象的equals()方法，必要的時候這個方法需要由調(diào)用者進行重寫。

其中，fastRemove()方法的實現(xiàn)和入?yún)閕ndex的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
}
2、removeAll()

removeAll()方法可以移除數(shù)組中所有被包含在輸入集合中的元素，ArrayList采用判斷后再賦值給新數(shù)組的方式，避免了頻繁的arraycopy操作。

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++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        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;
}

與removeAll()對應的是retainAll()方法，這個方法在調(diào)用fastRemove()方法時傳入true，將入?yún)⒓现邪脑亓粝聛聿h除其他元素。

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

五、indexOf()和lastIndexOf()

indexOf()和lastIndexOf()方法分別返回輸入元素按從前往后和從后往前兩種順序查找出的數(shù)組下標，如果該元素出現(xiàn)了多次，則只返回按當前順序查找到的第一個。

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

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

六、writeObject()和readObject()

由于elementData被transient修飾，不會在序列化時被轉換出來，ArrayList自己實現(xiàn)了writeObject()和readObject()方法。序列化時，ObjectOutputStream類會通過反射獲得ArrayList的這兩個方法，從而實現(xiàn)只序列化有elementData的有值部分。

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

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

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

七、subList()

subList()方法會返回一個ArrayList的內(nèi)部類，這個類同樣繼承自AbstractList，只是在起止index上與當前ArrayList有所不同。

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

/** 內(nèi)部類SubList */
private class SubList extends AbstractList<E> implements RandomAccess

八、iterator()

iterator()方法同樣返回一個類型為Itr的內(nèi)部類，它實現(xiàn)了Iterator<E>接口。

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

/** 內(nèi)部類Itr */
private class Itr implements Iterator<E>

九、其他

最后，ArrayList同樣提供了幾個入?yún)楦黝惤涌趯崿F(xiàn)的工具方法，用戶可以自定義操作的規(guī)則。

/** 遍歷并支持函數(shù)式處理 */
public void forEach(Consumer<? super E> action)
/** 有條件移除 */
public boolean removeIf(Predicate<? super E> filter)
/** 全部替換并支持函數(shù)式處理 */
public void replaceAll(UnaryOperator<E> operator)
/** 排序 */
public void sort(Comparator<? super E> c)
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

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