ArrayList源码分析

一 成员变量解析

/**
 * 默认初始化容量.
*/
private static final int DEFAULT_CAPACITY = 10;


/**
 * ArrayList存储数据的数组.
 * ArrayList的容量就是该数组的长度
 * 如果elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * 那么当地一个元素加进来时，elementData 的长度会扩充为DEFAULT_CAPACITY.
*/
transient Object[] elementData;

/**
 * 数组的容量
*/
private int size;

/**
 * 数组可申请的最大长度
 * 有些虚拟机需要在数组中保存头部信息
 * 申请长度超出范围会引起
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

二 关键方法解析

1 添加元素

public boolean add(E e) {
    // 增加ArrayList的容量（扩容，后边详述）
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}

2 扩容

ArrayList默认大小是10，如果底层数组大小不够了怎么办，答案是进行扩容，这就是为何说ArrayList的底层是基于动态数组实现的原因。

private void ensureCapacityInternal(int minCapacity) {
    /*
     * 如果elementData还是默认的空数组，
     * 那么会设置elementData的最小容量，
     * 最小容量为DEFAULT_CAPACITY和minCapacity的最大值
    */
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 如果最小容量大于elementData长度则扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 设置newCapacity 为oldCapacity 的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果newCapacity小于minCapacity ，则设newCapacity=minCapacity 
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果newCapacity超出数组可申请的最大长度则重新设置newCapacity
    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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

可以看到在每次扩容时新的容量大小是旧容量大小的1.5倍，最后会调用Arrays的copyOf方法将旧数组的内容复制到新数组中。

3 获取元素

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

/**
 * 检查index是否越界，该方法并不检查index是否为负数
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4 替换特定位置的元素

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

5 插入元素

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

看到在插入元素的时候，System.arraycopy方法将array中从index起始的子集复制到从index+1开始的地方，然后再index出加入新插入的元素。

6 删除元素

删除元素有两种方式：

1. 根据index删除和根据

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

2. 根据元素o删除，这会删除arrayList中第一个和o匹配的元素

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

三 ArrayList的优缺点

从上面的几个过程总结一下ArrayList的优缺点。ArrayList的优点如下：

1. ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快
2. ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已

不过ArrayList的缺点也十分明显：

1. 删除元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能
2. 插入元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能
   因此，ArrayList比较适合顺序添加、随机访问的场景。

四 ArrayList和Vector的区别

1. Vector是线程安全的，ArrayList是线程非安全的
2. Vector可以指定增长因子，如果该增长因子指定了，那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子；如果不指定增长因子，那么就给原数组大小*2，源代码是这样的：

int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

五 为什么ArrayList的elementData是用transient修饰的？

不知道大家有没有想过，为什么elementData是使用transient修饰的呢？关于这个问题，说说我的看法。我们看一下ArrayList的定义：

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

看到ArrayList实现了Serializable接口，这意味着ArrayList是可以被序列化的，用transient修饰elementData意味着我不希望elementData数组被序列化。这是为什么？因为序列化ArrayList的时候，ArrayList里面的elementData未必是满的，比方说elementData有10的大小，但是我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因此ArrayList中重写了writeObject方法：

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

每次序列化的时候调用这个方法，先调用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData不去序列化它，然后遍历elementData，只序列化那些有的元素，这样：

1. 加快了序列化的速度
2. 减小了序列化之后的文件大小