Java ArrayList.add 的实现方法

2023-09-06 04:10:05 154

ArrayList是平时相当常用的List实现,其中booleanadd(Ee)的实现比较直接:

/**
*Appendsthespecifiedelementtotheendofthislist.
*
*@parameelementtobeappendedtothislist
*@returntrue(asspecifiedby{@linkCollection#add})
*/
publicbooleanadd(Ee){
ensureCapacityInternal(size+1);//IncrementsmodCount!!
elementData[size++]=e;
returntrue;
}

有时候也使用voidadd(intindex,Eelement)把元素插入到指定的index上.在JDK中的实现是:

/**
*Insertsthespecifiedelementatthespecifiedpositioninthis
*list.Shiftstheelementcurrentlyatthatposition(ifany)and
*anysubsequentelementstotheright(addsonetotheirindices).
*
*@paramindexindexatwhichthespecifiedelementistobeinserted
*@paramelementelementtobeinserted
*@throwsIndexOutOfBoundsException{@inheritDoc}
*/
publicvoidadd(intindex,Eelement){
rangeCheckForAdd(index);

ensureCapacityInternal(size+1);//IncrementsmodCount!!
System.arraycopy(elementData,index,elementData,index+1,
size-index);
elementData[index]=element;
size++;
}

略有差别,需要保证当前elementData数组容量够用,然后把从index处一直到尾部的数组元素都向后挪一位.最后把要插入的元素赋给数组的index处.

一直以来,我都认为System.arraycopy这个native方法,它的c++实现是调用底层的memcpy,直接方便,效率也没问题.

但今天看了openJDK的源码发现并非如此.

以openJDK8u60为例,在objArrayKlass.cpp中:

voidObjArrayKlass::copy_array(arrayOops,intsrc_pos,arrayOopd,
intdst_pos,intlength,TRAPS){
assert(s->is_objArray(),"mustbeobjarray");

if(!d->is_objArray()){
THROW(vmSymbols::java_lang_ArrayStoreException());
}

//Checkisalloffsetsandlengthsarenonnegative
if(src_pos<0||dst_pos<0||length<0){
THROW(vmSymbols::java_lang_ArrayIndexOutOfBoundsException());
}
//Checkiftherangesarevalid
if((((unsignedint)length+(unsignedint)src_pos)>(unsignedint)s->length())
||(((unsignedint)length+(unsignedint)dst_pos)>(unsignedint)d->length())){
THROW(vmSymbols::java_lang_ArrayIndexOutOfBoundsException());
}

//Specialcase.Boundarycasesmustbecheckedfirst
//Thisallowsthefollowingcall:copy_array(s,s.length(),d.length(),0).
//Thisiscorrect,sincethepositionissupposedtobean'inbetweenpoint',i.e.,s.length(),
//pointstotherightofthelastelement.
if(length==0){
return;
}
if(UseCompressedOops){
narrowOop*constsrc=objArrayOop(s)->obj_at_addr(src_pos);
narrowOop*constdst=objArrayOop(d)->obj_at_addr(dst_pos);
do_copy(s,src,d,dst,length,CHECK);
}else{
oop*constsrc=objArrayOop(s)->obj_at_addr(src_pos);
oop*constdst=objArrayOop(d)->obj_at_addr(dst_pos);
do_copy(s,src,d,dst,length,CHECK);
}
}

可以看到copy_array在做了各种检查之后,最终copy的部分在do_copy方法中,而这个方法实现如下:

//EitheroopornarrowOopdependingonUseCompressedOops.
templatevoidObjArrayKlass::do_copy(arrayOops,T*src,
arrayOopd,T*dst,intlength,TRAPS){

BarrierSet*bs=Universe::heap()->barrier_set();
//Forperformancereasons,weassumewearethatthewritebarrierwe
//areusinghasoptimizedmodesforarraysofreferences.Atleastone
//oftheassertsbelowwillfailifthisisnotthecase.
assert(bs->has_write_ref_array_opt(),"Barriersetmusthaverefarrayopt");
assert(bs->has_write_ref_array_pre_opt(),"Forpre-barrieraswell.");

if(s==d){
//sincesourceanddestinationareequalwedonotneedconversionchecks.
assert(length>0,"sanitycheck");
bs->write_ref_array_pre(dst,length);
Copy::conjoint_oops_atomic(src,dst,length);
}else{
//Wehavetomakesureallelementsconformtothedestinationarray
Klass*bound=ObjArrayKlass::cast(d->klass())->element_klass();
Klass*stype=ObjArrayKlass::cast(s->klass())->element_klass();
if(stype==bound||stype->is_subtype_of(bound)){
//elementsareguaranteedtobesubtypes,sonochecknecessary
bs->write_ref_array_pre(dst,length);
Copy::conjoint_oops_atomic(src,dst,length);
}else{
//slowcase:needindividualsubtypechecks
//note:don'tuseobj_at_putbelowbecauseitincludesaredundantstorecheck
T*from=src;
T*end=from+length;
for(T*p=dst;fromklass())->is_subtype_of(bound)){
bs->write_ref_field_pre(p,new_val);
*p=element;
}else{
//Wemustdoabarriertocoverthepartialcopy.
constsize_tpd=pointer_delta(p,dst,(size_t)heapOopSize);
//pointerdeltaisscaledtonumberofelements(lengthfieldin
//objArrayOop)whichweassumeis32bit.
assert(pd==(size_t)(int)pd,"lengthfieldoverflow");
bs->write_ref_array((HeapWord*)dst,pd);
THROW(vmSymbols::java_lang_ArrayStoreException());
return;
}
}
}
}
bs->write_ref_array((HeapWord*)dst,length);
}

可以看到,在设定了heapbarrier之后,元素是在for循环中被一个个挪动的.做的工作比我想象的要多.

如果有m个元素,按照给定位置,使用ArrayList.add(int,E)逐个插入到一个长度为n的ArrayList中,复杂度应当是O(m*n),或者O(m*(m+n)),所以,如果m和n都不小的话,效率确实是不高的.

效率高一些的方法是,建立m+n长度的数组或ArrayList,在给定位置赋值该m个要插入的元素,其他位置依次赋值原n长度List的元素.这样时间复杂度应当是O(m+n).

还有,在前面的实现中,我们可以看到有对ensureCapacityInternal(int)的调用.这个保证数组容量的实现主要在:

/**
*Increasesthecapacitytoensurethatitcanholdatleastthe
*numberofelementsspecifiedbytheminimumcapacityargument.
*
*@paramminCapacitythedesiredminimumcapacity
*/
privatevoidgrow(intminCapacity){
//overflow-consciouscode
intoldCapacity=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);
}

大家知道由于效率原因,ArrayList容量增长不是正好按照要求的容量minCapacity来设计的,新容量计算的主要逻辑是:如果要求容量比当前容量的1.5倍大,就按照要求容量重新分配空间;否则按当前容量1.5倍增加.当然不能超出Integer.MAX_VALUE了.oldCapacity+(oldCapacity>>1)实际就是当前容量1.5倍,等同于(int)(oldCapacity*1.5),但因这段不涉及浮点运算只是移位,显然效率高不少.

所以如果ArrayList一个一个add元素的话,容量是在不够的时候1.5倍增长的.关于1.5这个数字,或许是觉得2倍增长太快了吧.也或许有实验数据的验证支撑.

关于这段代码中出现的Arrays.copyOf这个方法,实现的是重新分配一段数组,把elementData赋值给新分配的空间,如果新分配的空间大,则后面赋值null,如果分配空间比当前数组小则截断.底层还是调用的System.arraycopy.

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

Java ArrayList.add 的实现方法

热门推荐

随机推荐