集合-ArrayList扩容机制

引言

ArrayList是基于数组所实现的。
众所周知，数组是不能进行扩容操作的，而我们调用ArrayList的add()等方法时却可以实现扩容操作。

源码

其内部源码主要经历以下步骤：

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

• 当我们调用add()时，系统会先调用ensureCapacityInternal(size+1)来确认ArrayList的内部数组elementData是否有足够空间容纳size+1大小的数据。

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

• 在ensureCapacityInternal()中，首先系统会先判定内部数组elementData是否等于默认的空数组，如果是的话，则取DEFAULT_CAPACITY(默认容量为10)与minCapacity的最大值(即ArrayList默认构造一个容量为10的空数组)，然后调用ensureExplicitCapacity()确认是否需要扩容。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

• 在ensureExplicitCapacity()中，首先增加modCount数量(modCount是用来记录ArrayList元素数目被修改的次数)，其次进行判定minCapacity是否超过了当前数组elementData的长度，超过了则调用grow()方法，进行数组扩容操作。未超过则进行elementData[size++] = e赋值操作。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• 在grow()方法中，可以看到newCapacity = oldCapacity + (oldCapacity >> 1)，即是新的数组长度为原数组长度的1.5倍，再与传入的minCapacity大小进行比较，取最大值，如果超过了MAX_ARRAY_SIZE大小(值为Interger.MAX_VALUE - 8)，调用hugeCapacity()方法，然后调用Arrays.copyOf()将数组扩容并复制到新数组。

总结

ArrayList实现扩容操作的机制，就是在超过elementData数组长度时，将数组扩容1.5倍，并调用Arrays.copyOf复制到新数组。而至于1.5倍的扩容，是因为不会导致每次进行add操作时就要频繁进行扩容数组长度，也不会过于浪费内存空间。当然，如果我们能预知ArrayList的大小时，我们应该调用ensureCapacity()方法来事先扩容数组长度，避免频繁扩容影响性能。

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        ? 0
        : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

扩展知识

• 数组也不能进行删除操作，而ArrayList中可以调用remove()等方法来实现删除操作，实际上是先遍历查找出对应的position，然后调用System.arraycopy()方法将数据复制到新数组，然后再将原position位置的数据置空，使gc回收其资源。
• 由于ArrayList上述扩容机制，ArrayList的size()方法并不是返回其内部数组elementData的长度，而是返回size变量，size变量在调用add、remove等方法的时候增加或减小其值，例如在add方法中，在赋值操作中elementData[size++] = e;使size值加一。addAll、remove等方法同理。