新手入门了解ArrayList扩容机制
我们下面用最简单的代码创建ArrayList并添加11个元素,并一一讲解底层源码;在说之前,给大家先普及一些小知识:
》ArrayList底层是用数组来实现的
》数组一旦创建后,大小就是固定的,如果超出了数组大小后,就会创建一个新的数组
》接下来所谓数组的扩容实质上是重新创建一个大小更大的新数组
@Test publicvoidtestArrayList(){ //创建一个泛型为String的ArrayList(这里泛型是什么不重要) ArrayListlist=newArrayList (); //依次添加11个元素 list.add("1"); list.add("2"); list.add("3"); list.add("4"); list.add("5"); list.add("6"); list.add("7"); list.add("8"); list.add("9"); list.add("10"); list.add("11"); }
上面的代码中,我们就只调用了add(),在看add()源码前,我必须给你们先介绍一些在ArrayList的常量和变量,因为在接下来的源码中会涉及到这些,怕你们到时一脸蒙
privatestaticfinalintDEFAULT_CAPACITY=10; privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={}; transientObject[]elementData; privateintsize; privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;
》DEFAULT_CAPACITY:default_capcity,默认的容量大小,也就是当你第一次创建数组并往里面添加第一个元素时,数组的默认容量大小
》DEFAULTCAPACITY_EMPTY_ELEMENTDATA:defaultcapacity_empty_elementdata是默认的空数组,他的作用是当elementData为{},即空数组时,把它赋值给elementData,要是理解不了,请你往下继续看!
》elementData:表示的就是当前存储元素的数组
》size:他表示当前还没有添加新元素前的数组中有效的元素个数,比如说数组长度为10,只保存了5个元素,那有效长度就是5
》MAX_ARRAY_SIZE:最大数组长度,它用来标识当前数组可保存元素的最大长度,值为Integer_MAX_VALUE-8,即2147483647-8,这里的8代表8字节用来保存数组本身的内存大小。
现在我们进入到add()里面看他们具体如何实现的,如下代码:
publicbooleanadd(Ee){ ensureCapacityInternal(size+1);//IncrementsmodCount!! elementData[size++]=e; returntrue; }
》ensureCapacityInternal(size+1):这个方法意为“确保内部变量”,什么意思呢?他是用来判断当前数组的容量是否足够,不足就扩容;等下我们会进入这个方法来看他如何具体实现的,size表示当前还未添加新元素前的数组有效元素个数,而size+1表示传入当前数组的最小容量(有效长度)
》elementData[size++]=e:这段语句意思是给数组做赋值操作,简单说就是给数组添加元素;比如说当前数组已经有3个元素了,那现在再添加一个元素a,则这一步为elementData[3]=a;
》returntrue:代表添加成功;
现在我们就进入到ensureCapacityInternal(),如下代码:
privatevoidensureCapacityInternal(intminCapacity){ ensureExplicitCapacity(calculateCapacity(elementData,minCapacity)); }
这里面涉及两个方法ensureExplicitCapacity()和calculateCapacity():
》calculateCapacity():计算容量,它用来计算当前的数组所需的最小容量minCapacity,你可以理解为当前数组的有效长度;源码如下:
privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){//若传入的是个空数组,则返回的是最小容量是默认容量(10)和当前最小容量(0)之间的最大值 if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){ returnMath.max(DEFAULT_CAPACITY,minCapacity); } returnminCapacity; }
PS:第一次添加元素时calculateCapacity返回的最小容量minCapacity是10,从第二次开始minCapacity为2,第三次为3,依次类推..在这里第一次返回10大家不要纠结它的意义,重点在第二次及之后表示的意思
》ensureExplicitCapacity():判断是否需要扩容;查看它的源码:
privatevoidensureExplicitCapacity(intminCapacity){ modCount++; //overflow-consciouscode当最小容量大于当前的数组大小时 if(minCapacity-elementData.length>0)//计算扩容后的数组大小 grow(minCapacity); }
我们第一次list.add(),最小容量minCapacity是10,elementData.length长度为0,所以条件成立,进入grow()(第二次minCapacity是2,elementData.length为10,条件不成立就不再扩容了;当第11次时,11>10,又可以扩容了)
privatevoidgrow(intminCapacity){ //得到当前数组的大小,即老数组大小 intoldCapacity=elementData.length; //将旧数组大小+旧数组/2,即旧数组的1.5倍是新数组的大小(先不要在意>>1的意思,你只要知道oldCapacity>>1表示oldCapacity/2就行) intnewCapacity=oldCapacity+(oldCapacity>>1); //如果扩容后的是数组大小还是小于最小所需容量,直接让minCapacity赋值到新容量 if(newCapacity-minCapacity<0) newCapacity=minCapacity; //若新容量大小大于数组长度的最大预设值;由于扩容后是原数组的1.5倍,则非常有可能会溢出这个预设值 if(newCapacity-MAX_ARRAY_SIZE>0) newCapacity=hugeCapacity(minCapacity); //minCapacityisusuallyclosetosize,sothisisawin: //上面都是为了确定最终的新容量的大小,这个方法是真正的扩容实现 elementData=Arrays.copyOf(elementData,newCapacity); }
相信大家这上面大部分都能够理解,可能就一个地方不太清楚:当newCapacity>MAX_ARRAY_SIZE(新容量大于预设值较特殊的情况,一般数组长度不会扩容到这么大)时调用hugeCapacity有啥用?我们看下hugeCapacity()的源码:
privatestaticinthugeCapacity(intminCapacity){ //若最小容量小于0的情况,抛出异常 if(minCapacity<0)//overflow thrownewOutOfMemoryError(); //若最小容量>最大预设值,返回Integer.Max_VALUE,否则是MAX_ARRAY_SIZE(Integer.Max_VALUE-8) return(minCapacity>MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE; }
hugeCapacity()是用来限制新容量的大小的,是不能超出Integer.MAX_VALUE值的,最后说一点,数组的最大长度并不是MAX_ARRAY_SIZE,而是Integer.MAX_VALUE。
》Arrays.copyOf(elementData,newCapacity),就不看源码了,简单说一下:它这个方法能返回一个扩容后的数组,将旧数组elementData的数据复制到长度为newCapacity的新数组中。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。