Java 常用集合类 ArrayList

ArrayList 整体设计

ArrayList 是 List 中最常用的一个类，继承抽象父类 AbstractList。ArrayList 是一个数组队列，相比于 Java 数组，ArrayList 的容量可以动态增长。

ArrayList 采用数组 Object[] 作为数据存储结构。

属性和构造函数

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

// 元素存储
transient Object[] elementData;

// 当前大小
private int size;

// 创建一个初始容量为 initialCapacity 的 ArrayList
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);
    }
}

// 创建一个包含 collection 的 ArrayList
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

add 方法

ArrayList 的 get() 方法比较简单，根据索引返回返回数组指定位置的数据， 首先会检查数组是否越界。

ArrayList 的 add() 方法涉及到数组的扩容。

public boolean add(E e) {
    // 检查数组容量
    // 这一操作会修改 modCount
    ensureCapacityInternal(size + 1); 
    // 添加到数组中
    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) {
    // 修改 modCount
    modCount++;

    // 容量不足需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

ArrayList 也可以指定位置（index）添加元素

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

    // 检查数组容量（可能会执行扩容操作）
    ensureCapacityInternal(size + 1);  

    // 通过 arraycopy 将原位置以及之后的数据整体 向后 移动一位
    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)
        // 通过 arraycopy 将原位置以及之后的数据整体 向前 移动一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 数据向前移动一位后，数组的最后一位置为空
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

所以 ArrayList 在中间插入数据操作会比较影响效率，并且频繁的插入可能导致扩容的额外消耗，如果能够预估数据量的大小，建议尽量初始化时设置容量。

grow 方法

ArrayList 扩容逻辑：默认扩容原数组长度的一半，也就是新的数组大小是原来的 1.5 倍

计算公式：int newCapacity = oldCapacity + (oldCapacity >> 1);

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 计算新的容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 进行数组扩容（通过拷贝的方式）
    elementData = Arrays.copyOf(elementData, newCapacity);
}

clone 方法

ArrayList 实现了 Cloneable 接口，只是拷贝了这个 List 对象，而没有拷贝 List 中的元素，这意味着两个 List 持有的是同一组对象。

public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // 将当前 ArrayList 的全部元素拷贝到v中
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}