java集合-ArrayList

类图结构

ArrayList是List接口的可变大小数组的实现类。它的类层级结构如图所示：

Iterable接口：实现此接口的集合类可以执行forEach语句，另外spliterator接口是为了并行遍历数据源中的元素而设计的迭代器

Collection接口：集合类的通用接口，JDK不提供此接口的具体实现类，具体的集合子接口Set、List继承自Collection。因此此接口提供Set、List集合通用的一些功能接口以及默认实现。

AbstractCollection抽象类：提供集合通用功能骨架实现，如果要实现一个不可修改的Collection，可以继承自AbstractCollection并实现iterator和size方法。如果要实现一个可以修改的Collection，可以继承自AbstractCollection并实现add、remove方法。

List接口：继承自Collection接口，额外提供List类型需要实现的方法接口，如get、set、indexOf、lastIndexOf等。

AbstractList抽象类：提供List类型集合的通用功能骨架实现。如果要实现一个不可修改的List，可以继承自List并实现get和size方法。如果要实现一个可以修改的List，可以继承自List并实现set、add、remove方法。

RandomAccess接口：是一个标识接口，List集合实现此接口，表示List支持集合元素的随机访问。

Serializable接口：也是一个标识接口，实现此接口表示支持JDK序列化和反序列化。

Cloneable接口：也是一个标识接口，但是实现此接口的类应该要覆写Object类的clone方法并提供Class字段的拷贝。

类文件说明

ArrayList元素类型是泛型，可以存放【所有】类型的元素，包括null，感受一下ArrayList可以存放所有类型元素这句话：

ArrayList list = new ArrayList ();
list.add ( 1 );
list.add ( 1.2 );
list.add ( "1.3" );
list.add ( NaN );
list.add ( null );
list.add ( true );
list.add ( new Exception ("exp") );
list.add ( Class.class );

size、isEmpty、get、set、iterator、listIterator这些接口的操作时间复杂度都是O(1)。add接口操作的时间复杂度和添加的元素个数成正比为O(n)。

ArrayList的容量大于等于元素的size。添加元素的时候容量会自动增长（int newCapacity = oldCapacity + (oldCapacity >> 1);），并且扩容的时间复杂度平摊下来是O(1)。但是在扩容后会进行一次元素的全量拷贝，因此如果一次需要添加很多元素的时候，可以预先指定一个较大的容量来提高性能。

ArrayList不是线程安全的。多个线程同时操作ArrayList并且【至少一个线程修改了ArrayList的结构】时，必须进行同步。增加、删除元素或者扩容都属于修改ArrayList结构，但是设置元素的值不属于修改ArrayList的结构。

ArrayList的iterator()返回的迭代器属于fail-fast类型。就是说在返回迭代器之后如果不是通过iterator的add和remove方法来对ArrayList的结构进行修改，而且在外面进行了ArrayList 结构的修改的话，iterator会抛出ConcurrentModificationException异常。

add

public boolean add(E e) {
  modCount++;
  add(e, elementData, size);
  return true;
}

private void add(E e, Object[] elementData, int s) {
  if (s == elementData.length)
    elementData = grow();
  elementData[s] = e;
  size = s + 1;
}

可知：向ArrayList里添加一个元素时，只有当前size等于数组容量时才进行扩容，然后添加元素size+1

grow

private Object[] grow() {
  return grow(size + 1);
}

private Object[] grow(int minCapacity) {
  return elementData = Arrays.copyOf(elementData,
                                     newCapacity(minCapacity));
}

private int newCapacity(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity <= 0) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    if (minCapacity < 0) // overflow
      throw new OutOfMemoryError();
    return minCapacity;
  }
  return (newCapacity - MAX_ARRAY_SIZE <= 0)
    ? newCapacity
    : hugeCapacity(minCapacity);
}

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

可知：扩容分两步，第一步：newCapacity确定新的数组的容量是旧容量的1.5倍；第二步：调用Arrays.copyOf将原数组的元素拷贝到新数组，然后返回新数组。

这里注意有个技巧：overflow-conscious code

首先：计算机里的数字都是以补码表示（正数的补码不变，负数的补码是对应的正数取反加1），计算机里只有加法器，减法运算都要转换成加法运算比如10-5
$$
-\frac{0000 1010} {0000 0101}
$$

转换成10 + (-5):
$$
+\frac{0000 1010}{1111 1011}
$$

$$
1|00000101
$$

符号位前溢出不要，得到正数补码5也就是原码。

再回来看扩容的代码：添加元素自动扩容时size=底层数组长度length

当 oldCapacity很大接近Integer.MAX_VALUE时，比如oldCapacity = Integer.MAX_VALUE - 15；

则 newCapacity扩容为oldCapacity的1.5倍时，发生了溢出，newCapacity变为一个负数：-16；

这时minCapacity=size+1=Integer.MAX_VALUE-14；

此时：newCapacity - minCapacity = 2147483647 为正数，

所以以下判断为false，保证newCapacity溢出时不会进入此if分支

1	if (newCapacity - minCapacity <=0)

如果使用以下判断，则由于newCapacity为负数。判断为true，使得扩容后使用了minCapacity

1	if (newCapacity < minCapacity)

而newCapacity溢出的处理是以下return语句：由于newCapacity溢出为负数导致newCapacity - MAX_ARRAY_SIZE = 2147483641 为正数，所以会走分支hugeCapacity(minCapacity)使用MAX_ARRAY_SIZE 或 Integer.MAX_VALUE、Integer.MAX_VALUE - 8作为扩容后的新容量。

1
2
3

return (newCapacity - MAX_ARRAY_SIZE <= 0)
    ? newCapacity
    : hugeCapacity(minCapacity);

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

最后可知ArrayList的最大容量为：Integer.MAX_VALUE - 8 或者是Integer.MAX_VALUE.

首先，ArrayList的size类型是int，说明能存放的最大值是Integer.MAX_VALUE，而不是Long.MAX_VALUE。

其次，数组在Java中也是一个对象，在虚拟机中会创建一个数组对象出来，而Java的对象都有个对象头，数组的对象头布局如下，

|------------------------------------------------------------------------------------------|
|                                 Object Header (96/192 bits)                              |
|-----------------------------------|--------------------------|---------------------------|
|        Mark Word(32/64bits)       |    Klass Word(32/64bits) |  array length(32/64bits)  |
|-----------------------------------|--------------------------|---------------------------|

而JDK文档注释是这样说的：

 /**
     * The maximum size of array to allocate (unless necessary).
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

也就是说有些虚拟机是将数组长度放在数组对象的对象头的，而有些虚拟机是将数组长度放在数组实例数据里的，所以数组实例需要预留8个字节来保存自己的数组长度。所以数组的最大容量既可以是Integer.MAX_VALUE也可以是Integer.MAX_VALUE - 8。

注释也说了实际使用中尝试分配这么大的数组可能会导致OOM。

trimToSize

当ArrayList经过多次扩容后，capacity可能会比实际size 大的多，为了节省空间，trimToSize将capacity裁剪到当前size大小。

public void trimToSize() {
  modCount++;
  if (size < elementData.length) {
    elementData = (size == 0)
      ? EMPTY_ELEMENTDATA
      : Arrays.copyOf(elementData, size);
  }
}

Iterator

迭代器内部有一个属性：expectedModCount，在创建迭代器时，将当前集合的modCount赋值给属性expectedModCount

private class Itr implements Iterator<E> {
       int cursor;       // index of next element to return
       int lastRet = -1; // index of last element returned; -1 if no such
       int expectedModCount = modCount;
       ...
}

然后在使用迭代器进行集合元素迭代操作next、remove、forEach遍历时都会检测当前的modCount和expectedModCount是否相等，不等则会抛出运行时异常：ConcurrentModificationException，表示在遍历时集合被外部修改了。

final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

如果要在遍历时删除集合元素，可以使用Iterator的remove方法，它会在删除元素之后更新iterator的expectedModCount属性。

public void remove() {
  if (lastRet < 0)
    throw new IllegalStateException();
  checkForComodification();

  try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    lastRet = -1;
    expectedModCount = modCount;
  } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
  }
}

forEach

forEach遍历，会在每次执行forEach的Consumer函数接口方法前检测在forEach操作之外集合是否有结构性修改，即使是通过Iterator修改，forEach遍历也会抛出ConcurrentModificationException异常。

public void forEach(Consumer<? super E> action) {
  Objects.requireNonNull(action);
  final int expectedModCount = modCount;
  final Object[] es = elementData;
  final int size = this.size;
  for (int i = 0; modCount == expectedModCount && i < size; i++)
    action.accept(elementAt(es, i));
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

举例如下将会在forEach中抛出并发修改异常。

ArrayList list = new ArrayList ();
list.add ( 1.2 );
list.add ( "1.3" );
list.add ( NaN );
list.add ( null );
list.add ( 1 );
list.add ( true );
list.add ( new Exception ("exp") );
list.add ( Class.class );
new Thread (() -> {
  Iterator<Object> listItr = list.iterator ();
  while (listItr.hasNext ()) {
    try {
      Thread.sleep ( 500 );
    } catch (InterruptedException e) {
      e.printStackTrace ();
    }
    Object next = listItr.next ();
    if (next instanceof  Integer) {
      listItr.remove ();
    }
  }
}).start ();
list.forEach ( (element) -> {
  try {
    Thread.sleep ( 1000 );
  } catch (InterruptedException e) {
    e.printStackTrace ();
  }
  System.out.println ("list value: " + element);
} );

线程安全List

ArrayList和LinkedList都不是线程安全的，在多线程环境下需要进行同步。JDK提供了一个同步工具类SynchronizedList可以既对ArrayList和LinkedList进行同步。那SynchronizedList和Vector又有什么区别呢？

只从同步上来看，区别是：

SynchronizedList可以自己指定锁对象，而Vector不行。
SynchronizedList没有对listIterator方法进行加锁，所以通过listIterator对封装的List进行修改时需要手动加锁。

另外CopyOnWriteArrayList基于COW机制实现了线程安全，应用于读多写少的场景，因为在写时会进行数组的拷贝，如果读写都很频繁的场景则不适合。