动态数组ArrayList源码剖析

一、ArrayList是什么

        ArrayList可以看成是一个动态的数组，它的内部是通过数组实现的。为什么称它为“动态”数组呢？因为ArrayList拥有“扩容”机制。当ArrayList的长度不够的时候，它将会通过Arrays.copyof()方法，将其内部数组的长度进行增加操作。

二、ArrayList的特点

        为了记忆的方便，我的口诀是“序重步，数据结构”。

        顺序：有序。原因是因为内部数组是有序的。

        重复：可重复。原因是数组的元素是可以重复的。

“快速失败”的。

        数据结构：增删速度慢，查询速度快。因为ArrayList内部是数组数据结构，因此它可以根据索引快速的定位到元素。增加和删除速度慢，原因是ArrayList需要将当前元素和它后面的所有元素向前或者向后移动一位。

        下面为上面的特点做一下简单的解释。

        快速失败是：当前线程在迭代一个集合的时候，另外一个线程修改了你正在迭代的集合，这个时候会抛出异常。ArrayList是线程不安全的，所以可能会出现迭代ArrayList期间，另外一个线程修改了ArrayList集合中的元素，导致异常发生。

        安全失败是：准备迭代一个集合的时候，先将这个集合复制一个副本出来。当前线程迭代的是这个副本集合，另外一个线程修改的是原来的集合，因此不会产生冲突，不会抛出异常。java.util.concurrent包下的所有集合都是“安全失败”的。

        ArrayList为什么查询速度比LinkedList块？LinkedList它也是List集合的实现类，因此它也是有序的。但是LinkedList是链表数据结构，它的每个集合元素只知道自己的前一个元素和后一个元素的地址，而ArrayList是数组数据结构，数组是一段连续的内存空间。举个例子，假如有很多人，排成长队，这个时候要找5号的人就非常简单，问都不用问，直接定位。假如不排成长队，只是随机站在很大的广场里面，但是每个人只知道自己的前一个人和后一个人的位置，而且你只知道第一个人的位置，这个时候你要找第5个人的时候你就得从第一个人开始问后面的是谁，一直问下去才知道第5个人在哪里。例子出自：​​为什么ArrayList查询速度比较快​​

三、属性及构造函数分析

        底层使用数组实现。就是这个elementData数组，它就是ArrayList内部用来存放元素的数组。

transient Object[] elementData;      

        size是指的是ArrayList中内部数组elementData存放的实际元素个数，而不是此数组的长度。

private int size;      

        ArrayList默认长度是10。也就是说，我们通过空参构造函数创建的ArrayList它在第一次添加元素的时候，它的内部数组的长度将会被扩充为10。

private static final int DEFAULT_CAPACITY = 10;      

        ArrayList有三种构造函数。分别是空参的，指定初始化大小的，另外一个是传入一个Collection接口的实现类。

        空参的是最常见的，将底层数组elementData数组初始化为一个没有任何元素的数组。

public ArrayList() {
        this.elementData = EMPTY_ELEMENTDATA;// public static final Object[] EMPTY_ELEMENTDATA = {};
    }      

        下面的这个是初始化指定大小的数组。目的是把elementData初始化为一个指定大小的Object类型的数组。      

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = {};
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }      

        第三种用的不是很多。把另外一个集合的元素存放到ArrayList中，size是ArrayList中实际元素的个数。

/* 参数是Collection,证明数组中已经要存储c.size个元素 */  
    public MyArrayList(Collection<? extends E> c) {  
        super();  
        elementData = c.toArray();  
        size = c.size();  
    }      

四、添加元素

        添加元素的源码如下。我们看到方法的第一行执行了ensureCapacityInternal(size + 1); 这个方法。这个方法是什么意思呢？我们之前就提到过，size是这个ArrayList集合的实际元素个数，现在为这个集合元素添加了一个元素，那么这个ArrayList中的实际元素个数就是size+1个了。为了确保elementData数组的容量够用，我们得去检查一下elementData数组的长度是否能容的下 size+1 个元素。

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

        size+1传递给了minCapacity。minCapacity代表为了当前操作能够成功，elementData必须要达到的长度。比如，现在实际个数有12个，添加一个元素要求elementData数组至少要有13个元素位置。代码中，如果当前elementData数组没有元素，那么此时elementData必须要求达到的长度是10。DEFAULT_CAPACITY 就是最初分析到的那个空参情况下，ArrayList默认要被扩容的长度。

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

        ensureExplicitCapacity(minCapacity);
    }      

        为了当前操作能够成功，最小要求ArrayList的内部数组elementData的长度达到minCapacity。如果内部数组elementData的长度不能够达到此次操作的最小要求的minCapacity长度的话，那么就需要为内部数组elementData扩容。扩容方法就是grow()方法。这里的modCount是给ArrayList的迭代器使用的，在并发操作被修改时，提供快速失败行为。modCount可以看成是一种标记。

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

        //如果为了能够操作成功的长度 > 原来的数组的长度
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }      

        扩容方法是ArrayList的核心，可以看到ArrayList的神秘之处不过就是下面的寥寥几行代码。   

private void grow(int minCapacity) {    
        //先获取到elementData内部数组的 旧长度    
        int oldCapacity = elementData.length;    
        //将旧长度修改为1.5倍的旧长度。>>是位运算符，二进制中向右左移一位就是除以2    
        int newCapacity = oldCapacity + (oldCapacity >> 1);    
        //如果扩容后的新长度，仍然不能满足 此次操作的最小长度    
        if (newCapacity - minCapacity < 0)    
            //那么把 此次操作的最小长度 当作扩容后的新长度    
            newCapacity = minCapacity;    
        //将内部数组elementData复制成指定的新长度    
        elementData = Arrays.copyOf(elementData, newCapacity);    
    }      

        如果是在指定位置添加元素的话，只需要把指定位置的元素及其后面的元素向后移动一位，腾出指定的位置出来，给新添加的元素。关于System.arraycopy(Object src,int srcPos,Object dest, int destPos,int length) 方法的解释。

src:源数组； srcPos:源数组要复制的起始位置；

dest:目的数组； destPos:目的数组放置的起始位置； length:复制的长度。

将源数组src从srcPos索引处，复制length个元素，覆盖目标数组dest。从目标数组dest的destPos处开始覆盖，覆盖目标数组length个元素。

/* 在指定位置添加 */  
    public void add(int index, E element) {  
        ensureCapacityInternal(size + 1); // 保证数组有充足的空间，不行的话进行扩容，请参考上面的代码
        // 将指定索引位置右端元素右移  
        System.arraycopy(elementData, index, elementData, index + 1, size - index);  
        elementData[index] = element;// 将新添加的元素，添加到刚刚腾出来的索引处
        size++;  //实际个数加一
    }      

        删除操作，返回被删除的元素。

/* 删除指定角标上的元素 */  
    public E remove(int index) {  
        
        E oldValue = this.get(index);// 获取指定索引的值
        int numMoved = size - index - 1;// 右边准备向左移动的元素的个数  
        // 从被删除的元素的角标后面的第一个元素开始，直到elementData数组的最后一个元素，它们全部向前移动一位
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);  
        elementData[--size] = null;// 实际个数减一，数组最后一位置空  
        return oldValue;  
    }      

            其余方法的实现都简单易懂，有兴趣的话可以参考JDK源码和API文档。

五、要点

        ArrayList的特点，口诀是：“序重步，数据结构”。有序，可重复，不同步。因为是数组数据结构，增删慢，查询块。