以下源碼基于 Android SDK 23星虹， 與JDK中略有差別，但基本相同兼贸；整體源碼由 構(gòu)造段直、添加(add)、設(shè)置(set)溶诞、獲取(get)鸯檬、移除(remove)、迭代器(iterator) 和序列化(Serializable)組成螺垢，最后我還會(huì)把里邊一些不常用的方法舉例說明下作用喧务，下面我們就一一探究其實(shí)現(xiàn)原理。

概述

ArrayList 存儲(chǔ)的實(shí)質(zhì)是操作一個(gè)數(shù)組甩苛，這個(gè)數(shù)組可以根據(jù)內(nèi)容自動(dòng)擴(kuò)容蹂楣，所以讓 ArrayList看起來像一個(gè)無限大小的容器一樣。

屬性

/**
     * The minimum amount by which the capacity of an ArrayList will increase.
     * This tuning parameter controls a time-space tradeoff. This value (12)
     * gives empirically good results and is arguably consistent with the
     * RI's specified default initial capacity of 10: instead of 10, we start
     * with 0 (sans allocation) and jump to 12.
     */
    private static final int MIN_CAPACITY_INCREMENT = 12;

    /**
     * The number of elements in this list.
     */
    int size;

    /**
     * The elements in this list, followed by nulls.
     */
    transient Object[] array;

• 既然ArrayList可以自動(dòng)擴(kuò)容讯蒲，那么就要有一個(gè)描述每次擴(kuò)容的基準(zhǔn)痊土，MIN_CAPACITY_INCREMENT就是這個(gè)基準(zhǔn)，默認(rèn)值是12墨林。
• array 是 ArrayList的核心赁酝，所有數(shù)據(jù)均存儲(chǔ)在array這個(gè)數(shù)組中犯祠，發(fā)生自動(dòng)擴(kuò)容時(shí)， array 會(huì)指向新的數(shù)組首地址酌呆，但注意了衡载，transient 表示它不會(huì)參與序列化過程。
• size 始終描述 ArrayList 中實(shí)際的大小隙袁。

構(gòu)造方法

/**
     * Constructs a new instance of {@code ArrayList} with the specified
     * initial capacity.
     *
     * @param capacity
     *            the initial capacity of this {@code ArrayList}.
     */
    public ArrayList(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("capacity < 0: " + capacity);
        }
        array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
    }

    /**
     * Constructs a new {@code ArrayList} instance with zero initial capacity.
     */
    public ArrayList() {
        array = EmptyArray.OBJECT;
    }

    /**
     * Constructs a new instance of {@code ArrayList} containing the elements of
     * the specified collection.
     *
     * @param collection
     *            the collection of elements to add.
     */
    public ArrayList(Collection<? extends E> collection) {
        if (collection == null) {
            throw new NullPointerException("collection == null");
        }

        Object[] a = collection.toArray();
        if (a.getClass() != Object[].class) {
            Object[] newArray = new Object[a.length];
            System.arraycopy(a, 0, newArray, 0, a.length);
            a = newArray;
        }
        array = a;
        size = a.length;
    }

ArrayList共含有3個(gè)構(gòu)造方法痰娱，EmptyArray.OBJECT是一個(gè)length為0的空數(shù)組new Object[0]，new ArrayList() 則會(huì)創(chuàng)建一個(gè)大小為0的數(shù)組菩收；你也可以去指定初始的容量capacity梨睁，new ArrayList(int capacity) ，避免ArrayList 第一次add 或者其他操作就進(jìn)行擴(kuò)容娜饵；第三個(gè)構(gòu)造可以傳入一個(gè)集合坡贺，這里要提一下Collection，你可以認(rèn)為它是 List 箱舞、Queue遍坟、Set的始祖，這里只要在它們內(nèi)部實(shí)現(xiàn)了 toArray 方法晴股，并且返回一個(gè)Object[]類型的數(shù)據(jù)愿伴，就可以成功初始化到 ArrayList中。

添加(add / addAll)

/**
     * Adds the specified object at the end of this {@code ArrayList}.
     *
     * @param object
     *            the object to add.
     * @return always true
     */
    @Override public boolean add(E object) {
        Object[] a = array;
        int s = size;
        if (s == a.length) {
            Object[] newArray = new Object[s +
                    (s < (MIN_CAPACITY_INCREMENT / 2) ?
                     MIN_CAPACITY_INCREMENT : s >> 1)];
            System.arraycopy(a, 0, newArray, 0, s);
            array = a = newArray;
        }
        a[s] = object;
        size = s + 1;
        modCount++;
        return true;
    }

    /**
     * Inserts the specified object into this {@code ArrayList} at the specified
     * location. The object is inserted before any previous element at the
     * specified location. If the location is equal to the size of this
     * {@code ArrayList}, the object is added at the end.
     *
     * @param index
     *            the index at which to insert the object.
     * @param object
     *            the object to add.
     * @throws IndexOutOfBoundsException
     *             when {@code location < 0 || location > size()}
     */
    @Override public void add(int index, E object) {
        Object[] a = array;
        int s = size;
        if (index > s || index < 0) {
            throwIndexOutOfBoundsException(index, s);
        }

        if (s < a.length) {
            System.arraycopy(a, index, a, index + 1, s - index);
        } else {
            // assert s == a.length;
            Object[] newArray = new Object[newCapacity(s)];
            System.arraycopy(a, 0, newArray, 0, index);
            System.arraycopy(a, index, newArray, index + 1, s - index);
            array = a = newArray;
        }
        a[index] = object;
        size = s + 1;
        modCount++;
    }

    /**
     * This method controls the growth of ArrayList capacities.  It represents
     * a time-space tradeoff: we don't want to grow lists too frequently
     * (which wastes time and fragments storage), but we don't want to waste
     * too much space in unused excess capacity.
     *
     * NOTE: This method is inlined into {@link #add(Object)} for performance.
     * If you change the method, change it there too!
     */
    private static int newCapacity(int currentCapacity) {
        int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
                MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
        return currentCapacity + increment;
    }

    /**
     * Adds the objects in the specified collection to this {@code ArrayList}.
     *
     * @param collection
     *            the collection of objects.
     * @return {@code true} if this {@code ArrayList} is modified, {@code false}
     *         otherwise.
     */
    @Override public boolean addAll(Collection<? extends E> collection) {
        Object[] newPart = collection.toArray();
        int newPartSize = newPart.length;
        if (newPartSize == 0) {
            return false;
        }
        Object[] a = array;
        int s = size;
        int newSize = s + newPartSize; // If add overflows, arraycopy will fail
        if (newSize > a.length) {
            int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
            Object[] newArray = new Object[newCapacity];
            System.arraycopy(a, 0, newArray, 0, s);
            array = a = newArray;
        }
        System.arraycopy(newPart, 0, a, s, newPartSize);
        size = newSize;
        modCount++;
        return true;
    }

    /**
     * Inserts the objects in the specified collection at the specified location
     * in this List. The objects are added in the order they are returned from
     * the collection's iterator.
     *
     * @param index
     *            the index at which to insert.
     * @param collection
     *            the collection of objects.
     * @return {@code true} if this {@code ArrayList} is modified, {@code false}
     *         otherwise.
     * @throws IndexOutOfBoundsException
     *             when {@code location < 0 || location > size()}
     */
    @Override
    public boolean addAll(int index, Collection<? extends E> collection) {
        int s = size;
        if (index > s || index < 0) {
            throwIndexOutOfBoundsException(index, s);
        }
        Object[] newPart = collection.toArray();
        int newPartSize = newPart.length;
        if (newPartSize == 0) {
            return false;
        }
        Object[] a = array;
        int newSize = s + newPartSize; // If add overflows, arraycopy will fail
        if (newSize <= a.length) {
             System.arraycopy(a, index, a, index + newPartSize, s - index);
        } else {
            int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
            Object[] newArray = new Object[newCapacity];
            System.arraycopy(a, 0, newArray, 0, index);
            System.arraycopy(a, index, newArray, index + newPartSize, s-index);
            array = a = newArray;
        }
        System.arraycopy(newPart, 0, a, index, newPartSize);
        size = newSize;
        modCount++;
        return true;
    }

這里有必要先看一個(gè)方法队魏，System.arraycopy()

public static native void arraycopy(Object src, int srcPos,
        Object dst, int dstPos, int length);

這是一個(gè) native方法公般，負(fù)責(zé)數(shù)組拷貝，從 src 的 srcPos 開始胡桨，將 length長度的數(shù)據(jù)拷貝到 dst 中官帘，dstPos中的數(shù)據(jù)是srcPos位置的數(shù)據(jù)。

public boolean add(E object)

這是最簡(jiǎn)單的一個(gè)add操作昧谊，里邊會(huì)進(jìn)行擴(kuò)容判斷刽虹，如果當(dāng)前ArrayList.size與array.length相同，則進(jìn)行擴(kuò)容呢诬，擴(kuò)容的策略是s < (MIN_CAPACITY_INCREMENT / 2) ? MIN_CAPACITY_INCREMENT : s >> 1涌哲，即 s < 6 ? 6 : s * 2， 最終擴(kuò)容的大小為 (s + s < 6 ? 6 : s * 2)尚镰；newCapacity(int currentCapacity) 方法也是這個(gè)作用阀圾，返回最終擴(kuò)容后的大小。

public void add(int index, E object)

這個(gè)方法的作用是將 object 插入至 index位置狗唉，這里也會(huì)有擴(kuò)容判斷初烘，既然是插入一個(gè)值，那么size就會(huì) +1，所以 ArrayList.size 小于 array.length是一種情況肾筐，數(shù)組可以直接從 index處 后移一位哆料，再將 object 放入 index的位置；若是大于等于吗铐，則原array需要擴(kuò)容东亦，擴(kuò)容后現(xiàn)將old array 數(shù)據(jù) 復(fù)制到 new array中，再進(jìn)行后移唬渗，最終把object插入到index位置典阵。

public boolean addAll(Collection<? extends E> collection)

public boolean addAll(int index, Collection<? extends E> collection)

這兩個(gè)方法只是批量操作，內(nèi)部邏輯與add 是一樣的谣妻，都要先判斷 ArrayList.size與array.length的大小關(guān)系進(jìn)行擴(kuò)容萄喳，之后通過 System.arraycopy去操作array卒稳。

注：這里你有可能會(huì)發(fā)現(xiàn)有個(gè)變量 modCount蹋半，它用來表達(dá)ArrayList的修改次數(shù)（add、remove）充坑，是它導(dǎo)致ArrayList不是線程安全的减江，等講到迭代器iterator的時(shí)候再來說說這個(gè)變量。

設(shè)置

/**
     * Replaces the element at the specified location in this {@code ArrayList}
     * with the specified object.
     *
     * @param index
     *            the index at which to put the specified object.
     * @param object
     *            the object to add.
     * @return the previous element at the index.
     * @throws IndexOutOfBoundsException
     *             when {@code location < 0 || location >= size()}
     */
    @Override public E set(int index, E object) {
        Object[] a = array;
        if (index >= size) {
            throwIndexOutOfBoundsException(index, size);
        }
        @SuppressWarnings("unchecked") E result = (E) a[index];
        a[index] = object;
        return result;
    }

這個(gè)方法沒什么捻爷，就是把array[index] 替換辈灼，并且把原來的數(shù)據(jù)返回。

獲取

@SuppressWarnings("unchecked") 
@Override 
public E get(int index) {
        if (index >= size) {
            throwIndexOutOfBoundsException(index, size);
        }
        return (E) array[index];
    }

這個(gè)方法也不多說也榄，將array[index]返回巡莹。

移除

/**
     * Removes the object at the specified location from this list.
     *
     * @param index
     *            the index of the object to remove.
     * @return the removed object.
     * @throws IndexOutOfBoundsException
     *             when {@code location < 0 || location >= size()}
     */
    @Override public E remove(int index) {
        Object[] a = array;
        int s = size;
        if (index >= s) {
            throwIndexOutOfBoundsException(index, s);
        }
        @SuppressWarnings("unchecked") E result = (E) a[index];
        System.arraycopy(a, index + 1, a, index, --s - index);
        a[s] = null;  // Prevent memory leak
        size = s;
        modCount++;
        return result;
    }

    @Override public boolean remove(Object object) {
        Object[] a = array;
        int s = size;
        if (object != null) {
            for (int i = 0; i < s; i++) {
                if (object.equals(a[i])) {
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;  // Prevent memory leak
                    size = s;
                    modCount++;
                    return true;
                }
            }
        } else {
            for (int i = 0; i < s; i++) {
                if (a[i] == null) {
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;  // Prevent memory leak
                    size = s;
                    modCount++;
                    return true;
                }
            }
        }
        return false;
    }

    @Override protected void removeRange(int fromIndex, int toIndex) {
        if (fromIndex == toIndex) {
            return;
        }
        Object[] a = array;
        int s = size;
        if (fromIndex >= s) {
            throw new IndexOutOfBoundsException("fromIndex " + fromIndex
                    + " >= size " + size);
        }
        if (toIndex > s) {
            throw new IndexOutOfBoundsException("toIndex " + toIndex
                    + " > size " + size);
        }
        if (fromIndex > toIndex) {
            throw new IndexOutOfBoundsException("fromIndex " + fromIndex
                    + " > toIndex " + toIndex);
        }

        System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
        int rangeSize = toIndex - fromIndex;
        Arrays.fill(a, s - rangeSize, s, null);
        size = s - rangeSize;
        modCount++;
    }

add方法已經(jīng)進(jìn)行了詳細(xì)的講解，想必大家都能猜到甜紫，remove操作就是講 index 或者 range的一段數(shù)據(jù)從array中移除降宅，然后再通過System.arraycopy拷貝之后的數(shù)據(jù)前移補(bǔ)充空位，下圖以移除單個(gè)為例囚霸，將步驟分解：

image.png

迭代器

@Override public Iterator<E> iterator() {
        return new ArrayListIterator();
    }

    private class ArrayListIterator implements Iterator<E> {
        /** Number of elements remaining in this iteration */
        private int remaining = size;

        /** Index of element that remove() would remove, or -1 if no such elt */
        private int removalIndex = -1;

        /** The expected modCount value */
        private int expectedModCount = modCount;

        public boolean hasNext() {
            return remaining != 0;
        }

        @SuppressWarnings("unchecked") public E next() {
            ArrayList<E> ourList = ArrayList.this;
            int rem = remaining;
            if (ourList.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (rem == 0) {
                throw new NoSuchElementException();
            }
            remaining = rem - 1;
            return (E) ourList.array[removalIndex = ourList.size - rem];
        }

        public void remove() {
            Object[] a = array;
            int removalIdx = removalIndex;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (removalIdx < 0) {
                throw new IllegalStateException();
            }
            System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
            a[--size] = null;  // Prevent memory leak
            removalIndex = -1;
            expectedModCount = ++modCount;
        }
    }

迭代器腰根，一個(gè)很重要的概念，它的作用就是便利整個(gè)ArrayList拓型， for each 的原理其實(shí)就是迭代器的使用额嘿，上文說到了modCount與迭代器相關(guān)，

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

expectedModCount是iterator初始化時(shí)賦予的值劣挫，值為modCount册养，而modCount會(huì)根據(jù)add或者remove進(jìn)行++操作，這就表明压固，當(dāng)iterator創(chuàng)建好后球拦，只要使用這個(gè)iterator實(shí)例去進(jìn)行遍歷，就不能使用ArrayList.add或者ArrayList.remove操作，因?yàn)槿绻褂昧耍?code>modCount會(huì)發(fā)生變化刘莹，這樣在next()的時(shí)候就會(huì)拋出異常ConcurrentModificationException阎毅，這也進(jìn)一步說明ArrayList不是線程安全的。那么在遍歷中如何移除元素呢点弯，就是下邊實(shí)現(xiàn)的remove方法了扇调，remove過程與之前類似，關(guān)鍵在于expectedModCount = ++modCount;抢肛，remove需要使modCount 遞增狼钮，那么我讓expectedModCount重新賦值，即可完成刪除操作捡絮。

序列化

private static final long serialVersionUID = 8683452581122892189L;

    private void writeObject(ObjectOutputStream stream) throws IOException {
        stream.defaultWriteObject();
        stream.writeInt(array.length);
        for (int i = 0; i < size; i++) {
            stream.writeObject(array[i]);
        }
    }

    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
        stream.defaultReadObject();
        int cap = stream.readInt();
        if (cap < size) {
            throw new InvalidObjectException(
                    "Capacity: " + cap + " < size: " + size);
        }
        array = (cap == 0 ? EmptyArray.OBJECT : new Object[cap]);
        for (int i = 0; i < size; i++) {
            array[i] = stream.readObject();
        }
    }

這是在代碼末尾了熬芜，ArrayList是通過stream.writeObject 連續(xù)寫入 array的內(nèi)容。

其他

 public boolean contains(Object object)

利用 object 的 equals方法判斷ArrayList中是否包含object對(duì)象福稳。

 public int indexOf(Object object)

 public int lastIndexOf(Object object)

這兩個(gè)方法都是獲取 object 在 ArrayList中的位置涎拉，第一個(gè)是正序遍歷，找到的第一個(gè)返回的index的圆；第二個(gè)是倒序遍歷鼓拧，找到第一個(gè)返回的index。

 /**
     * Sets the capacity of this {@code ArrayList} to be the same as the current
     * size.
     *
     * @see #size
     */
    public void trimToSize() {
        int s = size;
        if (s == array.length) {
            return;
        }
        if (s == 0) {
            array = EmptyArray.OBJECT;
        } else {
            Object[] newArray = new Object[s];
            System.arraycopy(array, 0, newArray, 0, s);
            array = newArray;
        }
        modCount++;
    }

這個(gè)方法是將當(dāng)前的array “精簡(jiǎn)”一下越妈，比如 array.length 是10季俩，但里邊的size是 5個(gè)，那么就將 array.length變?yōu)?5梅掠，把數(shù)據(jù)通過 System.arraycopy 拷貝到新的 array中酌住。

 @Override public boolean equals(Object o) {
        if (o == this) {
            return true;
        }
        if (!(o instanceof List)) {
            return false;
        }
        List<?> that = (List<?>) o;
        int s = size;
        if (that.size() != s) {
            return false;
        }
        Object[] a = array;
        if (that instanceof RandomAccess) {
            for (int i = 0; i < s; i++) {
                Object eThis = a[i];
                Object ethat = that.get(i);
                if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
                    return false;
                }
            }
        } else {  // Argument list is not random access; use its iterator
            Iterator<?> it = that.iterator();
            for (int i = 0; i < s; i++) {
                Object eThis = a[i];
                Object eThat = it.next();
                if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
                    return false;
                }
            }
        }
        return true;
    }

再來看下這個(gè)長長的equals方法，非常好懂阎抒，但是乍眼一看有個(gè) RandomAccess酪我，這是什么？尋找了一下它的實(shí)現(xiàn)類挠蛉，發(fā)現(xiàn)ArrayList就是它的實(shí)現(xiàn)類祭示，再看下這個(gè)if(...){}else{}，如果是RandomAccess的實(shí)現(xiàn)類谴古，那么直接使用get(index)獲取元素质涛，否則需要使用迭代器iterator。以下是對(duì)于RandomAccess的一段摘錄：

jdk中有個(gè)RandomAccess接口掰担，這是一個(gè)標(biāo)記接口(Marker)汇陆，它沒有任何方法，這個(gè)接口被List的實(shí)現(xiàn)類（子類）使用带饱。如果List子類實(shí)現(xiàn)了RandomAccess接口毡代，那就表示它能夠快速隨機(jī)訪問存儲(chǔ)的元素阅羹。RandomAccess接口的意義在于：在對(duì)列表進(jìn)行隨機(jī)或順序訪問的時(shí)候，訪問算法能夠選擇性能最佳方式教寂。一般的列表訪問算法在訪問列表元素之前捏鱼，都被建議先使用instanceof關(guān)鍵字檢查一下列表是否是一個(gè)RandomAccess子類，然后再?zèng)Q定采用隨機(jī)還是順序方式訪問列表中的元素酪耕，這樣可以保證訪問算法擁有最佳的性能导梆。對(duì)于List的子類，如果：
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
的訪問方式比
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
快迂烁，那么它應(yīng)該實(shí)現(xiàn)RandomAccess接口看尼。