Java源码之ArrayList分析

一、ArrayList简介

ArrayList底层的数据结构是数组，数组元素类型为Object类型，即可以存放所有类型数据。

与Java中的数组相比，它的容量能动态增长。当创建一个数组的时候，就必须确定它的大小，系统会在内存中开辟一块连续的空间，用来保存数组，因此数组容量固定且无法动态改变。ArrayList在保留数组可以快速查找的优势的基础上，弥补了数组在创建后，要往数组添加元素的弊端。实现的基本方法如下：

快速查找：在物理内存上采用顺序存储结构，因此可根据索引快速的查找元素。
容量动态增长：当数组容量不够用时，创建一个比原数组容量大的新数组(1.5倍)，将数组中的元素“搬”到新数组，再将新的元素也放入新数组，最后将新数组赋给原数组即可。

二、源码分析

1、继承结构

ArrayList结构图如下：

public class ArrayList<E>

  extends AbstractList<E>

  implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList实现的接口：

List接口：ArrayList的父类AbstractList也实现了List接口，ArrayList还去实现？这是一个是mistake，作者写这代码的时候觉得会有用处，但是其实并没什么用，就一直保留着。说法来源自：https://www.cnblogs.com/zhangyinhua/p/7687377.html
RandomAccess接口：这个是一个标记性接口，它的作用就是用来快速随机存取，有关效率的问题，在实现了该接口的话，那么使用普通的for循环来遍历，性能更高，例如arrayList。
Cloneable接口：实现了该接口，就可以使用Object.Clone()方法。
Serializable接口：实现该序列化接口，表明该类可以被序列化，能够从类变成字节流传输，然后还能从字节流变成原来的类。

2、构造方法与属性

ArrayList中的属性如下：

public class ArrayList<E>

  extends AbstractList<E>

  implements List<E>, RandomAccess, Cloneable, Serializable{

  // 版本号

  private static final long serialVersionUID = 8683452581122892189L;

  // 默认容量

  private static final int DEFAULT_CAPACITY = 10;

  // 空对象数组

  private static final Object[] EMPTY_ELEMENTDATA = new Object[0];

  // 默认缺省空对象数组

  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];

  // 元素数组

  transient Object[] elementData;

  // 数组大小，默认0

  private int size;

  // 最大数组容量 值为Integer.MAX_VALUE - 8

  private static final int MAX_ARRAY_SIZE = 2147483639;

  }

ArrayList中有三种构造方法：

public ArrayList(){

    // 空的Object[]

    elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

// 根据paramInt创建ArrayList,若知道ArrayList大小，建议使用此构造方法，节省数组扩容拷贝的时间

public ArrayList(int paramInt){

    if (paramInt > 0) {

        elementData = new Object[paramInt];

    } else if (paramInt == 0) {

        elementData = EMPTY_ELEMENTDATA;

    } else {

        throw new IllegalArgumentException("Illegal Capacity: " + paramInt);

    }

}

public ArrayList(Collection<? extends E> paramCollection) {

    elementData = paramCollection.toArray();

    if ((size = elementData.length) != 0) {

        //每个集合的toarray()的实现方法不一样，需要判断一下，若不是Object[].class类型，就需要使用ArrayList中的方法去改造一下

        if (elementData.getClass() != Object[].class) {

            elementData = Arrays.copyOf(elementData, size, Object[].class);

        }

    }

    else {

        elementData = EMPTY_ELEMENTDATA;

    }

}

3、核心方法

3.1、插入数据方法

1）、单个插入

add(E)方法用于在数组末尾添加元素

public boolean add(E paramE){

    //确定数组大小

    ensureCapacityInternal(size + 1);

    //末尾添加数据

    elementData[(size++)] = paramE;

    return true;

}

ensureCapacityInternal(int paramInt)用于确定数组大小

private void ensureCapacityInternal(int paramInt){

    //数组为空数组，比较10与传入值大小，10为初次添加数据默认数组大小

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

        paramInt = Math.max(10, paramInt);

    }

    //确认容量，判断数组是否够用

    ensureExplicitCapacity(paramInt);

}

ensureExplicitCapacity判断若数组长度不够，增加数组长度

private void ensureExplicitCapacity(int paramInt){

    //注意：这里在后面说到

    modCount += 1;

    //当第一次add时，paramInt为1，此时数组设置默认长度为10

    //当多次add判断数组长度不够时，进行数组扩容操作

    if (paramInt - elementData.length > 0) {

        //数组扩容

        grow(paramInt);

    }

}

grow()是ArrayList自动扩展大小的核心方法。

private void grow(int paramInt){

    //扩容前数组大小

    int i = elementData.length;

    //扩容为原来的1.5倍

    int j = i + (i >> 1);

    if (j - paramInt < 0) {

        //适用于数组为空时，此处真正初始化数组的长度为10

        j = paramInt;

    }

    if (j - 2147483639 > 0) {

        //扩容后数组超出容量限制，将能给的最大值给数组

        j = hugeCapacity(paramInt);

    }

    //容量大小确定，copy数组

    elementData = Arrays.copyOf(elementData, j);

}

hugeCapacity赋数组最大值，ArrayList中默认的数组最大为：2147483639即为Integer.MAX_VALUE-8

private static int hugeCapacity(int paramInt){

    if (paramInt < 0) {

        throw new OutOfMemoryError();

    }

    //扩大数组容量到最大

    return paramInt > 2147483639 ? Integer.MAX_VALUE : 2147483639;

}

add(int, E)方法用于在指定位置插入元素

public void add(int paramInt, E paramE){

    //检查插入位置是否合适

    rangeCheckForAdd(paramInt);

    //确定数组大小,同上

    ensureCapacityInternal(size + 1);

    //在插入元素之后，要将paramInt之后的元素都往后移一位

    System.arraycopy(elementData, paramInt, elementData, paramInt + 1, size - paramInt);

    //目标位置存放元素

    elementData[paramInt] = paramE;

    //size增加

    size += 1;

}

rangeCheckForAdd()用于检查插入位置

private void rangeCheckForAdd(int paramInt){

    if ((paramInt > size) || (paramInt < 0)) {

        //数组越界异常

        throw new IndexOutOfBoundsException(outOfBoundsMsg(paramInt));

    }

}

arraycopy用于将指定位置之后的元素都后移一位

/*参数 :

src - 源数组。

srcPos - 源数组中的起始位置。

dest - 目标数组。

destPos - 目的地数据中的起始位置。

length - 要复制的数组元素的数量。

更多说明参见Java api文档

*/

public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length)

2）、批量插入

addAll(Collection<? extends E> paramCollection)用于末尾批量添加数据

public boolean addAll(Collection<? extends E> paramCollection){

    Object[] arrayOfObject = paramCollection.toArray();

    int i = arrayOfObject.length;

    //确定数组大小,同上

    ensureCapacityInternal(size + i);

    System.arraycopy(arrayOfObject, 0, elementData, size, i);

    size += i;

    return i != 0;

}

addAll(int, Collection<? extends E>)方法用于在指定位置批量添加数据

public boolean addAll(int paramInt, Collection<? extends E> paramCollection){

    //检查插入位置

    rangeCheckForAdd(paramInt);

    Object[] arrayOfObject = paramCollection.toArray();

    int i = arrayOfObject.length;

     //确定数组大小,同上

    ensureCapacityInternal(size + i);

    int j = size - paramInt;

    if (j > 0) {

        System.arraycopy(elementData, paramInt, elementData, paramInt + i, j);

    }

    //指定位置插入数据

    System.arraycopy(arrayOfObject, 0, elementData, paramInt, i);

    size += i;

    return i != 0;

}

3.2、删除数据方法

1）、remove(int)

删除指定位置的元素

remove函数在移除指定下标的元素，此时会把指定下标到数组末尾的元素向前移动一个单位，并且会把数组最后一个元素设置为null，让gc(垃圾回收机制)更快的回收

public E remove(int paramInt){

    //检查下标合理性

    rangeCheck(paramInt);

    //注意：这里在后面说到

    modCount += 1;

    //通过索引获取元素

    Object localObject = elementData(paramInt);

    //计算要移动的位数

    int i = size - paramInt - 1;

    if (i > 0) {

        //复制数据

        System.arraycopy(elementData, paramInt + 1, elementData, paramInt, i);

    }

    //将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收

    elementData[(--size)] = null;

    //返回删除元素

    return (E)localObject;

}

下标大于数组大小报越界异常

private void rangeCheck(int paramInt){

    if (paramInt >= size) {

        throw new IndexOutOfBoundsException(outOfBoundsMsg(paramInt));

    }

}

2）、remove(Object)

注意，在这个方法中知道arrayList可以存null

public boolean remove(Object paramObject){

    int i;

    if (paramObject == null) {

        for (i = 0; i < size; i++) {

            if (elementData[i] == null)

            {

                fastRemove(i);

                return true;

            }

        }

    } else {

        for (i = 0; i < size; i++) {

            if (paramObject.equals(elementData[i]))

            {

                fastRemove(i);

                return true;

            }

        }

    }

    return false;

}

fastRemove与remove实现类似，fastRemove为私有方法，主要提供remove(Object)这个方法使用

private void fastRemove(int paramInt){

    //注意：这里在后面说到

    modCount += 1;

    int i = size - paramInt - 1;

    if (i > 0) {

        System.arraycopy(elementData, paramInt + 1, elementData, paramInt, i);

    }

    elementData[(--size)] = null;

}

3）、removeAll(collection)

此方法用于批量删除

public boolean removeAll(Collection<?> paramCollection){

    //paramCollection判空

    Objects.requireNonNull(paramCollection);

    //用于两个方法，removeAll()指定清除集合中的元素，retainAll()测试两个集合是否有交集。　

    return batchRemove(paramCollection, false);

}

public static <T> T requireNonNull(T paramT){

    if (paramT == null) {

        throw new NullPointerException();

    }

    return paramT;

}

//complement为true用于retainAll()，false用于removeAll()

private boolean batchRemove(Collection<?> c, boolean complement) {

    final Object[] elementData = this.elementData;

    //r控制循环、w统计交集

    int r = 0, w = 0;

    boolean modified = false;

    try {

        for (; r < size; r++)

            //数组中不包含原数组指定位置的数据时，就将原数组的r位置的数据覆盖掉w位置的数据，r位置的数据不变，并其w自增，r自增;否则，r自增，w不自增

            //把需要移除的数据都替换掉，不需要移除的数据前移

            if (c.contains(elementData[r]) == complement)

                elementData[w++] = elementData[r];

    } finally {

        // Preserve behavioral compatibility with AbstractCollection,

        // even if c.contains() throws.

        //如果contains方法使用过程报异常,将剩下的元素都赋值给集合elementData

        if (r != size) {

            System.arraycopy(elementData, r,elementData, w,size - r);

            w += size - r;

        }

        //在removeAll()时，w一直为0，就直接跟clear一样，全是为null

        if (w != size) {

            // clear to let GC do its work

            for (int i = w; i < size; i++)

                //方便GC

                elementData[i] = null;

            //注意：这里在后面说到

            modCount += size - w;

            size = w;

            modified = true;

        }

    }

    return modified;

}

clear是将数组元素置为null，等待垃圾回收机制处理

public void clear(){

    modCount += 1;

    for (int i = 0; i < size; i++) {

        elementData[i] = null;

    }

    size = 0;

}

3.3、查找数据方法

set(int,E)设定指定下标索引的元素值

public E set(int paramInt, E paramE){

    //校验下标合法

    rangeCheck(paramInt);

    Object localObject = elementData(paramInt);

    elementData[paramInt] = paramE;

    return (E)localObject;

}

get(int)获取指定下标的元素

//

public E get(int paramInt){

     //校验下标合法

    rangeCheck(paramInt);

    return (E)elementData(paramInt);

}

E elementData(int paramInt){

    // 返回的值都经过了向下转型（Object -> E）

    return (E)elementData[paramInt];

}

从头开始查找数组里面是否存在指定元素

public int indexOf(Object paramObject){

    int i;

    //可为null或元素

    if (paramObject == null) {

        //遍历数组找到第一个null元素，返回下标

        for (i = 0; i < size; i++) {

            if (elementData[i] == null) {

                return i;

            }

        }

    } else {

        //遍历数组找到第一个元素，返回下标

        for (i = 0; i < size; i++) {

            if (paramObject.equals(elementData[i])) {

                return i;

            }

        }

    }

    return -1;

}

注意：ArrayList中可以存放null元素，与此函数对应的lastIndexOf，表示从尾部开始查找

3.4、modCount说明

在前面注释中多次说到modCount，它是继承自AbstractList类中的一个属性

protected transient int modCount = 0;

api中对它的描述是：

此列表已被结构修改的次数。结构修改是改变列表大小的那些修改，或以其他方式扰乱它，使得正在进行的迭代可能产生不正确的结果。
该字段由迭代器和列表迭代器实现使用，由iterator和listIterator方法返回。如果该字段的值意外更改，迭代器（或列表迭代器）将抛出一个ConcurrentModificationException响应next ， remove ， previous ， set或add操作。这提供了fail-fast行为，而不是面对在迭代期间的并发修改的非确定性行为

从上面的源码分析中可以发现，add,remove,clear等方法实现时，均添加了modCount++;而在在arraylist的迭代器是通过内部类实现的，在这个内部类中，同样维护了一个类似modCount的变量及检测方法：

int expectedModCount = modCount;

final void checkForComodification() {

    if (modCount != expectedModCount)

        throw new ConcurrentModificationException();

}

这个检测方法在迭代器中类似next方法里面作为首先需要判断的条件

public E next() {

    checkForComodification();

    int i = cursor;

    if (i >= size) {

        throw new NoSuchElementException();

    }

    Object[] arrayOfObject = elementData;

    if (i >= arrayOfObject.length) {

        throw new ConcurrentModificationException();

    }

    cursor = (i + 1);

    return (E)arrayOfObject[(lastRet = i)];

}

在使用迭代器遍历arrayList时，会初始化一个和modCount相等的变量，如果在迭代过程中，arraylist中发生了类似add这种改变结构的操作(modCount改变)，导致modCount != expectedModCount，那么会抛出一个异常ConcurrentModificationException，即产生fail-fast事件。

下面是多线程时fail-fast事件产生过程：

新建了一个ArrayList，名称为list，向list中添加内容。
新建一个“线程a”，并在“线程a”中通过Iterator反复的读取list的值。
新建一个“线程b”，在“线程b”中删除list中的一个“节点A”。

在某一时刻，“线程a”创建了list的Iterator。此时“节点A”仍然存在于list中，创建list时，expectedModCount = modCount(假设它们此时的值为N)。

在“线程a”在遍历list过程中的某一时刻，“线程b”执行了，并且“线程b”删除了list中的“节点A”。“线程b”执行remove()进行删除操作时，在remove()中执行了“modCount++”，此时modCount变成了N+1！

“线程a”接着遍历，当它执行到next()函数时，调用checkForComodification()比较expectedModCount和modCount的大小；而expectedModCount=N，modCount=N+1。这样，便抛出ConcurrentModificationException异常，产生fail-fast事件。

总结：modCount用于记录表结构的修改次数，当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)，此时会产生fail-fast事件，抛出ConcurrentModificationException异常。

参考了：

https://www.cnblogs.com/zhangyinhua/p/7687377.html

https://www.cnblogs.com/skywang12345/p/3308762.html

巴特西