ArrayList 扩容机制

拼搏现实的明天。 2024-03-16 19:48 54阅读 0赞

`ArrayList`实现了`List`接口。它可以存储包括`null`的任何类型的对象，允许重复元素。`ArrayList`在内部使用一个数组来存储元素，当元素数量超过数组容量时，`ArrayList`会自动重新分配更大的内部数组，并且将现有元素复制到新数组中。`ArrayList`基本等同于`Vector`，但是`ArrayList`是线程不安全的（执行效率高），在多线程情况下不建议使用`ArrayList`。

#### ArrayList 源码阅读及操作机制 ####

首先`ArrayList`中用来存储元素的数组是 Object 类型的数组 elementData，`ArrayList`的容量就是这个数组的大小。

transient Object[] elementData;

通过 debug 下面这段代码来观察`ArrayList`的扩容机制。

public class TestArrayList() {
      public static void main(String[] args) {
        ArrayList list = new ArrayList();
        // ArrayList list = new ArrayList(4);
            for (int i = 1; i <= 10; i++) {
                list.add(i);
            }
            for (int i = 11; i <= 15; i++) {
                list.add(i);
            }
      }
    }

构造方法

当使用无参构造器创建`ArrayList`对象时，会创建一个默认容量为10的空数组。

public ArrayList() {
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

// 用于默认大小的空实例的共享空数组。将其与 EMPTY_ELEMENTDATA 区分开，
    // 以便在添加第一个元素时知道需要扩容多少。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

使用指定大小的构造器创建`ArrayList`对象时，则初始 elementData 容量为指定大小。

public ArrayList(int initialCapacity) {
      if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
      } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
      } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
      }
    }

add(E e)

`add(E e)`方法将指定元素添加到列表末尾，该方法先调用`ensureCapacityInternal()`方法确保容量至少是所需的最小容量（即当前大小加一），然后再赋值。

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

由于`ArrayList`允许的元素类型是 Object，所以添加基本类型的数据时，会先将其转换为对应的包装类型。

ensureCapacityInternal(int minCapacity)

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

calculateCapacity()

该方法计算需要的容量，如果`elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA`（使用无参构造器时即符合该条件），则返回`DEFAULT_CAPACITY`（10），否则返回 minCapacity（size + 1）。

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

private static final int DEFAULT_CAPACITY = 10;

ensureExplicitCapacity(int minCapacity)

modCount 记录列表被结构性修改的次数（结构性修改是指添加或删除一个或多个元素，或显式调整后备数组的大小，仅仅设置元素的值不是结构性修改）。如果需要的容量大于 elementData 的长度，则调用`grow()`方法进行扩容。

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

grow()

该方法增加容量以确保列表至少能够容纳最小容量参数`minCapacity`指定的元素数量。计算得到新容量应为旧容量的 1.5 倍。如果计算得到的新容量小于需要的最小容量，则新容量应为需要的最小容量（使用无参构造器第一次添加元素时即为这种情况，第一次扩容为 10）。如果请求的数组大小超过了虚拟机的限制，可能会导致 OutOfMemoryError。最后通过数组复制`copyOf.copyOf()`来进行真正的扩容。

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 = copyOf.copyOf(elementData, newCapacity);
    }

总结

当使用无参构造器创建`ArrayList`对象时，elementData 初始容量为 0，第一次添加元素时 elementData 扩容为 10，以后再需要扩容，按 1.5 倍来扩容。若使用有参构造器创建`ArrayList`对象，elementData 初始容量为指定大小，如果需要扩容，则扩容为 1.5 倍。

值得注意的是，由于每次调整容量都需要将所有元素复制到新数组中，所以在元素数量较多时，频繁地调整容量可能会导致性能下降。为了避免频繁地调整容量，可以使用`ArrayList`的指定大小的构造方法或在添加大量元素之前使用`ensureCapacity()`方法预先指定较大的容量，以减少容量调整的次数。

另外，当从`ArrayList`中删除元素时，并不会立即缩小内部数组的容量。如果希望减少内存占用，可以使用`trimToSize()`方法来调整`ArrayList`的容量，使其与元素数量匹配。这样可以释放未使用的内存空间。