总结

总结放前面防止太长不看：

1. ArrayList内部是用数组实现的。
2. 如果使用无参构造函数建立ArrayList，在添加第一个元素的时候会分配10个元素的空间。
3. ArrayList的扩容是以1.5倍为基准的。
4. ArrayList是线程不安全的，有fail-fast机制作改动保障。

层次图

ArrayList的Hierarchy：

先来看看List接口：

List接口

List代表有序集合，元素可以重复。

List家族一览：

默认实现方法：

default void replaceAll(UnaryOperator operator);

以指定的方法替换List中的所有元素，UnaryOperator是一个函数式接口，输入一个类型对象，返回一个同类型对象。

default void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final ListIterator<E> li = this.listIterator();
    while (li.hasNext()) {
        li.set(operator.apply(li.next()));
    }
}

示例：

List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(3);
list.add(5);
list.replaceAll(a->a+1); //list = [2,4,6]

default void sort(Comparator<? super E> c);

根据排序方法排序。还是先转为了Array再使用Arrays的sort方法进行排序。

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

AbstractList接口

AbstractList接口继承自AbstractCollection，为什么要提它呢，因为里面有个重要的字段modCount，用于迭代器遍历元素时检查列表中的元素是否发生结构性变化。

参考下面“重要的内部类”中迭代器里next方法的实现。

重要的字段

transient Object[] elementData;

ArrayList的元素存储在这个数组中。

private int size;

记录空间大小。

重要的内部类

Itr实现了迭代器Iterator，ListItr实现了集合迭代器ListIterator

两者的介绍： 谈谈java中的Iterator

next的实现：

public E next() {
    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];
}jav

其中的checkForComodification()：

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

modCount在ArrayList每次add或者remove它的值都会加1。在初始化迭代器的时候，令expectedModCount = modCount，在迭代器迭代的过程中，如果modCount被改变了，就会造成expectedModCount不等于modCount，抛出ConcurrentModificationException警告。

比如下面这段程序就会抛出警告：

为什么在迭代器循环的时候不让使用list.remove修改元素呢？

有多线程下被影响的考虑，更重要的是，强制了在迭代器迭代的时候只能使用iterator.remove移除元素.

比如上面这段程序应该改成：

构造方法

已知ArrayList的元素是存放于一个数组中，那么在初始化一个ArrayList对象的时候会分配一个多大的数组？

先看两个构造方法：

public ArrayList() {    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

其中常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

使用一个初始容量初始化ArrayList。
如果传入的参数大于0，则分配一个这么大的数组。
注意到如果这里的initialCapacity等于0，令其等于常量EMPTY_ELEMENTDATA也是一个空数组。

那为什么要区分EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA呢？

因为他们是两个不同对象的引用，ArrayList通过这个区分当前对象是用无参构造方法创建的还是由ArrayList(0)这样一个构造方法创建的

在后文“重要的内部方法”中的calculateCapacity方法，当第一个元素被加进来的时候就能知道应该扩容多少。

重要的内部方法

空间分配相关

private static int calculateCapacity(Object[] elementData, int minCapacity);

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

这个方法用于计算：

当原来数组为空，第一次插入元素的时候，数组应该分配多少空间，DEFAULTCAPACITY_EMPTY_ELEMENTDATA呼应了上面构造方法中的无参构造方法，常量DEFAULT_CAPACITY=10。

这说明：如果ArrayList是以无参构造方法建立的，在添加第一个元素时会直接分配10个元素的空间。

private void grow(int minCapacity);

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //即newCapacity = 1.5*oldCapacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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);
}

可以看出数组是以1.5倍为基准扩容的，如果1.5倍后大于MAX_ARRAY_SIZE (Integer.MAX_VALUE - 8)，则使用hugeCapacity(minCapacity)确认（size是int类型，不能超过int范围的最大值）。

元素获取、增改相关

E elementData(int index);

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

取元素,就是从数组中获取元素，是get等方法的依赖。

private void rangeCheck(int index);

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

边界检查。

rangeCheck方法是提供给get,remove，set之类的方法检查的,是给已经存在元素的集合操作的，范围0至size-1,这个方法把检查负责的职责交给了数组的访问,像get(-1)时会报异常ArrayIndexOutOfBoundsException。

private void rangeCheckForAdd(int index);

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

这个方法是提供给add和addAll的，会检查负数。因为如果扩容了数组再抛出异常就白扩容了。