集合类源码浅析のArrayList

源码分析路线图：

初级部分：ArrayList->LinkedList->Vector->HashMap(红黑树数据结构，如何翻转，变色，手写红黑树)->ConcurrentHashMap

中级部分：Spring->Spring MVC->Spring Boot->Mybatis核心类源码

高级部分：中间件源码（有生之年系列）

第一篇，从最简单的ArrayList入手分析

1、成员变量

集合的初始容量：

private static final int DEFAULT_CAPACITY = 10;

下面两个成员变量都是Object类型的空数组，区分在于变量名，是用于区别通过何种构造方法创建了ArrayList集合，后面会提到。

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

elementData用于存放集合中元素的数组（ArrayList的底层本质上也是数组）

为什么要用transient修饰？我们首先简单复习一下transient关键字的作用：

字段声明为 transient表示该字段不会被序列化，即在对象被序列化为字节流时，transient字段的值不会被包含在序列化结果中。在对象反序列化后，elementData 数组将恢复为 null。

transient Object[] elementData;

记录当前集合的大小

private int size;

2、构造方法

2.1、无参构造

将空数组赋值给成员变量的elementData：

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

2.2、有参构造一

参数部分：

int initialCapacity：数组的大小，范围从0到Integer的最大值。

使用该构造方法，会传递一个初始数组的大小，然后进行if判断。

分支一：传入的参数大于0，就创建一个长度为参数的空数组，赋值给成员变量的elementData。
分支二：传入的参数为0，就将空数组赋值给成员变量的elementData。
分支三：传入的参数小于0，抛出异常，数组的长度不可能为负数。

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

通过上面两种构造的分析，可以得出一个结论：成员变量EMPTY_ELEMENTDATA用于区分用户使用的是有参构造，但是传递的参数为0。DEFAULTCAPACITY_EMPTY_ELEMENTDATA代表用户使用的是无参构造。

2.3、有参构造二

参数部分：

Collection<? extends E> c：Collection及其子类集合。

首先会将传入的集合转换为数组并赋值给成员变量elementData。

然后进入条件判断：

分支一：将传入的集合转换为数组的长度赋值给成员变量size，如果不为0，就再次进入判断，检查 elementData 的实际类型是否为 Object[]。如果不是，就将其复制为一个新的 Object[] 类型的数组，并将其赋值给 elementData。
分支二：将空数组赋值给成员变量的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;
        }
    }

3、add方法

重点介绍两个重载的方法：方法一是将一个元素放入链表的末尾，方法二是将元素放入指定的下标：

3.1、add(E e)

首先会跳转到ensureCapacityInternal(size + 1); 方法：

分支一：

假设目前是通过无参构造或有参构造传递0实例化的ArrayList，此时的size应该为0，size+1=0+1 = 1。

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

        ensureExplicitCapacity(minCapacity);
    }

条件块满足，取得传入参数（1）和DEFAULT_CAPACITY（10）的最大值，赋值给参数minCapacity，然后再次跳转入ensureExplicitCapacity(minCapacity);方法：

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

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

modCount++;是其父类AbstractList 中的成员变量，用于记录并发修改次数（不能一边遍历集合一边增删元素，否则会抛出并发修改异常。如果需要，请使用迭代器遍历）

然后会进入条件块。10-0>0，进入最关键的grow(minCapacity); 扩容方法，传入参数10：

    private void grow(int minCapacity) {
        //0
        int oldCapacity = elementData.length;
        //0
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //0-10 = -10 <0
        if (newCapacity - minCapacity < 0)
            //10
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //扩容成一个长度为10的新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

扩容使用了Arrays.copyOf(elementData, newCapacity); 方法，将原有数组中的元素复制到一个长度为10的新数组中，然后重新赋值给elementData。（也就是此时的elementData是一个长度为10的空数组）

然后回到add(E e)方法的elementData[size++] = e; 这一行，将元素赋值给elementData的第0索引的元素，然后size+1。（数组的长度为1，元素在0索引上，复习一下，数组的最大下标等于长度-1）

上述过程，证明了ArrayList的扩容时机是在加入第一个元素前进行扩容，然后才会加入元素。

分支二：

假设目前集合中已经有了10个元素，现在调用add(E e)添加第11个元素：

同样首先进入ensureCapacityInternal(int minCapacity)方法，参数为size + 1 = 10 + 1 = 11。

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

        ensureExplicitCapacity(minCapacity);
    }

这时的条件就不满足了，直接进入ensureExplicitCapacity(minCapacity) 方法：

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

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

11 - 10 = 1 > 0，条件块满足，进入grow(minCapacity); 扩容方法，传入参数11：

  private void grow(int minCapacity) {
        //10
        int oldCapacity = elementData.length;
        //10 + 10 / 2 = 15
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //15 - 10 = 5 > 0 条件不满足
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //条件也不满足
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

扩容同样使用Arrays.copyOf(elementData, newCapacity); 方法，将原有数组中的元素复制到一个长度为15的新数组中，然后重新赋值给elementData。（也就是此时的elementData是一个长度为15的数组。注意，此时数组中还是只有10个元素，最新的一个仍未添加）

然后回到add(E e)方法的elementData[size++] = e; 这一行，将元素赋值给elementData的第10个索引的元素，然后size+1。

上述过程，证明了ArrayList的扩容机制是，首次添加元素前扩容为10，以后都是扩容为旧容量的1.5倍。

并且元素是放在链表的末尾。

最后值得一提的是，ArrayList并不是无限制扩容，最大容量为Integer的长度。详见hugeCapacity(int minCapacity) 方法，逻辑很简单，有兴趣的请自己研究下！

3.2、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++;
    }

rangeCheckForAdd(index)方法用于检查数组下标越界异常。

ensureCapacityInternal(size + 1) 方法用于判断是否扩容，并执行扩容逻辑，不再重复说明。

System.arraycopy(elementData, index, elementData, index + 1,size - index) 是实现将元素添加到指定索引的前置工作，将 elementData 数组中从索引 index 开始到末尾的元素向右移动一个位置，为在索引 index 处插入新元素腾出空间。

然后将元素加到index所在的索引上，并且size长度+1。

此方法涉及到数组元素的移动，所以效率较低！

4、remove方法

重点介绍两个remove方法，方法一是删除指定索引的元素，方法二是删除指定的元素。

4.1、remove(int index)

此方法是删除传递参数所在索引的元素。

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

既然传递进来的是索引，就必须进行下标合法性的检查，通过rangeCheck(index) 方法。

E oldValue = elementData(index); 方法的作用是返回index索引位置的元素。

int numMoved = size - index - 1; 假设目前数组的长度为3，需要删除1索引处的元素，计算得到的值就是3 - 1 - 1 = 1。

System.arraycopy(elementData, index+1, elementData, index,numMoved) 将 elementData 数组中从索引 index+1 开始的 numMoved 个元素向左移动一个位置，以覆盖索引 index 处的元素。

为了方便理解我们来画个图：

初始情况：

执行System.arraycopy(elementData, index+1, elementData, index,numMoved) 代码，将要删除元素的索引是1：

执行完上面的代码后，将即将删除元素所在索引的后面元素向前移动，覆盖掉删除的元素。

elementData[--size] = null; 然后将链表末尾的元素的指针指向null，方便垃圾回收。

最后返回被删除的元素。

由此可见，ArrayList指定索引删除的效率不高，因为和指定索引新增一样，也涉及到其余元素的移动，如果元素较多则速度较慢。

4.2、remove(Object o)

此方法是删除指定的元素

分支一：传递的参数为null，则从0索引开始遍历整个集合，如果某个索引下的元素为null，就调用fastRemove(index)方法删除对应索引的元素。
分支二：传递的参数不为null，则从0索引开始遍历整个集合，如果某个索引下的元素和传入的元素相等，就调用fastRemove(index)方法删除对应索引的元素。

    public boolean remove(Object o) {
        if (o == null) {
            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;
    }

可以看出，remove(Object o) 的本质依旧是遍历集合，删除指定索引的元素，但是利用的是fastRemove(index)方法：

    private void fastRemove(int index) {
        modCount++;
        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
    }

虽然名字叫fast，实际上依旧涉及到数组元素下标的移动，所以效率依旧不高。

5、并发修改异常原因分析

有这样一段代码，通过增强for循环一边遍历一边增删元素：

public class Test {
    public static void main(String[] args) {
        ArrayList<String> strings = new ArrayList<>();
        strings.add("a");
        strings.add("b");
        strings.add("c");

        for (String s : strings) {
            if (s.equals("a")){
                strings.remove(s);
            }
        }
    }
}

毫无悬念的出现了并发修改异常：

我们来跟踪一下堆栈信息，这个异常出现在ArrayList的私有内部类Itr中的next()方法中的checkForComodification()。

Itr实现了迭代器接口，成员变量expectedModCount的值是ArrayList 父抽象类的成员变量modCount

首先通过打断点的方式了解一下modCount的机制，在Test的第7行打上断点，以及启动程序后，在AbstractList 类的modCount成员变量上打上断点，方便查看不同操作时modCount值的变化情况。

当我们添加第一个元素时，modCount+1 = 1

后续每添加一个元素，modCount都会+1，最终所有元素添加完成后，modCount = 3。

然后进入for循环的if块，删除a元素：

底层调用的fastRemove()方法，modCount = 3 + 1 = 4

在进入下一次循环时，Itr的成员变量expectedModCount为3

而实际modCount = 3 + 1 = 4 ，所以在checkForComodification() 中抛出异常。

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

总结

ArrayList是线程不安全的集合，一边遍历一边增删元素会导致并发修改异常。它的底层实现是数组，在构造时，可以自定义集合的长度，如果没有定义，则在添加第一个元素前扩容长度为10，然后会添加元素，后续扩容量为原有容量的1.5倍。插入和删除都可以指定下标位置，增删的效率较低，因为无论何种方式都涉及到数组元素的移动。如果没有指定下标，新增的元素默认在集合的尾部。相对的查询效率较高。