ArrayList源碼解析
序言：ArrayList是Java集合中的基礎中的基礎，也是面試中常問常考的點，今天我們來點簡單的，盤盤ArrayList
下面我憑自己的經驗大概說一下如何看源碼。
- 先看繼承結構，方便了解整體的邏輯和關係
- 再看核心調用方法，看它做了什麼，方便了解核心的功能
- 得有看英文注釋的習慣，畢竟它相當於說明書
ArrayList 簡介
註：本篇文章所有分析，針對 jdk1.8版本
-
ArrayList 的本質是可以動態擴容的數組集合，是基於數組去實現的List類
-
ArrayList 的底層的數據結構是 Object[] 類型的數組，默認創建為空數組，採用懶載入的方式節省空間，每次採取1.5倍擴容的方式
-
ArrayList 是執行緒不安全的，執行緒安全的 List 參考
Collections.synchronizedList()或者 CopyOnWriteArrayList
ArrayList源碼分析
繼承結構
大致結構如上圖，先考慮三個問題：
1.為什麼要繼承 AbstractList，而讓 AbstractList 去實現 List , 並不是直接實現呢 ?
這裡主要運用了模板方法設計模式，設想一下，jdk 開發作者 還有一個類要實現叫 LinkedList ，它也有何 ArrayList 相同功能的基礎方法，但是由於是直接實現介面的方式，這個 類 LinkedList 就沒法復用之前的方法了
2.ArrayList 實現了哪些其他介面，有什麼用 ?
RandomAccess 介面： 是一個標誌介面， 表明實現這個這個介面的 List 集合是支援快速隨機訪問的。也就是說，實現了這個介面的集合是支援 快速隨機訪問 策略的，實現了此介面 for循環的迭代效率，會高於 Iterator
Cloneable 介面： 實現了該介面，就可以使用 Object.Clone()方法
Serializable 介面：實現序列號介面，表明該類可以被序列化
3. 為什麼AbstractList 已經實現了 List介面了，作為父類ArrayList 再去實現一遍呢 ?
作者說這是一個錯誤，一開始拍腦袋覺得可能有用，後來沒用到，但沒什麼影響就留到了現在
類中的屬性
public class ArrayList extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private static final long serialVersionUID = 8683452581122892189L;
//默認初始容量為10
private static final int DEFAULT_CAPACITY = 10;
//空的對象數組
private static final Object[] EMPTY_ELEMENTDATA = {};
//預設空對象數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//集合容器，transient標識不被序列化
transient Object[] elementData;
//容器實際元素長度
private int size;
}
核心方法
創建集合
1. 使用無參構造器
/**
* 默認無參構造器創建的時候其實只是個空數組，使用懶載入節省記憶體開銷
* Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2. 創建時，指定集合大小，如何一開始就能預估存儲元素的size，推薦用此種方式
public ArrayList(int initialCapacity) {
/**
* 如果initialCapacity > 0,就申明一個這麼大的數組
* 如果initialCapacity = 0,就用屬性 EMPTY_ELEMENTDATA
* Object[] EMPTY_ELEMENTDATA = {}
* 如果initialCapacity < 0,不合法,拋異常
*/
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
添加集合元素
可以看出有四個添加的方式，我們挑選前兩個常用方法講解源碼，其他基本差不多
1. boolean add(E) 默認在末尾插入元素
/**
* 添加一個元素到list的末端
*/
public boolean add(E e) {
//確保內置的容量是否足夠
ensureCapacityInternal(size + 1);
//如果足夠添加加元素放進數組中,size + 1
elementData[size++] = e;
//返回成功
return true;
}
//minCapacity = size + 1
private void ensureCapacityInternal(int minCapacity) {
//確認容器容量是否足夠
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//先計算容量大小,elementData是初始創建的集合容器,minCapacity= size + 1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//判斷初始容器是否等於空
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//為空,就拿size + 1和默認容量10比,誰大返回誰
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//否則返回size + 1
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//列表結構被修改的次數,用戶迭代時修改列表拋異常(ConcurrentModifyException)
modCount++;
/**
* minCapacity 如果超過容器的長度，則進行擴容,兩種場景
* 1.第一次添加元素,minCapacity = size + 1,size = 0,在上個方法中會
* 與默認的容器容量10進行大小比較最後為10,那麼10 > 0,初始化容器
* 2.添加到第10個元素,上個方法則返回 size + 1 = 11,11 > 10,需要擴容
* 不然數組裝不下了
*/
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//容器的擴容方法
private void grow(int minCapacity) {
//將擴充前的容器長度賦值給oldCapacity
int oldCapacity = elementData.length;
//擴容後的newCapacity = 1 + 1/2 = 1.5,所以為1.5倍擴容
int newCapacity = oldCapacity + (oldCapacity >> 1);
/**
* 適用於初始創建,elementData為空數組,length = 0
* oldCapacity = 0,但minCapacity = 10,此處則進行了初始化
*/
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量超過容量上限Integer.MAX_VALUE - 8,則會再嘗試擴容
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//新的容量確定後,只需要將舊元素全部拷貝進新數組就可以了
elementData = Arrays.copyOf(elementData, newCapacity);
}
//此方法主要是給集合賦最大容量用的
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
/**
* 這一步無非再判斷一次
* size + 1 > Integ er.MAX_VALUE - 8 ?
* 如果大的話賦值 Integer.MAX_VALUE
* 說明集合最大也就 Integer.MAX_VALUE的長度了
*/
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2. void add(int，E)；在指定位置添加元素
public void add(int index, E element) {
//邊界校驗 插入的位置必須在0-size之間
rangeCheckForAdd(index);
//不分析了上面有
ensureCapacityInternal(size + 1);
//就是將你插入位置的後面的數組往後移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//放入該位置
elementData[index] = element;
//元素個數+1
size++;
}
private void rangeCheckForAdd(int index) {
//插入位置過於離譜,反手給你一個越界異常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* src：源對象
* srcPos：源對象對象的起始位置
* dest：目標對象
* destPost：目標對象的起始位置
* length：從起始位置往後複製的長度
*/
public static native void arraycopy(Object src, int srcPos, Object dest,
int destPos, int length)
總結:
初始容量為10，1.5倍擴容，擴容最大值為 Integer.MAX_VALUE，
當我們調用add方法時，實際方法的調用如下：
刪除集合元素
因為這幾個都基本類似，我們就選兩個進行剖析
1. remove(int)：通過刪除指定位置上的元素
public E remove(int index) {
//檢測index,是否在索引範圍內
rangeCheck(index);
//列表結構被修改的次數,用戶迭代時修改列表拋異常
modCount++;
//取出要被刪除的元素
E oldValue = elementData(index);
//和添加的邏輯相似,算數組移動的位置
int numMoved = size - index - 1;
//大於0說明不是尾部
if (numMoved > 0)
//將刪除位置後面的數組往刪除位前移一格
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
/*
* 由於只是將數組前移蓋住了一位，但是長度沒變
* 如果刪除位置不是末尾,此時末尾會有兩個相同元素
* 需要刪除末尾最後一個元素,size - 1
*/
elementData[--size] = null; // clear to let GC do its work
//返回要刪除的元素值
return oldValue;
}
/*
* 這個方法不過多解釋了，但是筆者認為這小小的檢查邊界的方法細節寫的不是很完美
* 這個地方沒有主動考慮,index < 0的情況，異常是後續直接拋的，並不是在這
* 後續版本似乎對這個細節做了糾正
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2. removeAll(collection c)：批量刪除元素
public boolean removeAll(Collection<?> c) {
//判斷非空
Objects.requireNonNull(c);
//批量刪除
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
//用一個引用變數接收容器
final Object[] elementData = this.elementData;
//r代表elementData循環次數,w代表不需要刪除的元素個數
int r = 0, w = 0;
//修改變動默認為false
boolean modified = false;
try {
//遍歷集合,遍歷幾次r就是幾,直至r=size
for (; r < size; r++)
//查看當前集合元素是否不被包含,complement = false
if (c.contains(elementData[r]) == complement)
//不被包含,那我在當前容器從頭開始放,w是下標
elementData[w++] = elementData[r];
} finally {
/**
* 如果r沒有成功遍歷完,拋異常了（這是個finally）
* 理所當然將後面沒有遍歷完的元素歸為不被包含
*/
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//存在不需要被刪除的元素
if (w != size) {
//遍歷刪除
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
//有做過修改變動
modified = true;
}
}
return modified;
}
修改集合元素
public E set(int index, E element) {
//邊界範圍校驗
rangeCheck(index);
//取出舊值
E oldValue = elementData(index);
//賦上新值
elementData[index] = element;
//返回舊值
return oldValue;
}
查找集合元素
public E get(int index) {
//邊界範圍校驗
rangeCheck(index);
//通過下標獲取查找的元素
return elementData(index);
}
總結
- 執行緒不安全
- 本質是數組，默認長度10，擴容核心方法為grow() ，每次擴容1.5倍，最大容量為 Integer.MAX_VALUE
- 實現了RandomAccess介面，所以for循環比迭代器循環效率更高
- 因為底層是數組，所以查詢快，修改快，增刪慢
