ArrayList源码摘要

本篇主要分析ArrayList源码。

java.util包(Java7)下的ArrayList是一个范型容器，它的继承关系见代码：

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

此文章主要围绕本人阅读ArrayList源码引出的问题来展开，有些问题涉及到上面列出的上层类和接口。

构造与初始化

private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}
public ArrayList() {
    this(10);
}
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

由这段代码可知ArrayList在没有传参的情况下会初始化一个大小为10的Object数组，在列出的第三个构造器中，if (elementData.getClass() != Object[].class)引人入胜，代码中给出了一条注释：c.toArray might (incorrectly) not return Object[] (see 6260652)，这是第一个要关注的问题。 在接口Collection代码中，有两个未实现的toArray方法，需要子类自己去实现。回到本代码中，具体执行哪一个toArray方法，取决于ArrayList构造器传入的参数，在ArrayList中，无参的实现是这样的：

1
2
3

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

继续查看util包中Arrays下的copyOf()代码：

@SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

因为在ArrayList中elementData是Object[]类型，所以其它的重载方法这里就不列出来了。这段代码中((Object)newType == (Object)Object[].class)也是第二个值得理解的问题。

先尝试理解第二个问题。

这个问题又可以分几个小问题：

为什么要将==左右两边强制转换为Object；
为什么要用三目运算符中的代码生成数组；
为什么不用三目运算符的表达式3取代三目运算符的部分；

1A:

这里举一个简单的例子，代码如下：

class Fruit {}
class Apple extends Fruit {}
class Jonathan extends Apple {}
class Orange extends Fruit {}
public Class Test07 {
  public static void main(String args[]) {
    Fruit a = new Apple();
    Orange b = new Orange();
    Jonathan c = new Jonathan();
    Fruit d = new Jonathan();
    System.out.println(b == c); //不可比较类型
    System.out.println(a == c); //false
    System.out.println((Fruit)b == c); //false
    System.out.println(c.getClass() == d.getClass()); //true
  }
}

这段代码说明“直系”类是可以比较的，例如a和c等；“旁系”不能比较（如b，c），编译不能通过。但如果转型为公共“祖先”（或者用父类引用指向要比较的对象），那么代码就可以运行（见(Fruit)b和c)。

所以在将==左右两边强制转换为Object，是为了让程序通过编译，但是即使进行了向上转型，==比较的是对象的内存地址，并不会破坏原本的比较逻辑。

2A:

Java不支持泛型数组，类似List<E>[] listarr = (ArrayList<E>[]）new ArrayList[10];是类型不安全的，但是可以通过编译，因为Java虽然不能创建泛型数组对象，但可以运用在声明和强制转换中。三目运算符包含的是创建“泛型数组”的代码。具体展开请见stackoverflow: How to create a generic array in Java?。“此时编译器是不可能证明这段程序是安全的，…但相关的数组保存在一个私有的域中，永远不会被返回到客户端，或者传递给任何其他方法。这个数组中保存的唯一元素，是传递给push方法的那些元素，它们的类型是E，因此未受检的转换不会有任何危害。”——《Effective Java中文版》(第二版) ArrayList代码中elementData是私有的域，传递给诸如add等方法的那些元素类型是E。

3A:

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {}这个方法服务于多处。多数情况下只需要new一个Object[]对象来实现“泛型数组”，毕竟在ArrayList内部elementData是Object[]，而反射创建对象的效率是比new创建对象要低。具体也可以参考stackoverflow: I have trouble understanding the source code of Arrays.copyOf。

在数组中，以下两种方式创建的对象具有不同的Class对象：

Object[] o1 = new Integer[]{1, 2, 3, 4, 5, };
Object[] o2 = {1, 2, 3, 4, 5, };
System.out.println(o1.getClass().getComponentType());
System.out.println(o2.getClass().getComponentType());

输出分别是class java.lang.Integer和class java.lang.Object。但o1[1] = “Hello World”;会通过编译，运行时报java.lang.ArrayStoreException。

再尝试理解第一个问题。

为什么在初始化中要添加if (elementData.getClass() != Object[].class)代码？因为虽然大部分的toArray操纵的是private的elementData，但在util包的Arrays下存在一个asList方法：

@SafeVarargs
@SuppressWarnings("varargs")
public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

而Arrays下toArrays的实现如下：

@Override
public Object[] toArray() {
    return a.clone();
}

这样只要Arrays.asList()传入的实参不是Object[]，就会导致elementData.getClass() 不等于Object[].class。

1 2	private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable {}

值得注意的是，Arrays内部实现了一个私有的静态内部类ArrayList，不是util包的ArrayList。这个bug具体详见JDK-6260652。

这里有一篇System.arraycopy的介绍Java的System.arraycopy()方法拷贝小数组时高效吗?。

迭代

ArrayList中另一个值得关注的地方就是迭代功能的实现。

ArrayList实现了Iterable接口：

1
2
3

public Iterator<E> iterator() {
    return new Itr();
}

Itr()的实现：

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
    public boolean hasNext() {
        return cursor != size;
    }
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

首先这段代码似乎违背了《Effective Java中文版》(第二版) 第24条：“你可以试着将注解放在整个方法上，但是在实践中千万不要这么做，而是应该声明一个局部变量来保存返回值，并注解其声明。”

cursor: 下一个要返回的元素的索引
lastRet: 最后一次已返回的元素的索引
expectedModCount: 预期修改次数的记录值

先看下面这行代码：

ArrayList<Integer> o4 = new ArrayList<Integer>();
o4.add(1);
o4.add(2);
for(Integer o: o4) {
  o4.remove(o);
}
System.out.println(o4.get(0));

啊哈哈，程序运行无误，没有产生java.util.ConcurrentModificationException异常，这可能是因为o4中只包含两个元素，没有触发fail-fast机制。

在正常的迭代过程中，不能让容器发生结构性变化，例如添加、删除等操作，于是设置变量expectedModCount和modCount(后者来自于AbstractList)。每次发生添加等操作的时候，modCount会增加，迭代时就通过比较expectedModCount和modCount来判断是否抛出异常。

Iterator<Integer> itr = list.iterator();
while(itr.hasNext()) {
  itr.next();
  itr.remove();
}
// System.out.println(o4.get(0));

如果代码中不添加itr.next();会报java.lang.IllegalStateException异常，如果取消注释会发生java.lang.IndexOutOfBoundsException异常。

小结

这篇笔记主要记录了本人读源码时注意到的几个点，后期如有新体会也会持续更新，若有错误也会即使更正。考虑到前文中有不少内容涉及到“泛型数组”，在这里不妨用《Effective Java中文版》(第二版)第25条的一段来收尾：

“当你得到泛型数组创建错误时，最好的解决办法通常是优先使用集合类型List<E>，而不是数组类型E[]。这样可能会损失一些性能或者简洁性，但是换回的却是更高的类型安全性和互用性。”