ArrayList 可以理解為動態(tài)數(shù)組，用 MSDN 中的說法，就是 Array 的復(fù)雜版本。與 Java 中的數(shù)組相比，它的容量能動態(tài)增長。ArrayList 是 List 接口的可變數(shù)組的實現(xiàn)。實現(xiàn)了所有可選列表操作，并允許包括 null 在內(nèi)的所有元素。除了實現(xiàn) List 接口外，此類還提供一些方法來操作內(nèi)部用來存儲列表的數(shù)組的大小。（此類大致上等同于 Vector 類，除了此類是不同步的。）
每個 ArrayList 實例都有一個容量，該容量是指用來存儲列表元素的數(shù)組的大小。它總是至少等于列表的大小。隨著向 ArrayList 中不斷添加元素，其容量也自動增長。自動增長會帶來數(shù)據(jù)向新數(shù)組的重新拷貝，因此，如果可預(yù)知數(shù)據(jù)量的多少，可在構(gòu)造 ArrayList 時指定其容量。在添加大量元素前，應(yīng)用程序也可以使用 ensureCapacity 操作來增加 ArrayList 實例的容量，這可以減少遞增式再分配的數(shù)量。
注意，此實現(xiàn)不是同步的。如果多個線程同時訪問一個 ArrayList 實例，而其中至少一個線程從結(jié)構(gòu)上修改了列表，那么它必須保持外部同步。（結(jié)構(gòu)上的修改是指任何添加或刪除一個或多個元素的操作，或者顯式調(diào)整底層數(shù)組的大??；僅僅設(shè)置元素的值不是結(jié)構(gòu)上的修改。）
我們先學(xué)習(xí)了解其內(nèi)部的實現(xiàn)原理，才能更好的理解其應(yīng)用。
對于 ArrayList 而言，它實現(xiàn) List 接口、底層使用數(shù)組保存所有元素。其操作基本上是對數(shù)組的操作。下面我們來分析 ArrayList 的源代碼：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
}ArrayList 繼承了 AbstractList，實現(xiàn)了 List。它是一個數(shù)組隊列，提供了相關(guān)的添加、刪除、修改、遍歷等功能。
ArrayList 實現(xiàn)了 RandmoAccess 接口，即提供了隨機訪問功能。RandmoAccess 是 java 中用來被 List 實現(xiàn)，為 List 提供快速訪問功能的。在 ArrayList 中，我們即可以通過元素的序號快速獲取元素對象；這就是快速隨機訪問。
ArrayList 實現(xiàn)了 Cloneable 接口，即覆蓋了函數(shù) clone()，能被克隆。 ArrayList 實現(xiàn) java.io.Serializable 接口，這意味著 ArrayList 支持序列化，能通過序列化去傳輸。
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
private transient Object[] elementData;
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
/**
* 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) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 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();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}ArrayList 提供了三種方式的構(gòu)造器：
public ArrayList()可以構(gòu)造一個默認初始容量為10的空列表；public ArrayList(int initialCapacity)構(gòu)造一個指定初始容量的空列表；public ArrayList(Collection<? extends E> c)構(gòu)造一個包含指定 collection 的元素的列表，這些元素按照該collection的迭代器返回它們的順序排列的。ArrayList 中提供了多種添加元素的方法，下面將一一進行講解：
1.set(int index, E element)：該方法首先調(diào)用rangeCheck(index)來校驗 index 變量是否超出數(shù)組范圍，超出則拋出異常。而后，取出原 index 位置的值，并且將新的 element 放入 Index 位置，返回 oldValue。
/**
* 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;
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}2.add(E e)：該方法是將指定的元素添加到列表的尾部。當(dāng)容量不足時，會調(diào)用 grow 方法增長容量。
/**
* 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;
}
private void ensureCapacityInternal(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);
}3.add(int index, E element)：在 index 位置插入 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);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}4.addAll(Collection<? extends E> c) 和 addAll(int index, Collection<? extends E> c)：將特定 Collection 中的元素添加到 Arraylist 末尾。
/**
* 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;
}
/**
* 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;
}在 ArrayList 的存儲方法，其核心本質(zhì)是在數(shù)組的某個位置將元素添加進入。但其中又會涉及到關(guān)于數(shù)組容量不夠而增長等因素。
這個方法就比較簡單了，ArrayList 能夠支持隨機訪問的原因也是很顯然的，因為它內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，而數(shù)組本身就是支持隨機訪問。該方法首先會判斷輸入的index值是否越界，然后將數(shù)組的 index 位置的元素返回即可。
/**
* 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 (E) elementData[index];
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}ArrayList 提供了根據(jù)下標或者指定對象兩種方式的刪除功能。需要注意的是該方法的返回值并不相同，如下：
/**
* 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);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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;
}注意：從數(shù)組中移除元素的操作，也會導(dǎo)致被移除的元素以后的所有元素的向左移動一個位置。
從上面介紹的向 ArrayList 中存儲元素的代碼中，我們看到，每當(dāng)向數(shù)組中添加元素時，都要去檢查添加后元素的個數(shù)是否會超出當(dāng)前數(shù)組的長度，如果超出，數(shù)組將會進行擴容，以滿足添加數(shù)據(jù)的需求。數(shù)組擴容有兩個方法，其中開發(fā)者可以通過一個 public 的方法ensureCapacity(int minCapacity)來增加 ArrayList 的容量，而在存儲元素等操作過程中，如果遇到容量不足，會調(diào)用priavte方法private void ensureCapacityInternal(int minCapacity)實現(xiàn)。
public void ensureCapacity(int minCapacity) {
if (minCapacity > 0)
ensureCapacityInternal(minCapacity);
}
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(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);
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ù)組進行擴容時，會將老數(shù)組中的元素重新拷貝一份到新的數(shù)組中，每次數(shù)組容量的增長大約是其原容量的 1.5 倍（從int newCapacity = oldCapacity + (oldCapacity >> 1)這行代碼得出）。這種操作的代價是很高的，因此在實際使用時，我們應(yīng)該盡量避免數(shù)組容量的擴張。當(dāng)我們可預(yù)知要保存的元素的多少時，要在構(gòu)造 ArrayList 實例時，就指定其容量，以避免數(shù)組擴容的發(fā)生?；蛘吒鶕?jù)實際需求，通過調(diào)用ensureCapacity 方法來手動增加 ArrayList 實例的容量。
ArrayList 也采用了快速失敗的機制，通過記錄 modCount 參數(shù)來實現(xiàn)。在面對并發(fā)的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發(fā)生任意不確定行為的風(fēng)險。 關(guān)于 Fail-Fast 的更詳細的介紹，我在之前將 HashMap 中已經(jīng)提到。
掃碼關(guān)注鍍金池微信號
手機訂課，優(yōu)惠多多