面试题：Java中ArrayList添加元素的底层逻辑

add(E e)方法底层实现基础
- ArrayList内部使用一个数组来存储元素。这个数组在ArrayList类中定义为elementData。
- 当调用add(E e)方法时，它会将指定的元素e添加到ArrayList的末尾。
具体实现步骤
- 检查容量：
  - 首先调用ensureCapacityInternal方法，这个方法会先计算所需的最小容量。如果是第一次添加元素，所需最小容量为DEFAULT_CAPACITY（默认是10），否则为当前元素个数加1。
  - 然后调用ensureExplicitCapacity方法，该方法会检查当前数组的容量（即elementData的长度）是否小于所需的最小容量。如果小于，则需要进行扩容。
- 添加元素：
  - 如果不需要扩容，直接将元素e添加到elementData数组的size位置，然后size自增1。这里size表示ArrayList中实际存储的元素个数。
数组扩容机制
- 扩容触发：当ensureExplicitCapacity方法检测到当前容量不足时，会调用grow方法进行扩容。
- 扩容策略：
  - grow方法中，新的容量为旧容量的1.5倍（通过oldCapacity + (oldCapacity >> 1)计算，oldCapacity >> 1相当于oldCapacity除以2）。
  - 如果新容量仍然小于所需的最小容量，则新容量直接设置为所需的最小容量。
  - 如果新容量大于MAX_ARRAY_SIZE（ArrayList定义的最大数组大小，通常是Integer.MAX_VALUE - 8），则会调用hugeCapacity方法进一步处理。
- 数组复制：
  - 确定新容量后，使用Arrays.copyOf方法将原数组elementData的内容复制到新的更大容量的数组中。新数组的大小为新确定的容量。
  - 然后将新元素添加到新数组的size位置，size自增1。

示例代码（简化示意）：

public class ArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData;
    private int size;

    public ArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

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

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

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

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

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
}

星途面试题库

面试题：Java中ArrayList添加元素的底层逻辑

知识考点

面试题答案