1，ArrayList面試必問
- 說說ArrayList和LinkedList的差別？
ArrayList基于數組實作，LinkedList基于連結清單實作，不同的資料結構決定了ArrayList查詢效率比較高，而LinkedList插入删除效率比較高，反過來就比較慢了。
- ArrayList預設初始容量為多少？按照幾倍來擴容？
10，1.5倍。
- 說說數組擴容的原理？
ArrayList擴容調用的是Array.copyof函數，把老數組周遊指派給新數組傳回。
- 說說ArrayList常見方法的時間複雜度？
- get方法通過下标擷取元素，時間複雜度為O（1）
- add方法直接添加會添加到集合的尾部，時間複雜度為O（1）
- add方法通過下标添加到非尾部會引起數組的批量移動，時間複雜度為O（n），否則為O（1）
- remove方法通過下标删除非尾部元素引起數組批量移動，時間複雜度為O（n），反之則為O（1）
- remove方法根據對象删除需要周遊集合，時間複雜度為O（n），如果删除的為非尾部元素，會使數組批量移動，時間複雜度為O（n^2）
總之，通過下标操作的時間複雜度為O（1），如果觸發了數組的批量移動，時間複雜度為O（n），如果通過對象操作需要周遊集合，時間複雜度已經為O（n），若同時觸發了數組的移動，時間複雜度為O（n^2）.
- ArrayList和vector的差別
- 最大的差別在于線程是否安全
- 其次Vector是兩倍擴容
- 最後就是在不指定大小的情況下，ArrayList容量初始化是在添加元素的時候，而Vector有一個無參構造器直接初始化為10
2，Debug ArrayList源碼
由于1.7和1.8幾乎沒什麼變化，本文以jdk1.8為例。
2.1 用Debug分析一個元素是如何add進ArrayList
編寫測試用例，打上斷點：
先分析構造函數如何初始化，關鍵步驟如下：
elementData是ArraList底層數組的實作，（ps：hashMap數組使用table命名）
DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示預設的空數組，也就是說ArrayList在構造函數初始化時并不會進行底層數組的初始化。
給元素的添加打上斷點，分析過程：
進入add方法内部：
public boolean add(E e) {
//確定内部容量，在元素添加進來前可能要進行擴容操作，size初始化為0，表示集合的長度
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加元素，size自增
elementData[size++] = e;
return true;
} 進入ensureCapacityInternal方法内部：此時elementData為空，size+1=minCapacity=1
ensureExplicitCapacity：確定明确的能力 計算容量，calculateCapacity方法：
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//判斷數組是否為空，若為空，傳回預設容量和最小容量的最大值，若不為空，傳回最小容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
} DEFAULT_CAPACITY預設容量為10：
繼續分析，進入：
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));此時參數為10，也就是ArrayList的預設容量 private void ensureExplicitCapacity(int minCapacity) {
modCount++; //集合的修改次數
//如果最小容量減去數組長度大于0，進行擴容，此時最小容量為10，數組長度為0
if (minCapacity - elementData.length > 0)
grow(minCapacity);
} 核心擴容函數grow：（ps：HashMap中擴容函數為resize）
private void grow(int minCapacity) {
//oldCapacity：舊數組容量
int oldCapacity = elementData.length;
//新容量等于舊容量加上舊容量的一半,>>1相當于除以2（ArrayList擴容是1.5倍）
int newCapacity = oldCapacity + (oldCapacity >> 1);
//新容量小于最小容量，則指派為最小容量，此時newCapacity等于0，minCapacity為10
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//指派給新數組
elementData = Arrays.copyOf(elementData, newCapacity);
} 數組複制Arrays.copyOf：
2.2 用Debug分析如何通過數組下标擷取ArrayList元素
打上斷點，debug：
首先進行範圍檢查，而後傳回元素
2.3 用Debug分析如何通過數組下标删除一個元素
打上斷點：
進入remove方法内部，
public E remove(int index) {
//下标範圍檢查
rangeCheck(index);
//修改次數自增
modCount++;
//保留目前删除元素的值，稍後傳回
E oldValue = elementData(index);
//需要移動元素的個數
int numMoved = size - index - 1;
if (numMoved > 0)
//底層使用native方法，debug進不去。native方法：java調用其他語言的接口
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//最後一位置空
elementData[--size] = null; // clear to let GC do its work
//傳回删除元素的值
return oldValue;
} 2.4 用Debug分析如何通過對象删除一個元素
進入remove方法：
public boolean remove(Object o) {
//如果對象為空，則周遊ArrayList集合
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;
} 進入fastRemove方法：
private void fastRemove(int index) {
modCount++;
//numMoved：需要移動數組的個數
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 wrk
} 2.5 用Debug分析向數組中間添加元素
進入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++;
} 關于System.arraycopy時間複雜度問題，在添加或者删除最後一個元素的時候不會觸發數組的複制機制，時間複雜度為O（1），若是添加到數組中間，由于會觸發數組的複制，時間複雜度為O（n）。對于删除元素同樣，根據數組下标删除的情況下，删除尾部元素是不會觸發數組的擴容機制的，若删除中間的元素，同樣會觸發數組的複制。若根據對象删除元素，由于本身周遊到對象的時間複雜度為O（n），删除元素後再對數組進行重組，是以時間複雜度為O（n^2）。