ArrayList 源碼分析
作者:vwFisher
時間:2019-11-04
GitHub代碼:https://github.com/vwFisher/JavaBasicGuide
目錄
1 構(gòu)造函數(shù) 和 屬性
private static final int DEFAULT_CAPACITY = 10; // 初始容量
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size; // 數(shù)組當前容量
/**
* 默認構(gòu)造函數(shù),使用初始容量10構(gòu)造一個空列表(無參數(shù)構(gòu)造)
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 帶初始容量參數(shù)的構(gòu)造函數(shù)撤嫩。(用戶自己指定容量)
*/
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);
}
}
/**
* 構(gòu)造包含指定collection元素的列表蠢终,這些元素利用該集合的迭代器按順序返回
* 如果指定的集合為null寻拂,throws NullPointerException。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
注意梦染,無參構(gòu)造函數(shù)朴皆,創(chuàng)建ArrayList遂铡,此時 容量是為0的,當添加元素才擴容為10
2. 擴容機制
一伪货、先看 add 方法
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 擴容方法
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
二、ensureCapacityInternal()
方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
如果 采用默認采購函數(shù)蒙挑,當 要 add 進第1個元素時愚臀,minCapacity為1,在Math.max()方法比較后馋袜,minCapacity 為10舶斧。
三、ensureExplicitCapacity()
方法
判斷是否需要擴容泽台,如果需要 則 調(diào)用 grow 方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
我們來仔細分析一下:
- 當我們要 add 進第1個元素到 ArrayList 時师痕,elementData.length 為0 (因為還是一個空的 list)而账,因為執(zhí)行了 ensureCapacityInternal() 方法 因篇,所以 minCapacity 此時為10。此時咐吼,minCapacity - elementData.length > 0 成立商佑,所以會進入 grow(minCapacity) 方法。
- 當add第2個元素時肌幽,minCapacity 為2喂急,此時e lementData.length(容量)在添加第一個元素后擴容成 10 了笛求。此時,minCapacity - elementData.length > 0 不成立析蝴,所以不會進入 (執(zhí)行)grow(minCapacity) 方法。
- 添加第3响禽、4···到第10個元素時荚醒,依然不會執(zhí)行g(shù)row方法,數(shù)組容量都為10侯繁。
直到添加第11個元素泡躯,minCapacity(為11)比elementData.length(為10)要大。進入grow方法進行擴容咕别。
四惰拱、grow()
方法
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// oldCapacity為舊容量啊送,newCapacity為新容量
int oldCapacity = elementData.length;
//將oldCapacity 右移一位,其效果相當于oldCapacity /2昔逗,
//我們知道位運算的速度遠遠快于整除運算,整句運算式的結(jié)果就是將新容量更新為舊容量的1.5倍勾怒,
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后檢查新容量是否大于最小需要容量声旺,若還是小于最小需要容量,那么就把最小需要容量當作數(shù)組的新容量卡乾,
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE,進入(執(zhí)行) `hugeCapacity()` 方法來比較 minCapacity 和 MAX_ARRAY_SIZE幔妨,
//如果minCapacity大于最大容量,則新容量則為`Integer.MAX_VALUE`误堡,否則,新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`陪踩。
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次擴容之后容量都會變?yōu)樵瓉淼?1.5 倍肩狂!(JDK1.6版本以后)
JDk1.6版本時姥饰,擴容之后容量為 1.5 倍+1!詳情請參考源碼
3 System.arraycopy() 和 Arrays.copyOf()方法
在 ArrayList 源碼大量調(diào)用了這兩個方法审磁。比如:我們上面講的擴容操作以及add(int index, E element)岂座、toArray() 等方法中都用到了該方法!
3.1 System.arraycopy() 方法
/**
* 在此列表中的指定位置插入指定的元素钾恢。
*先調(diào)用 rangeCheckForAdd 對index進行界限檢查吕喘;然后調(diào)用 ensureCapacityInternal 方法保證capacity足夠大刑桑;
*再將從index開始之后的所有成員后移一個位置祠斧;將element插入index位置;最后size加1辕漂。
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy()方法實現(xiàn)數(shù)組自己復(fù)制自己
//elementData:源數(shù)組;index:源數(shù)組中的起始位置;elementData:目標數(shù)組吴超;index + 1:目標數(shù)組中的起始位置; size - index:要復(fù)制的數(shù)組元素的數(shù)量跋涣;
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
我們寫一個簡單的方法測試以下:
public class ArraycopyTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[10];
a[0] = 0;
a[1] = 1;
a[2] = 2;
a[3] = 3;
System.arraycopy(a, 2, a, 3, 3);
a[2]=99;
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
結(jié)果:
0 1 99 2 3 0 0 0 0 0
3.2 Arrays.copyOf()方法
/**
以正確的順序返回一個包含此列表中所有元素的數(shù)組(從第一個到最后一個元素); 返回的數(shù)組的運行時類型是指定數(shù)組的運行時類型。
*/
public Object[] toArray() {
//elementData:要復(fù)制的數(shù)組奖年;size:要復(fù)制的長度
return Arrays.copyOf(elementData, size);
}
個人覺得使用 Arrays.copyOf()方法主要是為了給原有數(shù)組擴容沛贪,測試代碼如下:
public class ArrayscopyOfTest {
public static void main(String[] args) {
int[] a = new int[3];
a[0] = 0;
a[1] = 1;
a[2] = 2;
int[] b = Arrays.copyOf(a, 10);
System.out.println("b.length"+b.length);
}
}
結(jié)果:
10
3.3 兩者聯(lián)系和區(qū)別
聯(lián)系:看兩者源代碼可以發(fā)現(xiàn) copyOf() 內(nèi)部實際調(diào)用了 System.arraycopy() 方法
區(qū)別:
- arraycopy() 需要目標數(shù)組利赋,將原數(shù)組拷貝到你自己定義的數(shù)組里或者原數(shù)組,而且可以選擇拷貝的起點和長度以及放入新數(shù)組中的位置之碗。
- copyOf() 是系統(tǒng)自動在內(nèi)部新建一個數(shù)組季希,并返回該數(shù)組。
4 ensureCapacity方法
ArrayList 源碼中有一個 ensureCapacity 方法不知道大家注意到?jīng)]有博敬,這個方法 ArrayList 內(nèi)部沒有被調(diào)用過峰尝,所以很顯然是提供給用戶調(diào)用的,那么這個方法有什么作用呢祭往?
/**
如有必要火窒,增加此 ArrayList 實例的容量,以確保它至少可以容納由minimum capacity參數(shù)指定的元素數(shù)已骇。
*
* @param minCapacity 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
最好在 add 大量元素之前用 ensureCapacity 方法票编,以減少增量重新分配的次數(shù)
我們通過下面的代碼實際測試以下這個方法的效果:
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("使用ensureCapacity方法前:"+(endTime - startTime));
list = new ArrayList<Object>();
long startTime1 = System.currentTimeMillis();
list.ensureCapacity(N);
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("使用ensureCapacity方法后:"+(endTime1 - startTime1));
}
}
運行結(jié)果:
使用ensureCapacity方法前:4637
使用ensureCapacity方法后:241
通過運行結(jié)果慧域,我們可以很明顯的看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法,以減少增量重新分配的次數(shù)