ArrayList源代码分析

此篇主要解析 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<size; 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) {
    rangeCheckForAdd(index);// 检查index是否合理，比如说超出当前size以及小于0
    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;//返回之前的值
}

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