Java-基础-ArrayList

1. 简介

ArrayList 实现了 List 接口，其底层基于数组实现容量大小动态可变。既然是数组，那么元素存放一定是有序的，并允许包括 null 在内的所有元素。

每个 ArrayList 实例都有一个容量（capacity）。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。

2. 初始化

// Test::main() 构造一个List实例

List<Integer> list1 = new ArrayList<>();

ArrayList 初始化源码如下：

// 空数组

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 保存元素的缓冲数组（存放值的数组）

transient Object[] elementData; 

// 集合中包含的元素数量

private int size;

// 构造一个空的数组

public ArrayList() {

  this.elementData = DEFAULTCAPACITY_EMPTY_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);

  }

}

// 构造一个包含指定集合元素的列表，按照集合的迭代器返回的顺序

public ArrayList(Collection<? extends E> c) {

  Object[] a = c.toArray();

  if ((size = a.length) != 0) {

    if (c.getClass() == ArrayList.class) {

      elementData = a;

    } else {

      elementData = Arrays.copyOf(a, size, Object[].class);

    }

  } else {

    // replace with empty array.

    elementData = EMPTY_ELEMENTDATA;

  }

}

看了源码之后感觉ArrayList的初始化好简单，有如下几种方式：

构造一个空数组。
构造一个指定长度的数组。
将传入的集合转成数组，并指向 elementData。

既然创建ArrayList实例是通过new出来的，那我们不妨看一看list1实例在jvm中是如何分布的。

ArrayList.class 被加载时，static修饰的变量，会被加载到方法区。

当我们再创建一个ArrayList实例list2，会是如何分布呢？

通过数据在JVM中的分布，我们可以了解到作者设计的巧妙之处，当我们创建多个list实例时，其实底层都是指向缓存在方法区的Object[]数组。

3. 自动扩容

3.1 第一次添加元素

在看自动扩容之前，我们先了解下当我们第一次给list中添加元素的时候，底层都干了些什么事。

private int size;

// ArrayList::add()

public boolean add(E e) {

    ensureCapacityInternal(size + 1);

    // 给指定的索引元素赋值 没啥好说的

    elementData[size++] = e;

    return true;

}

我们继续看下ensureCapacityInternal方法。

// 默认的容量长度

private static final int DEFAULT_CAPACITY = 10;

private void ensureCapacityInternal(int minCapacity) {

  // 当第一次add的时候 minCapacity = 1，elementData = {}

  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

// 计算容量值

private static int calculateCapacity(Object[] elementData, int minCapacity) {

  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

    // 当 elementData = {}时，获取最大值，即返回10

    return Math.max(DEFAULT_CAPACITY, minCapacity);

  }

  return minCapacity;

}

private void ensureExplicitCapacity(int minCapacity) {

  modCount++;

  // 10 - 0 > 0

  if (minCapacity - elementData.length > 0)

    grow(minCapacity);

}

// 真正的扩容方法

private void grow(int minCapacity) {

  // 旧容量 = 0

  int oldCapacity = elementData.length;

  // 新容量 = 0 + 0 / 2 即：新容量 = 0。右移一位相当于除以2

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

  if (newCapacity - minCapacity < 0)

    // 0 - 10 < 0。 newCapacity = 10

    newCapacity = minCapacity;

  if (newCapacity - MAX_ARRAY_SIZE > 0)

    newCapacity = hugeCapacity(minCapacity);

  // 将elementData的值 copy 到 新容量的数组中

  elementData = Arrays.copyOf(elementData, newCapacity);

}

copy过程如下：

// Arrays::copyOf()

public static <T> T[] copyOf(T[] original, int newLength) {

    return (T[]) copyOf(original, newLength, original.getClass());

}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {

  @SuppressWarnings("unchecked")

  T[] copy = ((Object)newType == (Object)Object[].class)

    // 创建一个新长度的数组

    ? (T[]) new Object[newLength]

    : (T[]) Array.newInstance(newType.getComponentType(), newLength);

  // native方法，实现值copy

  System.arraycopy(original, 0, copy, 0,

                   Math.min(original.length, newLength));

  return copy;

}

从源码中得知，当我们创建一个空的list，并且第一次给list中添加元素的时候：

创建一个长度为DEFAULT_CAPACITY = 10的数组
将elementData中的值copy到新数组中（当然，这时的elementData为空）
将初始化好的新数组赋值给elementData

3.2 如何扩容

当我们了解了arrayList第一次添加元素的逻辑后，我们也基本明白了动态扩容的原理，其实就是创建一个新的数组覆盖之前的数组，如图：

但是有两个问题：

何时扩容？
扩多大？

我们带着疑问再去看下源码：

private void ensureExplicitCapacity(int minCapacity) {

  modCount++;

  // 当 elementData 没有空闲的位置时，才去扩容

  // 即：第一次扩容是发生在 添加第11位元素时 11 - 初始长度10 > 0

  if (minCapacity - elementData.length > 0)

    grow(minCapacity);

}

private void grow(int minCapacity) {

    int oldCapacity = elementData.length; // 10

    // newCapacity = 10 + 10 /2。

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

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

}

private static int hugeCapacity(int minCapacity) {

  if (minCapacity < 0) // overflow

    throw new OutOfMemoryError();

  return (minCapacity > MAX_ARRAY_SIZE) ?

    // 最大值：2的31次方

    Integer.MAX_VALUE :

  MAX_ARRAY_SIZE;

}

看到这里，心中的疑惑就解开了：

当ArrayList内部的elementData[]没有空闲位置时，才进行扩容。
每次将之前的size扩容1.5倍。

参考：

https://zhuanlan.zhihu.com/p/27873515

http://www.cnblogs.com/CarpenterLee/p/5419880.html

巴特西