ArrayList：读源码笔记

目录

ArrayList 实现/继承：

ArrayList

List 接口

• 定义
  线性集合的抽象，定义了获取容量size()、是否为空isEmpty()、是否包含某元素contains(Object o)、添加add() 和 remove() 等方法。
• 特点
  • 有序：存储和取出的按照顺序；
  • 有索引：包含一些带索引的方法；
  • 允许存储重复元素。

AbstractList 抽象类

• 定义
  线性表的进一步抽象，List 接口的骨干实现。从而最大限度地减少了实现由“随机访问”数据存储（如数组）支持的接口所需的工作。

数据结构 new ArrayList()

• 数组
  归根结底，ArrayList 维护的是一个数组。

transient Object[] elementData;

因为是 Object 数组，所以可以放 null。

• 容量
  初始默认容量是 10：

private static final int DEFAULT_CAPACITY = 10;

最大容量是 int 最大值-8（Integer.MAX_VALUE - 8），一些虚拟机需要在数组前加个 header 标签，所以减去 8 。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• 初始容器

// 创建一个容量为 0 的数组，使用该空数组创建
private static final Object[] EMPTY_ELEMENTDATA = {};
// 不传入参数，使用这样的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

不传入参数创建，默认最小容量为 10，第一次扩容后容量为 15（10+10/2）。
传入 0 长度，扩容时不会有那么大的初始容量。比如最小容量为 2 时，再次扩容容量为 3(2+2/1)。

添加元素 ArrayList#add()

添加单个元素

public boolean add(E e) {
    // 确认容量，不够就扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

扩容环节先跳过，扩容之后把实际元素个数+1，该位置放上新元素即可。

添加单个元素到指定位置

public void add(int index, E element) {
    // 1.确认下标不越界
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    // 2.确认容量，不够就扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 3.复制数据
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 4.在腾出的位置放置新元素
    elementData[index] = element;
    size++;
}

• 要插入的位置必须合法，大于 0、小于当前数组元素个数。
• System.arraycopy()：复制第一个参数的数组，从第二个参数开始复制；复制到第三个参数的数组、从第四个参数的位置开始放置，最后一个参数为复制的个数。

System.arraycopy()

添加一堆元素

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // 确定容量，不够扩容
    // 复制要添加的数组，从 0 开始。复制到当前数组，从尾部开始，直接到最后
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

从某位置添加一堆元素

public boolean addAll(int index, Collection<? extends E> c) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    
    int numMoved = size - index;
    if (numMoved > 0)
        // 如果要放置在中间的位置，将中间往后的数据集体挪一下
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    // 复制完腾出地方了，需要复制进来新元素
    // 如果不放在中间，只可能是放在尾部（因为有下标越界限制），直接复制
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

ArrayList 扩容机制 ArrayList#grow()

添加元素前会调用下面的方法确认容量，传入的参数是最小容量（如果是加入单个元素，就是 size++、多个元素是就是新增元素的个数 object[].length）：

ArrayList # ensureCapacityInternal

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

跟 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 进行对比，就是为了确认是传入空参数初始化的还是传入 0 创建的 ArrayList。

private void ensureExplicitCapacity(int minCapacity) {
    // 扩容前就添加了 modeCount，容量即将发生变化，这时不能正常遍历了
    modCount++;

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

private void grow(int minCapacity) {
    // 拿到旧的数组长度，注意这里并不是拿的元素个数 size
    int oldCapacity = elementData.length;
    // 新容量为旧的+旧的x2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 判断容量是否超限，如果非要大于最大容量，那就给你 Integer 的最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制数据到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

要注意的有以下几点：

• 扩容条件为最小容量大于当前数组长度（不一定是元素个数）。
  最小容量的生成：单个元素插入为元素个数 size加 1，多个为 元素个数+新加入元素个数。
• 扩容一次容量：旧数组容量+旧数组容量/2，右移 1 位表示除以 2。
• Arrays.copyOf 调用的是 native 的 System.arraycopy 方法，该方法有以下特点：
  • 浅复制：复制内存地址的引用到新数组，不存在的再创建；
  • 效率较高：直接操作内存地址，比遍历寻址效率要高；
  • 线程不安全。

外部方法 ensureCapacity()：

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

• 该方法可以传入最小容量，手动指定 ArrayList 容量。提前扩容，避免添加数据时再扩容影响性能。

ArrayList 移除元素 ArrayList#remove() clear()

移除单个元素

根据下标移除：

public E remove(int index) {
    if (index >= size) // 下标检查
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    // 找到旧的值，删除成功的返回
    E oldValue = (E) elementData[index];
    // 需要移动的元素数量：元素个数-下标-1
    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;
}

• int numMoved = size - index - 1：计算需要移动的元素的个数。
  假设数组元素个数为 3（下标：[0,1,2]），删除下标为 0 的元素。那么需要移动的元素个数为 3-0-1=2 个，也就是复制下标为 1和2 的元素到新数组。到后面会将新数组的最后最后一位置空，元素个数减 1。
  删除下标为 2 的元素，也就是最后一个元素。需要移动的元素个数为 3-2-1=0 个，也就是不需要复制数组，直接将元素个数-1、最后一个元素置空。

移除 Object：

public boolean remove(Object o) {
    // 分为移除 null 和不为 null 的情况
    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;
}

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
}

• 主要处理 null 值的移除，遍历找到下标调用 fastRemove() 方法移除；
• 这样看来根据下标移除的效率要高于 Object 移除。

移除或保留多个元素

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;// 两个指针，一个用于遍历，另一个用于记录要处理的数据
    boolean modified = false;
    try {
        for (; r < size; r++)
            // 快指针正常走，符合条件时，慢指针也跟着走
            // 不符合条件，快指针正常走，慢指针停留。
            // 下次遍历会把慢指针停留的位置替换快指针的值，
            // 相当于这个位置的数据被数组后面的值替换
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 发生了异常，遍历中断。直接把快指针后面的数据，复制到慢指针后面
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        // 如果 w==size 说明全部符合条件，慢指针经历了一整个循环，无需处理
        // 慢指针 w 前面的值该替换的都替换了，后面的值都没用了
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

• 重要的在于理解两个指针，一快一慢：快的就是遍历，慢的会在不符合条件暂停。符合条件会替换慢指针位置上的值，保证慢指针之前的值都是有用的。

清空

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

• 将所有元素置为 null，size 归零。

是否包含某元素 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;
}

• indexOf()方法默认返回 -1，遍历找到元素后返回下标。
• lastIndexOf() 就是倒着遍历，找到首个数据返回。

转换为数组 ArrayList#toArray()

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

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);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

• 主要还是利用 System.arraycopy 方法对数据进行复制。

迭代器 ArrayList#toArray()

public Iterator<E> iterator() {
        return new Itr();
}

private class Itr implements Iterator<E> {
    // Android-changed: 添加 limit 参数
    protected int limit = ArrayList.this.size;
    
    int cursor;       // 1. index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor < limit;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        // 2.modCount 与希望的不同，说明数组可能被修改，抛出异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        int i = cursor;
        if (i >= limit)
            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() {
        if (lastRet < 0)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
            limit--;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    ...
}

• 主要就是使用一个参数 cursor 记录当前遍历到的数组位置；
• 不支持在迭代的过程中修改数据（强），否则抛出 ConcurrentModificationException 异常；
• 普通遍历时 remove() 会下标异常，而迭代器不会。就是因为 cursor 和lastRet 是可变的，hasNext() 又保证了下标的安全性。

同步

ArrayList 线程不安全。

• 同步下进行数据修改，可能造成数据丢失；
• 使用迭代器遍历时，可能会抛出 ConcurrentModificationException 异常，因为 modCount 与遍历开始不一致。

想要实现同步，可以在外部加锁或者使用 Collections.synchronizedList()。

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}

synchronizedList() 方法的原理就是内部维护一个 Object，在 add() remove() 等方法使用时给该 Object 加锁。

SynchronizedList#add()

final Object mutex; 
public void add(int index, E element) {
    synchronized (mutex) {list.add(index, element);}
}