查看JDK1.8 ArrayList的源代码

1、默认初始容量为10

/***Defaultinitialcapacity.*/privatestaticfinalintDEFAULT_CAPACITY=10;

2、最大容量为 Integer.MAX_VALUE - 8

/***Themaximumsizeofarraytoallocate.*SomeVMsreservesomeheaderwordsinanarray.*Attemptstoallocatelargerarraysmayresultin*OutOfMemoryError:RequestedarraysizeexceedsVMlimit*/privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;

原因:之前参考别人的,有待求证:

数组对象有一个额外的元数据,用于表示数组的大小;

数组长度size为int类型,共32位,有一位符号位,所以最大长度为Integer.MAX_VALUE=2^31= 2,147,483,648;

8bytes用来存储size;

3、扩容方式:

(1)首先传递进来一个希望的最小容量minCapacity;

(2)新容量newCapacity = oldCapacity + (oldCapacity >> 1),即新容量等于原容量的1.5倍;

(3)如果minCapacity > newCapacity ,newCapacity = minCapacity ;

(4)如果 newCapacity > 最大容量 MAX_ARRAY_SIZE ,newCapacity = hugeCapacity(minCapacity);

(5)以新容量拷贝原数据

/***Increasesthecapacitytoensurethatitcanholdatleastthe*numberofelementsspecifiedbytheminimumcapacityargument.**@paramminCapacitythedesiredminimumcapacity*/privatevoidgrow(intminCapacity){//overflow-consciouscodeintoldCapacity=elementData.length;intnewCapacity=oldCapacity+(oldCapacity>>1);if(newCapacity-minCapacity<0)newCapacity=minCapacity;if(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);//minCapacityisusuallyclosetosize,sothisisawin:elementData=Arrays.copyOf(elementData,newCapacity);}privatestaticinthugeCapacity(intminCapacity){if(minCapacity<0)//overflowthrownewOutOfMemoryError();return(minCapacity>MAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE;}

Java ArrayList() 扩容原理

平常都是直接使用 ArrayList(),今天特地看一下 ArrayList() 的扩容原理。

先看下 ArrayList 的属性以及构造方法,这个比较重要

先看下属性

//ArrayList默认容量大小privatestaticfinalintDEFAULT_CAPACITY=10;//一个共享的空数组,在空实例时使用privatestaticfinalObject[]EMPTY_ELEMENTDATA={};//一个共享的空数组,在使用默认size的空实例时使用privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};/*存储ArrayList元素的数组缓冲区重点1:ArrayList的容量是数组缓冲区的长度重点2:从这个元素也可以看的出来ArrayList()的底层就是一个Object[]add第一个元素时,任何带有elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将被扩展为DEFAULT_CAPACITY*/transientObject[]elementData;//ArrayList的大小,我们平常使用的list.size()底层就是记录的这个sizeprivateintsize;//ArrayList最大privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;

再看构造器,带参构造器

/*带参构造器,参数为容量大小,例如:初始化一个容器为20类型为Integer的ArrayListArrayList<Integer>list=newArrayList<>(20);*/publicArrayList(intinitialCapacity){/*初始化容量>0,elementData初始化为初始化容量大小的数组初始化容量=0,elementData=EMPTY_ELEMENTDATA(空数组)初始化容量<0,直接抛出异常*/if(initialCapacity>0){this.elementData=newObject[initialCapacity];}elseif(initialCapacity==0){this.elementData=EMPTY_ELEMENTDATA;}else{thrownewIllegalArgumentException("IllegalCapacity:"+initialCapacity);}}

参数为 Collection 的构造器

/*将一个参数为Collection的集合转换为ArrayList*/publicArrayList(Collection<?extendsE>c){//Collection转换为数组Object[]类型elementData=c.toArray();//判断当前对象大小是否和Collection长度相等并且不等于0,false的话elementData等于空数组了if((size=elementData.length)!=0){//c.toArray()可能不会正确地返回一个Object[]数组,所以使用Arrays.copyOf()if(elementData.getClass()!=Object[].class)elementData=Arrays.copyOf(elementData,size,Object[].class);}else{this.elementData=EMPTY_ELEMENTDATA;}}

不带参构造器

/*不带参构造器就像我们平时使用一样,直接new一个ArrayList不需要传递任何参数构造方法中直接将elementData初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA(空数组)*/publicArrayList(){this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

看到这里就发现,带参的构造器我们可以直接传递参数,而默认的构造器怎么怎么样初始化容量大小的呢?

add() 方法可以直接得到答案。

publicbooleanadd(Ee){//这一行是关键,看下面ensureCapacityInternal(size+1);//将元素追加到集合的末尾假如当前size=10size++追加到第11位elementData[size++]=e;returntrue;}

ensureCapacityInternal() 方法调用

privatevoidensureCapacityInternal(intminCapacity){/*calculateCapacity()方法,刚初始化时会返回10,其他情况返回当前size+1ensureExplicitCapacity()方法,调用扩容*/ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));}privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){/*使用无参构造器创建创建ArrayList的集合,此时一定是相等的*/if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){/*两数相比返回最大值,此时Math.max(10,1);默认容量,由此而来*/returnMath.max(DEFAULT_CAPACITY,minCapacity);}//不相等的话只有返回当前的size+1returnminCapacity;}privatevoidensureExplicitCapacity(intminCapacity){//增量,记录修改/更新次数modCount++;//初始化:10-0>0//其他:size+1>0if(minCapacity-elementData.length>0)//扩容操作grow(minCapacity);}privatevoidgrow(intminCapacity){//老的长度,初始化时为0,intoldCapacity=elementData.length;//新的长度此时0+(0>>1),newCapacity=0intnewCapacity=oldCapacity+(oldCapacity>>1);//初始化场景:0-10<0?truenewCapacity=10if(newCapacity-minCapacity<0)newCapacity=minCapacity;//初始化场景:10-2147483639>0返回falseif(newCapacity-MAX_ARRAY_SIZE>0)//超大长度才可以执行这个方法,必须大于MAX_ARRAY_SIZE一般不会newCapacity=hugeCapacity(minCapacity);//复制原数组中的元素,并扩容elementData=Arrays.copyOf(elementData,newCapacity);}

上看说的是初始化场景,下面看一下其他场景,也是相当简单

privatevoidensureCapacityInternal(intminCapacity){/*calculateCapacity()方法,正常扩容返回size+1,比如10+1,因为默认长度为10当再次新增数据时就会出发扩容ensureExplicitCapacity()方法,调用扩容*/ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));}privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){returnMath.max(DEFAULT_CAPACITY,minCapacity);}/*elementData不等于空数组返回当前的size+1,即10+1返回11*/returnminCapacity;}privatevoidensureExplicitCapacity(intminCapacity){//增量,记录修改/更新次数modCount++;//其他:11-10>0true,触发扩容,如果当前下表是5的话5+1=6,6<10是,此时不会出发扩容if(minCapacity-elementData.length>0)//扩容操作grow(minCapacity);}privatevoidgrow(intminCapacity){//老的长度10intoldCapacity=elementData.length;//新的长度此时10+(10>>1),newCapacity=15intnewCapacity=oldCapacity+(oldCapacity>>1);//15-11<0?falseif(newCapacity-minCapacity<0)newCapacity=minCapacity;//15-2147483639>0返回falseif(newCapacity-MAX_ARRAY_SIZE>0)//超大长度才可以执行这个方法,必须大于MAX_ARRAY_SIZE一般不会newCapacity=hugeCapacity(minCapacity);//复制原数组中的元素,并扩容newCapacity=15elementData=Arrays.copyOf(elementData,newCapacity);}

结论

1、 触发扩容的关键是

当前 size + 1 是否大于当前容量,如果大于容量则证明,集合不够用了,需要扩容。如果小与当前容量则证明集合还有容量不需要扩容!

2、 每次扩容的大小是

oldCapacity+(oldCapacity>>1)即:10+(10>>1)

即:当前容量的 1.5 倍!