Java ArrayList源码分析(数据结构与算法)

文章资讯 2020-07-16 20:34:02

Java ArrayList源码分析(数据结构与算法)

ArrayList本质是通过一个可变长的数组来存储不定量的元素,且当元素通过不同方式被添加存储时,总是先计算自身容量,若符合扩容标准则对数组进行扩容并拷贝原有元素
本文将基于JDK8对ArrayList源码中的构造ArrayList()、存储add()、删除move()、扩容grow()、序列化(writeObject()、adObject())等过程中所涉及JDK源码做行级解释
ublicclassArrayList<E>extendsAbstractList<E>imlementsList<E>,RandomAccess,Cloneable,Serializable{
略···
}定义ArrayList时继承AbstractList抽象类表示这是一个数组队列,含有增删改查遍历等常用操作。实现RandomAccess接口表示此对象可进行随机访问。实现Cloneable接口表示此对象可被克隆。实现Serializable接口表示此对象可被序列化与反序列化,接下来开始进入正题!ArrayList实例化
ArrstList共提供了3种构造方法,支持指定长度和指定元素内容,满足各种常见场景下对容量的需求
默认初始容量
rivatestaticfinalintDEFAULT_CAPACITY=10;若初始化时指定了长度或添加集合,但长度为0,则赋值为此对象。若elementData等于此对象,表示有参实例化,首次add时数组仅扩容至1
如:ArrayList<Integer>mArrayList=newArrayList<Integer>(0);
rivatestaticfinalObject[]EMPTY_ELEMENTDATA=newObject[0];若初始化时不指定长度或添加集合则赋值为此对象。若elementData等于此对象,表示是无参实例化,首次add时数组默认扩充容量至10
如:ArrayList<Integer>mArrayList=newArrayList<Integer>();
区别赋值的原因猜测是因为后者实例方式更符合实际开发需要,所以首次就给了较多容量,减少多次扩容的资源开支
rivatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA=newObject[0];elementData是用来保存元素的数组。因为他的容量通常大于实际使用量,会产生空余空间,所以被修饰为transient,
表示不可被序列化,避免序列化时时间与空间的浪费,而ArrayList的序列化与反序列化通过writeObject和adObject完成
transientObject[]elementData;当前数组长度
rivateintsize;最大数组长度
rivatestaticfinalintMAX_ARRAY_SIZE=2147483639;第1种:初始化一个长度为0的空数组
ublicArrayList(){
this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}第2种:初始化时指定数组长度
ublicArrayList(intvar1){
检查长度参数var1是否合法,若合法则按需创建数组
if(var1>0){
this.elementData=newObject[var1];
}else{
若var1非零则表示为负数,抛出非法参数异常
if(var1!=0){
townewIllegalArgumentExcetion("IllegalCaacity:"+var1);
}
若var1为零,则创建长度为0的数组
this.elementData=EMPTY_ELEMENTDATA;
}
}第3种:初始化时批量添加元素
ublicArrayList(Collection<?extendsE>var1){
将传入的集合转为数组,并将结果进行赋值
this.elementData=var1.toArray();
若转换结果不为空,则继续处理
if((this.size=this.elementData.length)!=0){
if(this.elementData.getClass()!=Object[].class){
this.elementData=Arrays.coyOf(this.elementData,this.size,Object[].class);
}
}else{
若传入的集合为空,则仅仅只是初始化一个空数组
this.elementData=EMPTY_ELEMENTDATA;
}
}ArrayList添加元素
ArrstList共提供4种添加元素方法,支持指定位置、批量添加,在此检查是否符合扩容条件
第1种:添加一个在数组创建时指定类型的元素
ublicbooleanadd(Evar1){
检查是否需要扩容
this.ensuCaacityInternal(this.size+1);
向数组尾部插入新元素(size表示当前数组中最后一个被插入元素的下标)
this.elementData[this.size++]=var1;
turntrue;
}第2种:在指定位置,添加一个在数组创建时指定类型的元素
ublicvoidadd(intvar1,Evar2){
检查下标边界是否合法
this.rangeCheckForAdd(var1);
检查是否需要扩容
this.ensuCaacityInternal(this.size+1);
移动当前数组内元素位置
System.arraycoy(this.elementData,var1,this.elementData,var1+1,this.size-var1);
向指定位置插入新元素
this.elementData[var1]=var2;
更新尾元素下标位置
++this.size;
}第3种:添加一组指定类型的元素
ublicbooleanaddAll(Collection<?extendsE>var1){
转化为数组
Object[]var2=var1.toArray();
记录数组长度
intvar3=var2.length;
检查是否需要扩容
this.ensuCaacityInternal(this.size+var3);
向数组尾部插入一组新元素
System.arraycoy(var2,0,this.elementData,this.size,var3);
更新尾元素下标位置
this.size+=var3;
返回批量添加结果
turnvar3!=0;
}第4种:指定起始位置,添加一组指定类型的元素,
ublicbooleanaddAll(intvar1,Collection<?extendsE>var2){
检测起始位置是否合法
this.rangeCheckForAdd(var1);
转化为数组
Object[]var3=var2.toArray();
记录数组长度
intvar4=var3.length;
检查是否需要扩容
this.ensuCaacityInternal(this.size+var4);
计算所需插入区间的下标
intvar5=this.size-var1;
if(var5>0){
移动当前元素位置
System.arraycoy(this.elementData,var1,this.elementData,var1+var4,var5);
}
将新数组插入指定位置
System.arraycoy(var3,0,this.elementData,var1,var4);
更新尾元素下标位置
this.size+=var4;
返回批量添加结果
turnvar4!=0;
}相关方法源码解析
计算数组长度
rivatevoidensuCaacityInternal(intvar1){
若当前数组长度为0,则比较(10)与(目标长度),结果取大并更新目标数组长度值
if(this.elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
var1=Math.max(10,var1);
}
根据目标数组长度值,检查是否需要扩容
this.ensuExlicitCaacity(var1);
}检查是否需要扩容
rivatevoidensuExlicitCaacity(intvar1){
fail-fast机制用到的修改次数计数(ArrayList非线程安全,所以在使用迭代器过程中被修改的话,会抛出ConcurntModificationExcetions)
++this.modCount;
如果计算出来的目标数组长度大于当前数组的长度,则表示数组需要扩容
if(var1-this.elementData.length>0){
this.grow(var1);
}
}数组扩容
rivatevoidgrow(intvar1){
当前数组长度
intvar2=this.elementData.length;
扩容数组长度(默认1.5倍,也就是增加当前长度的50%)
intvar3=var2+(var2>>1);
如果扩容数组长度小于传入的目标数组长度,则更新扩容目标
if(var3-var1<0){
var3=var1;
}
扩容最大边界检查
if(var3-2147483639>0){
var3=hugeCaacity(var1);
}
数组扩容至目标长度,且保存现有元素
this.elementData=Arrays.coyOf(this.elementData,var3);
}检查目标插入下标边界是否合法
rivatevoidrangeCheckForAdd(intvar1){
if(var1>this.size||var1<0){
townewIndexOutOfBoundsExcetion(this.outOfBoundsMsg(var1));
}
}扩容长度检查
rivatestaticinthugeCaacity(intvar0){
if(var0<0){
非法参数则抛出异常
townewOutOfMemoryError();
}else{
如果扩容目标大于最大允许数组长度,则比较是否大于2147483639,大于的话扩容目标=2147483647,反之扩容目标=2147483639
turnvar0>2147483639?2147483647:2147483639;
}
}
ArrayList删除元素
ArrstList共提供3种删除元素方法,支持通过下标或对象删除
第1种:删除指定下标的元素(从0开始)
ublicEmove(intvar1){
检测下标是否合法
this.rangeCheck(var1);
fail-fast机制用到的修改次数计数(ArrayList非线程安全,所以在使用迭代器过程中被修改的话,会抛出ConcurntModificationExcetions)
++this.modCount;
获取即将被删除的元素
Objectvar2=this.elementData(var1);
计算需要移动的元素数量
intvar3=this.size-var1-1;
if(var3>0){
移动元素(被删除的元素,将被它后一个元素直接覆盖)
System.arraycoy(this.elementData,var1+1,this.elementData,var1,var3);
}
将尾部元素置空,因为它已被复制到前一个下标位置
this.elementData[--this.size]=null;
返回处理结果
turnvar2;
}第2种:删除指定对象
ublicbooleanmove(Objectvar1){
遍历起始下标
intvar2;
如果需要删除空对象
if(var1==null){
遍历当前数组中的空对象(但仅仅删除首个符合要求的元素)
for(var2=0;var2<this.size;++var2){
发现目标
if(this.elementData[var2]==null){
删除
this.fastRemove(var2);
turntrue;
}
}
}else{
遍历数组中的目标对象(但仅仅删除首个符合要求的元素)
for(var2=0;var2<this.size;++var2){
Object的equals和==比较的均是地址值
String的==比较的是值,equals则先比较地址,再顺序比较字符
if(var1.equals(this.elementData[var2])){
若相等则删除
this.fastRemove(var2);
turntrue;
}
}
}
turnfalse;
}第3种:清空
ublicvoidclear(){
++this.modCount;for(intvar1=0;var1<this.size;++var1){
this.elementData[var1]=null;
}
this.size=0;
}相关方法源码解析
检查下标是否合法
rivatevoidrangeCheck(intvar1){
若删除的元素下标大于数组内最后一个元素的下标,抛出IndexOutOfBoundsExcetion
var1是下标,从0开始;this.size是数组长度,从1开始,所以最后一个元素的下标最大也只能是this.size-1
if(var1>=this.size){
townewIndexOutOfBoundsExcetion(this.outOfBoundsMsg(var1));
}
}执行move()的删除操作(也可以讲是覆盖)
rivatevoidfastRemove(intvar1){
执行了删除操作,计数更新(用于Fail-Fast机制)
++this.modCount;
计算需要移动的元素数量
intvar2=this.size-var1-1;
if(var2>0){
移动元素(被删除的元素,将被它后一个元素直接覆盖)
System.arraycoy(this.elementData,var1+1,this.elementData,var1,var2);
}
将尾部元素置空,因为它已被复制到前一个下标位置
this.elementData[--this.size]=null;
}
System.arraycoy()数组复制
在对ArrayList进行操作的的过程中,System.arraycoy()这个native方法被频繁使用,它的作用是实现高效的数组间复制,在此标注下各项参数含义,避免产生困扰
ublicstaticnativevoidarraycoy(Objectvar0,intvar1,Objectvar2,intvar3,intvar4);Objectvar0:源数组
intvar1:源数组复制起始下标
Objectvar2:目标数组
intvar3:目标数组存储起始下标
intvar4:需复制长度ArrayList序列化
通过源码我们可以看到这项定义:transientObject[]elementData;,这表示被transient修饰的数组不可被序列化,但elementData又是实际存储了元素的数组,且ArrayList肯定可以序列化传输,那么这么操作的原因是为什么?
很简单,当Arraylist被定以后,每次添加元素都需检查当前容量是否符合扩容标准,而扩容并不会在数组长度被用完时进行,所以数组的长度总是大于实际使用长度,而在这种情况下直接序列化对象,必然造成时间成本与空间资源的浪费,所以ArrayList内提供了writeObject与 adObject两个方法,以this.size为循环条件,只处理有效元素
transientObject[]elementData;

略···rivatevoidwriteObject(ObjectOututStamvar1)towsIOExcetion{
intvar2=this.modCount;
var1.defaultWriteObject();
var1.writeInt(this.size);for(intvar3=0;var3<this.size;++var3){
var1.writeObject(this.elementData[var3]);
}if(this.modCount!=var2){
townewConcurntModificationExcetion();
}
}rivatevoidadObject(ObjectInutStamvar1)towsIOExcetion,ClassNotFoundExcetion{
this.elementData=EMPTY_ELEMENTDATA;
var1.defaultReadObject();
var1.adInt();
if(this.size>0){
this.ensuCaacityInternal(this.size);
Object[]var2=this.elementData;for(intvar3=0;var3<this.size;++var3){
var2[var3]=var1.adObject();
}
}
}