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

優(yōu)點(diǎn):

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

2.隨機(jī)讀的性能很高，仍然是因?yàn)锳rrayList底層基于數(shù)組實(shí)現(xiàn)。(隨機(jī)讀: 一會(huì)兒list.get(2)，一會(huì)兒list.get(10))

缺點(diǎn):

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

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

二. 源碼分析

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

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

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

當(dāng)執(zhí)行add操作后，才會(huì)為ArrayList進(jìn)行一次擴(kuò)容，這里使用的是ArrayList的初始長(zhǎng)度，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()方法，先會(huì)判斷一下，看看當(dāng)前數(shù)組是否已滿，能不能放得下本次待加進(jìn)去的元素，如果數(shù)組已經(jīng)被塞滿了，那就進(jìn)行擴(kuò)容，創(chuàng)建一個(gè)新數(shù)組，把老數(shù)組中的數(shù)據(jù)拷貝到新數(shù)組中，確保新數(shù)組能裝得下足夠多的元素。

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

list.add(“張三”);

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

list.add(“李四”)l;

elementData[size++]=e；此時(shí)會(huì)把"李四"插入到下標(biāo)為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); 檢查說，待插入的元素下標(biāo)不能大于當(dāng)前元素的個(gè)數(shù)，也不能小于0。

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

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

就拿當(dāng)前的例子來說，[“張三”, “李四”, “王五”]，現(xiàn)在想要執(zhí)行l(wèi)ist.add(4, “趙六”)；如果真的讓你得逞了，豈不是會(huì)出現(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ù)組擴(kuò)容，確保數(shù)組有足夠的空間能容納待插入的元素，別搞得插入元素后，把數(shù)組撐爆了。

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

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

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

1.4 ensureCapacityInternal

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

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

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

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

首先，執(zhí)行calculateCapacity(elementData, minCapacity); 這個(gè)方法主要是用來初始化空數(shù)組，有些時(shí)候，我們使用new ArrayList()初始化了數(shù)組，沒有指定數(shù)組的初始大小，那么當(dāng)往數(shù)組中插入元素時(shí)，ArrayList就會(huì)為我們初始化數(shù)組，默認(rèn)的長(zhǎng)度是10，如果你一次性加的元素太多(比如你使用的是addAll( ) )，則按照加入的元素個(gè)數(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ù)組沒有足夠的空間放下新增的元素，就會(huì)觸發(fā)擴(kuò)容。

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

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

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

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

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

比如說，原來的數(shù)組長(zhǎng)度為10，默認(rèn)情況下，擴(kuò)容一次長(zhǎng)度就是15，現(xiàn)在我一次想要插入100個(gè)元素(通過addAll()方法)，此時(shí)數(shù)組肯定是裝不下，這個(gè)時(shí)候，新數(shù)組的長(zhǎng)度就等于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ù)組中最后一個(gè)元素的后一個(gè)位置開始，加入新的元素。

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

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

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

然后，執(zhí)行elementData[index] = element; 在我們的案例中，也就是elementData[1] = “趙六”，把下標(biāo)為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];
}

就是這么簡(jiǎn)單，根據(jù)下標(biāo)，直接從數(shù)組中獲取數(shù)據(jù)。沒什么好說的，這個(gè)方法的性能是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)，看看你想刪除的元素的下標(biāo)是否存在，有沒有越界。比如數(shù)組中只有3個(gè)元素，你偏要?jiǎng)h第10個(gè)元素，那ArrayList上哪去幫你刪？

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

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

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

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

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

三. 結(jié)論

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

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

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

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

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

最新評(píng)論