本文內(nèi)容基于 jdk1.8 環(huán)境
本文最先發(fā)布于我的個人博客热押，簡書為同步發(fā)布窥浪，如有需要周蹭，可以訪問腿短快跑的個人博客獲取更多內(nèi)容
源碼獲取
jdk 源碼在我們 jdk 的安裝目錄下即可找到：
jdk1.8
在 jdk1.8 及之前的版本中，jdk的源碼均可在安裝目錄的根目錄下找到src.zip，此包即為 jdk 源碼jdk11
從 jdk11 開始涂籽，jdk的源碼包放在 jdk 安裝目錄下的 lib 目錄下，在 lib 目錄下找到src.zip即為源碼
實現(xiàn)接口
ArrayList 實現(xiàn)了以下接口：
List
實現(xiàn)了 List 接口展蒂，Java集合框架中常用接口RandomAccess
用于實現(xiàn)隨機訪問功能又活，因為底層使用數(shù)組實現(xiàn)，可以通過下標實現(xiàn)隨機訪問Cloneable
克隆接口锰悼，用于實現(xiàn)兩個 List 之間的克隆Serializable
序列化接口
核心屬性
// 定義默認List大小
private static final int DEFAULT_CAPACITY = 10;
// 用于存儲實際 ArrayList 中的數(shù)據(jù)
transient Object[] elementData;
// 用于存儲當前 ArrayList 的大小
private int size;
從上述代碼中我們可以得出以下結(jié)論：
- ArrayList 默認初始化大小為 10
- ArrayList 實際大小使用 size 變量存儲
- ArrayList 底層數(shù)據(jù)使用 Object 數(shù)組存儲
為什么數(shù)組使用transient關(guān)鍵字
transient關(guān)鍵字用于修飾類成員變量柳骄，不能用于修飾方法，用于標記對應(yīng)的類成員變量不是類持久化狀態(tài)的一部分箕般。
jvm默認序列化和反序列創(chuàng)建字節(jié)流的過程中會忽略 transient 關(guān)鍵字修飾的類成員變量
ArrayList 中底層數(shù)組使用 transient 修飾是出于性能考慮耐薯，因為底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，因此必然存在很多數(shù)組空間未使用的情況丝里，直接序列化將導致序列化性能大大降低和資源的浪費
雖然因為底層數(shù)組使用 transient 修飾導致數(shù)組不能由jvm默認序列化曲初，但是通過定義writeObject和readObject方法，自定義實現(xiàn)了列表元素的序列化與反序列化杯聚。此內(nèi)容文章后續(xù)講解
核心方法
構(gòu)造方法
此處以指定大小為例臼婆，其他構(gòu)造方法類似
用于初始化 ArrayList
// 默認空數(shù)組
private static final Object[] 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);
}
}
- 如果初始化大小 > 0 ，則創(chuàng)建一個對應(yīng)大小的 Object 數(shù)組
- 如果初始化大小 == 0幌绍，則使用默認的靜態(tài)空數(shù)組颁褂，此處是為了減少空間占用，避免多個空數(shù)組占用內(nèi)存
- 如果初始化大小 < 0傀广，則拋出異常
indexOf(Object o)
查找元素出現(xiàn)的第一個位置
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
- 判斷元素是否為空
- 遍歷數(shù)組列表颁独，找到值相同的索引返回，此處比較是否相同使用的 equals 方法
- 如果未找到對應(yīng)的元素伪冰，返回 -1
lastIndexOf(Object o)
查找元素出現(xiàn)的最后一個位置
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
- 判斷元素是否為空
- 從數(shù)組末尾向前遍歷誓酒，找到第一個值相同的索引返回，同上贮聂，使用 equals 方法
- 如果未找到對應(yīng)的元素靠柑，返回 -1
clone()
克隆出一個新的 List
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
- 底層是使用
System.arraycopy實現(xiàn)的 -
System.arraycopy是native方法 -
System.arraycopy當數(shù)組是基礎(chǔ)數(shù)據(jù)類型或者是String類型的時候是深拷貝 -
System.arraycopy當數(shù)組是非基礎(chǔ)數(shù)據(jù)類型且非String類型的時候是淺拷貝 -
System.arraycopy是不安全的
get(int index)
獲取指定位置的元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
- 進行范圍檢查寨辩，如果出現(xiàn)數(shù)組越界，直接拋出異常
- 返回數(shù)組對應(yīng)下標位置的數(shù)據(jù)
set(int index, E element)
設(shè)置指定位置的元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- 進行范圍檢查歼冰，如果出現(xiàn)數(shù)組越界捣染，直接拋出異常
- 獲取對應(yīng)索引位置的值
- 將對應(yīng)索引位置的值設(shè)置為新值
- 返回舊值
add(E e)
在 ArrayList 的末尾添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
- 當前大小+1作為最小數(shù)組容量
- 檢查容量是否需要擴容，如果需要擴容停巷，則執(zhí)行擴容操作
- 設(shè)置數(shù)組后面一個元素為對應(yīng)的元素
- 返回結(jié)果
擴容操作
數(shù)組擴容操作
/**
* 檢查容量，不滿足則擴容
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 計算應(yīng)該擴容到的容量
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 判斷是否需要擴容
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 擴容操作
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 計算當前應(yīng)該擴容到的容量
a. 數(shù)組是否是默認的空數(shù)組榕栏，是則返回當前最小容量和默認容量(10)的最大值
b. 否則畔勤，返回當前最小容量 - 判斷是否需要擴容
a. 先對 modCount 增加，modCount 用于標識數(shù)組是否被修改過扒磁，用于提供快速失敗的實現(xiàn)
b. 判斷應(yīng)該擴容到的容量是否超過了當前底層數(shù)組的實際大小庆揪，如果超過了才需要擴容 - 如果需要擴容則執(zhí)行擴容
a. 計算出新的數(shù)組大小 = 舊的數(shù)組的大小 + 舊的數(shù)組的大小 / 2，即妨托，擴容后的大小為原數(shù)組大小的 1.5 倍缸榛，采用 >> 1 的寫法是為了提升性能
b. 如果新的數(shù)組的大小 < 應(yīng)該擴容的數(shù)組的大小，則新的數(shù)組的大小設(shè)置為應(yīng)該擴容的數(shù)組的大小
c. 如果新的數(shù)組的大小超出了最大數(shù)組的大小(Integer.MAX_VALUE - 8 = 2147483639)兰伤，則新數(shù)組的大小設(shè)置為 Integer.MAX_VALUE内颗，否則為數(shù)組的最大大小(Integer.MAX_VALUE - 8 = 2147483639)
d. 如果擴容的數(shù)組的大小出現(xiàn)了數(shù)據(jù)溢出，則會拋出 OutOfMemoryError 內(nèi)存溢出異常
e. 創(chuàng)建新的數(shù)組敦腔，將舊數(shù)組數(shù)據(jù)復制到新的數(shù)組中
add(int index, E element)
在指定索引位置插入元素
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++;
}
- 范圍檢查均澳，如果出現(xiàn)數(shù)組越界，拋出異常
- 當前大小+1作為數(shù)組最小容量
- 檢查容量是否需要擴容符衔，如果需要擴容找前，則執(zhí)行擴容操作
- 將指定位置的數(shù)組內(nèi)容向后移動一位
- 在指定位置設(shè)置數(shù)組的元素值
- 數(shù)組size+1
remove(int index)
移除指定位置的元素
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
- 進行范圍檢查，如果出現(xiàn)數(shù)組越界判族，直接拋出異常
- 獲取對應(yīng)索引位置的數(shù)據(jù)
- 計算出需要移動的位置的索引躺盛，如果索引 > 0，則將后面的數(shù)組的內(nèi)容向前移動一位
- 將數(shù)組的最后一個元素設(shè)置為null
- 返回舊數(shù)據(jù)
remove(Object o)
移除指定元素形帮，僅會移除第一次出現(xiàn)的元素
public boolean remove(Object o) {
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)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
- 判斷要移除的元素是否為null
- 從開始位置遍歷數(shù)組元素槽惫，判斷元素是否相等，如果相等沃缘，則執(zhí)行快速移除(同
remove(int index)方法的實現(xiàn))躯枢，移除后返回結(jié)果
clear()
清空 ArrayList
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
- 修改數(shù)量+1，用于提供快速失敗機制
- 從開始位置遍歷數(shù)組槐臀，將數(shù)組中的元素全部設(shè)置為null
- 設(shè)置 size 大小為 0
addAll(Collection<? extends E> c)
添加集合元素至 ArrayList 結(jié)尾
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
- 將集合轉(zhuǎn)換為數(shù)組
- 當前大小+新數(shù)組的大小作為最小容量
- 根據(jù)最小容量判斷是否需要擴容锄蹂，如果需要擴容，執(zhí)行擴容操作
- 將新數(shù)組復制到數(shù)組的末尾
- size大小更新為當前新的大小
- 返回新增結(jié)果
addAll(int index, Collection<? extends E> c)
在指定位置添加集合元素
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
- 進行范圍檢查水慨，如果出現(xiàn)數(shù)組越界得糜，直接拋出異常
- 將集合轉(zhuǎn)換為數(shù)組
- 當前大小 + 新數(shù)組的大小作為最小容量
- 根據(jù)最小容量判斷是否需要擴容敬扛，如果需要擴容，執(zhí)行擴容操作
- 將當前數(shù)組從index開始位置的元素全部向后移動新數(shù)組大小的位置
- 將新數(shù)組的元素從index位置開始復制
- size大小更新為當前新的大小
- 返回新增結(jié)果
removeRange(int fromIndex, int toIndex)
移除指定區(qū)間內(nèi)的元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
- 修改數(shù)量+1朝抖，用于提供快速失敗機制
- size-toIndex是需要移動的元素的個數(shù)
- 將需要移動的元素移動至 fromIndex 位置
- size - (toIndex-fromIndex) 是現(xiàn)在新的數(shù)組的實際大小
- 從新的大小位置開始啥箭，將后面的元素全部設(shè)置為null
- size設(shè)置為新的大小
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;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
注意 complement 參數(shù)值為 false
- 檢查集合元素是否為空，為空則拋出異常
- 遍歷數(shù)組治宣，如果集合中不包含當前元素(通過 complement 值來判斷)急侥，則將當前元素依次從 r 位置排列
- 當 r != size 的時候說明 c.contains 可能出現(xiàn)了異常，做了一個兼容操作侮邀，此處不詳細講述
- w表示移動后的集合的元素的長度坏怪，如果 w != size 則證明存在元素被修改，將 w 位置后面的元素全部設(shè)置為 null绊茧， 并將 size 設(shè)置為 w
- 返回修改結(jié)果
retainAll(Collection<?> c)
ArrayList 和 集合取交集
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
注意 complement 參數(shù)值為 true
步驟和上面 removeAll 方法實現(xiàn)邏輯一樣铝宵，只是 complement 參數(shù)值不一樣，通過 complement 參數(shù)來控制是保留包含的元素還是不包含的元素
writeObject & readObject
序列化使用华畏，上面內(nèi)容我們講到為了保證性能和避免資源浪費鹏秋，底層數(shù)組使用了
transient關(guān)鍵字修復，導致無法使用 jvm 的序列化亡笑，通過 writeObject 和 readObject 方法實現(xiàn)了 ArrayList 的序列化和反序列化
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
總結(jié)
從上述源碼中我們可以得出以下結(jié)論：
- ArrayList也是List 的一種
- ArrayList底層使用 Object 數(shù)組實現(xiàn)
- ArrayList比較適合讀多寫少的情況(寫需要挪動元素)
- ArrayList初始容量大小為10
- ArrayList每次擴容大小為原容量的 1.5 倍
