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 =https://www.cnblogs.com/noneplus/p/= 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 = https://www.cnblogs.com/noneplus/p/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 = https://www.cnblogs.com/noneplus/p/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），
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/140866.html
標籤：Java