ArrayList的动态扩容源码

ArrayList可以理解成一种“会自动扩增容量的Array”。那么问题来了，ArrayList是如何扩容的？

首先打开ArrayList源码，我本地是Java 1.8版本。针对最初的问题，可以翻到add(E e) 方法：

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
   // 注意这里的size表示ArrayList的长度，而非Array(数组)的长度。

源码的内容真的非常的简单，可以看到扩容的处理在ensureCapacityInternal方法中处理的：

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

        ensureExplicitCapacity(minCapacity);
    }
    //这里的elementData是存储数据的对象，ArrayList实际上是对数组的一层封装。
    //注意minCapacity这里确定了最小值DEFAULT_CAPACITY，也就是10

ensureCapacityInternal方法又是一层神秘的面纱，继续掀。


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

咦，终于看到庐山真面目——grow(int minCapacity)方法。首先我们确认下minCapacity的值是多少。看下 add(E e)方法中有这么一行：

 ensureCapacityInternal(size + 1)

由此可见输入值minCapacity的值为size+1。在ensureCapacityInternal确定了minCapacity的最小值10。接下来看下 grow(int minCapacity) 方法中的这两行：

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

假设数组的初始化方法调用的是无参的new ArrayList()，这两行代码处理的逻辑就是：

oldCapacity = 0， newCapacity = 0 + 0000>>1 = 0 + 0000 = 0;
oldCapacity = 1， newCapacity = 1 + 0001>>1 = 1 + 0000 = 1;
oldCapacity = 2， newCapacity = 2 + 0010>>1 = 2 + 0001 = 3;
oldCapacity = 4， newCapacity = 4 + 0100>>1 = 4 + 0010 = 6;
oldCapacity = 7， newCapacity = 7 + 0111>>1 = 7 + 0011 = 10;
oldCapacity = 11， newCapacity = 11 + 1011>>1 = 11 + 0101 = 16;
oldCapacity = 17， newCapacity = 17 + 1 0001>>1 = 17 + 1000 = 25;
...

就算不理解位运算，也能归纳出来，newCapacity是oldCapacity的1.5倍。也就是说：每次执行完add(E e)方法，数组的容量大小都会扩大为原来的1.5倍

其他方法的阅读：

addAll(Collection<? extendsE> c)

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

与add(E e) 的步骤一直，先数组扩容，再合并数组。扩容基本逻辑：newCapacity会先扩大为原来的1.5倍，再和【数组当前容量+新增大小容量】进行比较，取较大的值进行扩容。

add(int index,E element)

    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

这个方法主要完成数组的拷贝：先将【第index位至末位】数组往后位移一位，然后在将element赋值给index位。

这个问题还是去年遇到的一道面试题，很惭愧当时没有回答上来。作为一件耿耿于怀的心病，今天总算时弄清楚扩容的步骤。希望自己未来能够收获更多有趣的知识。