ArrayList核心源码分析-扩容机制（jdk1.8）

一 、先从 ArrayList 的构造函数说起

ArrayList有三种方式来初始化，构造方法源码如下：

private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
        this.elementData = 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);
        }
    }
     public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

二、从add为入口出发查看扩容机制

2.1 add 方法

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

2.2 ensureCapacityInternal() 方法

可以看到 add 方法 首先调用了ensureCapacityInternal(size + 1)

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

如果该实例采用默认无参构造方法创立，且为第一次添加元素，此时传入minCapacity为size+1=1，在Math.max()方法比较后，minCapacity 为10。

2.3 ensureExplicitCapacity() 方法

如果调用 ensureCapacityInternal() 方法就一定会执行这个方法，下面我们来研究一下这个方法的源码！

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

举个例子分析一下：

• 当我们采用默认构造方法创造实例后，添加第一个元素时，minCapcity为10，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。
• 当add第2个元素时，minCapacity 为2，此时e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。
• 添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。

直到添加第11个元素，minCapacity(为size+1=11)比elementData.length（为10）要大。进入grow方法进行扩容。

2.4 grow() 方法

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;


        int newCapacity = oldCapacity + (oldCapacity >> 1);

        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;

        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);

        elementData = Arrays.copyOf(elementData, newCapacity);
    }

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍！（JDK1.6版本以后） JDk1.6版本时，扩容之后容量为 1.5 倍+1！详情请参考源码

我们再来通过例子探究一下grow() 方法 ：

• 当add第1个元素时，oldCapacity 为0，经比较后第一个if判断成立，newCapacity = minCapacity(为10)。但是第二个if判断不会成立，即newCapacity 不比 MAX_ARRAY_SIZE大，则不会进入 hugeCapacity 方法。此时数组将变为容量为10的新数组.
• 当add第11个元素进入grow方法时，newCapacity为15，比minCapacity（为11）大，第一个if判断不成立。新容量没有大于数组最大size，不会进入hugeCapacity方法。数组将移动到容量为15的新数组上。

2.5 hugeCapacity() 方法。

从上面 grow() 方法源码我们知道： 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) 
            throw new OutOfMemoryError();




        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

三、 System.arraycopy() 和 Arrays.copyOf()方法

阅读源码的话，我们就会发现 ArrayList 中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index, E element)、toArray() 等方法中都用到了该方法！

3.1 System.arraycopy() 方法

public void add(int index, E element) {

        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1); 


        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

我们写一个简单的方法模拟一下指定位置插入这个过程：

public class ArraycopyTest {

    public static void main(String[] args) {

        int[] a = new int[10];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;

        System.arraycopy(a, 2, a, 3, 2);

        a[2]=99;
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

}

结果：

0 1 99 2 3 0 0 0 0 0

3.2 Arrays.copyOf()方法

public Object[] toArray() {

        return Arrays.copyOf(elementData, size);
    }

个人觉得使用 Arrays.copyOf()方法主要是为了给原有数组扩容，该方法将数组数据挪至指定长度的新数组中，测试代码如下：

public class ArrayscopyOfTest {

    public static void main(String[] args) {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        int[] b = Arrays.copyOf(a, 10);
        System.out.println("b.length"+b.length);
    }
}

结果：

10

3.3 两者联系和区别

联系：

看两者源代码可以发现 copyOf() 内部实际调用了 System.arraycopy() 方法

区别：

arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。

四、 ensureCapacity方法

ArrayList 源码中有一个 ensureCapacity 方法不知道大家注意到没有，这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，那么这个方法有什么作用呢？

public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)? 

            0

            : DEFAULT_CAPACITY;



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

最好在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数，因为每次扩容都是创建一个新的对象数组，然后将元素挪至新数组中。相当耗费空间和时间。

我们通过下面的代码实际测试以下这个方法的效果：

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法前："+(endTime - startTime));

        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1));
    }
}

运行结果：

使用ensureCapacity方法前时间为：4637ms
使用ensureCapacity方法后为：241ms

通过运行结果，我们可以很明显的看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法，在实例化时，尽量指定可能的初始值。值得注意的是调用ensureCapacity 方法时，需要传入参数大于elementData.length，才有效果（ensureExplicitCapacity()方法中当判断minCapacity>length时，才进行grow操作），具体扩容为多大可参照上面的ensureExplicitCapacity()方法源码分析（一次源码阅读的练习，相当的重要）。