一、实现原理

以JDK1.8.0_74源码为基础进行分析。

1、基于数组的实现，是一个容量能自动增长的动态数组。

2、ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了Cloneable接口，能被克隆。

3、随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。

二、关键源码

（一）属性

1、默认初始容量

/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;

2、默认的空实例赋值

/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

3、顾名思义，含有默认值的空实例。其和EMPTY_ELEMENTDATA有什么区别呢？

其在添加第一个元素时，会默认将Object数组的容量扩展到默认大小，即10；依个人理解，好处就是在添加10以内的元素时不需要频繁扩容；具体在下面讲构造方法时予以说明。

/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

4、实际存放元素的Object数组

/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access

5、存放元素的数量

/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;

（二）构造方法

1、包含初始容量的构造方法。数组大小为指定容量，如果指定为0，则数组赋值为EMPTY_ELEMENTDATA；**在添加第1个元素时，仅扩展容量为1；**继续添加元素怎么扩容呢，请看“二.（三）”。

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

2、不含初始容量的构造方法。默认赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA；在添加第1个元素时，会扩展容量为默认值10。

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

3、构造包含指定元素的列表，不解释。

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

（三）研究下add(E e)方法

源码：

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

讲一下第1行的“扩容”：ensureCapacityInternal(size + 1)

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

这里的“扩容”方法并非是一定有扩容的操作；如果数组为空实例且等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA时，取默认容量10和扩容参数值的最大值；然后执行容量确认方法ensureExplicitCapacity(minCapacity)。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//每次add()、remove()、addAll()、removeRange()及clear()方法执行时，它的值都会加1；记录ArrayList结构性变化的次数；在迭代器执行next()方法时，判断了当前的modCount跟初始化Itr时的expectedModCount是否相同，不同则说明列表数据进行了结构性改变，此时就会抛出ConcurrentModificationException。
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)//要“扩容”的值大于当前容量时，执行扩容操作
       grow(minCapacity);
}

特此说明modCount++;//每次add()、remove()、addAll()、removeRange()及clear()方法执行时，它的值都会加1；记录ArrayList结构性变化的次数；在迭代器执行next()方法时，判断了当前的modCount跟初始化Itr时的expectedModCount是否相同，不同则说明列表数据进行了结构性改变，此时就会抛出ConcurrentModificationException。

真正的扩容方法：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//大约增加1.5倍
    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);//将原数据复制到扩容后的数组中，赋值给elementData。
}

扩容规律，总结：当添加元素后的需要的容量X大于原容量Y时进行扩容，首先将Y扩大约1.5倍（取整）得到Z，取X和Z中的最大值作为此次扩容的实际容量。

用一个表格来展示（请先弄懂有参和无参构造方法的区别，前面有讲到）：

（四）Arrays.copyOf(elementData, newCapacity)

Arrays类与ArrayList处在同一个包下，源码中对该类的注释为：该类包含用于操作数组的各种方法(例如排序和搜索)。该类还包含一个静态工厂允许将数组视为列表。

扩容时用到此类的copyOf()方法，源码如下：

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;
}
public static native void arraycopy(Object src,  int  srcPos,
                         Object dest, int destPos,
                         int length);

通过源码可以看到，扩容的原理其实是在创建具有新长度的数组，调用System.arraycopy()方法将原数组中的内容复制到新数组中；System.arraycopy()方法使用native修饰，调用的是系统本地方法；在openJDK中可以看到其实际是调用的是C语言的函数；memmove()函数复制效率高，Java强烈推荐在复制大批量数组元素时使用此方法。

三、应用技巧

1、元素个数确定或可预知范围时，可使用有参构造方法构造实例列表。ArrayList的频繁扩容对时间和空间都会有较大的效率影响。

2、为了避免空间浪费，在对List操作完成后可以执行trimToSize()方法，将其处理成刚好填满的状态，即容量大小为元素个数。（需要注意的是，这里不会处理掉值为null的元素）

四、其他知识

1、线程不安全。因此多线程环境下请使用如下列表：

（1）使用Collections的以下方法返回线程安全的ArrayList类

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

（2）使用concurrent并发包下的CopyOnWriteArrayList类

2、Fail-Fast机制。

ArrayList采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败。是对不支持并发操作的快速响应。

3、ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。

4、ArrayList自己实现了序列化和反序列化的方法，通过实现 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法来对自身被transient修饰的属性进行序列化和反序列化。

五、知识延伸：几种列表实现的泛解

需要对比的列表实现：ArrayList、Vector、CopyOnWriteArrayList、Collections.synchronizedList(list)

（一）ArrayList

非线程安全，在一个线程遍历，另一个线程修改时，会报ConcurrentModificationException异常。除此之外，由于未做同步处理，可能导致数据不一致。

（二）Vector

线程安全，同样采用数组实现。其实现线程安全的的方式是在方法上添加synchronized关键字，这种方式严重影响执行效率，因此不推荐使用。

（三）Collections.synchronizedList

这个方法的源码见四.1.（1）。我们这里讨论的是ArrayList，而ArrayList实现了RandomAccess接口，因此通过Collections的这个方法返回的是SynchronizedRandomAccessList类的实例。

SynchronizedRandomAccessList继承于SynchronizedList，SynchronizedList继承于SynchronizedCollection；在SynchronizedCollection中有2个成员变量，如下：

final Collection<E> c;  // Backing Collection

final Object mutex;     // Object on which to synchronize

Collection<E> c为实际的集合；Object mutex 用于同步加锁，在每个方法中通过对mutex的加锁，达到操作c线程安全的目的。

（四）CopyOnWriteArrayList

先看源码，成员变量有2个：

/** The lock protecting all mutators */

final transient ReentrantLock lock = new ReentrantLock();

/** The array, accessed only via getArray/setArray. */

private transient volatile Object[] array;

1、关键字transient，被修饰属性不参与默认序列化，其序列化的实现通过writeObject方法和readObject方法实现。

2、使用ReentrantLock重入锁，实现线程安全。

官方说明：一个可重入的互斥锁定 Lock，它具有与使用 synchronized 方法和语句所访问的隐式监视器锁定相同的一些基本行为和语义，但功能更强大。ReentrantLock 将由最近成功获得锁定，并且还没有释放该锁定的线程所拥有。当锁定没有被另一个线程所拥有时，调用 lock 的线程将成功获取该锁定并返回。如果当前线程已经拥有该锁定，此方法将立即返回。可以使用 isHeldByCurrentThread() 和 getHoldCount() 方法来检查此情况是否发生。

3、来自网上的一段解释

CopyOnWriteArrayList:CopyOnWriteArrayList这是一个ArrayList的线程安全的变体，其原理大概可以通俗的理解为:初始化的时候只有一个容器，很常一段时间，这个容器数据、数量等没有发生变化的时候，大家(多个线程)，都是读取(假设这段时间里只发生读取的操作)同一个容器中的数据，所以这样大家读到的数据都是唯一、一致、安全的，但是后来有人往里面增加了一个数据，这个时候CopyOnWriteArrayList 底层实现添加的原理是先copy出一个容器(可以简称副本)，再往新的容器里添加这个新的数据，最后把新的容器的引用地址赋值给了之前那个旧的的容器地址，但是在添加这个数据的期间，其他线程如果要去读取数据，仍然是读取到旧的容器里的数据。

（五）CopyOnWriteArrayList和Collections.synchronizedList性能说明

CopyOnWriteArrayList，发生修改时候做copy，新老版本分离，保证读的高性能，适用于以读为主，读操作远远大于写操作的场景中使用，比如缓存。而Collections.synchronizedList则可以用在CopyOnWriteArrayList不适用，但是有需要同步列表的地方，读写操作都比较均匀的地方。