省流

1. 类的声明

  1. public class ArrayList<E> extends AbstractList<E>
  2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  1. ArrayList继承自AbstractList；实现了List接口。
  2. 实现了RandomAccess接口，支持随机访问随机读取，对于能够用索引实现数据的查询修改需要实现该接口。
  3. 实现Cloneable接口，支持克隆。

  4. 实现Serializable接口，支持序列化。

    2. 成员变量

    ```java /**

    • Default initial capacity. */ // 初始容量，默认扩容阈值 private static final int DEFAULT_CAPACITY = 10;

      /**

    • Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {};

      /**

    • Shared empty array instance used for default sized empty instances. We
    • distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when

    • first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

      /**

    • The array buffer into which the elements of the ArrayList are stored.
    • The capacity of the ArrayList is the length of this array buffer. Any
    • empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    • will be expanded to DEFAULT_CAPACITY when the first element is added. / /
      1. transient: 不能序列化;
      1. 实现了Serializable接口，主题数组elementData却又不支持序列化；ArrayList重写了序列化接口 */ transient Object[] elementData; // non-private to simplify nested class access

      /**

    • The size of the ArrayList (the number of elements it contains). *
    • @serial */ private int size;
  2. 1. `_DEFAULT_CAPACITY _`_:_ 数组默认扩容大小。（不一定第一次扩容就是10，具体原因后面详解）
  3. 1. `_DEFAULTCAPACITY_EMPTY_ELEMENTDATA_ `和 `_EMPTY_ELEMENTDATA_`_：_默认初始化的时候的两个空数组，具体用哪个，有条件。（这里和1中的扩容也有关系）
  4. 1. `transient Object[] elementData;` ：这个就是ArrayList底层的数组。（为什么要用transient修饰？既然支持序列化，但数组对象缺用不可序列化关键字修饰）
  5. 1. `size`：数组的元素个数，不是当前的容量。
  6. <a name="pjvPM"></a>
  7. # 3. 构造方法
  8. ```java
  9. public ArrayList(int initialCapacity) {
  10.     if (initialCapacity > 0) {
  11.         this.elementData = new Object[initialCapacity];
  12.     } else if (initialCapacity == 0) {
  14.         this.elementData = EMPTY_ELEMENTDATA;
  15.     } else {
  16.         throw new IllegalArgumentException("Illegal Capacity: "+
  17.                                            initialCapacity);
  18.     }
  19. }
  1. 带参构造，参数为设定初始容量大小。

  2. 由else if语句中可知，当带参构造的参数为0的时候，用到了两个空数组中的_EMPTY_ELEMENTDATA_，这里直接影响到了后面的扩容方法。（详情参见:ensureCapacityInternal方法）

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

  3. 这里就是直接给elementData赋值为_DEFAULTCAPACITY_EMPTY_ELEMENTDATA_

    4. 关键方法（常考）

    4.1 trimToSize()

    该方法，节约内存空间设置的，相当于手动回收内存。

    4.2 扩容

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

    1.  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    2.      return Math.max(DEFAULT_CAPACITY, minCapacity);
    3.  }
    4.  return minCapacity;

    }

    private void ensureCapacityInternal(int minCapacity) {

    1.  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

    }

    private void ensureExplicitCapacity(int minCapacity) {

    1.  // 和快速失败相关，在AbstractList中
    2.  modCount++;
    4.  // overflow-conscious code
    5.  if (minCapacity - elementData.length > 0)
    6.      grow(minCapacity);

    }

    /**

    • The maximum size of array to allocate.
    • 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;

      /**

    • 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; // 移位运算右移一位，等于除二取整。所以扩容大小约等于1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0)

      1.  newCapacity = minCapacity;

      if (newCapacity - MAX_ARRAY_SIZE > 0)

      1.  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

      1.  throw new OutOfMemoryError();

      return (minCapacity > MAX_ARRAY_SIZE) ?

      1.  Integer.MAX_VALUE :
      2.  MAX_ARRAY_SIZE;

      }

```

  1. add方法会先执行ensureCapacityInternal方法，传入的参数是当前数组元素个数+1

（size+1（minCapacity 当前所需的最小容量））；

  1. ensureCapacityInternal中会进行一次calculateCapacity，
    1. 如果当前的elementData是_DEFAULTCAPACITY_EMPTY_ELEMENTDATA_则calculateCapacity会比较minCapacity和_DEFAULT_CAPACITY_，返回两者中的大值。所以，无参构造，第一次扩容后的容量为_DEFAULT_CAPACITY_。
    2. 如果当前的elementData是_EMPTY_ELEMENTDATA_（有参构造，传入参数0时），则calculateCapacity会直接返回minCapacity。
  2. 当minCapacity大于elementData.length时，走扩容方法void grow(int minCapacity)。
    1. 扩容大小大约为elementData.length的1.5倍oldCapacity + (oldCapacity >> 1);这里做了移位运算，右移一位等于除以2向下取整。移位运算对计算机来说更快。
    2. elementDate的最大长度为Integer._MAX_VALUE _- 8 减8是为了存储数组长度；
    3. Arrays._copyOf_方法待补充

  3. 经过上面分析可知，如果ArrayList的构造参数为0时，扩容方法就会按每次1.5倍进行扩容。这时候，在数组中添加10个元素，就会进行7次扩容！！！

    4.3 修改方法

  4. 插入删除操作时，有数组的移位。JDK里面都是用的public static native void arraycopy(Object src, int srcPos,Object dest, int destPos, int length);方法来实现，说明在生产时，大List拷贝操作，可以考虑使用该方法。

  5. public E set(int index, E element)set（remove也一样）方法是有返回值的，返回值为该位置上的被替换元素（oldValue）；
  6. public E remove(int index)remove方法中，删除元素后会进行一次elementData[--size] = null;操作，目地时为了让JVM进行GC。
  7. public void clear()clear方法，只是在吧elementData所有位置置为null，并没有重置elementData，所以当一个List在clear之后，重新添加元素执行add，在超过原有容量前不会进行扩容。

  8. public boolean removeAll(Collection<?> c)方法第一行对参数c使用Objects._requireNonNull_(c);进行null值判断，但是没有判空，所以如果是空的参数c，则会走batchRemove方法判断一次，有性能损耗。

    4.4 序列化

  9. private void writeObject(java.io.ObjectOutputStream s)

    1. elementData被transient修饰不能被序列化，这里是通过for循环一个一个进行序列化的；
    2. ArrayList的扩容是1.5倍扩容；当扩容后如果直接进行序列化，会有空元素进行序列化，会有两个问题
      1. 浪费空间；
      2. 需要考虑空元素的序列化问题。
    3. if (modCount != expectedModCount) 在多线程情况下，有修改时序列化失败。（多线程在该list的改操作，优先级大于序列化操作。）

      5. 其他小技巧

      5.1 Arrays.asList()

  10. Arrays 内部实现了一个私有ArrayList类，所以可以用List接收；

  11. 但是Arrays 的私有ArrayList类没有重写父类（AbstractList）的add方法。导致直接调用父类（AbstractList）中的add方法：throw new UnsupportedOperationException();

  12. 在List的大小不再改变的场景下（不再增加和减少），使用Arrays.asList()；因为它没有add 和 remove方法，确保数组大小不会改变。

    5.2 Collections.emptyList();

  13. 这块代码的使用场景是：当有需要返回空List的时候；

  14. 因为：Collections._emptyList_();无需进行新对象的创建；JVM再进行编译的时候已经对final关键字的对象进行了创建。 public static final <T> List<T> emptyList()