引：大家在集合框架中用的最多一定是ArrayList吧，今天我们就来一探究竟！

概览

ArrayList是基于可变数组实现了，允许包括 null 在内的所有元素。

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。

在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

注意： 此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问。

此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：在创建迭代器之后，除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出 ConcurrentModificationException。

ArrayList从类 java.util.AbstractList 继承了字段 modCount，在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。

构造

// 默认数组初始大小为10
private static final int DEFAULT_CAPACITY = 10;

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 返回空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

增

// 新增元素
public boolean add(E e) {
    // 确保容量足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // 如果是默认创建的数组，则和容量默认值比较
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 确保容量足够
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // 修改操作加1
    modCount++;
    // overflow-conscious code
    // 如果需要的容量比数组长度大，则进行扩容
    if (minCapacity - elementData.length > 0) grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    // 新容量将使原来的1.5倍
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 1.5倍还不够的话，就将容量设置为需要的大小
    if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
    // 如果新容量比最大的数组容量（Integer.MAX_VALUE - 8;）还要大，则创建更大的容量（Integer.MAX_VALUE）
    if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // Arrays.copyOf() 是把原数组整个复制到新数组，这个代价很高
    // 因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数
    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;
}

删

删除需要将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，所以ArrayList 删除元素的代价是非常高的。

public E remove(int index) {
    // 验证index是否超出size大小
    rangeCheck(index);

    modCount++;
    // 拿到值
    E oldValue = elementData(index);
    // 统计要移动的位数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 调用系统方法开始拷贝
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 即时放开引用，等待GC
    elementData[--size] = null; // clear to let GC do its work
    // 返回被删除的元素
    return oldValue;
}

改

public E set(int index, E element) {
    // 验证index是否超出size大小
    rangeCheck(index);
    // 拿出原值
    E oldValue = elementData(index);
    // 设置新值
    elementData[index] = element;
    // 返回被替换的值
    return oldValue;
}

查

public E get(int index) {
    // 验证index是否超出size大小
    rangeCheck(index);
    return elementData(index);
}

E elementData(int index) {
    // 拿出值
    return (E) elementData[index];
}

序列化

ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。

// 保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化
transient Object[] elementData;

// 序列化
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]);
    }
    // 比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。
    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();
        }
    }
}

雨过，云过

JDK源码分析——ArrayList

概览

构造

增

删

改

查

序列化