ArrayList
ArrayList集合是我們平時使用相當多的集合了际长，本文是我學習ArrayList的源碼铃剔，對于ArrayList源碼相關方法實現(xiàn)的記錄费变。
ArrayList繼承結構
ArrayList初始化
其實ArrayList底層就是一個數(shù)組粥帚。
private transient Object[] elementData;
對這個數(shù)組（也就是ArrayList）的初始化一共有三種方式，分別如下祟剔。
/**
* 第一種方式傅事，設定初始大小。
**/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 第二種方式峡扩，初始化為空的數(shù)組。
**/
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* 第三種方式障本，使用現(xiàn)有的集合教届，對ArrayList進行初始化
**/
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底層原理
ArrayList底層就是一個數(shù)組响鹃，所有add進去的對象都會存儲在elementData這個數(shù)組中。
private transient Object[] elementData; //存儲對象的數(shù)組
首先先來看add方法案训，這里有重載的add方法允許我們分別在index位置和集合最后一個對象后面添加對象买置。
在調(diào)用add方法添加對象的時候，會先調(diào)用ensureCapacityInternal方法强霎，該方法會判斷elementData是否是空的數(shù)組忿项，如果是的話，那么將會把最小容量設置為10城舞，否則最小容量為size + 1轩触。之后調(diào)用ensureExplicitCapacity方法，如果最小容量大于elementData的長度家夺，那么代表數(shù)組存不下了脱柱，那么則進行grow方法進行數(shù)組的擴容操作。
public boolean add(E e) {
ensureCapacityInternal(size + 1); //插入新元素拉馋，判斷size+1是否超過了數(shù)組的大小榨为，如果超過了則進行擴容
elementData[size++] = e;
return true;
}
private static final int DEFAULT_CAPACITY = 10; //集合的默認長度
private void ensureCapacityInternal(int minCapacity) {
//判空操作，如果elementData是{}的話煌茴，則minCapacity將變成默認長度10随闺。
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//如果size +1大于elementData的長度，那么就代表數(shù)組不夠存了蔓腐，就要調(diào)用grow對數(shù)組進行擴容矩乐。
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//elementData擴容方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //新的容量為舊容量的1.5倍。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity); //將舊數(shù)組中的元素拷貝到新容量的新數(shù)組中
}
/**
* 在集合指定位置插入對象合住，與上面的add方法原理相同绰精。
**/
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++;
}
add方法總結：調(diào)用方法時，則判斷size+1是否還小于elementData的長度透葛，也就是數(shù)組是否還能存的下笨使，如果存不下，則將數(shù)組擴容為原來的1.5倍長度僚害，將舊數(shù)組中的所有對象拷貝到新長度的數(shù)組中硫椰，從而先實現(xiàn)了ArrayList可以無限存入對象。
toArray方法
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
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;
}
get方法
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) { //判斷是否會發(fā)生數(shù)組越界
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
檢查index是否數(shù)組越界了萨蚕，之后返回對應位置的對象靶草。
remove方法（容易遇坑的方法）
這里容易遇到兩個坑
坑一，使用for循環(huán)時刪除元素岳遥。
下面代碼是為了刪除集合中2的倍數(shù)的元素奕翔。
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(2);
arrayList.add(4);
arrayList.add(5);
arrayList.add(4);
arrayList.add(0);
arrayList.add(1);
arrayList.add(8);
for(int i = 0; i < arrayList.size(); i++){
if((arrayList.get(i) % 2) == 0){
arrayList.remove(i);
}
}
System.out.println(Arrays.toString(arrayList.toArray()));
}
最后運行結果為 [4, 5, 0, 1]
那么問題來了，4也是2的倍數(shù)浩蓉，怎么沒被刪除派继？
觀察remove的代碼
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); //刪除index位置的元素宾袜，所有元素向前移動。
elementData[--size] = null;
return oldValue;
}
這里使用 System.arraycopy（）方法驾窟，將index位置后的元素向前移動庆猫。那么此時i指向的位置還是index的位置，但是i+1指向的卻是刪除之前index+2的位置了绅络，也就是說下一次循環(huán)月培，就會跳過一個元素。所以每一次刪除之后要將i--恩急。
坑二杉畜，使用foreach循環(huán)的時候進行remove操作。
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(2);
arrayList.add(4);
arrayList.add(5);
arrayList.add(4);
arrayList.add(0);
arrayList.add(1);
arrayList.add(8);
for(Integer integer : arrayList){
if((integer % 2) == 0){
arrayList.remove(integer);
}
}
System.out.println(Arrays.toString(arrayList.toArray()));
}
這是會報ConcurrentModificationException異常
觀察源碼
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
}
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];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
原因：foreach使用的是迭代器假栓，每一次remove寻行，modCount都會+1，之后iterator調(diào)用next方法匾荆，會執(zhí)行checkForComodification方法拌蜘， 就會發(fā)現(xiàn)modCount和expectedModCount值不同就會出現(xiàn)異常。
解決辦法牙丽，獲得迭代器對象简卧，使用迭代器的remove方法。
