Hello大家好，今天就來介紹一下ArrayList，說到ArrayList，很多人都知道它的底層是使用數(shù)組實現(xiàn)的，線程不安全的，說到它的特點，都會說查找快，增刪慢，因為面試題大家都是這么背過來的。今天就來說說它的底層源碼吧。
ArrayList更準確的說是動態(tài)數(shù)組去實現(xiàn)的，這里使用動態(tài)兩字，是為了能夠充分體現(xiàn)它的特點。
再者就是ArrayList不是線程安全的，所以效率比較高，但是否這個是絕對的呢？答案是否定的 。
重慶分公司
重慶分公司
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
} (1) ArrayList繼承AbstractList抽象類，實現(xiàn)了RandomAccess、Cloneable、Serializable接口，RandomAccess使其擁有快速訪問的能力。
(2) Cloneable其實就是一個標記接口，只有實現(xiàn)這個接口后，然后在類中重寫Object中的clone方法，然后通過類調(diào)用clone方法才能克隆成功，如果不實現(xiàn)這個接口，則會拋出CloneNotSupportedException(克隆不被支持)異常。
(3) Serializable是序列化接口，支持序列化和反序列化。
(4) DEFAULT_CAPACITY 是ArrayList默認的初始化集合的大小。
(5) EMPTY_ELEMENTDATA是一個空對象數(shù)組，用于空實例的共享空數(shù)組實例。
(6) DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是使用默認構(gòu)造函數(shù)創(chuàng)建集合的時候使用該對象
(7) elementData用于存放當前數(shù)據(jù)的數(shù)組對象。
(8) size是集合的大小。
(9) 當集合中的元素超出數(shù)組規(guī)定的長度時，數(shù)組就會進行擴容操作，擴容操作就是ArrayList存儲操作緩慢的原因，尤其是當數(shù)據(jù)量較大的時候，每次擴容消耗的時間會越來越多。
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);
}
}(1) 該構(gòu)造函數(shù)很簡單，直接判斷傳進來的數(shù)值大小，要是大于零，直接初始一個該長度的數(shù)組對象，并賦值給elementData，要是等于零，將空數(shù)組對象EMPTY_ELEMENTDATA賦給elementData，否則，直接拋出異常。
(2) ?該構(gòu)造函數(shù)一般使用在要初始化一個比較大數(shù)據(jù)量的的集合的時候使用。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}(1) 將DEFAULTCAPACITY_EMPTY_ELEMENTDATA空數(shù)組對象賦給elementData
public ArrayList(Collection c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}這里主要做了兩件事:
(1) 先將集合c轉(zhuǎn)化為數(shù)組，然后賦值給elementData數(shù)組對象。
(2) 然后判斷size和是否相等并且不等于0，是則執(zhí)行數(shù)據(jù)的賦值并重新賦值給數(shù)組對象elementData，否則直接將空數(shù)組對象賦值給elementData。
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}(1) 執(zhí)行ensureCapacityInternal方法，判斷原有的數(shù)組對象是否需要擴容。
(2) 將e對象添加到elementData數(shù)組對象中。
接下來我們來看看ensureCapacityInternal方法的源碼。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}在ensureCapacityInternal 中調(diào)用了ensureExplicitCapacity 方法和 calculateCapacity 方法，我們來看下calculateCapacity 方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}(1) 這里的任務(wù)主要是計算容量的大小，先判斷elementData數(shù)組對象是否有初始化大小，若沒有就取DEFAULT_CAPACITY或 minCapacit中的較大者為容量的大小，若已經(jīng)初始化了就minCapacity為容量大小。
接著來看看ensureExplicitCapacity的源碼：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}(1) 執(zhí)行modCount自增，modCount為當前列表結(jié)構(gòu)被修改次數(shù)。
(2) 判斷minCapacity要是大于elementData.length就執(zhí)行擴容，否則，直接退出此方法，進行添加元素的操作。
接著我們來看看grow方法的源碼：
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}(1) 這里先拿到原來數(shù)據(jù)elementData的長度賦給一個變量oldCapacity，然后將原來的長度擴大1.5倍并付給oldCapacity。
(2) 判斷minCapacity 是否大于newCapacity，成立則將minCapacity賦給newCapacity，為什么要這么做呢？因為從前的一層層的方法進行解析之后來看，minCapacity是允許擴容后的最小長度，也就是實際存有數(shù)據(jù)的最小長度，要是你擴容后的長度還比minCapacity要小，那么只能將minCapacity作為容器的長度。
(3) 然后判斷容器新長度newCapacity是否大于容器所允許的大長度MAX_ARRAY_SIZE，成立則將擴容長度設(shè)置為大可用長度。
(4) 拷貝，擴容，構(gòu)建一個新的數(shù)組。
接著我們來看看grow方法調(diào)用的hugeCapacity的源碼：
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}(1) 直接判斷minCapacity是否小于零，成立拋出異常，然后比較容器所允許的最小長度值是否大于MAX_ARRAY_SIZE，成立則將Integer的大值賦值給minCapacity作為容器的大長度。
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++;
}(1) ?這里主要做三件事，第一件就是判斷下標是否越界，如果是則拋出IndexOutOfBoundsException異常。
(2) 然后就是判斷是否需要擴容，這個方法和上面的一樣，已經(jīng)說過了，就不再贅述了。
(3) 最后就是執(zhí)行數(shù)組對象index后的對象后移一位，將元素添加到指定位置。
接下來我們來看看rangeCheckForAdd的源碼
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}(1) 直接就是判斷index > size或者index < 0條件，成立就直接拋出數(shù)組下標越界異常。
public boolean addAll(Collection c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}(1) addAll(Collection c)方法里面直接調(diào)用addAll(this.size, c)，在addAll(this.size, c)里面第一件事就是判斷是否下標越界。
(2) 然后判斷c的大小是否大于0，如果等于0 返回 false。
(3) 檢查修改的次數(shù)是否相等，若不相等直接則拋出ConcurrentModificationException（并發(fā)修改）異常，這個也就是當我們用迭代器循環(huán)list的時候，在其中用list的方法新增/刪除元素，就會出現(xiàn)這個錯誤。
(4) 將元素插入到數(shù)組中，將修改次數(shù)賦值給 modCount，最后size大小加一
(5) 在進行 add 操作時先判斷下標是否越界，是否需要擴容，如果需要擴容，就復制數(shù)組，默認擴容一半，如果擴容一半不夠的話，就用目標的size作為擴容后的容量，然后設(shè)置對應(yīng)的下標元素值。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}(1) 這個就很簡單了直接就是先判斷是否下標越界，越界就拋出異常，最后返回指定index位置的元素值。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}(1) 先判斷是否越界，然后取出原來index位置的值為oldValue，將新的值element設(shè)置到index位置，最后將舊的值oldValue返回。
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;
}(1) 判斷是否越界，然后將修改次數(shù)modCount值加1，然后就是獲得原來index位置的舊值。
(2) 然后是計算index位置后面有多少個元素，接著將index位置后的元素向前移動一位，最后將舊值返回。
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
}(1) 這個根據(jù)對象刪除的方法比較簡單，首先判斷o對象是否為null對象，為null就遍歷集合中的元素，是否存在null值，存在執(zhí)行刪除，刪除指定對象的方法是fastRemove，原理就是計算index位置后的元素個數(shù)，然后將index后的元素都往前移動一位，最后將最后的一位賦值為null值。
(2) 若o對象是不為null對象的時候，執(zhí)行的邏輯是一樣的，那么為什么要分開寫呢？很簡單，因為它后面要調(diào)用o.equals(elementData[index]方法進行判斷，要是為null，不就報空指針異常了。
public Iterator iterator() {
return new Itr();
}
private class Itr implements Iterator {
int cursor;
int lastRet = -1;
int expectedModCount = modCount;
Itr() {}
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();
}
}
} (1) 迭代器中有幾個屬性比較重要，int cursor是下一個要返回的元素的索引， int lastRet = -1 ?是返回的最后一個元素的索引，默認為-1，就是沒有的情況。
(2) hasNext方法判斷是否存在下一個元素，通過判斷以下一個下標是否為數(shù)組大小。
(3) next方法獲取下一個元素，首先先調(diào)用checkForComodification方法檢查修改的次數(shù)是否一致，然后定義下一個元素的下標，判斷下標，如果下標大于ArrayList包含的元素個數(shù)，拋出 NoSuchElementException （沒有這樣的元素異常）異常，接著拿到ArrayList中的elementData數(shù)據(jù)對象，再次判斷下標，如果此次判斷不一致則說明數(shù)組被修改過，最后將cursor +1，指向下一個元素的下標，最后將lastRet定義為返回的元素的下標，然后返回下標對應(yīng)的值。
(4) remove移除當前元素，首先判斷最后一個元素的下標lastRet 是否小于0，成立則不存在該元素，拋出異常，然后又調(diào)用 checkForComodification，判斷修改次數(shù)是否一致，接著調(diào)用ArrayList的remove方法，最后重新更新cursor 、 lastRet、expectedModCount的值。
