集合_Collection_ArrayList扩容机制

总结：
01.ArrayList中维护了一个Object类型的数组elementData（transient Object[] elementData）
02.创建ArrayList对象时 若使用的是无参构造器 则elementData容量为0 第一次添加元素时扩容为10 若再次扩容 则扩容为当前容量的1.5倍
03.创建ArrayList对象时 若使用的是有参构造器 则elementData容量为参数指定容量 扩容时扩容为当前容量的1.5倍（注：存在0-1、1-2的情况）

不可认为 new ArrayList<>() 与 new ArrayList<>(0) 等价 文章末尾处将图解说明

关于修饰elementData数组的transient关键字：被transient关键字修饰的对象不会被序列化
关于扩容后的数组：扩容实际上调用了Arrays.copyOf(elementData, newCapacity)方法 返回了一个新数组

无参构造

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

一些属性

    transient Object[] elementData;
 
    private static final Object[] EMPTY_ELEMENTDATA = {};
 
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

扩容机制解读（以add方法为例）：

        进入add方法后，将先调用ensureCapacityInternal方法以判断是否需要扩容，若需要则进行扩容，反之则不进行扩容，之后再向elementData数组中添加元素（即向集合中添加元素时，均会检测是否需要进行扩容）；参数size + 1将作为minCapacity传入，即集合的最小容量需求

注：size指集合中存放的元素个数

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

        进入ensureCapacityInternal方法，将调用ensureExplicitCapacity方法，该方法为判断是否需要进行扩容，并真正调用扩容方法的方法，但传入的参数需要先经过calculateCapacity方法处理

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

        进入calculateCapacity方法，若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，即集合是通过无参构造创建的， 将minCapacity修改为DEFAULT_CAPACITY，即minCapacity = 10；否则返回传入的minCapacity，不做修改

注：该方法决定了，集合若为无参构造创建，则第一次扩容将被扩容为10

    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;

        进入ensureExplicitCapacity方法，若minCapacity - elementData.length > 0，即集合的最小容量需求大于elementData数组的容量，将调用grow方法进行扩容，否则不进行扩容

注：modCount用于记录集合元素的被修改次数，在许多方法中均被调用

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

        进入grow方法，在进行一些简单判断后，调用Arrays.copyOf方法进行扩容；Arrays.copyOf方法将返回一个新的数组，即扩容后的数组实际上和扩容前的数组不是同一个数组，但Arrays.copyOf方法会保留扩容前的数组中的元素，并在扩容的部分填入null

注：oldCapacity + (oldCapacity >> 1)即为oldCapacity + oldCapacity/2，该代码决定了大部分的扩容，扩容后的数组容量为扩容前的1.5倍（存在0-10、0-1、1-2的特殊情况）

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

注意事项：

 不可认为 new ArrayList<>() 与 new ArrayList<>(0) 等价

前者：很显然，扩容后elementData数组容量为10

后者：很显然，扩容后elementData数组容量为1