ArrayList自动扩容原理

ArrayList自动扩容原理 前言

ArrayList底层数据结构为数组，

• 数组的特点是：查询快，增删慢
  原因为：顺序存储，有索引，可以根据索引，直接定位到元素，所以查询快；由于是顺序存储，新增或者删除，都会对后续的元素有影响。

1.首先从创建一个ArrayList集合开始，集合如下：

       ArrayList list = new ArrayList();

2.进入源码后可以看到如下源码：

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

    transient Object[] elementData; // non-private to simplify nested class access

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

1. 首先ArrayList的构造方法里边有一句赋值代码，等于号左边是源码自定义的一个Object类型的常量数组，然后赋值给了用transient修饰的一个Object类型的elementData数组。
2. 以上结论就是创建对象的时候ArrayList底层创建了一个数组，数组的初始容量为空。

ArrayList集合中第一次add元素：

1.第一次调用add方法的时候看做了哪些事，还需要进入源码。

       list.add("aa");

2.add方法的源码如下：

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

1. 调用add方法的时候给里边传入一个字符串“aa”。

2. add方法体中的第一句调用了一下ensureCapacityInternal方法，中文意思为：（确定内部容量）往里边传了最小容量为1，因为size是一个源码自定义的一个int类型的变量没有赋初始值所以size为0。

3. 第二句空数组里边size++，此时elementData数组为0，把传过来的值赋值给数组的0下标。

4. 进入（确定内部容量）方法，最小容量此时为1。

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

5.确定内部容量方法里边又调用了一个（计算容量）方法里边传了两个参数：一个是空数组，一个是最小容量。然后追进源码。

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

    
    private static final int DEFAULT_CAPACITY = 10;

6.此时该方法里边做了一个判断，条件为true，因为 这条语句就是创建集合对象时底层调用的那条语句。
7.调用Math类的一个方法比较最大值，最小容量为1，DEFAULT_CAPACITY常量为10，因为是源码自己定义并赋初始值为10。

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

8.做判断 10减0大于0 条件成立，调用grow方法将最小容量10传入进去。

    private void grow(int minCapacity) {
        // overflow-conscious code
        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);
    }

9.此时minCapacity为10。源码的第二句和最后一句是核心。
newCapacity = minCapacity; 旧容量赋值给新容量后，新容量现在为10.
最后一句是将新容量10通过Arrays工具类中的copyof方法复制给了elementData，并且赋值给了elementData，等号左边的elementData指向原来的空数组。此时新的数组长度就变为10了。

结论：第一次调用add方法时，数组长度为10.

ArrayList集合第二次调用add方法添加元素：

       list.add("bb");

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

1. 数组长度为10，aa已经存入0下标了，size++现在变成1了。最小容量现在为2.

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


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

    //次代码意思问是否要确定扩容，if条件成立在执行扩容。
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

1. 此时elementData为10，minCapacity为2.
2. 条件不成立不会调用grow方法。当添加第11次数据的时候才会调用grow扩容方法进行扩容。

minCapacity为11的时候调用扩容方法：扩容为原来的1.5倍。

扩容代码为上图框选。

最后总结：

1. ArrayList底层数据结构是数组，当创建ArrayList对象时，底层初始化了一个空数组，数组是Object类型，数组名是elementData。当第一次添加元素时，数组长度扩容为10。

2. 当第11次添加时，会触发扩容机制，其实就是调用 grow方法，扩容为原数组长度的1.5倍。

3. 每次扩容时，都是创建一个新数组，将老数组的元素通过 Arrays工具类复制到新数组中。elementData 指向了新数组

4. ***扩容不是在老数组基础上拼接，而创建一个1.5倍长度的新数组，并把老数组的元素复制到新数组中。