ArrayList分析

ArrayList 实现于 List、RandomAccess 接口。可以插入空数据，也支持随机访问。

ArrayList 相当于动态数据，其中最重要的两个属性分别是: elementData 数组，以及 size 大小。

成员变量

/** 默认的初始化容量 */
private static final int DEFAULT_CAPACITY = 10;
/** 空 ArrayList 实例共享的空数组实例 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** 默认大小的空 ArrayList 实例共享的空数组实例，和 EMPTY_ELEMENTDATA 区分开 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** 
 * 存储arraylist元素的数组缓冲区。
 * 任何使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 实例，
 * 在首次添加元素时容量扩展到默认容量 DEFAULT_CAPACITY 。
 */
transient Object[] elementData; // 非私有以简化嵌套类访问
/** ArrayList包含的元素个数 */
private int size;

构造函数

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) { // 新建 initialCapacity 大小的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) { // 采用 EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() { // 采用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，和 EMPTY_ELEMENTDATA 区分开来
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

c.toArray might (incorrectly) not return Object[] (see 6260652)

查看 ArrayList(Collection<? extends E> c) 构造函数时，有个注释 c.toArray might (incorrectly) not return Object[] (see 6260652)，具体什么意思呢？先看个示例：

1 2	List<Object> list = new ArrayList<Object>(Arrays.asList("foo", "bar")); list.set(0, new Object());

如果 ArrayList 的构造函数中没有类型检查的代码 elementData.getClass() != Object[].class，会导致其elementData 的实际类型是String[]，而不是 Object[]，所以当你将其中一个元素更换为 Object 元素时会报错，你可以试下如下代码，肯定会报 ArrayStoreException 的错误。

1
2
3

Object[] arr = new String[]{"a","b"};
arr[0]=new Object(); // Causes ArrayStoreException,
                     // because you cannot put arbitrary Object into String[]

主要问题出在 Arrays.asList 上面，Arrays.asList 返回的 ArrayList 实际上是内部类 ArrayList ，并不是我们经常使用的 ArrayList。

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

内部类 ArrayList 的 toArray() 使用的是 clone 方法，而我们经常使用的 ArrayList 的 toArray() 使用的是 Arrays.copyOf() 方法，具体差别如下：

Object[] arr = new ArrayList<Object>(Arrays.asList("foo", "bar")).toArray();
System.out.println(arr.getClass()); // class [Ljava.lang.Object; Object数组
Object[] arr1 = Arrays.asList("foo", "bar").toArray();
System.out.println(arr1.getClass()); // class [Ljava.lang.String; String 数组，操作不当会引起 ArrayStoreException

关于 Arrays.asList 的一个坑使用Java时的一些坑

add

在调用 add() 方法的时候：

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

首先进行扩容校验。
将插入的值放到尾部，并将 size + 1 。

如果是调用 add(index,e) 在指定位置添加的话：

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //复制，向后移动
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

也是首先扩容校验。
接着对数据进行复制，目的是把 index 位置空出来放本次插入的数据，并将后面的数据向后移动一个位置。

其实扩容最终调用的代码:

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);
}

也是一个数组复制的过程。

由此可见 ArrayList 的主要消耗是数组扩容以及在指定位置添加数据，在日常使用时最好是指定大小，尽量减少扩容。更要减少在指定位置插入数据的操作。

序列化

由于 ArrayList 是基于动态数组实现的，所以并不是所有的空间都被使用。因此使用了 transient 修饰，可以防止被自动序列化。

1	transient Object[] elementData;

因此 ArrayList 自定义了序列化与反序列化：

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    //只序列化了被使用的数据
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

从实现中可以看出 ArrayList 只序列化了被使用的数据。

ArrayList VS Vector

Vector 也是实现于 List 接口，底层数据结构和 ArrayList 类似，也是一个动态数组存放数据。不过是在 add() 方法的时候使用 synchronized 进行同步写数据，但是开销较大，所以 Vector 是一个同步容器并不是一个并发容器。

以下是 add() 方法：

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

以及指定位置插入数据:

public void add(int index, E element) {
    insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}