Java.util.ArrayList的自动扩容机制

ArrayList的扩容规则是：新的大小是上次容量的大约1.5倍，为什么是大约见下文。

References:
JDK 8U151 Source

ArrayList并不是真正意义上的可变数组，而是在内部存储了一个数组，每次添加元素前都会检查容量是否足够，如果容量不够就会自动创建一个更大的数组，并把原来的数据拷进去，以此来实现动态数组。通常，网上把这种机制叫做“自动扩容”。
ArrayList的默认容量大小是10个元素，但这并不适合大多数情况，所以ArrayList也有一个可以指定初始化容量的构造方法

public ArrayList(int initialCapacity)

合理的设置初始化大小的数组可以避免多次扩容，影响性能。
下面通过源码(JDK 8u151)分析一下ArrayList的自动扩容究竟是怎么回事： 自动扩容发生在add()方法调用之后，结束之前。通过跟踪add方法

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

其中elementData[size++] = e;是赋值，所以再进入ensureCapacityInternal方法查看

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

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

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

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

ensureCapacityInternal只是调用了其他的两个方法，依次查看，calculateCapacity是计算容量的方法，由于默认无参的构造方法只会初始化一个空数组，而不是默认容量10的数组，所以这里如果数组为空，则返回实际大小和默认的10之中较大值。如果不是空则返回最小预期容量。然后在ensureExplicitCapacity中对刚刚返回的容量进行判断，如果期望的最小容量大于数组实际长度，就会进行扩容，也就是grow方法了。

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

仔细分析下这个方法，首先扩容前的容量就是当前大小，扩容后的容量 = 扩容前容量 + (扩容前容量 >> 1);相当于(1+1/2)即1.5倍大小，这里用了右移操作(右移一位相当于除以2)，虽然提高了性能，但是也因此会在奇数时丢失精度，导致并不能保证扩容后的容量一定大于扩容前的容量，所以有了下一步的if判断。如果由于精度的问题导致容量不正确，那么直接将期望容量设置为扩容后的容量(这点我也不清楚为什么会这样？为什么不直接设置为期望容量的1.5倍？为了性能？)。下一步是防止溢出的判断，略过。最后就是拷贝原数组到新数组中了。(最后一步的注释中可以看到此时通常已经接近实际大小，或许这是答案吧)。

此外，由于默认构造函数只是创建一个空数组，默认的10个大小也是在自动扩容中创建的，所以指定初始大小可以避免初始化的一次容量判断。

这样整个add方法就结束了，许多具体的细节并未分析，只是介绍了自动扩容机制，有兴趣可以自己查看源码。比如ensureExplicitCapacity方法中的modCount++涉及了Fail-fast机制。另外Map的自动扩容和List的自动扩容又不一样，Map的扩容时机不一样，并且有额外的rehash步骤因此复杂了很多，感兴趣可以自行查阅。