ArrayList在Java中的内部实现或者ArrayList在Java中如何内部工作是一个非常重要的面试问题。可能出现的一些问题是

• ArrayList在哪里存储其元素？
• ArrayList的初始或者默认容量是多少？如何创建该容量的ArrayList？
• ArrayList中的add方法如何工作？
• remove方法如何在ArrayList中工作？
• ArrayList如何自动增长和收缩？

在这篇文章中，我们通过研究Java中ArrayList的内部实现来尝试回答这些问题。

ArrayList在哪里存储其元素

Java内部的ArrayList使用数组存储其元素。这是一个Object数组，定义如下。

transient Object[] elementData;

ArrayList的容量

创建的ArrayList的初始容量取决于所使用的构造函数。有3个构造函数。

ArrayList(int initialCapacity)-如果在构造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);
  }
}

从Java的ArrayList类的代码中可以看到，如果initialCapacity> 0，则使用该初始容量创建elementData数组。

ArrayList()–如果未指定初始容量，则使用默认容量创建ArrayList。

这是Java中ArrayList类的代码。

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

如果我们在代码中看到DEFAULTCAPACITY_EMPTY_ELEMENTDATA被定义为一个空数组。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

只有将元素添加到ArrayList时，才会使用默认容量创建阵列。 ArrayList类中的默认容量定义如下。

private static final int DEFAULT_CAPACITY = 10;

ArrayList(Collection <？extends E> c)–如果使用现有集合构造ArrayList，则将传递的集合的元素复制到elementData数组。

public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();
  if ((size = elementData.length) != 0) {
    if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  } else {
    // replace with empty array.
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

从代码中可以看到，在此语句中elementData = c.toArray();集合的元素以数组形式返回。

elementData = Arrays.copyOf(elementData，size，Object []。class);
这一行确保将elementData数组转换为Object类型的数组。

add方法如何在ArrayList中工作

那就是覆盖ArrayList的可调整大小的数组实现功能的地方。如果我们看到Java中的ArrayList内部实现，则每次调用add()方法时，都会确保ArrayList具有所需的容量。如果容量用尽，则会创建一个新阵列，其容量比前一个阵列多50％。所有元素也将从先前的数组复制到新的数组。

最初调用add()方法时，将进行检查以确保容量。

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

如我们所见，是否必须创建默认容量ArrayList，在这里实际将容量初始化为10.

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

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

根据需要，从此代码中调用grow()方法以增加ArrayList的容量。

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
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);
}

如我们所见，在以下语句中，使用右移运算符将容量增加了50％。

int newCapacity = oldCapacity + (oldCapacity >> 1);

还将elementData数组更改为具有新的容量，还将旧数组中的元素也复制到新数组中。

elementData = Arrays.copyOf(elementData, newCapacity);

这就是ArrayList在内部保持动态增长的方式。

删除方法如何在ArrayList中工作

如果从数组中删除任何元素，那么所有后续元素都将移动以填充由删除的元素创建的间隙。这就是remove方法在Java的ArrayList类中内部执行的操作。

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 */
public E remove(int index) {
  rangeCheck(index);

  modCount++;
  E oldValue = elementData(index);

  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  elementData[--size] = null; // clear to let GC do its work

  return oldValue;
}

这是实际上在改组数组元素的语句。

System.arraycopy(elementData, index+1, elementData, index, numMoved);

这就是ArrayList动态缩小的方式。