ArrayList扩容

众所周知，ArrayList是基于数组实现的，而在使用的时候我们从未担心过它的容量问题，毫无疑问这部分工作在源码中进行维护以及实现了。

这篇文章做一个研究源码的记录，使用的jdk版本是jdk11(不同的jdk版本源码可能不同)
首先查看ArrayList的构造函数，有三种方式来初始化ArrayList，分别是指定容量，不指定容量，以及用集合来初始化。

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

使用默认构造方法的时候，先初始化一个空的数组，而在第一次插入的时候，将其初始化为默认容量的数组，默认容量为10.

只有在add或者addAll的时候会触发扩容机制。
首先我们先来考虑第一次插入元素的情况,一下为add的源码:

 private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

第一次插入的时候，size是0，数组长度也为0，这是需要执行grow方法，接下来我们进入grow方法：

  private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1);
    }

可以看到grow将size+1作为最小需要内容传入重载的grow(int minCapacity)方法，这个方法返回数组拷贝，拷贝大小为newCapacity方法返回的内容。接下来进入newCapacity方法：

  private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

可以看到新容量是旧容量的1.5倍，如果扩容容量小于需要的容量，满足if条件，对比数组是否为空数组，如果是空的话，数组容量为默认容量和最小需要容量的更大值（防止空间不足，第一次插入情况），若不为空，直接返回所需要容量。不满足if条件的话，如果返回新容量大于最大数组容量，则使用hugeCapacity方法确认容量，超过数组容量最大值的话返回int最大值，否则返回数组容量最大值。单个非首次add的情况不会触发新容量小于最小需要容量的情况。hugeCapacity方法：

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

而使用addAll方法的时候，则可能触发该条件。
使用情况：

当add第1个元素时，oldCapacity 为0，经比较后第一个if判断成立，newCapacity = minCapacity(为10)。但是第二个if判断不会成立，即newCapacity 不比 MAX_ARRAY_SIZE大，则不会进入 hugeCapacity 方法。数组容量为10，add方法中 return true,size增为1。
当add第11个元素进入grow方法时，newCapacity为15，比minCapacity（为11）大，第一个if判断不成立。新容量没有大于数组最大size，不会进入hugeCapacity方法。数组容量扩为15，add方法中return true,size增为11