注释翻译

• ArrayList是实现List接口的可变大小数组实现。它允许存储所有元素，包括null。与实现了Vector类似，但不提供同步功能。

• ArrayList支持所有可选的列表操作，并提供了一些方法来操作内部用于存储列表的数组大小。其中，size、isEmpty、get、set、iterator和listIterator等操作都在常数时间内运行。而add操作在摊销的常数时间内运行，即添加n个元素的时间复杂度为O(n)。其他操作的时间复杂度为线性时间，具体而言是相对于列表大小的线性时间。ArrayList的常数因子相对于LinkedList实现较低。

• 每个ArrayList实例都有一个容量。容量是用于存储列表元素的数组大小，它始终至少与列表大小一样大。当向ArrayList中添加元素时，其容量会自动增长。容量增长策略的细节没有明确定义，只知道添加一个元素的摊销时间代价是常数的。

• 应用程序可以在添加大量元素之前，通过使用ensureCapacity方法增加ArrayList实例的容量，这样可以减少增量式的重新分配操作。

• 需要注意的是，ArrayList的实现不是线程安全的。如果多个线程同时访问同一个ArrayList实例，并且至少有一个线程对列表进行结构上的修改，那么必须对列表进行外部同步。结构上的修改包括添加或删除一个或多个元素，或者显式调整后备数组的大小；而仅仅设置元素的值不属于结构上的修改。为了实现线程安全，通常可以在一个自然封装了列表的对象上进行同步。

• 如果没有这样的对象可用，可以使用Collections.synchronizedList方法来”包装”列表，使其变为线程安全的。最好在创建列表时进行这样的操作，以防止意外地无序访问列表。

  List list = Collections.synchronizedList(new ArrayList(…));

• ArrayList的迭代器是快速失败（fail-fast）的。如果在迭代器创建后的任何时候，除了通过迭代器自身的remove或add方法之外，以任何方式对列表进行了结构上的修改，迭代器都会抛出ConcurrentModificationException异常。这样，在面对并发修改时，迭代器能够迅速且干净地失败，而不是在未来的某个不确定的时间里冒着任意、不确定的行为风险。

类签名

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{}

基本属性

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

private static final Object[] EMPTY_ELEMENTDATA = {};   // 空的数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData; // non-private to simplify nested class access  真正存放数据的

private int size;

源码

构造函数

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;       // 初始化一个空数组
    }

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {          // 初始化一个传入容量大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {        // 初始化容量小于0 ？ 笨蛋,其实这里有时候不是有意传入负数，比如传入Integer.MAX_VALUE + 1 那就是负数了啊！！！
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    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;
        }
    }

扩容方法grow

扩容是一个私有方法。

// 这里是扩容的入口
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) { // 如果修改后的数组容量大于当前的数组长度那么就需要调用grow进行扩容
        modCount++;

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

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity  minCapacity:需要的最小容量
     */
    private void grow(int minCapacity) {    // 扩容1.5倍
        // overflow-conscious code
        int oldCapacity = elementData.length;   // 旧容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);     // 新容量 = 旧容量+旧容量大小/2
        if (newCapacity - minCapacity < 0)      // 如果新容量 < 需要的最小容量
            newCapacity = minCapacity;          // 取一个相对大的,(不能让他容量不够啊）
        if (newCapacity - MAX_ARRAY_SIZE > 0)   // 边界判断
            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最大值
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

add & addAll

add方法没有什么可讲的，
有一点提一下

i++ & ++i

• i++ 先赋值在运算,例如 a=i++,先赋值a=i,后运算i=i+1,所以结果是a=1
  • ++i 先运算在赋值,例如 a=++i,先运算i=i+1,后赋值a=i,所以结果是a=2

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

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

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

addAll

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;                              // numNew 新添加的
        ensureCapacityInternal(size + numNew);  // Increments modCount  看看是否满足最小容量需求，不满足就扩容

        int numMoved = size - index;                      // 需要复制到长度， [2,3,4,5,6,7,8] 在index为1的3位置插入【9,8,7】,size-index=7-1 = 6
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,   // 上面例子： [2,3,4,5,6,7,8,0,0,0]=>[2,  (3,4,5),  3,4,5,6,7,8]
                             numMoved);     // 相比这块代码你得想一会吧，其实简单，需要复制两次，第一次，先把原土著元素占坑位的移到后面去，再把新进来的移进来

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

remove & removeIf

    public E remove(int index) {
        rangeCheck(index);

        modCount++;                     // 涉及数量变更，就要改了！！
        E oldValue = elementData(index); // 先把要删除的元素捞出来在旁边沥干，晾着

        int numMoved = size - index - 1;    // 要拷贝数组的长度 [2,3,4,5,6,7,8] remove index为2的元素4，size=7,size-index-1=7-2-1=4,
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, // 从index加一位置开始，越过index那个元素进行拷贝，就是玩，气不气人！
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work  把尾元素置为空，因为不是整体前移了吗，看写的多好，一个元素也要gc，!!!

        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])) { // 这里为什么分开写，因为：null没有.equals哦， 也不能全用==， 因为Integer有缓存哦
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

fastRemove

    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
    }

removeIf

    public boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        // figure out which elements are to be removed
        // any exception thrown from the filter predicate at this stage
        // will leave the collection unmodified
        int removeCount = 0;
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

        // shift surviving elements left over the spaces left by removed elements
        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
            final int newSize = size - removeCount;             // 剩下的大小
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { // i,j分别是两个指针遍历原数组和 removeSet
                i = removeSet.nextClearBit(i);  // [0,1,2,3,4,5] 移除【3,4】index=(2,3), removeSet{3,4}, i和j为1,2的时候下面的复制语句都正常，是一样的，当j为3的时候，i就不一样了，变成5了:elementData[3] = elementData[5]
                elementData[j] = elementData[i];        // 使用 removeSet.nextClearBit(i) 更新 i 的值。这个方法从索引 i 开始在 removeSet 中查找下一个为0的位。这个位置表示剩余元素的新位置。
            }
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;  // Let gc do its work    后面不需要的元素置空
            }
            this.size = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }

retain & remove

    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false); // 和retain是相反的，retain求交集，remove保留当前不在c中的元素
    }

    public boolean retainAll(Collection<?> c) { // 求两个集合的交集
        Objects.requireNonNull(c);  // 为空检查
        return batchRemove(c, true); // 批量删除，删除不存在包含Ｃ的元素, 用了contains，加单层for
    }

get

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
    E elementData(int index) {
        return (E) elementData[index];
    }

set

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }