## ArrayList [TOC] ### 1. 概览 实现了 RandomAccess 接口，因此支持随机访问，这是理所当然的，因为 ArrayList 是基于数组实现的。 ```java public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable ``` 数组的默认大小为 10。 ```java private static final int DEFAULT_CAPACITY = 10; ```  ### 2. 序列化 基于数组实现，保存元素的数组使用 transient 修饰，该关键字声明数组默认不会被序列化。ArrayList 具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。ArrayList 重写了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。 ```java transient Object[] elementData; // non-private to simplify nested class access ``` ### 3. 扩容 添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 `oldCapacity + (oldCapacity >> 1)`，也就是旧容量的 1.5 倍。 扩容操作需要调用 `Arrays.copyOf()` 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。 ```java // JDK 1.8 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! 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) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } // 扩容 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍 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) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } ``` ### 4. 删除元素  需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上。 ```java public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); //复制的个数 int numMoved = size - index - 1;//删除23，则后面的元素的位置index 7 8 9，所以需要3个 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved);//numMoved代表需要复制几个！ elementData[--size] = null; // clear to let GC do its work return oldValue; } ``` ### 5. Fail-Fast **开始之前我们想讲讲，什么是 fail-fast 机制?** fail-fast 机制在遍历一个集合时，当集合结构被修改，会抛出 Concurrent Modification Exception。 fail-fast 会在以下两种情况下抛出 Concurrent Modification Exception （1）单线程环境 - 集合被创建后，在遍历它的过程中修改了结构。 - 注意 remove() 方法会让 expectModcount 和 modcount 相等，所以是不会抛出这个异常。 （2）多线程环境 - 当一个线程在遍历这个集合，而另一个线程对这个集合的结构进行了修改。 modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指**添加**或者**删除**至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。 在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 Concurrent Modification Exception。 ```java private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } ```