java常见面试问题之ArrayList如何实现扩容

ArrayList是java中非常常用的一个类，它可以实现一个无限长度的数组。由于一般的List的长度（即容量）是有限的，所以ArrayList的扩容是一个非常被容易问到的点。
当面试被问到这个问题的时候，最好的解决方法就是询求查看源代码，因为jdk的文档设计的可读性非常高，通过查看文档可以很好的回答这个问题。

进入ArrayList文档中的add方法
扩容的实现，是什么时候需要用到的呢？答案非常简单，就是当你往列表中增加新的元素的时候才需要。jdk中ArrayList.add()如下：

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

其中调用了ensureCapacityInternal这个方法。这个方法翻译为中文意思为确保容量足够，看方法名就知道这个方法和扩容有关，因此要进入这个方法继续查看。

进入ensureCapacityInternal方法
源代码如下：

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

这个方法很简单，直接调用了另一个方法ensureExplicitCapacity（确保明确的容量）,因此我们进入这个方法继续看看。

进入ensureExplicitCapacity方法
源代码如下：

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

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

到这里，我们终于很接近答案了，里面有一行注释，中文意思大概是容量溢出的代码，里面经过一个判断后调用了grow方法，这应该就是答案，因此点进去看看。

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

翻译起来就是，把原来list的长度作为旧的容量：int oldCapacity = elementData.length;
新的容量为旧的容量加上旧的容量的右移一位（涉及位运算，就是原来容量的0.5倍）：int newCapacity = oldCapacity + (oldCapacity >> 1);
创建一个长度为新容量的ArrayList，然后把旧的都copy过去，从而实现扩容。