ArrayList 的构造器

ArrayList 无参构造器初始化时，默认大小是空数组，并不是大家常说的 10，10 是在第一次 add 的时候扩容的数组值。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * Shared empty array instance used for empty instances.
     */
    // 用于空实例的共享空数组实例
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 数组缓冲区，数组列表的元素被存储在其中
    // 空数组列表时 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    // 将在添加第一个元素时扩展为 DEFAULT_CAPACITY
    // 非私有的，以简化嵌套类访问
    transient Object[] elementData;
    /**
     * The size of the ArrayList (the number of elements it contains).
     */
    // ArrayList 的大小(它包含的元素数量)
    // 没有使用 volatile 修饰，非线程安全的
    private int size;
    // 构造一个具有指定初始容量的空 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);
        }
    }
    // 构造一个初始容量为 10 的 ArrayList  
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    // 构造一个包含指定元素的 ArrayList,集合 c 按照它的迭代器返回它们的顺序。  
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray 可能(不正确)不返回对象[]  
            if (elementData.getClass() != Object[].class)
                // 如果元素不是 Object[]，将其转换成 Object[]
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 给定集合 c 无值，则替换为空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    // 统计当前数组结构修改的次数 (是 AbstractList 中的属性)
    protected transient int modCount = 0;

构造一个包含指定元素的 ArrayList 时，构造器中有一个这样的注释 see 6260652，这是 Java 的一个 bug，意思是：当给定集合内的元素不是 Object 类型时，我们会转化成 Object 的类型。
一般情况下都不会触发此 bug，只有在下列场景下才会触发：
ArrayList 初始化之后（ArrayList 元素非 Object 类型），再次调用 toArray 方法，得到 Object 数组，并且往 Object 数组赋值时，才会触发此 bug，问题在 Java 9 中被解决，代码和原因如图：

@Test
public void test17() {
    List<String> list = Arrays.asList("hello", "world");
    Object[] objArray = list.toArray();
    System.out.println(objArray.getClass().getSimpleName());
    // 打印结果为：String[]
    objArray[0] = new Object();
    // 抛出了 java.lang.ArrayStoreException: java.lang.Object
}

ArrayList 的新增 & 扩容实现

新增就是往数组中添加元素，主要分成两步：

• 判断是否需要扩容，如果需要执行扩容操作
• 赋值操作

ArrayList 类中 add() 底层源码实现如下

public boolean add(E e) {
    // 确保数组大小足够，不够执行扩容，size 为当前数组的大小
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 直接赋值，线程不安全
    elementData[size++] = e;
    return true;
}
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将索引位置为 i 的后面的元素后移一个位置
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
// 如果传入的集合为 null，返回 false，否则返回 true
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    int numMoved = size - index;
    if (numMoved > 0)
        // 将索引位置为 i 的后面的元素后移 numNew 个位置
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    // 如果 index >= size，则在执行该方法时抛出 ArrayIndexOutOfBoundsException 异常
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

扩容的底层源码实现如下：

private void ensureCapacityInternal(int minCapacity) {
    // 如果初始化数组大小时，有给定初始值，以给定的大小为准，不走 if 逻辑
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 默认初始化大小第一次 add 时，执行此逻辑
        // minCapacity = 10;
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 确保容量达到 minCapacity（我们期望的最小容量）
    // 未达到则扩容
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    // 数组结构被修改次数 + 1
    modCount++;
    // 如果我们期望的最小容量 > 目前数组的长度，那么就扩容
    if (minCapacity - elementData.length > 0) {
        // 具体的扩容逻辑
        grow(minCapacity);
    }
}
// 要分配的数组的最大大小，有些虚拟机在数组中保留了一些 header words
// 尝试分配更大的数组可能导致 OutOfMemoryError，请求的数组大小超过虚拟机限制  
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容，并把现有数据拷贝到新的数组里面去
// 如果按原数组大小的1.5倍扩容后 < 我们的期望值，则按照我们的期望值扩容
// 如果按原数组大小的1.5倍扩容后 > 我们的期望值，则按照原数组大小的1.5倍扩容
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)
        // 如果扩容后的值 > jvm 所能分配的数组长度的最大值，执行此逻辑
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    // 如果 期望容量 > (Integer.MAX_VALUE - 8)，则扩容后的值将为 Integer.MAX_VALUE
    // 否则，扩容后的值将为 (Integer.MAX_VALUE - 8)
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

扩容的规则是：原来容量大小 + 原来容量大小的一半，直白来说，扩容后的大小是原来容量的 1.5 倍。
ArrayList 中的数组的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了。
新增时，并没有对值进行严格的校验，所以 ArrayList 是允许 null 值的。
从新增和扩容源码中，下面这点值得我们借鉴：

• 源码在扩容的时候，有数组大小溢出意识，就是说扩容后数组的大小下界不能小于 0，上界不能大于 Integer 的最大值，这种意识值得学习

扩容的本质
扩容是通过 Arrays.copyOf(elementData, newCapacity); 实现的，这行代码描述的本质是：数组之间的拷贝。
扩容是会先新建一个符合我们预期容量的新数组，然后把老数组的数据拷贝过去。
copyOf() 的底层代码实现如下：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    // 该方法是 native 的
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}
/**
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPos 目标数组中的起始位置
* @param length 要拷贝的数组长度
* 此方法是没有返回值的，通过 dest 的引用进行传值
*/
public static native void arraycopy(Object src, int srcPos,
                                    Object dest, int destPos,
                                    int length);

ArrayList 的删除

ArrayList 删除元素有很多种方式，比如根据数组索引删除、根据值删除或批量删除等，原理和思路都差不多。
根据数组索引删除 底层源码实现如下：

public E remove(int index) {
    // 该方法的唯一作用：如果 index >= size，抛出 IndexOutOfBoundsException
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    // numMoved 表示删除 index 位置的元素后，需要从 index 后移动多少个元素到前面去
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // clear to let GC do its work
    // 让 GC 完成它的清理工作
    elementData[--size] = null; 
    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++)
            // 根据 equals() 判断值是否相等，然后根据索引位置删除
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    // size = 0 或未找到要删除的值时，返回 false
    return false;
}
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;
}

批量删除 底层源码实现如下：

// 从 ArrayList 中删除指定集合中包含的所有元素  
public boolean removeAll(Collection<?> c) {
    // 保证集合 c 非空，为 null 时抛出 NullPointerException
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
// 从 ArrayList 中删除指定集合中不包含的所有元素  
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    // r为遍历索引 w为结果索引。类似于双指针，r 是快指针，w 是慢指针
    int r = 0, w = 0;
    boolean modified = false;
    try {
        // 把需要移除的数据都替换掉，不需要移除的数据前移
        for (; r < size; r++)
            // if条件成立时，保存 elementData[r]，不成立时不保存
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // 存在并发修改
        if (r != size) {
            // 如果存在并发删除，则 size - r 为负数
            // 负数，System.arraycopy 会抛出 IndexOutOfBoundsException 运行时异常
            // 如果存在并发添加，则将添加的元素追加到 w 索引后面
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
        }
        // 成功删除了元素，将后面空间置空
        if (w != size) {
            // clear to let GC do its work
            // 让 GC 完成它的清理工作  
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

ArrayList 的修改

public E set(int index, E element) {
    // 该方法的唯一作用：如果 index >= size，抛出 IndexOutOfBoundsException
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

ArrayList 的查询

contains() 的源码实现如下：

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

get() 的源码实现如下：

public E get(int index) {
    // 该方法的唯一作用：如果 index >= size，抛出 IndexOutOfBoundsException
    rangeCheck(index);
    return elementData(index);
}
E elementData(int index) {
    return (E) elementData[index];
}

ArrayList 的迭代器

如果要自己实现迭代器，实现 java.util.Iterator 接口就好了，ArrayList 也是这样做的。
Iterator 和 ListIterator 接口的底层源码实现如下：

public interface Iterator<E> {
    // 还有没有下一个值可以迭代，有返回 ture，无返回 false
    boolean hasNext();
    // 下一个可以迭代的值是多少
    E next();
    // 需要实现类重写实现该方法
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    // Java8 新增的遍历操作方法
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}
public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

ArrayList 的 Iterator() 源码实现如下：

public Iterator<E> iterator() {
    return new Itr();
}
// ListItr 继承该 Itr
private class Itr implements Iterator<E> {
    // 下一次调用 next() 时返回的元素的索引
    int cursor;
    // 最近一次调用 next() 返回的元素的索引，若没有调用过，则默认 -1
    // 删除场景：如果索引位置 lastRet 上的元素被删除，则 lastRet 重置为 -1
    // 新增场景：如果通过 listIterator() 的 add() 在索引位置 lastRet 上新增，
    // 则索引位置 lastRet 后的元素后移一个位置，且 lastRet 重置为 -1
    int lastRet = -1;
    // expectedModCount：迭代过程中期望版本号；modCount：目前最新版本号
    int expectedModCount = modCount;
    // 空参构造器
    Itr() {}
    public boolean hasNext() {
        return cursor != size;
    }
    public E next() {
        // 迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException
        checkForComodification();
        // 本次迭代过程中，元素的索引位置
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // 下一次迭代时，元素的位置，为下一次迭代做准备
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    public void remove() {
        // lastRet < 0，存在不同的情况
        // 情况1：还没有迭代过，即还没有执行过 next()
        // 情况2：已经 remove() 一次，lastRest 被置为 -1，防止重复删除
        if (lastRet < 0)
            throw new IllegalStateException();
        // 迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException 异常
        checkForComodification();
        try {
            ArrayList.this.remove(lastRet);
            // remove 后索引 lastRet 位置后的元素前移了，
            // 因此索引位置 lastRet 需要重新迭代 
            cursor = lastRet;
            lastRet = -1;
            // 删除元素时 modCount 的值已经发生变化
            // 在此赋值给 expectedModCount 这样下次迭代时，两者的值是一致的
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    @Override
    @SuppressWarnings("unchecked")
    // Java8 新增的迭代操作方法
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

ArrayList 的 listIterator() 源码实现如下：

// 可以实现从中间 / 尾部迭代
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}
// 双向迭代器
private class ListItr extends Itr implements ListIterator<E> {
    // index 为迭代的起始索引位置
    ListItr(int index) {
        super();
        cursor = index;
    }
    // 该类继承 Itr,hasNext()、next() 在 Itr 类中有实现
    public boolean hasPrevious() {
        return cursor != 0;
    }
    public int nextIndex() {
        return cursor;
    }
    public int previousIndex() {
        return cursor - 1;
    }
    @SuppressWarnings("unchecked")
    public E previous() {
        // 迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }
    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    public void add(E e) {
        checkForComodification();
        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

ArrayList 的其他方法

ArrayList.toArray() 的底层源码实现如下：

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
    // 如果 a 的空间不够，新拷贝一个数组返回
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

ArrayList 的常见问题

说一下你对 ArrayList 的了解

底层数据结构
ArrayList 的底层数据结构是一个 Object 类型的数组，add 的元素被存储在其中。

构造器相关
若使用默认构造器构造一个 ArrayList 时，这个数组为 null，此时并不会被初始化，只有当第一次 add 元素时才会执行初始化扩容操作，此时数组大小被初始化为 10。
若使用给定初始容量的构造器构造一个 ArrayList 时，就直接在构造器中 new 一个给定大小的 Object 类型的数组。
若要构造一个包含指定 Collection 集合中元素的 ArrayList 时，在构造器中获取指定集合的底层数组的副本，该 ArrayList 的底层数组指向该副本。

数组自动扩容
ArrayList 在每次执行 add 时，都会先执行 ensureCapacityInternal(size + 1); 确保数组有容量将要 add 的元素存储在底层数组【我们期望数组容量最小为 (size + 1)】，若当前数组大小 < 我们期望的数组容量时，执行 grow(minCapacity);，该方法中是真正的扩容逻辑。
如果将要扩容后的数组容量 > MAX_ARRAY_SIZE【jvm 所能分配的数组长度的最大值】的话，则用 期望的数组容量 和 MAX_ARRAY_SIZE 作比较，最终在 期望的数组容量、MAX_VALUE、Integer.MAX_VALUE 三者中取一个合适的值。