基本使用

ArrayList位于java.util包，在JDK1.2引入，ArrayList是List接口中较为常用的类型，基于数组实现，查询效率高，删除和指定位置的插入元素效率相对较低。查看其类图关系：

底层实现

查看ArrayList的源码，在该类中定义了如下的类变量或成员变量，这也说明其底层的数据结构实现为Object数组，允许添加null元素。

// 静态变量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 成员变量
transient Object[] elementData;
private int size;

关于在ArrayList中定义的这些变量，DEFAULT_CAPACITY和size含义比较简单，一个是初始长度大小，一个是当前集合长度大小：

DEFAULT_CAPACITY：默认初始化长度为10
size：ArrayList实例中包含的元素个数。

以下三个变量需要注意的是，包含了两个已经初始化的空数组常量，和一个用关键字transient修饰的未初始化的成员变量：

elementData：存储ArrayList元素的缓冲区，在进行元素操作的时候，该变量所指向的空间即实际数据存储区域，由于使用transient关键字修饰也就意味着不可序列化，其生命周期仅存于调用者的内存中而不会持久化到磁盘。当添加第一个元素时，任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList都将扩展为长度为DEFAULT_CAPACITY的Object数组。
EMPTY_ELEMENTDATA：用于空实例的共享空数组实例。当调用ArrayList的有参构造时，如果指定的集合长度为0时，elementData会指向EMPTY_ELEMENTDATA。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA：用于默认大小的空实例的共享空数组实例。当调用ArrayList无参构造时，elementData会指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA。用来确定添加第一个元素时需要膨胀的长度。

扩容机制

在JDK1.8的源码中，ArrayList做了一些优化，在创建一个空数组实例时并不会立即对其长度进行初始化，在使用时才会判断容量，进行扩容。
下面从调用ArrayList的无参构造，并添加一个元素，对源码实现进行分析，查看下面测试代码

public class TestArrayList {
  public static void main(String[] args) {
      List<Integer> list = new ArrayList<>();
      list.add(1);
      System.out.println(list);
  }
}

此处使用了ArrayList的无参构造，查看源码，elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA，此时数组长度为0。

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

当调用add方法时，会进行如下操作，查看源码，首先会调用ensureCapacityInternal方法进行容量校验。

public boolean add(E e) {
  // 校验数组容量
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  // 指定下标位置，在Object数组elementData的缓冲区中存储元素
  elementData[size++] = e;
  return true;
}

查看ensureCapacityInternal方法中的实现，这里面进一步进行显式容量的确认，并且使用calculateCapacity方法对当前ArrayList对象的elementData进行计算，返回结果。

private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

查看calculateCapacity方法的源码，首次添加元素并且ArrayList的初始化长度为0时，对ArrayList的长度进行初始化，通过计算返回默认值DEFAULT_CAPACITY。这里也说明，如果ArrayList通过在new的时候指定了长度，且其值大于默认值，则返回elementData的当前长度。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  // 在首次实例化ArrayList时，elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  // 因此在第一次添加元素时，if条件满足。此时DEFAULT_CAPACITY为10,minCapacity值为1
  // 所以第一次计算结果返回为此时DEFAULT_CAPACITY的默认值10
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

继续查看方法ensureExplicitCapacity源码，此时方法入参minCapacity的值为DEFAULT_CAPACITY=10

private void ensureExplicitCapacity(int minCapacity) {
  // 继承自Abstract类的保护参数，用来记录集合被修改的次数，保证迭代不被影响，这里不再扩展
  modCount++;
  // 此时minCapacity=10,elementData.length=0，因此会对ArrayList进行扩容
  if (minCapacity - elementData.length > 0)
      grow(minCapacity);
}

查看grow方法的源码，minCapacity的值为size+1

private void grow(int minCapacity) {
  // 首次调用oldCapacity为0
  int oldCapacity = elementData.length;
  // 此时newCapacity的值为0 + 0 >> 1 = 0 
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  // 满足0 - 10 < 0
  if (newCapacity - minCapacity < 0)
      // 此时newCapacity = 10
      newCapacity = minCapacity;
  // 如果扩容后的大小超过了MAX_ARRAY_SIZE，会对容量进行重新计算
  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);
}

MAX_ARRAY_SIZE：这也是要ArrayList的最大大小。MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，至于为什么要减8，源码中对此做了解释：一些 VM 在数组中保留一些header words，尝试分配更大的数组可能会导致 OutOfMemoryError，请求的数组大小超过VM限制。

查看hugeCapacity方法

private static int hugeCapacity(int minCapacity) {
    // 如果size+1后的结果minCapacity溢出了，会抛出内存溢出异常
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果扩容后的值minCapacity大于Integer.MAX_VALUE - 8，那就取Integer.MAX_VALUE
    // 如果下一次再进行递增，就会抛出OutOfMemoryError异常，其实这里也说明了ArrayList的底层
    // 数组最大长度为MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

进行newCapacity的值确定后，会调用Arrays.copyOf进行数据复制，查看copyOf方法的源码

// 该方法的入参为原始数组引用，以及newCapacity的值
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

数组的copy过程调用了工具类Arrays中的方法，调用arraycopy方法进行数据复制完成后，对于需要扩容的长度会使用null来占位填充。


public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    // 进行泛型类型判断，如果不能确定类型使用Object表示
    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;
}

然后调用native方法

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

最终回到add方法，将新元素占用到size + 1下标位置，一个元素添加完成。如果使用add指定index进行元素添加，需要对其后面的元素进行时间复杂度O(n)的操作，直接add的时间复杂度为O(1)，

public boolean add(E e) {
    // 每次进行add时都要重复一遍对内部容量的确保校验动作   
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 指定下标位置，在Object数组elementData的缓冲区中存储元素
    elementData[size++] = e;
    return true;
}

总结

ArrayList的底层实现使用的是Object[]来存储数据，会根据当前对象的容量和要添加的元素进行自动扩容，通过调用操作系统层面的arraycopy方法进行数据拷贝。
在JDK1.8中，调用无参构造创建ArrayList对象时并不会立即初始化空间，在首次调用add方法时才会初始化容量，自动扩容的长度为newCapacity = oldCapacity + (oldCapacity >> 1)，也就是原容量的1.5倍。
ArrayList的理论最大长度为MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，一些 VM 在数组中保留一些header words，尝试分配更大的数组可能会导致 OutOfMemoryError，请求的数组大小超过VM限制。