Java集合 - ArrayList源码阅读笔记

说明

本文内容为本人平时学习时的笔记，是参考了网上、书上以及源码（基于JDK1.8）等资料结合自己的学习方式的总结；如若有不对的地方也欢迎指正。

关系

ArrayList关系图（蓝色实线为继承、绿色虚线为实现、绿色实线为接口继承）

大概

ArrayList继承自AbstractList，实现了List、RandomAccess、Cloneable、Serializable

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

ArrayList是实现了基于动态数组的数据结构，容量可以进行动态的增长，实现List接口，具有List的特性

List关注的是索引，拥有一系列和索引相关的方法，查询速度快。也正因为此，在插入或删除数据时，会伴随着后面数据的移动，所以插入删除数据速度慢。

实现RandomAccess接口，支持快速随机访问
实现Cloneable接口，支持浅克隆
实现Serializable接口，支持序列化

成员变量

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

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

/** 默认初始容量的空数组（用于不指定容量创建实例时使用，与EMPTY_ELEMENTDATA做区分） */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** 
*  用于存放ArrayList数据的数组 
*  使用transient修饰使得该关键字声明数组默认不会被序列化（原因后面单独做说明）
*/
transient Object[] elementData;

/** 长度即实际数据的数量 */
private int size;

/** 继承自AbstractList的成员变量，用于记录更改次数 */
protected transient int modCount = 0;

构造

构造方法总有有三个：无参构造、指定容量大小、带Collection形参的构造

无参构造直接将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

构造一个指定容量大小的ArrayList，构造时传入一个int类型的容量大小，在创建时会先判断传入的值是否为0，不为0则直接将elementData初始化一个容量为initialCapacity的数组，为0则直接将EMPTY_ELEMENTDATA赋值给elementData

/** 指定大小初始化，通过initialCapacity来指定初始ArrayList容量大小 */
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);
      }
}

将Collection类型的集合作为参数来构造ArrayList，调用c.toArray()，将集合转换为数组并赋值给elementData
不过源码中有这么一句注释：
// c.toArray might (incorrectly) not return Object[] (see 6260652)
参考Java官方Bug文档，大致意思就是：Arrays.asList()是将数组转换为集合的一种方法，但是其内部对toArray方法的实现与集合中不一样，不能保证返回的一定是Object[]类型（例如创建String类型的时候），简单说就是Arrays内部类ArrayList中的toArray实现与ArrayList中的不一样，所以就有了对elementData类型的判断
不过在1.9中已经修复了这个问题

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

常用API方法

增加 add
在了解add方法之前，我们需要先了解一下ArrayList的扩容机制

ArrayList的扩容机制
在两个add方法中，首先都会调用ensureCapacityInternal(size + 1);这个方法来确保容量始终满足当前的要求。先看下源码中的内容

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

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

private 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_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

在ensureCapacityInternal方法中，首先会判断当前elementData是否是无参构造是时赋值的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果是，则在DEFAULT_CAPACITY（默认大小，也就是10）与minCapacity（size + 1）中取最大值进行下一步操作。到这可能会有一个疑问，都确定是第一次无参创建时elementData，为什么还要进行最大值的比较而不直接给一个10，源码搜索ensureCapacityInternal时，会发现调用这个方法的不只是add，还有addAll，当调用addAll的时候，传入的是一个Collection的集合，传入的minCapacity是Collection的length+ArrayList的size，所以是有minCapacity > DEFAULT_CAPACITY的可能存在的。
接着会调用ensureExplicitCapacity方法，比较minCapacity和elementData.length的大小来判断是否需要进行扩容。（需要注意的是用于比较的是elementData.length而不是size，elementData.length是底层数组的容量，而size是ArrayList的容量。）
接下来就是gow方法就是动态扩容的核心了。
首先获取elementData的长度所谓原始容量oldCapacity，然后计算一个扩容后的容量（原始容量 + （原始容量向右位移1位后的容量）），也就是原始容量的1.5倍作为新容量newCapacity，接着比较新容量与需要容量大小，把两者中最大者赋值给newCapacity。最后再进行newCapacity与MAX_ARRAY_SIZE进行比较，这里有一个常量MAX_ARRAY_SIZE具体为值：Integer.MAX_VALUE - 8 数组

获取 get
删除 remove
更新 set
是否包含 indexof/contains
容量判断 size/isEmpty

并发修改异常ConcurrentModificationException

ArrayList中有一个继承制AbstractList的成员变量modCount，它的作用主要就是一个计数器，用于记录集合被修改的次数。
在线程不安全的ArrayList使用迭代器（Iterator）的过程中，如果其他线程修改了ArrayList中的数据，就会报ConcurrentModificationException（并发修改异常），这就是所谓的fail-fast机制；同时需要注意的是，该异常不会始终指出对象已经由不同线程并发修改，如果单线程违反了规则，同样也有可能会抛出该异常。
在使用Iterator进行遍历的过程中，如果使用List的remove方法删除元素，会报并发修改异常也是这个原因；在ArrayList内部实现的Iterator中的next方法和remove方法中，首先都需要执行checkForComodification方法用于校验迭代器中的modCount值是否与ArrayList中的值相同，不相同则报并发修改异常；而使用迭代器自身的remove方法时，会调用ArrayList自身的remove方法进行删除操作同时更新modCount值，并且同时更新迭代器的modCount（expectedModCount）值，这就是为什么使用迭代器删除不会报并发修改异常。

Java集合 - ArrayList源码阅读笔记

说明

关系

大概

成员变量

构造

常用API方法

并发修改异常ConcurrentModificationException

ArrayList中的坑