ArrayList是我們開發中最常用到的集合，但是很多人對它的原始碼并不了解，導致面試時，面試官問的稍微深入的問題，就無法作答，今天我們一起來探究一下ArrayList原始碼，
1. 簡介
- ArrayList底層是陣列，允許元素是null，能夠動態擴容
- size、isEmpty、get、set、add 等方法時間復雜度都是 O (1)
- 非執行緒安全，并發修改時，會拋出ConcurrentModificationException
2. 初始化
// 初始容量
private static final int DEFAULT_CAPACITY = 10;
// 空陣列
private static final Object[] EMPTY_ELEMENTDATA = https://www.cnblogs.com/yidengjiagou/p/{};
// 默認空陣列
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存盤元素的陣列
transient Object[] elementData;
// 無參初始化，默認是空陣列
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 有參初始化，指定容量大小
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);
}
}
切記：無參初始化的時候，默認是空陣列，并沒有初始化容量大小，容量是在第一次添加元素的才進行初始化，
3. 添加元素
public boolean add(E e) {
// 確保陣列容量夠用，size是元素個數
ensureCapacityInternal(size + 1);
// 直接賦值
elementData[size++] = e;
return true;
}
// 確保陣列容量夠用
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 計算所需最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果陣列等于空陣列，最小容量為10
if (elementData =https://www.cnblogs.com/yidengjiagou/p/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果所需最小容量大于陣列長度，就進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
看一下擴容邏輯：
// 擴容，就是把舊資料拷貝到新陣列里面
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// oldCapacity >> 1 是把oldCapacity除以2，意思是1.5倍擴容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果擴容后的容量小于最小容量，擴容后的容量就等于最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果擴容后的容量大于Integer的最大值，就用Integer最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 擴容并賦值給原陣列
elementData = https://www.cnblogs.com/yidengjiagou/p/Arrays.copyOf(elementData, newCapacity);
}
可以看到：
- 擴容是以原容量的1.5倍擴容，并不是翻倍擴容
- 最大容量是Integer的最大值
- 添加元素時，沒有對元素校驗，可以是null
再看一下陣列拷貝的邏輯，這里都是Arrays類里面的方法了：
/**
* @param original 原陣列
* @param newLength 新的容量大小
*/
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
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;
}
最終呼叫了System類的陣列拷貝方法，是native方法：
/**
* @param src 原陣列
* @param srcPos 原陣列的開始位置
* @param dest 目標陣列
* @param destPos 目標陣列的開始位置
* @param length 被拷貝的長度
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
4. 洗掉單個元素
public boolean remove(Object o) {
// 判斷要洗掉的元素是否為null
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)
// 從index+1位置開始拷貝，也就是后面的元素整體向左移動一個位置
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 陣列最后一個元素賦值為null，防止會導致記憶體泄漏
elementData[--size] = null;
}
可以知道，洗掉元素，就是遍歷陣列，回圈比較是否等于目標值，如果相等，就把該位置后面的元素整體向左移動一個位置，再把陣列最后一個元素賦值為null，
5. 批量洗掉
// 批量洗掉ArrayList和集合c都存在的元素
public boolean removeAll(Collection<?> c) {
// 非空校驗
Objects.requireNonNull(c);
// 批量洗掉
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement){
final Object[] elementData = https://www.cnblogs.com/yidengjiagou/p/this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
// 把需要保留的元素左移
elementData[w++] = elementData[r];
} finally {
// 當出現例外的時候，可能不相等
if (r != size) {
// 1：可能是上面的for回圈出現了例外
// 2：可能是其它執行緒添加了元素
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// 把不需要保留的元素賦值為null
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
可以知道，批量洗掉的時候，只會進行一次陣列拷貝，比用for回圈單個洗掉效率更高，所以洗掉一批元素的時候，盡量用removeAll()方法，
5. 總結
本文分析了ArrayList的初始化、put、add、remove、動態擴容等方法的底層原始碼，相信大家對于ArrayList有了更深層次的了解，下篇一塊學習一下LinkedList的原始碼，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/488683.html
標籤：Java