ArrayList源码详解

引言

ArrayList是JAVA中的经典集合类，其底层是数组队列，与普通的数组类型相比，它的容量能动态增长。

源码解析

首先我们看看构造函数。构造函数有含参数的构造参数和无参数的构造参数。其中，有参数的构造函数,其中一个可以用来指定数组的大小，其实就是创建一个指定大小的数组，避免了扩容可能带来的时空损耗。

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //如果传入的参数大于0，创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //如果传入的参数等于0，创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //其他情况，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

而无参构造函数初始化数组容量为10,但是实际上并没有请求生成大小为10的数组。。

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

另外可以传入集合，将集合中的元素存入ArrayList的底层数据中。

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

我们上面看到，如果用我们常用的无参构造方法构造ArrayList的话，我们

我们实际上初始赋值的是一个空数组。只有当真正对数组进行添加元素操作的时候，才真正分配容量。

对ArrayList进行添加操作带代码如下：

 /**
  * 将指定的元素追加到此列表的末尾。
  */
 public boolean add(E e) {
//添加元素之前，先调用ensureCapacityInternal方法
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     //这里看到ArrayList添加元素的实质就相当于为数组赋值
     elementData[size++] = e;
     return true;
 }

private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
             // 获取默认的容量和传入参数的较大值
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }

       ensureExplicitCapacity(minCapacity);
   }

上面在进行添加操作的时候，如果：

数组没有进行真正的添加元素操作，那么就将 数组希望设置的最小容量（最终的minCapcity） 设置为默认值和传入来的 经添加操作后数组可能的容量（作为参数穿进来的minCapcity）的最大值。

如果数组已经非空，那么数组希望设置的最小容量就是本次add操作所传进来的minCapacity。

然后就调用ensureExplicitCapacity方法如下：

//判断是否需要扩容
  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;

      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
          //调用grow方法进行扩容，调用此方法代表已经开始扩容了
          grow(minCapacity);
  }

我们将之前我们希望设置的最小的数组容量和当前的数组长度做比较，如果发现当前的数组长度已经无法满足最小数组容量的需求，就将希望设置的最小容量作为参数传入grow方法。

/**
 * 要分配的最大数组大小
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * ArrayList扩容的核心方法。
 */
private void grow(int minCapacity) {
    // oldCapacity为旧容量，newCapacity为新容量
    int oldCapacity = elementData.length;
    //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
    //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
   // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
   //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
    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倍长度的变量newCapacity。如果该量还是满足不了扩容的需求，就将该量设置为minCapacity。

如果newCapacity大于最大容量，进入hugeCapacity方法来比较minCapacity和MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。然后将newCapacity传入Arrays.copyOf函数实现扩容操作。

因此，newCapacity的变化流程如下：

1.首先是在add操作的时候，size+1和DEAFULT_CAPACITY做比较，取出其中的最大值设置为MinCapacity。

2.然后是如果MinCapactiy比当前的数组长度大，那么就调用grow方法。

3.首先设置旧数组长度1.5倍长度变量newCapacity。

​ 如果newCapacity小于MinCapacity,此时newCapacity = minCapacity.

4.如果新的数组容量大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8），那么：

​ 如果minCapacity大于MAX_ARRAY_SIZE则新容量则为Integer.MAX_VALUE，

​ 否则，newCapacity=MAX_ARRAY_SIZE。

这里可能会解释一下为什么MAX_ARRAY_SIZE容量为Integer.MAX_VALUE-8。这里在源码注释中有说明：

/**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

因为有一些vm的实现中，在数组结构中会有一些meta data就是描述数组特性的数据，因此这里留了一部分空间。如果直接拉满，对于一些vm实现，数组就会报一个溢出错误。

此外，ArrayList中还有一个ensureCapacity 方法。这个方法可以实现一个近似手动扩容的效果。ensureCapacity源码如下所示：

/**
如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。
 *
 * @param   minCapacity   所需的最小容量
 */
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

其主要逻辑其实就是给定一个容量，只要这个容量大于0(赋数组值后)或者大于DEFAULT_CAPCITY(赋数组值后)就进行扩容操作。