ArrayList是Java中常用的一個集合類畅姊，是List接口的一個實現(xiàn)類席怪，而List接口繼承自Collection接口腌紧，所以ArrayList是Collection的一個實現(xiàn)類砸喻。
本篇主要討論一下ArrayList底層代碼的實現(xiàn)陶珠。
核心的成員變量
先來看看ArrayList中幾個核心的成員變量挟裂。
//初始化數(shù)組的大小，ArrayList底層是基于數(shù)組實現(xiàn)的
private static final int DEFAULT_CAPACITY = 10;
//一個空數(shù)組對象动分，用于無參數(shù)的情況下初始化數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//底層存放數(shù)據(jù)的數(shù)組
transient Object[] elementData;
//已存放的元素數(shù)量
private int size;
//定義數(shù)組的最大容量滨溉，實際數(shù)組的大小可以擴大到Integer.MAX_VALUE的大小住诸，該字段應(yīng)該是預(yù)留字段
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
默認(rèn)無參的構(gòu)造函數(shù)
public ArrayList() {
//這里首先初始化用于存放數(shù)據(jù)的數(shù)組，默認(rèn)數(shù)組的大小為空
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
add方法實現(xiàn)
//這里添加一個元素渠啤，添加成功后將size+1，并返回true
public boolean add(E e) {
//傳入size+1添吗，表示數(shù)組的容量應(yīng)該滿足最小的容量
ensureCapacityInternal(size + 1);
//將當(dāng)前添加的元素存放到數(shù)組中
elementData[size++] = e;
return true;
}
//該方法用來確保當(dāng)前數(shù)組的大小是否滿足最小要求沥曹，并對數(shù)組擴容
private void ensureCapacityInternal(int minCapacity) {
//calculateCapacity方法傳入存放數(shù)據(jù)的數(shù)組與該數(shù)組要求滿足的最小容量，并返回設(shè)置的容量大小
//ensureExplicitCapacity會判斷當(dāng)前數(shù)組的是否需要擴容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//當(dāng)數(shù)組的第一次使用時碟联，返回初始化容量DEFAULT_CAPACITY=10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//判斷當(dāng)前數(shù)組的是否需要擴容
private void ensureExplicitCapacity(int minCapacity) {
//該變量為AbstractList中的成員變量妓美，在用iterator迭代器獲取數(shù)據(jù)的數(shù)據(jù)使用
modCount++;
//此處判斷當(dāng)前數(shù)組的容量是否滿足要求
if (minCapacity - elementData.length > 0)
//調(diào)用該方法對數(shù)組進(jìn)行擴容
grow(minCapacity);
}
//實際進(jìn)行數(shù)組擴容拷貝操作
private void grow(int minCapacity) {
//當(dāng)前數(shù)組的容量大小
int oldCapacity = elementData.length;
//新數(shù)組的容量大小，oldCapacity >> 1實際為oldCapacity/2
//這里也就是將數(shù)組的容量擴大1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//由于第一次調(diào)用該方法時鲤孵，數(shù)組的容量大小為0壶栋，所以這里會將默認(rèn)數(shù)組大小賦予newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//當(dāng)新數(shù)組的容量大小大于MAX_ARRAY_SIZE時，將數(shù)組的大小設(shè)置為Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//最后普监，將數(shù)組進(jìn)行拷貝擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
//該方法返回數(shù)組的最大容量大小
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
具體步驟如下：
- 當(dāng)?shù)谝淮握{(diào)用add方法添加元素時贵试，會對elementData數(shù)組進(jìn)行擴容，默認(rèn)大小為DEFAULT_CAPACITY=10鹰椒；
- 之后每一次調(diào)用add方法時锡移，會對elementData數(shù)組的大小進(jìn)行判斷，判斷當(dāng)前容量是否滿足最小要求漆际；
- 如果不滿足淆珊，則調(diào)用grow方法，對數(shù)組的大小擴容為原來大小的1.5倍奸汇；
- 當(dāng)elementData數(shù)組的容量大小大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）時施符，將數(shù)組的容量大小設(shè)置為Integer.MAX_VALUE往声；
- 添加成功后，對size加1戳吝，并對數(shù)組進(jìn)行賦值數(shù)據(jù)浩销，然后返回true；
帶參數(shù)的構(gòu)造函數(shù)
//傳入初始化數(shù)組大小的參數(shù)
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//初始化elementData數(shù)組大小
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
在add方法中听哭，我們了解到慢洋，在添加元素的過程中，涉及到對元素進(jìn)行擴容的操作陆盘，如果需要在數(shù)組中頻繁添加大量元素普筹，將會對elementData數(shù)組進(jìn)行多次拷貝擴容操作，很消耗性能隘马，所以太防，我們可以先預(yù)估數(shù)組的大小，并調(diào)用帶參數(shù)的構(gòu)造函數(shù)酸员，傳入初始化數(shù)組的大小的參數(shù)蜒车，可以避免在add元素的拷貝擴容操作，提升性能幔嗦。
get方法實現(xiàn)
//傳入要獲取數(shù)據(jù)的索引下標(biāo)酿愧，返回對應(yīng)位置的數(shù)據(jù)
public E get(int index) {
//檢查該索引下標(biāo)是否越界
rangeCheck(index);
return elementData(index);
}
//判斷當(dāng)前索引下標(biāo)是否大于當(dāng)前數(shù)組存放數(shù)據(jù)的大小，如果索引下標(biāo)越界崭添，則報IndexOutOfBoundsException異常
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//返回數(shù)組中對應(yīng)索引下標(biāo)位置的數(shù)據(jù)
E elementData(int index) {
return (E) elementData[index];
}
get方法實現(xiàn)比較簡單寓娩，步驟如下：
- 首先對傳入索引下標(biāo)進(jìn)行檢查，如果下標(biāo)越界呼渣，則拋出IndexOutOfBoundsException異常棘伴；
- 如果該索引下標(biāo)合法，則返回對應(yīng)索引下標(biāo)位置的數(shù)據(jù)屁置；
remove(int index)方法實現(xiàn)
//傳入要刪除的索引下標(biāo)焊夸，并返回該索引下標(biāo)元素，也就是刪除了的元素
public E remove(int index) {
//檢查索引下標(biāo)是否合法
rangeCheck(index);
modCount++;
//取出該下標(biāo)位置的元素
E oldValue = elementData(index);
//數(shù)組中要向前移動的元素的數(shù)量蓝角，刪除指定索引元素時阱穗，會將該索引后面的元素向前移
int numMoved = size - index - 1;
if (numMoved > 0)
//將指定索引下標(biāo)之后的元素向前移動
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//因為數(shù)組向前移動了，所以將數(shù)組中最后一個元素的值設(shè)置為null
elementData[--size] = null;
//返回刪除了的元素
return oldValue;
}
具體步驟如下：
- 檢查指定索引下標(biāo)是否合法使鹅，如不合法揪阶，拋出IndexOutOfBoundsException異常；
- 獲取指定索引下標(biāo)的元素數(shù)據(jù)患朱，用于刪除后返回鲁僚；
- 刪除數(shù)據(jù)是基于數(shù)組前移操作的，numMoved 為要前移元素的數(shù)量，假如當(dāng)前數(shù)組為[1,2,3,4]冰沙，那么數(shù)組的size為4侨艾，當(dāng)要刪除的index=1時，這里計算出來的numMoved=2拓挥，所以實際調(diào)用的是System.arraycopy([1,2,3,4], 2, [1,2,3,4], 1, 2)唠梨，也就是從索引下標(biāo)為2的位置開始后兩個元素向前移動到下標(biāo)為1的位置，移動后的結(jié)果為[1,3,4,4]侥啤；
- 將數(shù)組元素的最后一個值設(shè)置為null当叭；
- 返回刪除了的元素；
remove(Object o)方法實現(xiàn)
//刪除某個元素愿棋，刪除成功科展，返回true，否則返回false
public boolean remove(Object o) {
//如果要刪除的對象為null糠雨，則刪除數(shù)組第一個為null的元素
if (o == null) {
//遍歷數(shù)組，獲取出要刪除的元素的下標(biāo)
for (int index = 0; index < size; index++)
//查找出第一個元素為null的下標(biāo)
if (elementData[index] == null) {
//執(zhí)行按照索引刪除元素徘跪，實現(xiàn)方法與remove(int index)類似
fastRemove(index);
return true;
}
} else {
//遍歷數(shù)組甘邀，獲取出要刪除的元素的下標(biāo)
for (int index = 0; index < size; index++)
//查找出要刪除的元素的下標(biāo)
if (o.equals(elementData[index])) {
//執(zhí)行按照索引刪除元素，實現(xiàn)方法與remove(int index)類似
fastRemove(index);
return true;
}
}
return false;
}
//刪除指定索引的元素垮庐，與remove(int index)方法邏輯類似
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
}
具體步驟：
- 判斷要刪除的元素是否為null松邪，如果為null，則先遍歷獲取數(shù)組中第一個為null的索引下標(biāo)哨查，然后根據(jù)該索引下標(biāo)刪除元素逗抑，也就是刪除數(shù)組中第一個為null的元素；
- 如果要刪除的元素不為空寒亥，則遍歷獲取第一個出現(xiàn)在數(shù)組中的索引下標(biāo)邮府，然后根據(jù)索引下標(biāo)刪除該元素，也就是刪除第一個與元素匹配的數(shù)據(jù)溉奕；
- 刪除成功褂傀，返回true，否則加勤，返回false;
適用場景
通過源碼的分析仙辟，我們知道，arrayList底層是基于數(shù)組實現(xiàn)的鳄梅，每個存儲的元素叠国，都擁有一個元素的下標(biāo)，所以戴尸，當(dāng)我們需要通過下標(biāo)獲取數(shù)據(jù)的時候粟焊，適合使用ArrayList來存取數(shù)據(jù)；而當(dāng)在添加與刪除元素的時候，可能會涉及到數(shù)組的擴容與拷貝吆玖，所以arrayList不適添加和刪除比較多的場景筒溃。
