源码分析之 —— ArrayList

ArrayList

描述

List接口的可调整大小的数组实现。实现所有可选的 List 操作，并允许包括 null 的所有元素。除了实现 List 接口之外，此类还提供一些方法来操纵内部用于存储列表的数组的大小。（此类与Vector大致等效 ，但它是不同步的。）

size, isEmpty, get, set, iterator, 和 listIterator 在 O(1) 时间内运行。add操作运行摊销恒定时间，添加N元素需要O(n)的时间。其他操作均以线性时间运行（大致而言）。

每个ArrayList实例都有一个容量。容量是用于在列表中存储元素的数组的大小。它总是至少与列表大小一样大。随着元素添加到ArrayList中，其容量会自动增长。除了添加元素具有固定的摊销时间成本外，没有指定增长策略的详细信息。

应用程序可以使用ensureCapacity 操作在添加大量元素之前增加ArrayList实例的容量。这可以减少增量重新分配的数量。

请注意，ArrayList是线程不安全的。 如果多个线程同时访问ArrayList实例，并且至少有一个线程在做是修改操作，则 必须在外部进行同步。（修改是添加或删除一个或多个元素，或显式调整后备数组的大小的任何操作；仅设置元素的值不是修改。）通常通过在自然封装了对象的某个对象上进行同步来实现。清单。如果不存在这样的对象，则应使用Collections.synchronizedList 方法“包装”列表 。最好在创建时完成此操作，以防止意外的不同步访问列表：

List list = Collections.synchronizedList（new ArrayList（...））;

此类iterator和 listIterator方法返回的迭代器是快速失败的：如果在创建迭代器之后的任何时间对列表进行结构修改，则除了通过迭代器自己的remove或 add方法外，迭代器都将抛出 ConcurrentModificationException。因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来的不确定时间内冒任意，不确定的行为的风险。

注意，迭代器的快速失败行为无法得到保证，因为通常来说，在存在不同步的并发修改的情况下，不可能做出任何严格的保证。快速失败的迭代器会ConcurrentModificationException尽力而为。因此，编写依赖于此异常的程序的正确性是错误的： 迭代器的快速失败行为应仅用于检测错误。

源码细节

变量

/** 序列化id */
private static final long serialVersionUID = 8683452581122892189L;

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

/**
 * 指定容量为０或Collection为０的时候 <code>elementData</code> 的值
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 与 EMPTY_ELEMENTDATA的区别在于默认不指定容量大小的时候
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * ArrayList存储的数据，不可序列化，ArrayList的容量就是这个数组buffer的大小
 */
transient Object[] elementData; 
/**
 * ArrayList的实际大小
 */
private int size;

构造器

/**
 * 指定容量
 * - 大于0：创建对应大小的数组
 * - 等于0：使用空数组
 */
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 ArrayList() {
    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;
    }
}

方法

初始容量为 10

若数组长度小于要扩容的最小值：

• 默认扩容 1/2

• 如果还不够就扩容到 最小扩容值

• 若扩容后的大小超出设置的数组最大容量（Integer.MAX_VALUE - 8）

  • 如果 要扩容的最小值 溢出，抛出异常

  • 如果 要扩容的最小值 小于最大容量值，就使用最大容量值作为扩容后的大小

  • 如果大于，使用 Interger.MAX_VALUE 作为扩容后的大小

trimToSize

/**
 * 修建当前容量为实际大小
 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                : Arrays.copyOf(elementData, size);
    }
}

get

/**
 * 获取下标所在的元素
 */
public E get(int index) {
    // 范围检查，index无效会抛出异常
    rangeCheck(index);

    return elementData(index);
}

set

/**
 * 设置
 */
public E set(int index, E element) {
    // 范围检查+1
    rangeCheck(index);
// 获取旧值
    E oldValue = elementData(index);
    // 设置新值，返回旧值
    elementData[index] = element;
    return oldValue;
}

add

/**
 * 添加元素
 */
public boolean add(E e) {
    // 确认容量，进行扩容策略处理
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // calculateCapacity 计算最小容量＝minCapacity，若 elementData 为默认的空数组，返回最小容量和初始大小的最大值
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 如果最小容量大于当前数组的大小，扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 数组分配的最大值
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 扩容策略
 * @param minCapacity 扩容的最小容量
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新容量为原来的 3/2，扩容 1/2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        // 如果还不够，设置为最小容量的值
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 如果新容量超出规定的最大值（Integer.MAX_VALUE - 8）
        // 若最小容量也大于规定的最大值，就扩容到 Integer.MAX_VALUE
        // 否则就扩容到规定的最大值
        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;
}

add(int index, E element)

public void add(int index, E element) {
    // 检查下标是否合理
    rangeCheckForAdd(index);
    // 容量操作
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // index - size 区域后移
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 设置值
    elementData[index] = element;
    size++;
}

remove

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);
    // 删除元素
    // 容量-1
    elementData[--size] = null; // clear to let GC do its work

    // 返回旧值
    return oldValue;
}

/**
 * 移除遇到的第一个元素 返回是否移除成功
 */
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;
}

/*
 * 和普通的remove区别只在于没有进行范围检查和旧值获取
 */
private void fastRemove(int index) {
    modCount++;
    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
}

关于 modCount

上面的源码中我们可以看到 modCount++ 出现了多次。

源码的doc文档是这样描述的：

modCount 是结构修改的次数（结构修改参考描述中的说明），这个字段用于 iterator、listIterator 方法所返回的 iterator 实现中：

在 next、remove、previous、set、add 操作中，如果值得改变不是所预期的，意味着多个线程同时修改了 List，这样就会抛出异常：ConcurrentModificationException 。这也是所说的快速失败机制。