ArrayList源码分析

本文所查看的源码基于JDK1.8

RandomAccess

ArrayList实现了RandomAccess接口，另外LinkedList类则没有实现这个接口。这是个标志接口，只要List实现了这个接口，就能支持快速随机访问。例如Collections类中的binarySearch方法

public static <T>int binarySearch(List<? extends Comparable<? super T>> list, T key) {    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key);    else return Collections.iteratorBinarySearch(list, key);}

可以看出，如果List实现了RandomAccess接口，在遍历的时候就会采用基于索引的传统for循环，否则就使用迭代器遍历
也就是说在JDK的设计中，遍历ArrayList时采用for循环，遍历LinkedList时采用迭代器iterator遍历。因为遍历ArrayList采用for循环会比使用迭代器快，而遍历LinkedList时采用迭代器iterator遍历会比使用for循环快
原因：ArrayList是基于数组(索引)的存储结构，因此使用索引去获取一个元素的复杂度为O(1)，所以使用for进行遍历已经足够快，没有必要去借助迭代器花费额外的时间；而LinkedList底层是基于双向链表实现的，使用索引获取元素的复杂度为O(n)，而使用迭代器遍历LinkedList的话是直接顺着链表节点的后继节点移动的，所以使用迭代器遍历花费时间比使用for循环要少

主要成员变量

private static final int DEFAULT_CAPACITY = 10; //默认容量，在加入第一个元素时扩容会用到private static final Object[] EMPTY_ELEMENTDATA = {}; //一个空数组//也是一个空数组，与上面那个空数组的区别在ArrayList的构造函数以及存入第一个元素时再进行分析private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; //存放数据元素的数组private int size; //当前结构中存储的元素个数private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//JDK设定的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); }    }public ArrayList() {    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

当构造ArrayList有指定其大小时，如果指定的大小大于0，就以用户指定的数值为ArrayList的大小，如果指定的数值小于0抛出异常，如果等于0，就令存放数据的elementData直接指向EMPTY_ELEMENTDATA
如果使用无参构造函数，就令elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA

public ArrayList(Collection<? extends E> c) {    Object[] a = c.toArray();    if ((size = a.length) != 0) { if (c.getClass() == ArrayList.class) {     elementData = a; } else {     elementData = Arrays.copyOf(a, size, Object[].class); }    } else { // replace with empty array. elementData = EMPTY_ELEMENTDATA;    }}

这个构造函数用于传入一个Collection集合，通过复制集合中的内容作为ArrayList的内容

扩容机制

说到ArrayList一般都会说到其底层的扩容机制，相关的方法有add，grow等等。接下来从add方法入手，模拟往ArrayList中添加元素时的扩容过程
首先，使用无参构造函数构造一个ArrayList，那么其elementData会指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA，然后调用如下的add方法加入第一个元素

add

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

要添加一个元素，先要判断当前ArrayList中的数据域elementData的大小是否足够多存放一个元素，即在正式添加这个元素前，应该确保elementData的大小至少为当前elementData中所存放元素的个数size + 1。所以添加第一个元素时要求至少大小minCapacity为1。这个确保工作用到了ensureCapacityInternal方法

ensureCapacityInternal

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

calculateCapacity

先看calculateCapacity方法

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

可以看出，如果是第一次添加元素，且创建ArrayList对象使用的是无参构造函数，那么默认第一次要扩容的大小为DEFAULT_CAPACITY，即10 (代码中选择的是DEFAULT_CAPACITY跟minCapacity中的最大值，但实际上第一次添加元素的时候minCapacity就是1) ，这就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA跟EMPTY_ELEMENTDATA的区别所在，如果用户在创建ArrayList对象时使用的是有参构造函数指定了其初始容量，那么第一次扩容时就不会尝试扩容至10，而是以用户指定的容量大小为主
我的理解是，如果用户使用的是无参构造函数，可以认为他对ArrayList的初始容量大小并没有什么要求，那么JDK在第一次扩容，索性就直接将容量扩充为10，这样在添加第一到第十个元素的时候也不用去扩容，如果用户指定了初始容量，那么就以用户指定的为准，不去默认扩容，就算用户设置的初始容量也为0，在添加前几个元素的时候可能会出现多几次的扩容操作，也不去管，完全尊重用户

ensureExplicitCapacity

接下来是ensureExplicitCapacity方法，Explicit意为明确的，确实的，也就是说经过calculateCapacity方法决策后的最小容量才是确切的最小容量：

private void ensureExplicitCapacity(int minCapacity) {    modCount++;    // overflow-conscious code    if (minCapacity - elementData.length > 0) grow(minCapacity);}

overflow-conscious是JDK设计者考虑到溢出所设置的判断代码
判断所要求的最小容量minCapacity跟当前elementData的容量的关系，最小容量为1，而当前elementData的容量为0，所以要扩容，调用grow方法进行，此时minCapacity值为10

grow

private void grow(int minCapacity) {    // overflow-consciouscode    int oldCapacity = elementData.length;    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);}

先设置新的容量大小newCapacity为旧容量大小的1.5倍，但如果newCapacity比所要求的最小容量minCapacity还小，就把newCapacity设为minCapacity；如果newCapacity比设计的elementData最大大小MAX_ARRAY_SIZE还大，就调用hugeCapacity方法来计算最终要设置的新容量
此时newCapacity为0，minCapacity为10，且10小于MAX_ARRAY_SIZE，所以最终的newCapacity为10，然后将elementData扩容至10，最后回到add方法执行elementData[size++] = e语句，将添加的这第一个元素正式加入elementData，同时size置为1，表示当前整个ArrayList中存储的元素个数为1，第一个元素添加成功
接下来添加第二个元素，传入ensureCapacityInternal方法的minCapacity参数为2，经calculateCapacity方法决策后返回的还是2，然后执行ensureExplicitCapacity方法，由于当前elementData的长度为10，故不会经过扩容，直接回到add方法执行将元素放入elementData数组的操作。添加第三，四，五…十个元素的过程都是相同的
当添加第十一个元素时，传入ensureCapacityInternal方法的minCapacity参数为11，经calculateCapacity方法后返回11，然后执行ensureExplicitCapacity方法，由于当前elementData的长度为10小于11，所以会执行grow(11)，当前容量为10，所以计算得到newCapacity为15，15大于11，所以最后newCapacity值为15，这也就是说我们常说的默认扩容1.5倍

hugeCapacity

在grow方法中可以看到当newCapacity计算出的结果大于MAX_ARRAY_SIZE，就需要执行hugeCapacity方法来确定newCapacity的最终结果

private static int hugeCapacity(int minCapacity) {    if (minCapacity < 0) // overflow throw new OutOfMemoryError();    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

如果所要求的最小容量minCapacity也比MAX_ARRAY_SIZE还大，就直接取整型变量最大值为新容量的大小，否则取MAX_ARRAY_SIZE作为新容量的大小，确定了最终的新容量大小newCapacity的值

删除元素

删除元素主要涉及的方法为remove(int index)方法：

public E remove(int index) {    rangeCheck(index);    modCount++;    E oldValue = elementData(index);    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;}

该方法首先对索引index的合法性进行校验，然后获取被删除元素，作为方法最后的返回值
用numMoved = size - index - 1计算出删除元素后要复制的空间长度，因为每删除一个元素(除了删除最后一个元素)后都要把从被删除元素的后一个元素开始直到最后一个元素之间的所有元素向前移动一位，当index为size - 1的时候，自然计算得到的值为0，即不用复制进行前移元素。当numMoved大于0，就把elementData中最后numMoved个元素通过复制一起向前移动一位，最后返回被删除元素，方法执行完毕

关于modCount

关于modCount这个字段在ArrayList的父类AbstractList的源码中有详细的注释，大概意思就是：这个字段记录这个List的结构被改变的次数 (类似于乐观锁的实现方法中有一种版本号version法，数据每被修改一次，version加一)，结构被改变例如List的长度大小被改变，或其它可能导致迭代遍历的过程被影响的操作。这个字段被iterator以及list iterator的实现类所使用，如果它的值被意外修改，那么iterator就会在调用next，remove，previous等方法时抛出ConcurrentModificationException，并发修改异常。这其实是一种fast-fail快速失败机制，防止在迭代时，由于并发修改而导致的不确定性行为。子类对这个字段的使用与否是可选的，如果子类希望迭代器iterator或List iterator能具有fail-fast机制，那么子类只需要在add方法，remove方法，以及其它会导致List结构被改变的方法中为这个字段添加增量操作即可
而ArrayList是使用了这个字段的。所以当我们使用迭代器遍历(或增强for循环)时，如果有其它线程并发对List进行了修改，就会抛出ConcurrentModificationException