繼承關(guān)系

ArrayList繼承關(guān)系圖

1. ArrayList概述

ArrayList是List接口的可變數(shù)組的實現(xiàn)。實現(xiàn)了所有可選列表操作，并允許包括 null 在內(nèi)的所有元素规婆。除了實現(xiàn) List 接口外耸峭，此類還提供一些方法來操作內(nèi)部用來存儲列表的數(shù)組的大小桩蓉。
每個 ArrayList 實例都有一個容量，該容量是指用來存儲列表元素的數(shù)組的大小劳闹。它總是至少等于列表的大小院究。隨著向 ArrayList 中不斷添加元素洽瞬，其容量也自動增長。自動增長會帶來數(shù)據(jù)向新數(shù)組的重新拷貝业汰，因此伙窃，如果可預(yù)知數(shù)據(jù)量的多少，可在構(gòu)造 ArrayList 時指定其容量样漆。在添加大量元素前为障，應(yīng)用程序也可以使用 ensureCapacity操作來增加 ArrayList實例的容量，這可以減少遞增式再分配的數(shù)量放祟。

注意：此實現(xiàn)不是同步的产场。如果多個線程同時訪問一個 ArrayList 實例，而其中至少一個線程從結(jié)構(gòu)上修改了列表舞竿，那么它必須保持外部同步京景。相對比的，Vector 是線程安全的骗奖，其中涉及線程安全的方法皆被同步操作了确徙。

2. ArrayList實現(xiàn)

對于 ArrayList 而言，它實現(xiàn) List 接口执桌、底層使用數(shù)組保存所有元素鄙皇。其操作基本上是對數(shù)組的操作。下面我們來分析 ArrayList 的Java源代碼：

（1）底層實現(xiàn)：數(shù)組

 /**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

（2）構(gòu)造器

1）構(gòu)造初始容量為10的空集合

    /**
 * Constructs an empty list with an initial capacity of ten. 
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2）構(gòu)造指定初始容量為initialCapacity的空集合

    /**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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）構(gòu)造一個包含指定集合元素的列表仰挣，其順序由集合的迭代器返回

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
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;
    }
}

（3）存儲

ArrayList 提供了 set(int index, E element)伴逸、add(E e)、add(int index, E element)膘壶、addAll(Collection<? extends E> c)错蝴、addAll(int index, Collection<? extends E> c) 這些添加元素的方法

1）set(int index,E element)：用指定的元素代替此列表中指定位置的元素，并返回之前位于該位置的元素

    /**
 * Replaces the element at the specified position in this list with
 * the specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

2）add(E e)：將指定的元素添加到此列表的尾部

    /**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

add(E e) 的實現(xiàn)原理：

第一步：檢查列表是否需要擴(kuò)容
- 容量足夠颓芭，直接添加
- 容量不足顷锰，擴(kuò)容
第二步：在列表尾部插入元素

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 跟默認(rèn)容量10比較，得到最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
// 比較看是否需要擴(kuò)容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

擴(kuò)容的方法grow(int minCapacity)：

    /**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 擴(kuò)容1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;  // 如果擴(kuò)容還不滿足要求亡问，則將容量直接擴(kuò)為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);
}

擴(kuò)容原理：第一次擴(kuò)容為原來的1.5倍官紫，如果第一次擴(kuò)容后還沒有達(dá)到要求，直接擴(kuò)容為minCapacity州藕。

3）add(int index, E element)：將指定元素插入此列表指定位置

    /**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    // 如果當(dāng)前位置有元素束世，則向右移動當(dāng)前位于該位置的元素以及所有后續(xù)元素（將其索引加1）
    // 檢查容量，如果數(shù)組長度不足床玻，將其擴(kuò)容毁涉，擴(kuò)容原理同上
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 將elementData中從index位置、長度為size-index的元素笨枯，拷貝到從下標(biāo)為index+1
    // 位置開始的新的elementData數(shù)組中薪丁，即將當(dāng)前位于該位置以及所有后續(xù)元素向后移動一個位置
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;
    size++;
}

4）addAll(Collection<? extends E> c)：按照指定集合的迭代器返回的順序遇西，將指定集合中的所有元素追加到此列表的末尾

    /**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the
 * specified collection's Iterator.  The behavior of this operation is
 * undefined if the specified collection is modified while the operation
 * is in progress.  (This implies that the behavior of this call is
 * undefined if the specified collection is this list, and this
 * list is nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return <tt>true</tt> if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
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;
}

5）addAll(int index, Collection<? extends E> c)：從指定位置開始，將指定collection中的所有元素添加到此列表的尾部

    /**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection's iterator.
 *
 * @param index index at which to insert the first element from the
 *              specified collection
 * @param c collection containing elements to be added to this list
 * @return <tt>true</tt> if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
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;
}

（4）讀取元素：獲取列表中某個位置的元素

    /**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

（5）刪除：刪除指定位置元素

    /**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);
    // 左移元素個數(shù)
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 元素左移
        System.arraycopy(elementData, index+1, elementData, index,numMoved);
     // 空閑位置設(shè)置為null严嗜，讓GC回收
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

（6）容量調(diào)整

從上面介紹的向 ArrayList 中存儲元素的代碼中粱檀，我們看到，每當(dāng)向數(shù)組中添加元素時漫玄，都要去檢查添加后元素的個數(shù)是否會超出當(dāng)前數(shù)組的長度茄蚯，如果超出，數(shù)組將會進(jìn)行擴(kuò)容睦优，以滿足添加數(shù)據(jù)的需求渗常。數(shù)組擴(kuò)容通過一個公開的方法 ensureCapacity(int minCapacity)來實現(xiàn)。在實際添加大量元素前汗盘，我也可以使用 ensureCapacity來手動增加 ArrayList 實例的容量皱碘，以減少遞增式再分配的數(shù)量
擴(kuò)容核心代碼：
```
 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);
}
```
數(shù)組進(jìn)行擴(kuò)容時，會將老數(shù)組中的元素重新拷貝一份到新的數(shù)組中隐孽，每次數(shù)組容量的增長大約是其原容量的 1.5 倍【oldCapacity + (oldCapacity >> 1)癌椿，等于oldCapacity +（oldCapacity /2）】。這種操作的代價是很高的菱阵，因此在實際使用時踢俄，我們應(yīng)該盡量避免數(shù)組容量的擴(kuò)張。當(dāng)我們可預(yù)知要保存的元素的多少時晴及，要在構(gòu)造 ArrayList 實例時都办，就指定其容量，以避免數(shù)組擴(kuò)容的發(fā)生虑稼×斩ぃ或者根據(jù)實際需求，通過調(diào)用 ensureCapacity 方法來手動增加 ArrayList 實例的容量动雹。

ArrayList 還給我們提供了將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實際元素的大小的功能槽卫。它可以通過 trimToSize 方法來實現(xiàn)。

  /**
 * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 * list's current size.  An application can use this operation to minimize
 * the storage of an <tt>ArrayList</tt> instance.
 */
public void trimToSize() {
  modCount++;
  if (size < elementData.length) {
      elementData = (size == 0)
        ? EMPTY_ELEMENTDATA
        : Arrays.copyOf(elementData, size);
  }
}

3.Fail-Fast 機(jī)制

（1）fail-fast策略：

我們知道 java.util.HashMap 不是線程安全的胰蝠，因此如果在使用迭代器的過程中有其他線程修改了集合，那么將拋出 ConcurrentModificationException震蒋，這就是所謂 fail-fast策略茸塞。fail-fast 機(jī)制是 java 集合(Collection)中的一種錯誤機(jī)制。當(dāng)多個線程對同一個集合的內(nèi)容進(jìn)行操作時查剖，就可能會產(chǎn)生 fail-fast 事件钾虐。

（2）舉例

例如：當(dāng)某一個線程 A 通過 iterator去遍歷某集合的過程中，若該集合的內(nèi)容被其他線程所改變了笋庄；那么線程 A 訪問集合時效扫，就會拋出 ConcurrentModificationException 異常倔监，產(chǎn)生 fail-fast 事件。
這一策略在源碼中的實現(xiàn)是通過 modCount 域菌仁，modCount 顧名思義就是修改次數(shù)浩习，對集合內(nèi)容（HashMap、 ArrayList 中都有）的修改都將增加這個值济丘，那么在迭代器初始化過程中會將這個值賦給迭代器的 expectedModCount谱秽。

（3）ArrayList

ArrayList 也采用了快速失敗的機(jī)制，通過記錄 modCount 參數(shù)來實現(xiàn)摹迷。在面對并發(fā)的修改時疟赊，迭代器很快就會完全失敗，而不是冒著在未來某個不確定時間發(fā)生任意不確定行為的風(fēng)險峡碉。
```
protected transient int modCount = 0;

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

在迭代過程中近哟，判斷 modCount 跟 expectedModCount 是否相等，如果不相等就表示已經(jīng)有其他線程修改了集合鲫寄。

在 HashMap 的 API 中指出：
- 由所有 HashMap 類的“collection 視圖方法”所返回的迭代器都是快速失敗的：在迭代器創(chuàng)建之后吉执，如果從結(jié)構(gòu)上對映射進(jìn)行修改，除非通過迭代器本身的 remove 方法塔拳，其他任何時間任何方式的修改鼠证，迭代器都將拋出 ConcurrentModificationException。

注意靠抑，迭代器的快速失敗行為不能得到保證量九，一般來說，存在非同步的并發(fā)修改時颂碧，不可能作出任何堅決的保證荠列。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException载城。因此肌似，編寫依賴于此異常的程序的做法是錯誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯誤诉瓦。

Java集合 - ArrayList

Java集合 - ArrayList

繼承關(guān)系

1. ArrayList概述

2. ArrayList實現(xiàn)

（1）底層實現(xiàn)：數(shù)組

（2）構(gòu)造器

1）構(gòu)造初始容量為10的空集合

2）構(gòu)造指定初始容量為initialCapacity的空集合

3）構(gòu)造一個包含指定集合元素的列表仰挣，其順序由集合的迭代器返回

（3）存儲

1）set(int index,E element)：用指定的元素代替此列表中指定位置的元素，并返回之前位于該位置的元素

2）add(E e)：將指定的元素添加到此列表的尾部

3）add(int index, E element)：將指定元素插入此列表指定位置

4）addAll(Collection<? extends E> c)：按照指定集合的迭代器返回的順序遇西，將指定集合中的所有元素追加到此列表的末尾

5）addAll(int index, Collection<? extends E> c)：從指定位置開始，將指定collection中的所有元素添加到此列表的尾部

（4）讀取元素：獲取列表中某個位置的元素

（5）刪除：刪除指定位置元素

（6）容量調(diào)整

3.Fail-Fast 機(jī)制

（1）fail-fast策略：

（2）舉例

（3）ArrayList