Java中ArrayList源码解析

一、ArrayList介绍

ArrayList是Java和Android开发中使用最为频繁的一种集合。它的底层数据结构是动态数组，并且是线程不安全，允许元素为null. ArrayList类结构如下:

//实现了List、RandomAccess、Cloneable、Serializable接口
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ 
                      //... 
}

其中, ArrayList实现了RandomAccess标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。ArrayList实现了Cloneable标记接口，用来指示Object.clone()方法可以合法地对该类实例按字段复制。如果在没有实现 Cloneable接口的实例上调用 Object 的 clone 方法，则会导致抛出 CloneNotSupportedException 异常。Serializable 接口： 类通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化

二、ArrayList基本使用

List<String> dataList = new ArrayList<>();//创建一个ArrayList集合
List<String> dataList = new ArrayList<>(3);//指定初始化集合的大小为3的ArrayList集合
List<String> dataList = new ArrayList<>(originalList);//指定已经存在集合

三、ArrayList特性

1、是否保证线程安全：

不是同步的，不能保证线程安全

2、底层数据结构：

ArrayList底层使用的是Object数组数据结构，动态数组

3、插入和删除是否受元素位置的影响：

ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。

4、是否支持快速随机访问：

ArrayList 实现了RandomAccess 接口，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

5、内存空间占用：

ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间

四、ArrayList类的继承关系

五、ArrayList源码分析

1、构造器

通过分析ArrayList的构造器，发现其实构造ArrayList有三种方式，一种最为常见就是创建一个不带构造参数的ArrayList的实例，默认是DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组；然后第二种就是传入指定初始容量大小，默认会创建指定容器大小的Object数组；第三种就是传入已存在Collection集合，默认会直接把Collection集合转化成Object数组，并且如果转化失败就会利用Arrays.copyOf方法会把集合中元素批量加入到Object数组以此来初始化elementData.

关于Arrays.copyOf(elementData, size, Object[].class)方法，就是根据class的类型来决定是new 还是反射去构造一个泛型数组，同时利用native函数，批量赋值元素至新数组中。

2、ArrayList操作之增

add(E e)

• 执行add(E e)方法，往集合尾部添加元素，每执行一次add操作之前都会调用ensureCapacityInternal来确认是否需要扩容

add(int index, E element)

• 执行add(int index, E element)方法, 先检查index是否合法，是否越界。然后确认是否需要扩容，然后将index开始之后的所有数据元素整体向后移动一位，然后再把指定index的元素进行新值覆盖，最后size自增1

addAll(Collection<? extends E> c)

addAll(int index, Collection<? extends E> c)

3、ArrayList扩容流程

• 1、扩容源码分析

• 2、扩容原理流程图

• 3、扩容原理的总结

对于ArrayList扩容，首先需要明确一点ArrayList的size和elementData.length数组长度不是相等的，size表示当前数组的元素个数。如果ArrayList是以默认无参构造的，那么当第1次执行add操作后，会默认第一次扩容容量为DEFAULT_CAPACITY = 10, 后面再执行第210次执行add操作后，就不会进行扩容操作；当第11次执行add操作后就会就触发扩容操作，此次扩容的容量为当前数组长度(注意是数组长度而不是size,size增加只有真正把值add到数组中后才增加)的一半也就是5；所以当第1115次执行add操作后，又不会进行扩容操作。依次类推后续每次会扩容的容量为当前数组长度的一半，在扩容容量范围内就不会触发扩容操作。

验证上述理论，可以明显发现ArrayList的add操作执行的第1次，第11次，第16次会明显耗时更长。

4、ArrayList操作之删

remove(int index)

remove(Object o)

removeAll(Collection<?> c)

   //在当前集合中批量删除传入集合c中的元素
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);//removeAll方法实际上是委托给batchRemove方法实现的，传入参数分别要删除，注意传入第二个参数，complement = false表示在当前集合删除传入的集合
    }
    //在当前集合中批量删除除了传入集合c中的元素(保留传入集合c中的元素，其他全删除)
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);//注意传入第二个参数，complement = true表示在当前集合保留传入的集合元素，其他全部删除
    }

    //批量移除集合中元素
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;//将当前集合中元素赋值给elementData
        int r = 0, w = 0;//设置两个游标分别读游标r和写游标w
        boolean modified = false;
        try {
            for (; r < size; r++)//遍历当前集合中的所有元素
            //注意: 这里需要考虑两种情况:
            //第一: 如果当前集合中元素在需要删除集合c中且complement为false则表示在当前集合中移除传入集合c中元素，
            //会把当前集合中不在c集合中的元素，整体往前移动，w游标增加
            //第二: 如果当前集合中元素在需要保留集合c中且complement为true则表示在当前集合中保留传入集合c中元素，
            //会把当前集合中在c集合中的元素，整体往前移动，w游标增加
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // 出现异常会导致r != size，则将出现异常处后面的数据全部复制覆盖到数组里
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;//修改w游标
            }
            //最后w游标值就是产生新的数组的size
            if (w != size) {
                //从w之后到size的所有位置重置为null，以便GC回收
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                //modCount增加表示修改到元素次数    
                modCount += size - w;
                size = w;//最后的w也就是size集合大小
                modified = true;
            }
        }
        return modified;
    }

5、ArrayList操作之改

    //注意修改数组中对应元素的值是不需要修改modCount
    public E set(int index, E element) {
        rangeCheck(index);//越界检查

        E oldValue = elementData(index);//通过elementData按到index元素
        elementData[index] = element;//并用传入的新值覆盖旧值
        return oldValue;//并返回旧值oldValue
    }

6、ArrayList操作之查

    //注意查找数组中对应元素的值是不需要修改modCount
    public E get(int index) {
        rangeCheck(index);//越界检查

        return elementData(index);
    }
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];//直接获取对应index的值
    }

7、ArrayList操作之clear

  public void clear() {
        modCount++;//修改modCount
        //elementData数组中的元素全部复制为null, 以便GC回收
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;//最后重置size为0
   }

8、ArrayList操作之包含contains

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    public int indexOf(Object o) {
        if (o == null) {//如果o为null, 遍历elementData数组找到第一个出现null的位置
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {//如果o不为null, 遍历elementData数组找到第一个出现与o值相等的位置
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;//否则找不到就返回-1
    }

9、ArrayList操作之迭代器Iterator

    private class Itr implements Iterator<E> {
        int cursor;       // 返回下一个元素的index
        int lastRet = -1; // 返回上一个元素的index，没有上一个元素就默认返回-1
        int expectedModCount = modCount;//整个过程中操作集合(包括add、remove操作)次数modCount

        public boolean hasNext() {
            return cursor != size;//当前游标cursor不等于size，说明集合并没有迭代完毕，还有下一个元素
        }

        @SuppressWarnings("unchecked")
        //获取迭代器中当前的元素next
        public E next() {
            checkForComodification();//检查修改集合次数modCount
            int i = cursor;
            if (i >= size)//越界检查
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;//取出集合中数组elementData
            if (i >= elementData.length)//越界检查
                throw new ConcurrentModificationException();
            cursor = i + 1;//cursor游标累加
            return (E) elementData[lastRet = i];//取出当前i的元素中的值返回，并设置上一次返回的元素的下标
        }

        //迭代中移除当前迭代元素
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();//modCount检查

            try {
                ArrayList.this.remove(lastRet);//移除元素
                cursor = lastRet;//删除的游标
                lastRet = -1;//不能重复删除 所以修改删除的标志位
                expectedModCount = modCount;//更新 判断集合是否修改的标志，
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        //主要是为了检查线程安全，ArrayList不是线程安全的，但是避免多线程操作ArrayList中在迭代器迭代过程中，
        //对集合具有写操作的修改导致modCount次数和expectedModCount不一致就会抛出ConcurrentModificationException异常
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

7、ArrayList中的modCount了解一下

我们都知道ArrayList是非线程安全的，在使用迭代器遍历的时候，用来检查列表中的元素是否发生结构性变化（列表元素数量发生改变）了，主要在多线程环境下需要使用，防止一个线程正在迭代遍历，另一个线程修改了这个列表的结构，那么这个modCount就是记录被修改的次数。使用迭代器遍历时,iterator.hasNext()方法中的checkForComodification()方法会检查modCount和expectedModCount是否相等,从而判断在多线程环境下,迭代器遍历的过程中列表中的元素是否发生结构性变化。

一起来看个有趣例子:

class ArrayListTest {
    public static void main(String[] args) {
        List<Integer> resultList = new ArrayList<>();
        resultList.add(10);
        Iterator iterator = resultList.iterator();
        while (iterator.hasNext()) {
            Integer value = (Integer) iterator.next();
            if (value == 10){
                resultList.remove(value);//注意这里是调用了ArrayList中的remove方法, 值删除后resultList为空，modCount++
            }
        }
    }
}

得到的运行结果会抛出一个异常:

为什么会抛出这个异常呢？这个其实就是modCount导致的，不妨再次来看下ArrayList remove的源码。

    public E remove(int index) {
        rangeCheck(index);

        modCount++;//会发现remove调用后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中的Iteator迭代源码，会发现resultList为空，所以size为0，但是cursor不为0，hasNext()返回true, 就会继续执行next()方法

        public boolean hasNext() {
            return cursor != size;//会发现size为0，但是cursor不为0，hasNext()返回true
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();//检查modCount，还记得在ArrayList中的remove方法中modCount会自增后就造成expectedModCount和modCount不一致，抛出异常
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        //注意使用iteator自带的remove方法就不会抛出异常
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();//会先去检查modCount

            try {
                ArrayList.this.remove(lastRet);//虽然内部也是调用remove方法，modCount自增了
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;//但是这里需要特别注意它把修改后的最新的modCount重置给expectedModCount，所以需要在迭代过程中删除元素还是调用iteator自带的remove方法
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }