ArrayList源码要点浅析

这篇主要是扫一下java.util.ArrayList(有一些同名的类,注意包路径)的源码,整理一下要点,做一个小结。(本文会参看并贴出sun jdk1.7的一些源码,只是对“重点”部分的整理,觉得无聊可以直接去看类实现的全部源码)

0.  既然是ArrayList,就是用数组实现的List类,这点上源码上也可以印证。

private transient Object[] elementData;
private int size;

整个类主要就是围绕着这两个属性来实现的。一是注意数组是Object类型的数组,而且数组用transient关键字修饰,表示序列化的时候是不做处理的(ArrayList实现了java.io.Serializable接口),二是size是容器中对象的个数,而不是数组的长度,顺便看下整型单参的构造方法中一句实现。

this.elementData = new Object[initialCapacity];

其中默认构造方法初始化容量是10。由于数组列表有扩容问题,所以建议根据使用ArrayList的具体需求给出一个适合的容量,避免扩容带来的性能损失。

1. 向ArrayList末尾或特定位置添加新元素,以及数组的扩容

说说这个,毕竟add()方法几乎是必然用到的。分末尾和中间两种方式加入。

(1)先说默认无参的末尾加入:

public boolean add(E e) {
ensureCapacityInternal(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}

其中值得关注的是容量足够的保证。ensureCapacityInternal(size + 1)的调用一方面是自增了modCount,这个前面谈和迭代器相关修改一致性的文章说过,另外就是如果发现容量比现有的elementData.length大,做扩容。

private void grow(int minCapacity) {
   // overflow-conscious code
   int oldCapacity = elementData.length;
   int newCapacity = oldCapacity + (oldCapacity >> 1);
   if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
   if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
   // minCapacity is usually close to size, so this is a win:
   elementData = Arrays.copyOf(elementData, newCapacity);

}

重点在黑体的两句,一个是通常的扩容计算,即按原容量的1.5倍(原容量+=原容量/2),另外一个就是实际的数据拷贝,这个过程也进行了新数组对象的构建,旧的就等着GC就行了,当然这些是在Arrays类实现中完成。

T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);

这就是前面建议结合实际需要,在构造ArrayList对象时就传入合适长度的原因,因为不断扩容是很有成本的。

至于ArrayList的最大长度,一般考虑是Integer.MAX_VALUE – 8,极限也不过就是Integer.MAX_VALUE (2^31-1)了,不过考虑有OOM风险,不被建议。

(2)而对于中间插入(指定插入位置):

多了一步插入位置的检查,不能比size大,不能小于0。还要一个重点就是,数据的移动:

 System.arraycopy(elementData, index, elementData, index + 1,    size – index);

这也是有成本的,所以这类操作较多的,很自然地,会被建议用LinkedList。

2. 类似的,说下单个删除remove()

有两个版本,一个参数是int型的位置,另一个是Object版本。

第一个版本是先做index范围检查,并获取原值,准备返回用。然后数据拷贝迁移,把末值设置为null,并–size。

后一个版本,省了返回原值的过程,index需要对比,找到第一个equals的对象,所以也不用做index校验,因为是可靠的,后续流程和前面的版本一致。

3. 对于批量的addAll()、removeRange()等,和前面两个基本一致,只不过容量确认和数组数据拷贝从1个变成了多个。

4. 对于参数为Collection的removeAll()或者retainAll()

for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];

则在原数组循环比较并拷贝需要留下的数据,循环扫描后把结尾剩下的直接null掉。

5. 序列化和反序列化

先存放/读取数组总长度,而后循环存放/读取数据。

6. subList()方法和内部类SubList

这个稍微说下。ArrayList有个subList()方法和内部类SubList(java.util包也有一个SubList,实现极为类似)。需要注意的是这个内部类主要是维护了对parent的List的引用和偏移量,实际的操作都是在父List引用上进行的。

7. 拷贝

回头再看下类的头部:

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

List接口不说了,后面三个接口都不强行要求实现什么方法。除了随机访问和序列化,我们再稍微说下拷贝(克隆)。 clone()方法的实现实际上是用了Arrays.copyOf()方法对数组元素进行了拷贝,不过是“浅拷贝”,数组是不同的数组,但数组中的元素仍然是原来对象的引用。

不考虑并发情况,ArrayList和HashMap可能是容器类中使用率比较高的,因为ArrayList简单而易用。由于ArrayList的实现本质是数组,自然也具备着数组的一些特点,如容量固定需要扩容,还有中间数据元素的变化会需要数据拷贝迁移等,同时ArrayList也具备了优秀的随机访问性能。

相比之下LinkedList方法更丰富多样,使用双向链表实现。ArrayList的缺憾正能通过LinkedList得到弥补,中间元素的操作更为简洁。但随机访问性能比ArrayList要差,这在LinkedList中是不得不沿着链表循环查找访问的。

为了更好的使用ArrayList,熟知其实现还是有必要的。至于ArrayList其它的内容,包括(List)Iterator实现,逻辑都比较简单而且有点杂,这里就不赘述了。

此条目发表在 Java, Java语言, 开发, 计算机技术 分类目录,贴了 , , 标签。将固定链接加入收藏夹。

ArrayList源码要点浅析》有 2 条评论

  1. scugxl 说:

    博主 请教个 问题就是序列化/反序列化都需要调用 defaultWriteObject /defaultReadObject 这个是什么原因呢? 我看arraylist里面确实是如你所说实现的,参考了http://stackoverflow.com/questions/16239239/why-does-the-defaultwriteobject-function-have-to-be-called-first-when-writing-in 但是好像也没说清楚~。

    • 好久没搞Java了,我理解你的问题是这两个方法在java.io.Serializable的API文档中没有列出来详细说明,这个接口没有明确声明。我的理解这是Java在序列化和反序列化这个地方设计的时候的采用一种比较隐晦的方案,不强制实现readObject()和writeObject(),不强制使用defaultWriteObject/defaultReadObject,知道就好,没什么特别的原因。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>