ArrayList那点事儿

java集合框架图：

Collection 接口下的 Queue接口，打算以后放到多线程那块分析，今天来分析下 ArrayList类

ArrayList

ArrayList集合是 java.util 包下最常用的集合类，它的继承结构如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

继承自AbstractList，实现了List、RandomAccess、Cloneable、Serializable接口，这里有个有意思的地方：

AbstractList已经实现了 List 接口，ArrayList 作为它的子类，自然也实现了 List 接口，为什么ArrayList 还要再去实现 List 接口呢？

关于这个网上众说纷纭，大家可以自行搜索下，我的看法是从 Java 基本语法上来讲，接口重复实现，完全没必要额。

属性

/**
 * 初始化默认容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 一个空数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 默认空数组，这玩意是 JDK1.8中加进来了，与上面的 EMPTY_ELEMENTDATA 有何区别呢？后面分析
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 存放元素的数组，用transient关键字修饰的好处？
 */
transient Object[] elementData; 

/**
 * ArrayList 集合中存放元素的个数
 */
private int size;

通过 ArrayList 的属性看出，它是基于数组实现的，elementData数组用于存放元素。

EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这两个都是空数组，原英文文档：

We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added. 意思就是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 与 EMPTY_ELEMENTDATA 的区别就是当添加第一个元素的时候知道如何扩容，这个其实在add(E e)方法的里有体现。

构造方法

无参构造

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

我们看到注释是这个方法初始化一个容量为10的 ArrayList，可是代码中明明只是把一个空数组赋值给 elementData，没初始化容量为10啊？当初看到这里时心里一阵 mmp，又骗我？后来耐着性子继续看完才明白原因所在。

有参构造

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);
    }
}

这个有参构造很简单，判断传入的参数如果大于0，就初始化一个长度是 initialCapacity 的数组给

elementData，如果 initialCapacity 等于0 则elementData 等于空数组，否则抛异常。

再看另一个有参构造:

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;
    }
}

传入一个 Collection 对象，并且泛型加以限定，将这个 Collection 对象先转为数组赋值给 elementData ，数组的长度赋值给 size，判断传入的 Collection 是否是个空集合，如果不是空集合，然后检查转化的类型，如果不是Object[] 类型，使用Arrays类中的copyOf方法进行复制，如果 Collection 是空集合，将空数组赋值给elementData。

add(E e)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

函数功能：将元素添加至 ArrayList 末尾，第一行调用ensureCapacityInternal(size + 1);函数，确保扩容，我们查看其源码：

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

其中 calculateCapacity(elementData, minCapacity) 函数计算 ArrayList 的容量，继续查看此函数：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

重点来了，在这个函数内部，先是判断 elementData 是否等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果相等就返回 DEFAULT_CAPACITY（值是10）和 minCapacity（值是size+1）的最大值，什么时候elementData 才等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA呢？就是上面提到 ArrayList的无参构造方法：

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

整体意思就是当我们调用 ArrayList 的无参构造方法新建一个 ArrayList 对象，这只是让 elementData 指向一个空数组，容量为0，当我们第一次添加元素时，则就用默认容量10来进行开辟空间，所以也解释了无参构造方法为什么会初始化一个默认容量是10的数组，这也是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的用途所在。

扩容

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

当添加元素后的容量大于elementData数组的长度时，会进行扩容：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果计算出的newCapacity扩展的过小。则应该至少扩张到所需的空间大小minCapacity
    // 比如原来的容量是1
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    /** newCapacity扩张的过大，如果过大，则用Integer.MAX_VALUE来代替,所以 ArrayList 的最大长度是	 *  Integer.MAX_VALUE
    */
    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);
}

由扩容源码知道每次扩容，容量变为原先的1.5倍，并伴随着数组的拷贝，拷贝数组会消耗一定的性能，所以当我们初始化一个 ArrayList 值时，尽量预估好自己的元素数量，初始化 ArrayList 的容量，以减少扩容时的数组拷贝。

add(int index, E element)

在某个索引处插入元素

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

它的实现是通过把原来 index和index 之后的元素向后挪移，新元素插入放置 index 位置，用到了数组拷贝。

ArrayList其他操作源码比较简单，不一一赘述了。

elementData 为何用 transient 关键字修饰？

我们知道一般情况下被 transient 关键字修饰的关键字是不能被序列化和反序列化的，elementData是存放集合元素的数组，在实际开发应用中证明 ArrayList 的数据是可以被序列化的，这是为什么呢？

writeObject和readObject方法

ArrayList 定义了writeObject和readObject方法:

在序列化过程中，如果被序列化的类中定义了writeObject 和 readObject 方法，虚拟机会试图调用对象类里的 writeObject 和 readObject 方法，进行用户自定义的序列化和反序列化。

如果没有这样的方法，则默认调用是 ObjectOutputStream 的 defaultWriteObject 方法以及 ObjectInputStream 的 defaultReadObject 方法。

用户自定义的 writeObject 和 readObject 方法可以允许用户控制序列化的过程，比如可以在序列化的过程中动态改变序列化的数值（如敏感信息）。

writeObject方法：

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();
    }
}

readObject 方法：

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

ArrayList实际上是动态数组，上面提到每次在放满以后会进行扩容，容量变为原先的1.5倍，例如原来数组的长度是200，都存放着元素，当添加第201个元素时，容量扩容为300，而实际只增加了一个元素，那另99处没有存任何元素，为了保证在序列化的时候只序列化 elementData 中实际添加的元素，ArrayList把元素数组设置为transient，当序列化和反序列化时通过调用 writeObject 方法和 readObject 方法只序列化/反序列化实际添加的元素，避免空间不必要的浪费。

细节 RandomAccess

一开始就提到，ArrayList实现了 RandomAccess 接口，实现这个接口后随即访问索引速度会很快，但是在遍历时采用迭代器遍历比较慢。

举例：

List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();

LinkedList 没有实现 RandomAccess 接口，那么遍历这两个集合应该选择更合适的方法提高性能。

遍历 ArrayList 使用 fori 这种方式，length提前计算出来，避免每次遍历都要重新计算，提高效率

for (int i = 0,length = arrayList.size();i < length; i++) {
	doSomthing...
}

遍历 LinkedList 可以使用 foreach 的方式，因为 foreach 是个语法糖，底层还是使用了迭代器 Iterator。

for (String str : linkedList) {
    doSomthing...
}

如果要遍历的对象是是 List，我们不知道具体的List有没有实现 RandomAccess 接口（可能是 ArrayList，也可能是 LinkedList），如果list数据量大，且要求性能的话，最好加个判断：

if(list instanceof RandomAccess){
    for (int i = 0,length = list.size();i < length; i++) {
		doSomthing...
    } 
}else{
    for (String str : list) {
		doSomthing...
    }
}

ArrayList 的 toString 方法是继承自 AbstractCollection 的( ArrayList 继承 AbstractList，AbstractList 继承

AbstractCollection)，但是源码中 toString 方法的遍历并没有判断集合是否实现 RandomAccess，而是直接使用迭代器遍历，这是不是不严谨呢？

public String toString() {
    Iterator<E> it = iterator();
    if (! it.hasNext())
        return "[]";

    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = it.next();
        sb.append(e == this ? "(this Collection)" : e);
        if (! it.hasNext())
            return sb.append(']').toString();
        sb.append(',').append(' ');
    }
}