ArrayList源码分析

ArrayList类的定义，父类及实现的接口：

1
2
3

public class ArrayList<E> extends AbstractList<E>

    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

继承AbstractList类，该类中实现了get，add，remove，clear，indexOf，lastIndexOf，和获取迭代器等方法，其中indexOf和lastIndexOf查找元素是用ListIterator实现的；
实现RandomAccess接口，该接口空的，即标记接口，那么它的作用是什么？

* Marker interface used by List implementations to indicate that

* they support fast (generally constant time) random access. The primary

* purpose of this interface is to allow generic algorithms to alter their

* behavior to provide good performance when applied to either random or

* sequential access lists.

* 以上是jdk官方文档的解释，即RandomAccess是List实现锁使用的标记接口，

* 用来表明其支持快速（通常是固定时间）随机访问。

* 此接口的主要目的是允许一般的算法更改其行为，

* 从而在将其应用到随机或连续访问列表时能提供良好的性能

RandomAccess 这个标记接口就是标记能够随机访问元素的集合，简单来说就是底层是数组实现的集合。更具体的可以看看这篇文章： https://juejin.im/post/5a26134af265da43085de060
实现了 Cloneable 接口，以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制。如果在没有实现 Cloneable接口的实例上调用 Object 的 clone 方法，则会导致抛出CloneNotSupportedException异常。
类通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。

扩容

数组的默认大小为10

1	private static final int DEFAULT_CAPACITY = 10;

添加元素时使用ensureCapacityInternal()方法来保证容量足够，如果不够时，需要使用grow()方法进行扩容，新容量的大小为oldCapacity + (oldCapacity >> 1) ，也就是旧容量的1.5倍。

扩容操作需要调用 Array.copyOf()把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建ArrayList对象时就指定大概容量大小，减少扩容操作的次数。

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

public void ensureCapacityInternal(int minCapacity){
    if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

public void ensureExplicitCapacity(int minCapacity){
    modCount++;
    //overflow-conscious code
    if(minCapacity - elementData.length > 0)
        grow(minCapacity);
}

public void grow(int minCapacity){
    //overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if(newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if(newCapacity - MAX_ARRAAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //minCapacity is usually close to size, so this is a win
    elementData = Arrays.copyOf(elementData, newCapacity);;
}

删除元素

需要调用System.arraycopy()将index+1后面的元素都复制到index位置上，该操作的时间复杂度为O(N)，可以看出ArrayList删除元素的代价是非常高的。

public E remove(int index){
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index -1;;
    if(numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved)
        elementData[--size] = null; //clear to let GC do its work
    return oldValue;
}

部分序列化

ArrayList基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。保存元素的数组elementData使用transient修饰，该关键词声明数组默认不会被序列化。
1
transient Object[] elementData; // non-private to simplify nested class access

ArrayList实现了writeObject()和readObject()来控制只序列化数组中有元素填充那部分内容

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.Exception{
    //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();
    }
}

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
        ensureCapacityInternal(size);

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

* 序列化时需要要使用`ObjectOutputStream`的`writeObject()`将对象转换为字节流并输出。而`writeObject()`方法在传入的对象存在`writeObject()`存在`writeObject()`的时候会去反射调用该对象的`writeObject()`来实现序列化。

* 反序列化使用的是`ObjectInputStream`的`readObject()`方法，原理类似。比如下面的例子，oos的`writeObject(list)`方法，传入的对象list存在自己的`writeObject()`方法，则反射调用list对象的`writeObject()`方法来实现部分序列化（有内容的数组部分）

  1
2
3
ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);

Fail-Fast

fail-fast，快速失败，是Java集合的一种错误检测机制。迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。详细可见： https://blog.csdn.net/chenssy/article/details/38151189
modCount用来记录ArrayList结构发生变化的次数，结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组大小，仅仅只是设置元素的值不算结构发生变化。
在进行序列化或者迭代等操作时，需要比较操作前后modCount是否改变，如果改变了需要抛出ConcurrentModificationException。
- toArray()异常问题
- ArrayList中提供了2个toArray()方法：
  1
  2
  Object[] toArray()
  <T> T[] toArray(T[] contents)
- 调用toArray()函数会抛出”java.lang.ClassCastException”异常，但是调用toArray(T[] contents)能正常返回T[]。toArray()会抛出异常是因为toArray()返回的是Object[]数组，将Object[]转换为其它类型（比如将Object[]转换为Integer[]）则会抛出”java.lang.ClassCastException”异常，因为java不支持向下转型。解决该问题的办法是调用T[] toArray(T[] contents)，而不是Object[] toArray()。