ArrayList簡介 ArrayList是基於數組實現的，是一個動態數組，其容量能自動增長，類似於C語言中的動態申請記憶體，動態增長記憶體。 ArrayList不是線程安全的，只能用在單線程環境下，多線程環境下可以考慮用Collections.synchronizedList(List l)函數返回一 ...
ArrayList簡介
ArrayList是基於數組實現的，是一個動態數組，其容量能自動增長，類似於C語言中的動態申請記憶體，動態增長記憶體。
ArrayList不是線程安全的，只能用在單線程環境下，多線程環境下可以考慮用Collections.synchronizedList(List l)函數返回一個線程安全的ArrayList類，也可以使用concurrent併發包下的CopyOnWriteArrayList類。
ArrayList實現了Serializable介面，因此它支持序列化，能夠通過序列化傳輸，實現了RandomAccess介面，支持快速隨機訪問，實際上就是通過下標序號進行快速訪問，實現了Cloneable介面，能被克隆。
ArrayList源碼
ArrayList的源碼如下（加入了簡單的註釋，版本號為1.56）：
/**@(#)ArrayList.java 1.56 06/04/21
* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*/
package java.util;
/**
* @author Josh Bloch
* @author Neal Gafter
* @version 1.56, 04/21/06
* @see Collection
* @see List
* @see LinkedList
* @see Vector
* @since 1.2
*/
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
// ArrayList基於該數組實現，用該數組保存數據
private transient Object[] elementData;
// 實際大小
private int size;
// 帶容量大小的構造函數
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
// 預設構造函數
public ArrayList() {
this(10);
}
// Collection構造函數
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);
}
// 當前容量值為實際個數
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
// 確定ArrayList容量
// 若容量不足以容納當前全部元素，則擴容，新的容量=“(原始容量x3)/2 + 1”
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
// 返回實際大小
public int size() {
return size;
}
// 清空
public boolean isEmpty() {
return size == 0;
}
// 是否包含o
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// 正向查找，返回o的index
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;
}
// 逆向查找，返回o的index
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;
}
// 克隆函數
public Object clone() {
try {
ArrayList<E> v = (ArrayList<E>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
// 返回ArrayList的Object數組
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// 返回ArrayList組成的數組
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;
}
// Positional Access Operations
// 得到index位置的元素
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
// 向index插入element
public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
// 添加e
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 向index插入element
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
// 移除index位置的元素
public E remove(int index) {
RangeCheck(index);
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; // Let gc do its work
return oldValue;
}
// 移除o
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;
}
// 快速移除index位置的元素
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; // Let gc do its work
}
// 清空
public void clear() {
modCount++;
// Let gc do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
// 添加Collection
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
// 在index添加Collection
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(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;
}
// 移除fromIndex到toIndex之間的全部元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newSize = size - (toIndex-fromIndex);
while (size != newSize)
elementData[--size] = null;
}
// 移除index位置的元素
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
// java.io.Serializable的寫入函數,將ArrayList的“容量，所有的元素值”都寫入到輸出流中
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 array length
s.writeInt(elementData.length);
// 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();
}
}
// java.io.Serializable的讀取函數：根據寫入方式讀出,先將ArrayList的“容量”讀出，然後將“所有的元素值”讀出
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in array length and allocate array
int arrayLength = s.readInt();
Object[] a = elementData = new Object[arrayLength];
// Read in all elements in the proper order.
for (int i=0; i<size; i++)
a[i] = s.readObject();
}
}
ArrayList詳細分析
1.構造函數
ArrayList有三個構造函數，如下(英文註釋全部刪掉，預設代碼摺疊，太占地方了)：
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
this(10);
}
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本質上是一個Object類型的數組，前面加入了transient關鍵字，在序列化的時候忽略，但是在最後自己重寫了writeObject和readObject這兩個函數，第一個是構造傳入固定大小的ArrayList，第二個是預設大小為10，第三個是將傳入的Collection轉成ArrayList。
序列化有2種方式：
A、只是實現了Serializable介面。
序列化時，調用java.io.ObjectOutputStream的defaultWriteObject方法，將對象序列化。
註意：此時transient修飾的欄位，不會被序列化。
B、實現了Serializable介面，同時提供了writeObject方法。
序列化時，會調用該類的writeObject方法。而不是java.io.ObjectOutputStream的defaultWriteObject方法。
註意：此時transient修飾的欄位，是否會被序列化，取決於writeObject
2.自動擴容函數
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
關鍵在這裡int newCapacity = (oldCapacity * 3)/2 + 1;新的數組大小是舊的數組大小的二分之三加一，然後調用Arrays.copyOf(elementData, newCapacity);得到新的elementData對象。說到這裡我默默的翻看了一下jdk1.7的源碼，發現在jdk1.7當中，擴容效率有了本質上的提高，請看下麵的代碼：（出自jdk1.7）
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);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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);
}
1.7相比較1.6，自動擴容增加了兩個方法，增加了數組擴容時的判斷，最重要的是這句話：int newCapacity = oldCapacity + (oldCapacity >> 1);沒有再用*3再/2這種低端的玩法，直接採用了移位運算，我不是太懂十進位數的移位運算，經過幾次自己的測試發現如果是偶數，這個移位運算正好是一半，如果是奇數，則是向下取整。
3.存儲
第一判斷ensureSize，如果夠直接插入，否則按照policy擴展，複製，重建數組。
第二步插入元素。
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)這些添加元素的方法。
3.1. set(int index, E element),取代，而非插入，返回被取代的元素
public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
3.2.add(E e) 增加元素到末尾，如果size不溢出，自動增長
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
3.3.add(int index, E element) 增加元素到某個位置，該索引之後的元素都後移一位
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
3.4.後面兩個方法都是把集合轉換為數組利用c.toArray，然後利用Arrays.copyOF 方法
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(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) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(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.刪除
一種是按索引刪除，不用查詢，索引之後的element順序左移一位，並將最後一個element設為null，由gc負責回收。
public E remove(int index) {
RangeCheck(index);
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; // Let gc do its work
return oldValue;
}
5.Arrays.copyOf
源碼如下：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
這裡有所優化，如果是Object類型的，直接new Object數組，如果不是則通過Array.newInstance(newType.getComponentType(), newLength)方法產生相應的數組類型。通過System.arraycopy實現數組複製，System是個final類，arraycopy是個native方法。
該方法被標記了native，調用了系統的C/C++代碼，在JDK中是看不到的，但在openJDK中可以看到其源碼。該函數實際上最終調用了C語言的memmove()函數，因此它可以保證同一個數組內元素的正確複製和移動，比一般的複製方法的實現效率要高很多，很適合用來批量處理數組。Java強烈推薦在複製大量數組元素時用該方法，以取得更高的效率。
6.Arrays.newInstance()的意義
Java反射技術除了可以在運行時動態地決定要創建什麼類型的對象，訪問哪些成員變數，方法，還可以動態地創建各種不同類型，不同維度的數組。
動態創建數組的步驟如下：
1.創建Class對象，通過forName(String)方法指定數組元素的類型
2.調用Array.newInstance(Class, length_of_array)動態創建數組
訪問動態數組元素的方法和通常有所不同，它的格式如下所示，註意該方法返回的是一個Object對象
Array.get(arrayObject, index)
為動態數組元素賦值的方法也和通常的不同，它的格式如下所示， 註意最後的一個參數必須是Object類型
Array.set(arrayObject, index, object)
動態數組Array不單可以創建一維數組，還可以創建多維數組。步驟如下：
1.定義一個整形數組：例如int[] dims= new int{5, 10, 15};指定一個三維數組
2.調用Array.newInstance(Class, dims);創建指定維數的數組
訪問多維動態數組的方法和訪問一維數組的方式沒有什麼大的不同，只不過要分多次來獲取，每次取出的都是一個Object，直至最後一次，賦值也一樣。
動態數組Array可以轉化為普通的數組，例如:
Array arry = Array.newInstance(Integer.TYPE,5);
int arrayCast[] = (int[])array;
7.為何要序列化
ArrayList 實現了java.io.Serializable介面，在需要序列化的情況下，覆寫writeObjcet和readObject方法提供適合自己的序列化方法。
1、序列化是乾什麼的？
簡單說就是為了保存在記憶體中的各種對象的狀態（也就是實例變數，不是方法），並且可以把保存的對象狀態再讀出來。雖然你可以用你自己的各種各樣的方法來保存object states，但是Java給你提供一種應該比你自己好的保存對象狀態的機制，那就是序列化。
2、什麼情況下需要序列化
a）當你想把的記憶體中的對象狀態保存到一個文件中或者資料庫中時候；
b）當你想用套接字在網路上傳送對象的時候；
c）當你想通過RMI傳輸對象的時候；
8.總結
8.1.Arraylist基於數組實現，是自增長的
8.2.非線程安全的
8.3.插入時可能要擴容，刪除時size不會減少，如果需要，可以使用trimToSize方法，在查詢時，遍歷查詢，為null，判斷是否是null， 返回； 如果不是null，用equals判斷，返回
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
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;
}
8.4. 允許重覆和 null 元素
————————————————————————————————————————————————————————————
參考資料：
