本系列文章所描述的所有類或接口都是基于 JDK 1.7的源碼，在其它 JDK 的實現(xiàn)方式中可能會有所不同轮纫。
一、 ArrayList
1. 創(chuàng)建 ArrayList
在 JDK 1.7 中創(chuàng)建 ArrayList 提供了三個構(gòu)造函數(shù)金赦，分別如下：
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
super(); // 調(diào)用的是 AbstractList 空的構(gòu)造函數(shù)
this.elementData = EMPTY_ELEMENTDATA; // EMPTY_ELEMENTDATA 的初始值為 Object[] EMPTY_ELEMENTDATA = {}
}
/**
* 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);
}
據(jù)此可以看出跷究，ArrayList 采用的是數(shù)組的方式來存放對象跳昼，在沒有指定初始化容量的時候般甲，就分配了一個空的對象數(shù)組，沒有任何對象元素鹅颊，也就是容量為0欣除，沒有分配空間。
2. 插入對象：add(E)
add 方法簡單來看就是將數(shù)組中某元素的值賦值為傳入的對象挪略，但在 add 時有個很明顯的問題是：如果此時數(shù)組滿了，該怎么辦滔岳？
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // DEFAULT_CAPACITY = 10
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(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);
}
當調(diào)用 ArrayList 的 add 方法時杠娱，首先基于 ArrayList 中已有的元素數(shù)量加1，產(chǎn)生一個名為 minCapacity 的變量谱煤，然后比較此值和 Object 數(shù)組的大小摊求，如果此值大于 Object 數(shù)組大小值，產(chǎn)生一個新的數(shù)組的容量值刘离，此值的計數(shù)方法為當前數(shù)組大小值*1.5室叉，注意：網(wǎng)上很多人說是新的容量值是原來的1.5倍然后加1，其實這是錯誤的硫惕。茧痕，如果得出的容量值仍然小于 minCapacity ，那么就以 minCapacity 作為新的容量值恼除，在得出這個容量值后踪旷，調(diào)用 Arrays.copyOf 來生成新的數(shù)組對象。如果想調(diào)整容量的增長策略豁辉，可以調(diào)用 ensureCapacity 方法令野。
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != EMPTY_ELEMENTDATA)
// any size if real element table
? 0
// larger than default for empty table. It's already supposed to be
// at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
Arrays.copyOf 的實現(xiàn)方法簡單來說，首先是創(chuàng)建一個新的數(shù)組對象徽级，該數(shù)組對象的類型和之前 ArrayList 中元素的類型是一致的气破，如果是 Object 類型，則直接通過 new Object[newLength] 的方式來創(chuàng)建餐抢；如果不是 Object 類型现使，則通過 Array.newInstance 調(diào)用 native 方法來創(chuàng)建相應類型的數(shù)組低匙，在創(chuàng)建完新的數(shù)組對象后，調(diào)用 System.arraycopy 通過 native 方法將之前數(shù)組中的對象復制到新的數(shù)組中朴下。ArrayList相當于在沒指定initialCapacity時就是會使用延遲分配對象數(shù)組空間努咐，當?shù)谝淮尾迦朐貢r才分配10個對象空間。
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;
}
當我們已經(jīng)確定了要插入的對象的數(shù)目（并不是在創(chuàng)建ArrayList之前就知道有多少對象要插入的情況）殴胧，就應該首先調(diào)用ensureCapacity來一次性擴容到可以容得下要插入的對象個數(shù)渗稍，這樣就避免的多次進行數(shù)組拷貝的情況，提高了效率团滥，算是優(yōu)化吧竿屹，當然，我們在創(chuàng)建ArrayList之前就知道有多少對象要插入就使用有參構(gòu)造灸姊。
在 Collection 中增加對象時拱燃，ArrayList 還提供了 add(int, E) 這樣的方法，允許將元素直接插入指定的 int 位置上力惯，這個方法的實現(xiàn)首先要確保插入的位置是目前的 Array 數(shù)組中存在的碗誉，之后還要確保數(shù)組的容量是夠用的。在完成了這些動作后父晶，和 add(E) 不同的地方就出現(xiàn)了哮缺，它要將當前的數(shù)組對象進行一次復制，即將目前 index 及其后的數(shù)據(jù)都往后挪動一位甲喝，然后才能將指定的 index 位置的賦值為傳入的對象尝苇，可見這種方式要多付出一次復制數(shù)組的代價。
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++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
除了 add(int, E) 這種方法可將對象插入指定的位置外埠胖，ArrayList 還提供了 set(int, E) 這樣的方法來替換指定位置上的對象糠溜。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
ArrayList 還對外提供了 addAll(Collection<? extends E> c) 和 addAll(int index, Collection<? extends E> c) 這樣的方法，其實現(xiàn)方式和 add(E)直撤、add(int, E) 基本類似非竿。
3. 刪除對象：remove(E)
remove 對于集合的性能而言也非常重要，當執(zhí)行此方法時谋竖，ArrayList 首先判斷對象是否為 null汽馋，如為 null，則遍歷數(shù)組中已有值的元素圈盔，并比較其是否為 null豹芯，如為 null，則調(diào)用 fastRemove 來刪除相應位置的對象驱敲。fastRemove 方法的實現(xiàn)方式為將 index 后的對象往前復制一位铁蹈，并將數(shù)組中的最后一個元素的值設(shè)置為 null，即釋放了對此對象的引用众眨；如對象非 null握牧，唯一的不同在于通過 E 的 equals 來比較元素的值是否相同容诬，如相同則認為是需要刪除對象的位置，然后同樣是調(diào)用 fastRemove 來完成對象的刪除沿腰。由此可見調(diào)用 remove 方法一次只會移除一個元素览徒。
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;
}
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; // clear to let GC do its work
}
ArrayList 中還提供了 remove(int) 這樣的方法來刪除指定位置的對象，remove(int) 的實現(xiàn)比 remove(E) 多了一個數(shù)組范圍檢測颂龙，但少了對象位置的查找习蓬，因此性能會更好。
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; // clear to let GC do its work
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
4. 獲取單個對象：get(int)
get 傳入的參數(shù)為數(shù)組元素的位置措嵌，因此 ArrayList 僅須先做數(shù)組范圍的檢測躲叼，然后即可直接返回數(shù)組中位于此位置的對象。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
5. 遍歷對象：iterator()
當每次調(diào)用 iterator 方法時企巢，都會創(chuàng)建一個新的內(nèi)部類 Itr 的實例枫慷。當調(diào)用此實例的 hasNext 方法時，比較當前指向的數(shù)組的位置是否和數(shù)組中已有的元素大小相等浪规，如相等則返回 false或听，否則返回 true。
當調(diào)用實例的 next 方法時笋婿，首先比較在創(chuàng)建此 Iterator 時獲取的 modCount 與目前的 modCount誉裆，如果這兩個 modCount 不相等，則說明在獲取 next 元素時萌抵，發(fā)生了對于集合大小產(chǎn)生影響（新增、刪除）的動作元镀。當發(fā)生這種情況時绍填，則拋出 ConcurrentModificationException。如果 modCount 相等栖疑，則比較當前的游標讨永，如果當前的游標大于數(shù)組的實際大小，則拋出 NoSuchElementException遇革。如果當前游標大于數(shù)組的長度則拋出 ConcurrentModificationException卿闹。
注意：返回的 iterator 是 fail-fast 的。fail-fast 也就是“快速失敗”萝快，它是Java 集合的一種錯誤檢測機制锻霎。當多個線程對集合進行結(jié)構(gòu)上的改變的操作時，有可能會產(chǎn)生fail-fast機制揪漩。記住是有可能旋恼，而不是一定。例如：假設(shè)存在兩個線程（線程1奄容、線程2）冰更，線程1通過Iterator在遍歷集合A中的元素产徊，在某個時候線程2修改了集合A的結(jié)構(gòu)（是結(jié)構(gòu)上面的修改，而不是簡單的修改集合元素的內(nèi)容）蜀细，那么這個時候程序就會拋出 ConcurrentModificationException 異常舟铜，從而產(chǎn)生fail-fast機制。
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
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 != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
fail-fast解決辦法
方案一：在遍歷過程中所有涉及到改變modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList奠衔，這樣就可以解決谆刨。但是不推薦，因為增刪造成的同步鎖可能會阻塞遍歷操作涣觉。
方案二：使用CopyOnWriteArrayList來替換ArrayList痴荐。推薦使用該方案。
6. 判斷對象是否存在：contains(E)
為了判斷 E 在 ArrayList 中是否存在官册，做法為遍歷整個 ArrayList 中已有的元素生兆，如 E 為 null，則直接判斷已有元素是否為 null膝宁，如為 null鸦难，則返回 true；如 E 不為 null员淫，則通過判斷 E.equals 和元素是否相等合蔽，如相等則返回 true。
indexOf 和 lastIndexOf 是 ArrayList 中用于獲取對象所在位置的方法介返，其中 indexOf 為從前往后尋找拴事，而 lastIndexOf 為從后向前尋找。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
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;
}
7. 注意要點
對于 ArrayList 而言圣蝎，最須注意的有以下幾點：
- ArrayList 基于數(shù)組方式實現(xiàn)刃宵，無容量的限制；
- ArrayList 在執(zhí)行插入元素時可能要擴容徘公，在刪除元素時并不會減小數(shù)組的容量(如希望相應的縮小數(shù)組容量牲证，可以調(diào)用 ArrayList 的 trimToSize() )，在查找元素時要遍歷數(shù)組关面，對于非 null 的元素采取 equals 的方式尋找暑塑；
- ArrayList 是非線程安全的钧敞。
