第關(guān)于ArrayList的動(dòng)態(tài)擴(kuò)容機(jī)制解讀目錄1.前言2.ArrayList的動(dòng)態(tài)擴(kuò)容機(jī)制2.1.ArrayList的主要屬性2.2.ArrayList的構(gòu)造器2.3.ArrayList的動(dòng)態(tài)擴(kuò)容3.小結(jié)3.1.初始容量3.2.動(dòng)態(tài)擴(kuò)容大小3.3.動(dòng)態(tài)擴(kuò)容大小測(cè)試

1.前言

對(duì)于ArrayList的動(dòng)態(tài)擴(kuò)容機(jī)制想必大家都聽(tīng)說(shuō)過(guò)，之前的文章中也談到過(guò)，不過(guò)由于時(shí)間久遠(yuǎn)，早已忘卻。

所以利用這篇文章做做筆記，加深理解記憶

2.ArrayList的動(dòng)態(tài)擴(kuò)容機(jī)制

要了解其動(dòng)態(tài)擴(kuò)容機(jī)制就必須先看它的源碼，源碼是基于jdk1.8的

2.1.ArrayList的主要屬性

//如果不指定容量（空構(gòu)造器）,則在添加數(shù)據(jù)時(shí)的空構(gòu)造器默認(rèn)初始容量最小為10

privatestaticfinalintDEFAULT_CAPACITY=10;

//出現(xiàn)在需要用到空數(shù)組的地方，其中一處是使用自定義初始容量構(gòu)造方法時(shí)候如果你指定初始容量為0的時(shí)候，那么elementData指向該數(shù)組

//另一處是使用包含指定collection集合元素的列表的構(gòu)造方法時(shí)，如果被包含的列表中沒(méi)有數(shù)據(jù)，那么elementData指向該數(shù)組

privatestaticfinalObject[]EMPTY_ELEMENTDATA={};

//如果使用默認(rèn)構(gòu)造方法，那么elementData指向該數(shù)組

//在添加元素時(shí)會(huì)判斷是否是使用默認(rèn)構(gòu)造器第一次添加，如果是數(shù)組就會(huì)擴(kuò)容至10個(gè)容量

privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};

//默認(rèn)未初始化的儲(chǔ)存ArrayList集合元素的底層數(shù)組,其長(zhǎng)度就是ArrayList的容量

transientObject[]elementData;

//私有的elementData數(shù)組中具體的元素對(duì)象的數(shù)量,可通過(guò)size方法獲得。默認(rèn)初始值為0，在add、remove等方法時(shí)size會(huì)改變

privateintsize;

可以看到ArrayList底層核心是一個(gè)Object[]elementData的數(shù)組

2.2.ArrayList的構(gòu)造器

//默認(rèn)的構(gòu)造器

publicArrayList(){

//Object[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={}空數(shù)組

this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

//自定義容量大小的構(gòu)造器

publicArrayList(intinitialCapacity){

if(initialCapacity0){

this.elementData=newObject[initialCapacity];

}elseif(initialCapacity==0){

this.elementData=EMPTY_ELEMENTDATA;

}else{

thrownewIllegalArgumentException("IllegalCapacity:"+

initialCapacity);

}

從上面的構(gòu)造器中，可以得出以下結(jié)論

如果使用ArrayList的默認(rèn)構(gòu)造器時(shí)，它的初始容量就是0如果使用ArrayList的有參構(gòu)造器時(shí)，它的初始容量就是你傳入的參數(shù)initialCapacity的值

2.3.ArrayList的動(dòng)態(tài)擴(kuò)容

根據(jù)上面的兩個(gè)結(jié)論，不管是使用默認(rèn)或有參構(gòu)造器時(shí)，我們可以使其初始容量為0，那么它的動(dòng)態(tài)擴(kuò)容發(fā)生在哪里？

可以肯定就發(fā)生在add()方法中，那么查看add()方法源碼如下

publicbooleanadd(Ee){

//ensureCapacityInternal()如下

ensureCapacityInternal(size+1);//IncrementsmodCount!!

elementData[size++]=e;

returntrue;

}

按照我們第一次add，size肯定是0了，所以ensureCapacityInternal這個(gè)函數(shù)傳入的是1

//第一次add時(shí)，參數(shù)minCapacity=1

privatevoidensureCapacityInternal(intminCapacity){

ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));

//calculateCapacity()方法

privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){

//如果是第一次add元素

if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){

//minCapacity設(shè)置為DEFAULT_CAPACITY與minCapacity的最大值

returnMath.max(DEFAULT_CAPACITY,minCapacity);

returnminCapacity;

//ensureExplicitCapacity()方法

privatevoidensureExplicitCapacity(intminCapacity){

modCount++;

//overflow-consciouscode

if(minCapacity-elementData.length0)

grow(minCapacity);

}

elementData.length是數(shù)組長(zhǎng)度，它是隨著數(shù)組擴(kuò)容而動(dòng)態(tài)變化的

如果是第一次add元素時(shí)，它為0之后它是隨著oldCapacity+(oldCapacity1)而動(dòng)態(tài)變化的

首先看calculateCapacity()方法

如果是第一次add元素，那么minCapacity設(shè)置為DEFAULT_CAPACITY與minCapacity的最大值，即10與1取最大值，這里返回最大值10否則，直接返回minCapacity

再看ensureExplicitCapacity()方法

如果是第一次add元素，由上面方法可知minCapacity=10，即10-00返回true，再調(diào)用grow()方法只要minCapacity-elementData.length0為true，就會(huì)再調(diào)用grow()方法

privatevoidgrow(intminCapacity){

//原容量

intoldCapacity=elementData.length;

//擴(kuò)容后的容量，擴(kuò)大到原容量的1.5倍左右，右移一位相當(dāng)于原數(shù)值除以2的商

intnewCapacity=oldCapacity+(oldCapacity1);

//如果新容量減去最小容量的值小于0

if(newCapacity-minCapacity0)

//新容量等于最小容量

newCapacity=minCapacity;

//如果新容量減去建議最大容量的值大于0

if(newCapacity-MAX_ARRAY_SIZE0)

//調(diào)整新容量上限或者拋出OutOfMemoryError

newCapacity=hugeCapacity(minCapacity);

//最終進(jìn)行新數(shù)組的構(gòu)建和重新賦值，此后原數(shù)組被摒棄

//elementData:原數(shù)組;newCapacity:新數(shù)組容量

elementData=Arrays.copyOf(elementData,newCapacity);

}

elementData.length是數(shù)組長(zhǎng)度，它是隨著數(shù)組拷貝而動(dòng)態(tài)變化的

如果是第一次add元素時(shí)，它為0之后它是隨著oldCapacity+(oldCapacity1)而動(dòng)態(tài)變化的

如果是第一次add元素，由上面的方法可知參數(shù)minCapacity=10，第一次add元素oldCapacity=0，可得知newCapacity=0+0，由于newCapacity-minCapacity0，所以newCapacity=minCapacity=10重新賦值，最終進(jìn)行新數(shù)組的構(gòu)建和拷貝賦值

3.小結(jié)

3.1.初始容量

如果使用ArrayList的默認(rèn)無(wú)參構(gòu)造器時(shí)，它的初始容量就是0

如果使用ArrayList的有參構(gòu)造器時(shí)，它的初始容量就是你傳入的參數(shù)initialCapacity的值

3.2.動(dòng)態(tài)擴(kuò)容大小

ArrayList的初始容量為0，當(dāng)?shù)谝淮蝍dd元素時(shí)，才會(huì)發(fā)生擴(kuò)容操作，它的擴(kuò)容大小是10

當(dāng)?shù)谝淮蝍dd元素完成后，此時(shí)的elementData.length=10，后面要想發(fā)生擴(kuò)容操作，必須minCapacity-elementData.length0為true，即minCapacity最小為11，也就是說(shuō)當(dāng)ArrayList第十一次add時(shí)，才會(huì)接著發(fā)生擴(kuò)容操作，且擴(kuò)容大小為15=10+5

3.3.動(dòng)態(tài)擴(kuò)容大小測(cè)試

publicclassTestArrayList{

publicstaticvoidmain(String[]args){

ListIntegerlist=newArrayList();

list.add(1);

list.add(2);

list.add(3);

list.add(4);

list.add(5);

list.add(6);

list.add(7);