本篇通过阅读JDK1.8源码，了解ArrayList是如何进行自动扩容的。

初始化

无参构造方法创建ArrayList()
1
ArrayList arrayList = new ArrayList();

源码：

1
2
3
4
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

将默认的大小为0的object数组赋值给elementData实现初始化。

指定容量的够着方法创建ArrayList()
1
ArrayList arrayList = new ArrayList(14);

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    //指定容量大于0，则创建一个指定容量的Object数组
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    //指定容量等于0，则将他指向EMPTY_ELEMENTDATA的size为0的空Object数组引用
    /**
    *另外注意：EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA都是空Object数组
    *但是其含义不一样，在后面自动扩容的时候会讲到
    **/
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    //其他情况抛出异常
    throw new IllegalArgumentException("Illegal Capacity: "+                              initialCapacity);
  }
}

自动扩容

当添加元素时，会根据情况进行是否扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean add(E e) {
  //ensureCapacityInternal：翻译：确保内部容量
  //size == elementData.length 即当前数组大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}

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

再看 ensureCapacityInternal 是如何确保内部容量的

1
2
3
4
5
6
//minCapacity 数组需要的最小容量，（原容量+添加元素个数）
private void ensureCapacityInternal(int minCapacity) {
  //ensureExplicitCapacity：翻译：确保明确的容量
  //确保明确的容量，那 calculateCapacity（计算容量） 计算的就是明确的容量值咯
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

calculateCapacity 如何计算容量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static final int DEFAULT_CAPACITY = 10;//默认扩容容量

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  /**
  在添加元素方法到这里的时候，如果是 new ArrayList() 创建的对象，
  就会进入到if中返回的，DEFAULT_CAPACITY(10) 将最小所需容量设置为 10
  其他情况不设默认值，直接返回最小所需容量
  还有一个是如果是new ArrayList(0) 创建的，也会直接返回 minCapacity，而不是给默认扩容容量
  因为此时elementData指向的是EMPTY_ELEMENTDATA
  */
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

接下来看 ensureExplicitCapacity :

1
2
3
4
5
6
7
private void ensureExplicitCapacity(int minCapacity) {
  modCount++;

  // 最少所需容量 > 原来容量 才进行扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity); //扩容的方法
}

扩容方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void grow(int minCapacity) {
  // overflow-conscious code
  //原来的容量
  int oldCapacity = elementData.length;
  //新的容量 （原来的容量+原来容量的一半[拟扩容的容量]）
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  //新的容量 < 最少所需容量
  if (newCapacity - minCapacity < 0)
  newCapacity = minCapacity;
  //新的容量 > 数组最大容量（Integer.MAX_VALUE - 8;）
  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);
}

重新计算大容量：

1
2
3
4
5
6
7
8
9
private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
  //大于数组最大容量则用Integer.MAX_VALUE
  //否则用数组最大容量作为新的容量值。
  return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
}

总结

  • ArrayList用默认无参构造方法创建时，在第一次添加元素时将数组大小扩展至默认容量(10)。

  • 通常每次扩展容量，扩展至原来容量的1.5倍。

  • 所需最少容量 > 原来容量的1.5倍时， 则扩展至所需最少容量。

  • 拟扩容至的容量 > 数组的最大大小时，进行一次大容量扩容

    • 所需最少容量 > 数组最大大小：扩容至Integer的最大值
    • 所需最少容量 < 数组最大大小：扩容至数组最大大小(Integer.Max -8)