Java集合框架ArrayList源码分析(一)
ArrayList底层维护的是一个动态数组,每个ArrayList实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。
ArrayList不是同步的(也就是说不是线程安全的),如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步,在多线程环境下,可以使用Collections.synchronizedList方法声明一个线程安全的ArrayList,例如:
Listarraylist=Collections.synchronizedList(newArrayList());
下面通过ArrayList的源码来分析其原理。
1、ArrayList的构造方法:ArrayList提供了三种不同的构造方法
1)ArrayList(),构造一个初始容量为10的空列表。
2)ArrayList(intinitialCapacity),构造一个具有指定初始容量的空列表。
3)ArrayList(Collection<?extendsE>c),构造一个包含指定collection的元素的列表,这些元素是按照该collection的迭代器返回它们的顺序排列的。
源码如下:
privatetransientObject[]elementData; publicArrayList(intinitialCapacity){ super(); if(initialCapacity<0) thrownewIllegalArgumentException("IllegalCapacity:"+initialCapacity); this.elementData=newObject[initialCapacity];//生成一个长度为10的Object类型的数组 } publicArrayList(){ this(10);//调用ArrayList(inti) }<br><br> publicArrayList(Collection<?extendsE>c){ elementData=c.toArray();//返回包含此collection中所有元素的数组 size=elementData.length; //c.toArraymight(incorrectly)notreturnObject[](see6260652) if(elementData.getClass()!=Object[].class) elementData=Arrays.copyOf(elementData,size,Object[].class);//复制指定的数组,返回包含相同元素和长度的Object类型的数组 }
当采用不带参数的构造方法ArrayList()生成一个集合对象时,其实是在底层调用ArrayList(intinitialCapacity)这一构造方法生产一个长度为10的Object类型的数组。当采用带有集合类型参数的构造方法时,在底层生成一个包含相同的元素和长度的Object类型的数组。
2、add方法:ArrayList提供了两种添加元素的add方法
1)add(Ee),将指定的元素添加到此列表的尾部。
2)add(intindex,Ee),将指定的元素插入此列表中的指定位置。向右移动当前位于该位置的元素(如果有)以及所有后续元素(将其索引加1)privateintsize;
publicbooleanadd(Ee){ ensureCapacity(size+1);//扩大数组容量 elementData[size++]=e;//将元素e添加到下标为size的Object数组中,并且执行size++ returntrue; } publicvoidadd(intindex,Eelement){ if(index>size||index<0)//如果指定要插入的数组下标超过数组容量或者指定的下标小于0,抛异常 thrownewIndexOutOfBoundsException("Index:"+index+",Size:"+size); ensureCapacity(size+1);//扩大数组容量 System.arraycopy(elementData,index,elementData,index+1,size-index);//从指定源数组中复制一个数组,复制从指定的位置开始,到目标数组的指定位置结束。<br>//elementData---源数组index---源数组中的起始位置<br>//elementData---目标数组index+1---目标数组中的起始位置<br>//size-index---要复制的数组元素的数量 elementData[index]=element;//将要添加的元素放到指定的数组下标处 size++; }
publicvoidensureCapacity(intminCapacity){ modCount++; intoldCapacity=elementData.length;//原数组的容量 if(minCapacity>oldCapacity){ ObjectoldData[]=elementData; intnewCapacity=(oldCapacity*3)/2+1;//定义新数组的容量,为原数组容量的1.5倍+1 if(newCapacity<minCapacity) newCapacity=minCapacity; //minCapacityisusuallyclosetosize,sothisisawin: elementData=Arrays.copyOf(elementData,newCapacity);//复制指定的数组,返回新数组的容量为newCapacity } }
如果集合中添加的元素超过了10个,那么ArrayList底层会新生成一个数组,长度为原数组的1.5倍+1,并将原数组中的元素copy到新数组中,并且后续添加的元素都会放在新数组中,当新数组的长度无法容纳新添加的元素时,重复该过程。这就是集合添加元素的实现原理。
3、get方法:
1)get(intindex),返回此列表中指定位置上的元素。
publicEget(intindex){ RangeCheck(index);//检查传入的指定下标是否合法 return(E)elementData[index];//返回数组下标为index的数组元素 } privatevoidRangeCheck(intindex){ if(index>=size)//如果传入的下标大于或等于集合的容量,抛异常 thrownewIndexOutOfBoundsException( "Index:"+index+",Size:"+size); }
4、remove方法:
1)Eremove(intindex),移除此列表中指定位置上的元素。向左移动所有后续元素(将其索引减1)。
2)booleanremove(Objecto),移除此列表中首次出现的指定元素(如果存在)。如果列表不包含此元素,则列表不做改动,返回boolean值。
publicEremove(intindex){ RangeCheck(index);//检查指定的下标是否合法 modCount++; EoldValue=(E)elementData[index];//获取指定下标的数组元素 intnumMoved=size-index-1;//要移动的元素个数 if(numMoved>0) System.arraycopy(elementData,index+1,elementData,index,numMoved);//移动数组元素 elementData[--size]=null;//Letgcdoitswork returnoldValue; } publicbooleanremove(Objecto){ if(o==null){//如果传入的参数为null for(intindex=0;index<size;index++) if(elementData[index]==null){//移除首次出现的null fastRemove(index); returntrue; } }else{ for(intindex=0;index<size;index++) if(o.equals(elementData[index])){ fastRemove(index); returntrue; } } returnfalse; } privatevoidfastRemove(intindex){//移除指定位置的元素,实现方法类似remove(inti) modCount++; intnumMoved=size-index-1; if(numMoved>0) System.arraycopy(elementData,index+1,elementData,index, numMoved); elementData[--size]=null;//Letgcdoitswork }
5、clone方法:
1)Objectclone(),返回此ArrayList实例的浅表副本(不复制这些元素本身)。
publicObjectclone(){ try{ ArrayList<E>v=(ArrayList<E>)super.clone();//调用Object类的clone方法返回一个ArrayList对象 v.elementData=Arrays.copyOf(elementData,size);//复制目标数组 v.modCount=0; returnv; }catch(CloneNotSupportedExceptione){ //thisshouldn'thappen,sinceweareCloneable thrownewInternalError(); } }
以上通过对ArrayList部分关键源码的分析,知道了ArrayList底层的实现原理,关于ArrayList源码有以下几点几点总结:
1)ArrayList底层是基于数组来实现的,可以通过下标准确的找到目标元素,因此查找的效率高;但是添加或删除元素会涉及到大量元素的位置移动,效率低。
2)ArrayList提供了三种不同的构造方法,无参数的构造方法默认在底层生成一个长度为10的Object类型的数组,当集合中添加的元素个数大于10,数组会自动进行扩容,即生成一个新的数组,并将原数组的元素放到新数组中。
3)ensureCapacity方法对数组进行扩容,它会生成一个新数组,长度是原数组的1.5倍+1,随着向ArrayList中不断添加元素,当数组长度无法满足需要时,重复该过程。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。