一. 基本原理和優(yōu)缺點

優(yōu)點:

1.通過下標讀取元素的速度很快，這是因為ArrayList底層基于數(shù)組實現(xiàn)，可以根據(jù)下標快速的找到內(nèi)存地址，接著讀取內(nèi)存地址中存放的數(shù)據(jù)。

2.隨機讀的性能很高，仍然是因為ArrayList底層基于數(shù)組實現(xiàn)。(隨機讀: 一會兒list.get(2)，一會兒list.get(10))

缺點:

1.數(shù)組的長度是固定的，如果ArrayList的初始長度太小，后續(xù)又不斷的向list寫入數(shù)據(jù)，會導(dǎo)致數(shù)組頻繁的擴容和復(fù)制數(shù)據(jù)，而這些過程非常影響系統(tǒng)的運行。

2.由于是數(shù)組實現(xiàn)的，如果想往中間插入一個元素，會導(dǎo)致這個元素后面所有的元素都要往后挪動一個位置。

二. 源碼分析

1.1 默認的構(gòu)造函數(shù)

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

如果使用默認的構(gòu)造函數(shù)，初始化時是一個空數(shù)組，數(shù)組的類型是Object[ ]，數(shù)組的長度為0。

當(dāng)執(zhí)行add操作后，才會為ArrayList進行一次擴容，這里使用的是ArrayList的初始長度，10。

1.2 add(E e)

list.add("張三");
list.add("李四");

public boolean add(E e) {
	ensureCapacityInternal(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
}

每次執(zhí)行ArrayList的add()方法，先會判斷一下，看看當(dāng)前數(shù)組是否已滿，能不能放得下本次待加進去的元素，如果數(shù)組已經(jīng)被塞滿了，那就進行擴容，創(chuàng)建一個新數(shù)組，把老數(shù)組中的數(shù)據(jù)拷貝到新數(shù)組中，確保新數(shù)組能裝得下足夠多的元素。

剛剛我們說了，使用ArrayList的無參構(gòu)造函數(shù)，初始化時數(shù)組的長度為0。

list.add(“張三”);

elementData[size++]=e；此時會把元素插入到下標為0的位置，接著把size設(shè)置成0+1=1。(顯然，size就是ArrayList實際存儲元素的個數(shù))

list.add(“李四”)l;

elementData[size++]=e；此時會把"李四"插入到下標為1的位置，接著把size設(shè)置成1+1=2。

1.3 add(int index, E element)

list.add("張三");
list.add("李四");
list.add("王五");
list.add(1, "趙六");

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++;
}

首先，執(zhí)行rangeCheckForAdd(index); 檢查說，待插入的元素下標不能大于當(dāng)前元素的個數(shù)，也不能小于0。

問題: 不能小于0倒是好理解，為什么待插入的元素下標可以等于當(dāng)前元素的個數(shù)呢？

答: 若相等，則代表插入這個元素，正好不需要挪動舊數(shù)組中任何的元素，不會造成任何的壞影響。但是當(dāng)待插入元素的下標大于當(dāng)前元素，會導(dǎo)致數(shù)組跳躍式的插入元素，這對于數(shù)組來說，是絕對不允許的。

就拿當(dāng)前的例子來說，[“張三”, “李四”, “王五”]，現(xiàn)在想要執(zhí)行l(wèi)ist.add(4, “趙六”)；如果真的讓你得逞了，豈不是會出現(xiàn) [“張三”, “李四”, “王五”, , “趙六”] 導(dǎo)致數(shù)組中存放的數(shù)據(jù)不連續(xù)的恐怖后果？

private void rangeCheckForAdd(int index) {
	if (index > size || index < 0)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

接著，執(zhí)行ensureCapacityInternal(size + 1)，數(shù)組擴容，確保數(shù)組有足夠的空間能容納待插入的元素，別搞得插入元素后，把數(shù)組撐爆了。

然后，執(zhí)行System.arraycopy(elementData, index, elementData, index + 1,size - index); 挪動舊元素，為待插入的元素騰位置。案例中，System.arraycopy(elementData, 1, elementData, 2,2); 就是從elementData的第二個元素開始，拷貝2個元素到elementData的第三個元素的位置上。

我們可以看看elementData，原本[“張三”, “李四”, “王五”] ，現(xiàn)在是[“張三”, “李四”, “李四”, “王五”]

最后，elementData[index] = element; 把趙六插入到index=1的位置上，現(xiàn)在是[“張三”, “趙六”, “李四”, “王五”]

1.4 ensureCapacityInternal

這個方法的作用是擴容，它可以說是ArrayList中最為核心的代碼了，所以單獨拿出來說一下。

private void ensureCapacityInternal(int minCapacity) {
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

執(zhí)行add操作時，總是會先執(zhí)行ensureCapacityInternal()，計算出加上了本次待新增的元素后，總共需要多大的空間來存儲。

假設(shè)初始化數(shù)組的大小是10，陸陸續(xù)續(xù)的已經(jīng)有10個元素填入了數(shù)組，此時想要加入第11個元素。

首先，執(zhí)行calculateCapacity(elementData, minCapacity); 這個方法主要是用來初始化空數(shù)組，有些時候，我們使用new ArrayList()初始化了數(shù)組，沒有指定數(shù)組的初始大小，那么當(dāng)往數(shù)組中插入元素時，ArrayList就會為我們初始化數(shù)組，默認的長度是10，如果你一次性加的元素太多(比如你使用的是addAll( ) )，則按照加入的元素個數(shù)來定。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	return minCapacity;
}

接著執(zhí)行ensureExplicitCapacity()，modCount指的是數(shù)組被修改的次數(shù)，如果數(shù)組沒有足夠的空間放下新增的元素，就會觸發(fā)擴容。

這個很好理解，比如你的數(shù)組長度是10，已經(jīng)放滿了，現(xiàn)在想要插入第11個元素，肯定是插不進去的，所以自然就要擴容。

private void ensureExplicitCapacity(int minCapacity) {
	modCount++;

	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

那么怎么擴容呢？很簡單，增加原有數(shù)組容量的一半。比如原來的數(shù)組長度為10，擴容一次后，數(shù)組長度=10 + 10/2 =15。

如果原數(shù)組經(jīng)過1.5倍的擴容后，仍然放不下待插入的元素，怎么辦？那么新數(shù)組的長度就以添加新元素后的最小長度為準。

比如說，原來的數(shù)組長度為10，默認情況下，擴容一次長度就是15，現(xiàn)在我一次想要插入100個元素(通過addAll()方法)，此時數(shù)組肯定是裝不下，這個時候，新數(shù)組的長度就等于10+100=110了。

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);
}

最后一步，從當(dāng)前數(shù)組中最后一個元素的后一個位置開始，加入新的元素。

elementData[size++] = e;

1.5 set(int index, E element)

list.add("張三");
list.add("李四");
list.add("王五");
list.set(1, "趙六");

public E set(int index, E element) {
 	rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

首先，執(zhí)行rangeCheck(index)，這一步就是在檢查，你想替換的下標是否存在元素。從1.2節(jié)我們知道了，size代表著ArrayList內(nèi)實際存放的元素個數(shù)，別忘了ArrayList的底層是數(shù)組實現(xiàn)的，所以不可能跳躍的存儲元素，因此，下標從0到size-1，一定會有元素。如果你現(xiàn)在想要替換的下標大于等于size，那么在ArrayList中，連這個元素都不存在，那你還怎么替換元素？替換空氣嗎？

private void rangeCheck(int index) {
	if (index >= size)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

接著，執(zhí)行E oldValue = elementData(index); 看看，這里直接把要替換的元素給取出來了。在上述案例中，list.set(1, “趙六”)會把下標為1的元素給取出來，也就是李四，所以oldValue=李四。

然后，執(zhí)行elementData[index] = element; 在我們的案例中，也就是elementData[1] = “趙六”，把下標為1的位置上的元素替換成了"趙六"。

最后，返回被替換的舊數(shù)據(jù)，也就是李四。

1.6 get(E element)

list.get(1);

public E get(int index) {
  rangeCheck(index);
  return elementData(index);
}

E elementData(int index) {
	return (E) elementData[index];
}

就是這么簡單，根據(jù)下標，直接從數(shù)組中獲取數(shù)據(jù)。沒什么好說的，這個方法的性能是ArrayList所有方法中最高的。

1.7 remove(int index)

list.remove(1);
list.remove(2);

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;
}

執(zhí)行rangeCheck(index)，看看你想刪除的元素的下標是否存在，有沒有越界。比如數(shù)組中只有3個元素，你偏要刪第10個元素，那ArrayList上哪去幫你刪？

執(zhí)行int numMoved = size - index - 1; 所謂刪除元素，說白了就是把待刪除元素后面的元素，全部前進一格，相當(dāng)于是add(index, E)的逆向操作。

問題: 不就是挪動待刪除元素右邊的元素么，干脆寫成int numMoved = size + 1；這樣可以不？

答: 不可以。numMoved 代表的是需要移動的元素的個數(shù)。

執(zhí)行elementData[–size] = null; 現(xiàn)在已經(jīng)把元素往前挪了一格，比如舊數(shù)組為[“張三”, “李四”, “王五”, “趙六”]，現(xiàn)在想刪除index=1的元素，當(dāng)執(zhí)行完System.arraycopy，也就是移動(實際上是復(fù)制)元素的過程后，數(shù)組為 [“張三”, “王五”, “趙六”, “趙六”]，最后，我們只需要刪除末尾元素即可。

所謂的刪除，就是置為null，由于之前的對象沒有了引用，接著讓JVM來回收即可。

三. 結(jié)論

1.在對ArrayList做隨機位置的插入和刪除操作時，會涉及到數(shù)組大量元素的移動(其實就是拷貝和刪除)，所以性能都不高。(具體可以參考add(int index, E element) 和 remove(int index)這兩個方法)

2.執(zhí)行add或者add(int index, E element)時，如果插入的比較頻繁，偶爾會由于舊數(shù)組容量不夠，導(dǎo)致擴容，擴容就會導(dǎo)致創(chuàng)建新數(shù)組，復(fù)制數(shù)據(jù)，所以性能不高。

3.set()或者get()，這兩個方法都是靠數(shù)組下標來定位待操作的元素，接著替換或者讀取元素，這個性能還是不錯的。

4.一旦經(jīng)歷了擴容后，就算后期刪除了元素，ArrayList也不會主動縮容。

到此這篇關(guān)于Java中的ArrayList底層源碼分析的文章就介紹到這了,更多相關(guān)ArrayList底層源碼內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論