此篇主要解析 ArrayList 的源码处理逻辑

继承关系

几个有意思的参数

// 默认初始容量private static final int DEFAULT_CAPACITY = 10;// 共享空数组private static final Object[] EMPTY_ELEMENTDATA = {};// 同上private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 指向实际存储数据的数组transient Object[] elementData;// 当前列表中所含元素的个数private int size;

为什么会有两个空数组

源代码中的解释：为了在添加第一个元素时，确定初始空间的大小。

此话怎讲？先从上述两变量的引用处说起。初始化一个 ArrayList 对象的构造函数有 3 个，分别如下

// 不带任何参数public ArrayList() {    // 当第一次添加元素时，元素个数小于10，初始容量置为10    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) {    elementData = c.toArray();    if ((size = elementData.length) != 0) {        // c.toArray might (incorrectly) not return Object[] (see 6260652)        if (elementData.getClass() != Object[].class)            elementData = Arrays.copyOf(elementData, size, Object[].class);    } else {        // replace with empty array.        this.elementData = EMPTY_ELEMENTDATA;    }}

可以看出，只有没有指明容量的情况下，才会使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。且在添加第一个元素时，会进行相应的判断，如果为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就会使用默认的容量 10。

public boolean add(E e) {  ensureCapacityInternal(size + 1);  elementData[size++] = e;  return true;}private void ensureCapacityInternal(int minCapacity) {  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  }  // 由此看来，初始化的容量会因为上述两个空数组的不同而不同  ensureExplicitCapacity(minCapacity);}

那为什么不能在 ArrayList() 中使用 EMPTY_ELEMENTDATA 呢？因为这样会与 ArrayList(int initialCapacity) 一样，但后者必须初始化成指定的容量，如 0。

为什么可以序列化却使用了transient修饰elementData

数组中所有的容量并非一直都被元素占用，可能会存在此数组大部分空间并未使用的情况，此时序列化所有的元素会比较浪费空间。因此在这里源码选择的是，将所有添加的元素，进行序列化。

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        s.writeObject(elementData[i]);    }    // ...}

对于new ArrayList()和new ArrayList(0)之间的差别是什么

添加第一个元素之后，容量不一样。

增加元素

增加元素到list当中，也就是我们常用的`add()`。有两种增加方式，一种是添加元素到尾端：

// 添加到列表的尾部public boolean add(E e) {    ensureCapacityInternal(size + 1);    // 此时elementData的长度已经被保证可以存下当前元素    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++;    //当前的minCapacity为size+1或10，所以当此条件成立时，说明再不扩容    //将有可能导致溢出    if (minCapacity - elementData.length > 0)        grow(minCapacity);}// 扩容private void grow(int minCapacity) {    // 防止溢出    int oldCapacity = elementData.length;    // 右移1位，变成一半，因此此时的容量变成了之前的1.5倍    int newCapacity = oldCapacity + (oldCapacity >> 1);    // 若新的容量比所需要的最小容量小，那么将新容量改成最小所需容量    if (newCapacity - minCapacity < 0)        newCapacity = minCapacity;    // 若新的容量比MAX_ARRAY_SIZE大    if (newCapacity - MAX_ARRAY_SIZE > 0)        newCapacity = hugeCapacity(minCapacity);    // 分配新的数组，并将原数据拷贝到其中    elementData = Arrays.copyOf(elementData, newCapacity);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private static int hugeCapacity(int minCapacity) {    // 此时已超过Integer.MAX_VALUE，变成负数，溢出    if (minCapacity < 0)    throw new OutOfMemoryError();    // 到这一步，有两个原因：    // 1. 通过扩容至原来的1.5倍，引起比MAX_ARRAY_SIZE大；    // 2. 此次加入的元素数量太多，以至于1.5倍的扩容也不能满足。    return (minCapacity > MAX_ARRAY_SIZE) ?    Integer.MAX_VALUE :// 此处为第二种情况    MAX_ARRAY_SIZE;// 此处为第一种情况}

一种是将元素添加元素到列表中的某一位置。

// 添加到列表中的某个位置public void add(int index, E element) {    // 检查index是否合理，比如说超出当前size以及小于0    rangeCheckForAdd(index);    // 如前所述    ensureCapacityInternal(size + 1);     // 将elementData中从index起的size-index个元素，依次拷贝到elementData中index+1起后续位置上        // 简而言之，就是从index位起，整体后移1位    System.arraycopy(elementData, index, elementData, index + 1, size - index);    // 复制到目标位置上        elementData[index] = element;    size++;}

删除元素

删除确定元素(删除最先加入的那个元素，如果存在的话)

public boolean remove(Object o) {    if (o == null) {// 为什么要做这个判断？为避免NullPointer        for (int index = 0; index < size; index++)            if (elementData[index] == null) {                fastRemove(index);                return true;            }    } else {        // 遍历全部元素，找到第一个相同的，将其删除        for (int index = 0; index < size; index++)            if (o.equals(elementData[index])) {            fastRemove(index);            return true;        }    }    return false;}private void fastRemove(int index) {    modCount++;    int numMoved = size - index - 1;    // 大于0说明：所删除的不是最后一项    // 因为其最多等于0，且为0时index为最后一项，即size - 1 == index.    if (numMoved > 0)// 从index+1项起，整体前移1位    System.arraycopy(elementData, index+1, elementData, index, numMoved);    elementData[--size] = null; //注意：此处置空的是最后一位。}

删除指定下标的元素

public E remove(int index) {    rangeCheck(index);//不要超过size    modCount++;    E oldValue = elementData(index);//先取出元素。为负数，如何处理？    int numMoved = size - index - 1;//计算其位置    if (numMoved > 0)        // 同前述        System.arraycopy(elementData, index+1, elementData, index, numMoved);    elementData[--size] = null; // 同前述    return oldValue;//返回所删除的元素}

批量删除元素

这两个函数的唯一差别在于传给batchRemove()的第二个参数，前者为false，后者为true。它们之间的差距，我们可以通过后续源码进行分析。

public boolean removeAll(Collection> c) {    Objects.requireNonNull(c);// 处理为null情况    return batchRemove(c, false);}public boolean retainAll(Collection> c) {    Objects.requireNonNull(c);// 处理为null情况        return batchRemove(c, true);}

批量处理删除

private boolean batchRemove(Collection> c, boolean complement) {  final Object[] elementData = this.elementData;// 指向当前list元素数组  int r = 0, w = 0;  boolean modified = false;  try {    for (; r < size; r++)    if (c.contains(elementData[r]) == complement)      elementData[w++] = elementData[r];      // 体现差距的地方，就在这里：对于elementData中的每个元素，      // complement为true：c中存在，则将其移动到最前端；c中不存在，略过。      //          为false：c中存在，略过；c中不存在，保留。  } finally {    // r未达到size，说明中途遇到错误    if (r != size) {      // 将r到size的元素，保存到w后面      System.arraycopy(elementData, r,      elementData, w,      size - r);      w += size - r;    }    // w未达到size，说明需要删除某些元素；==size说明，全部保留，不作处理。    if (w != size) {      // 从w位开始，到size-1，全部置为空      for (int i = w; i < size; i++)        elementData[i] = null;      modCount += size - w;      size = w;      modified = true;    }  }  return modified;}

清空列表

public void clear() {  modCount++;  for (int i = 0; i < size; i++)    elementData[i] = null;// 全部置空  size = 0;}

查询

public E get(int index) {  rangeCheck(index);  return elementData(index);}E elementData(int index) {  return (E) elementData[index];}

修改

public E set(int index, E element) {  rangeCheck(index);  E oldValue = elementData(index);  elementData[index] = element;//更新  return oldValue;//返回之前的值}

关键的一些操作，感觉已经摸得差不多了。其它的一些查询、更新，都比较简单。