ArrayList
基本原理
内部组成
可以看出,ArrayList的基本用法是比较简单的,它的基本原理也是比较简单的,原理与我们在前面几节介绍的DynaArray类似,内部有一个数组elementData,一般会有一些预留的空间,有一个整数size记录实际的元素个数,如下所示:
1 | transient Object[] elementData; |
我们暂时可以忽略transient这个关键字。各种public方法内部操作的基本都是这个数组和这个整数,elementData会随着实际元素个数的增多而重新分配,而size则始终记录实际的元素个数。
Add方法
add方法的代码:
1 | public boolean add(E e) { |
它首先调用ensureCapacityInternal确保数组容量是够的,ensureCapacityInternal的代码是:
1 | private void ensureCapacityInternal(int minCapacity) { |
它先判断数组是不是空的,如果是空的,则首次至少要分配的大小为DEFAULT_CAPACITY
,DEFAULT_CAPACITY
的值为10,接下来调用ensureExplicitCapacity,代码为:
1 | private void ensureExplicitCapacity(int minCapacity) { |
modCount++是什么意思呢?modCount表示内部的修改次数,modCount++当然就是增加修改次数,为什么要记录修改次数呢,在迭代器里会用到,每次发生结构性变化的时候modCount都会增加,而每次迭代器操作的时候都会检查expectedModCount是否与modCount相同,这样就能检测出结构性变化。
如果需要的长度大于当前数组的长度,则调用grow方法。这段代码前面有个注释:overflow-conscious code,翻译一下,大意就是代码考虑了溢出这种情况,溢出是什么意思呢?我们解释下,假设a,b都是int,下面两行代码是不一样的:
1 | 1 if(a>b) |
为什么呢?考虑a=Integer.MAX_VALUE, b=Integer.MIN_VALUE
:
a>b为true
但由于溢出,a-b的结果为-1
反之,再考虑a=Integer.MIN_VALUE, b=Integer.MAX_VALUE
:
a>b为false
但由于溢出,a-b的结果为1。
不过,在a, b都为正数且数值没有那么大的情况下,一般也没有溢出问题,为便于理解,在后续的分析中,我们将忽略溢出问题。
接下来,看grow方法:
1 | private void grow(int minCapacity) { |
排除边缘情况,长度增长的主要代码为:
1 | int newCapacity = oldCapacity + (oldCapacity >> 1); |
右移一位相当于除2,所以,newCapacity相当于oldCapacity的1.5倍。
Remove方法
Remove方法的代码:
1 | public E remove(int index) { |
它也增加了modCount,然后计算要移动的元素个数,从index往后的元素都往前移动一位,实际调用System.arraycopy方法移动元素。elementData[--size] = null;
这行代码将size减一,同时将最后一个位置设为null,设为null后就不再引用原来对象,如果原来对象也不再被其他对象引用,就可以被垃圾回收。
RandomAccess
RandomAccess的定义为:
1 | public interface RandomAccess { |
没有定义任何代码。这有什么用呢?这种没有任何代码的接口在Java中被称之为标记接口,用于声明类的一种属性。
这里,实现了RandomAccess接口的类表示可以随机访问,可随机访问就是具备类似数组那样的特性,数据在内存是连续存放的,根据索引值就可以直接定位到具体的元素,访问效率很高。下节我们会介绍LinkedList,它就不能随机访问。
有没有声明RandomAccess有什么关系呢?主要用于一些通用的算法代码中,它可以根据这个声明而选择效率更高的实现。比如说,Collections类中有一个方法binarySearch,在List中进行二分查找,它的实现代码就根据list是否实现了RandomAccess而采用不同的实现机制,如下所示:
1 | public static <T> |
ArrayList特点分析
各种容器类和数据组织方式,之所以有各种不同的方式,是因为不同方式有不同特点,而不同特点有不同适用场合。考虑特点时,性能是其中一个很重要的部分,但性能不是一个简单的高低之分,对于一种数据结构,有的操作性能高,有的操作性能可能就比较低。
作为程序员,就是要理解每种数据结构的特点,根据场合的不同,选择不同的数据结构。
对于ArrayList,它的特点是:内部采用动态数组实现,这决定了:
- 可以随机访问,按照索引位置进行访问效率很高,用算法描述中的术语,效率是O(1),简单说就是可以一步到位。
- 除非数组已排序,否则按照内容查找元素效率比较低,具体是O(N),N为数组内容长度,也就是说,性能与数组长度成正比。
- 添加元素的效率还可以,重新分配和拷贝数组的开销被平摊了,具体来说,添加N个元素的效率为O(N)。
- 插入和删除元素的效率比较低,因为需要移动元素,具体为O(N)。