ArrayList扩容

重要属性

    //初次扩容(size为0)时的默认容量
   private static final int DEFAULT_CAPACITY = 10;

    //存在常量池的零值
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //实际存储对象的数组，文档管他叫array buffer
   //容量就是指elementData的长度
    private transient Object[] elementData;
    
    //数组最大值是2147483639，不是2147483647的原因是
    //有些虚拟机在创建数组时会有头部信息
    //超过这个值会报OutOfMemoryError
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

初始扩容

• 如果容量从0到1,比如调用add(E e)，会将数组elementData变成{obj,null,null,null,null,null,null,null,null,null}
• 如果容量从0到12(超过了DEFAULT_CAPACITY )，比如调用addAll(Collection<? extends E>c)添加一个长度为12的数组，那么elementData的长度就是12

超过10后的扩容

如果容量超过10，再次扩容时比较,至少需要的容量和1.5当前容量，取大值。至少需要的容量指实际元素的个数(size的值)。比如当前容量15，实际元素12，需要一次性添加4个元素，那么至少需要的容量是16，1.5当前容量是22，容量将变为22。

代码实现

//以下三个函数用来确认是否需要扩容
public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != EMPTY_ELEMENTDATA)
            // any size if real element table
            ? 0
            // larger than default for empty table. It's already supposed to be
            // at default size.
            : DEFAULT_CAPACITY;

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

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

        ensureExplicitCapacity(minCapacity);
    }

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
   //计算扩容值的函数
    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);
    }
   //分配容量的函数
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

trimToSize方法

    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

由于扩容后会产生很多填充的null，这个方法可以讲这些null都去掉以节省内存，做法是调用一次copyOf方法创建一个新数组再把原来的拷贝进去。

总结

注意到copyOf方法会重新创建一个新的newLength长度的Object[]，并调用native方法来将原数组复制到新的Object[]里，这个动作开销还是很大的。这也就是数组扩容逻辑的意义:尽量减少调用这个copyOf方法，从而提高效率。