1.什么是ArrayList

• 使用動態(tài)數(shù)組Object[]保存元素陨簇，允許null值
• 實(shí)現(xiàn)List接口两入，允許使用下標(biāo)操作元素
• 非線程安全鸭轮，線程安全參見Vector
• 適用于頻繁訪問的場景赚哗，不合適頻繁插入或者刪除（參見LinkedList）
• 支持批量操作

2.ArrayList的數(shù)據(jù)結(jié)構(gòu)

2.1 類定義

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

• 繼承AbstractList：實(shí)現(xiàn)了List，對List中重要操作的實(shí)現(xiàn)稿蹲，包括add，remove等
• 實(shí)現(xiàn) RandmoAccess 接口：支持快速隨機(jī)訪問鹊奖，即通過元素的序號快速獲取元素對象
• 實(shí)現(xiàn)Cloneable:重寫clone(）苛聘，能被克隆（淺拷貝）
• 實(shí)現(xiàn)Serializable：支持序列化

2.2 重要的全局變量

可以思考一下忠聚，如果讓我們來設(shè)計(jì)ArrayList设哗，需要哪些全局變量和函數(shù)？

• Object[] 數(shù)組两蟀，用來存放元素
• size:數(shù)組中元素個數(shù)
• MaxSize：數(shù)組的最大長度
• add方法（考慮擴(kuò)容）网梢，get方法，remove方法（考慮減容）赂毯，size()方法战虏，isEmpty()方法

jdk的實(shí)現(xiàn)拣宰，全局變量包括：

>//Default initial capacity.
    private static final int DEFAULT_CAPACITY = 10;
//Shared empty array instance used for empty instances.
    private static final Object[] EMPTY_ELEMENTDATA = {};
// 存放元素的數(shù)組，空的ArrayList烦感，即elementData = EMPTY_ELEMENTDATA徐裸，在添加第一個元素時，會擴(kuò)容到DEFAULT_CAPACITY 啸盏。transient 標(biāo)記序列化時不需要序列化該字段重贺。
    transient Object[] elementData;
// 元素個數(shù)size
    private int size;
//父類AbstractList中的成員變量，記錄集合被修改的次數(shù)回懦，用于迭代時的異常檢查（下文會詳細(xì)講解）
  protected transient int modCount = 0;

2.3 重要的函數(shù)

2.3.1 add方法

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

添加一個元素到集合尾部气笙，首先對數(shù)組大小進(jìn)行檢查，需要擴(kuò)容的進(jìn)行擴(kuò)容怯晕，然后將元素添加到尾部下標(biāo)所在位置潜圃，并將size加1。

private void ensureCapacityInternal(int minCapacity) {
      // 如果數(shù)組為空舟茶，則選擇DEFAULT_CAPACITY與當(dāng)前需要的總?cè)萘康妮^大者谭期，作為擴(kuò)容的參數(shù)
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //若需要的容量比數(shù)組的長度還大，則需要進(jìn)行擴(kuò)容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    // 新的參考容量為舊容量的1.5倍（向上取整）吧凉，和hashmap的2倍不一樣
    //等同于 (int)Math.floor(oldCapacity*1.5) 
    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:
       //進(jìn)行數(shù)組拷貝，引用直接指向新數(shù)組阀捅，原數(shù)組被拋棄胀瞪，等待回收
         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;
    }

2.3.2 remove()方法

刪除指定位置的元素

   public E remove(int index) {
        if (index >= size)//檢查下標(biāo)是否合法
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        modCount++;//修改modCount
        E oldValue = (E) 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;
    }

2.3.3 sort(）方法

    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

注意：ArrayList的排序采用的是折半插入排序。

     * Sorts the specified portion of the specified array using a binary
     * insertion sort.  This is the best method for sorting small numbers
     * of elements.  It requires O(n log n) compares, but O(n^2) data
     * movement (worst case).
* @param a the array in which a range is to be sorted
     * @param lo the index of the first element in the range to be sorted
     * @param hi the index after the last element in the range to be sorted
     * @param start the index of the first element in the range that is
     *        not already known to be sorted ({@code lo <= start <= hi})
     */
    @SuppressWarnings({"fallthrough", "rawtypes", "unchecked"})
    private static void binarySort(Object[] a, int lo, int hi, int start) {
        assert lo <= start && start <= hi;
        if (start == lo)
            start++;
        for ( ; start < hi; start++) {
            Comparable pivot = (Comparable) a[start];

            // Set left (and right) to the index where a[start] (pivot) belongs
            int left = lo;
            int right = start;
            assert left <= right;
            /*
             * Invariants:
             *   pivot >= all in [lo, left).
             *   pivot <  all in [right, start).
             */
            while (left < right) {
                int mid = (left + right) >>> 1;
                if (pivot.compareTo(a[mid]) < 0)
                    right = mid;
                else
                    left = mid + 1;
            }
            assert left == right;

            /*
             * The invariants still hold: pivot >= all in [lo, left) and
             * pivot < all in [left, start), so pivot belongs at left.  Note
             * that if there are elements equal to pivot, left points to the
             * first slot after them -- that's why this sort is stable.
             * Slide elements over to make room for pivot.
             */
            int n = start - left;  // The number of elements to move
            // Switch is just an optimization for arraycopy in default case
            switch (n) {
                case 2:  a[left + 2] = a[left + 1];
                case 1:  a[left + 1] = a[left];
                         break;
                default: System.arraycopy(a, left, a, left + 1, n);
            }
            a[left] = pivot;
        }
    }

2.3.4 writeObject()方法

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

這里不直接使用s.writeObject(elementData)的方法饲鄙，是因?yàn)榭紤]到數(shù)組有一些空余的空間不需要序列化凄诞。

2.3.5 兩個toArray方法

• 1

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

• 2

public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

如果toArray()需要向下轉(zhuǎn)型（例如將Object[]轉(zhuǎn)換為的Integer[])，則需要使用第2種方式忍级，傳入一個子類數(shù)組（如下代碼段）帆谍。否則直接使用第1種方法。由于java不支持向下轉(zhuǎn)型轴咱，第1種方式會拋java.lang.ClassCastException異常汛蝙。

public static Integer[] toArray(ArrayList<Integer> arrayList) {
    Integer[] newArrayList = (Integer[])arrayList.toArray(new Integer[0]);
    return newArrayList;
}

2.4 內(nèi)部類

ArrayList的內(nèi)部類

• 靜態(tài)內(nèi)部類：ArrayListSpliterator可分割的迭代器，用于并行遍歷集合嗦玖。(jdk1.8才有)

靜態(tài)內(nèi)部類的使用場景是： 1 當(dāng)外部類需要是用內(nèi)部類患雇，而內(nèi)部類無需外部類的資源，并且內(nèi)部類可以單獨(dú)創(chuàng)建的時候宇挫，會考慮使用靜態(tài)內(nèi)部類苛吱。2 內(nèi)部類與外部類關(guān)系密切的，且不依賴外部類實(shí)例的器瘪，都可以使用靜態(tài)內(nèi)部類翠储。
例如builder模式中的builder類绘雁；hashmap的static class HashMapEntry<K,V>類。

• private迭代器：Itr和ListItr
• private SubList:集合的子集

2.5 其它

2.5.1 modCount與Fail-Fast機(jī)制

modCount記錄數(shù)組被修改的次數(shù)援所，作為線程不安全的集合類的成員變量庐舟，主要用在迭代器以及序列化writeObject()等場景。由下面迭代器代碼可以看到住拭，每次獲取元素之前都會檢查當(dāng)前modCount與該迭代器對象初始化時的modCount是否一致挪略，如果不一致，則拋出異常滔岳。這就是Fail-Fast機(jī)制杠娱。對于線程不安全的集合類，通過modCount域快速檢查集合內(nèi)容是否有變化谱煤。JDK為了提示開發(fā)者將非線程安全的類使用到并發(fā)的場景下時摊求，拋出一個異常，盡早發(fā)現(xiàn)代碼中的問題刘离。當(dāng)然室叉，這種機(jī)制并不一定有效。首先硫惕，jdk1.7中取消了modCount的volatitle修飾符茧痕，失去了各個線程直接對modCount的可見性。
注意：
在使用迭代器對象時疲憋，是可以修改數(shù)據(jù)的凿渊。即一下代碼是合法的。

while (iterator.hasNext()) {    
  if(iterator.next().equals("c")) {        
    iterator.remove("c");    
  }
}

public boolean hasNext() {
            return cursor < limit;
        }

原因在于：hasNext()方法并沒有使用modCount進(jìn)行判斷缚柳，而是比較下一個元素的位置與數(shù)組總長度。

    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 class Itr implements Iterator<E> {
        // The "limit" of this iterator. This is the size of the list at the time the
        // iterator was created. Adding & removing elements will invalidate the iteration
        // anyway (and cause next() to throw) so saving this value will guarantee that the
        // value of hasNext() remains stable and won't flap between true and false when elements
        // are added and removed from the list.
        protected int limit = ArrayList.this.size;

        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor < limit;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        ……
}

2.5.2 System.arrayCopy() Arrays.copyOf()的區(qū)別

1 public static native void arraycopy(Object src, int srcPos,Object dest, int destPos, int length);
參數(shù)依次對應(yīng)為：源數(shù)組搪锣，源數(shù)組copy的起始位置秋忙，目標(biāo)數(shù)組，目標(biāo)數(shù)組存放的起始位置构舟，需要copy的數(shù)組長度

2 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)
參數(shù)依次對應(yīng)為:源數(shù)組灰追，新數(shù)組長度，新數(shù)組元素類型

實(shí)際上狗超， Arrays.copyOf()里面還是通過調(diào)用System.arrayCopy()實(shí)現(xiàn)最終的數(shù)組元素拷貝弹澎。所以，Arrays.copyOf()實(shí)際上是受限的System.arrayCopy()努咐。
區(qū)別主要為：

• 1 System方法需要傳入新的數(shù)組苦蒿，Arrays方法不用（會在內(nèi)部自己新建一個數(shù)組并返回）。
• 2 System方法沒有返回值渗稍，Arrays方法返回新的數(shù)組