Java 集合框架分析 - ArrayList

本篇文章主要分析一下Java集合框架中的List部分，ArrayList，该源码分析基于JDK1.8，分析工具，AndroidStudio，文章分析不足之处，还请指正！

相关文章
1、Java 集合框架分析-概述
2、Java集合框架分析-HashMap
3、Java集合框架分析-LinkedHashMap

一、ArrayList简介

ArrayList底层维护的是一个动态数组，每个ArrayList实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。ArrayList不是同步的（也就是说不是线程安全的，同HashMap、LinkedHashMap一样），如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步，在多线程环境下，可以使用Collections.synchronizedList方法声明一个线程安全的ArrayList，例如：

List arraylist = Collections.synchronizedList(new ArrayList());

二、源码分析

2.1 类结构定义

首先我们来看一下关于ArrayList的类结构，

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

上面是是ArrayList类的定义，它继承了抽象类AbstractList，但是真正继承的方法只有equals和hashCode，别的方法在ArrayList 中都有自己的重新实现；List接口在AbstractList中已经实现，这里是为了表明一下，没有太大含义；RandomAccess没有方法，表明ArrayList支持快速随机访问；实 现了 Cloneable 接口，以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制，如果在没有实现 Cloneable 接口的实例上调用 Object 的 clone 方法，则会导致抛出 CloneNotSupportedException 异常；类通过实现 java.io.Serializable 接口以启用其序列化功能，未实现此接口的类将无法使其任何状态序列化或反序列化

2.2 变量定义

接着我们分析一下ArrayList定义的变量。

    //序列化ID
    private static final long serialVersionUID = 8683452581122892189L;

    //数组初始容量大小
    private static final int DEFAULT_CAPACITY = 10;

    //
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //elementData存储ArrayList内的元素
    transient Object[] elementData;

    //存储在ArrayList内的元素的数量
    private int size;

2.3 构造函数

    //设定初始容量大小的构造函数
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //数组初始化
        this.elementData = new Object[initialCapacity];
    }

    //无参数构造函数
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }

    //将提供的集合转成数组返回给elementData（返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[]）
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;

        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

构造函数还是比较简单的，我们来看看ArrayList的最常用的方法add,

2.4 add(E e)添加数据

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

发现ArrayList的add方法，只有简单的两行代码，粗略的看一下是在数组elementData的尾部添加一个元素E，那么到底是怎么样操作的呢？我们详细查看一下源码，首先进入ensureCapacityInternal方法中一探究竟。看这个方法的名字就大概知道这是确保数组容量的，怎么个确保法呢？

    private void ensureCapacityInternal(int minCapacity) {
        //当我们调用ArrayList的无参构造函数时调用此代码
        if (elementData == EMPTY_ELEMENTDATA) {
            //设置数组容量为10，默认的大小
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //
        ensureExplicitCapacity(minCapacity);
    }

    //确保容量大小,modCount自增，并判断数组大小是否足够，不够的话将增大数组
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //如果最小需要空间比elementData的内存空间要大，则需要扩容  
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

到了这里还是有点模糊到底怎么数组扩容的？我们接着看grow的方法

//扩容并重新copy一份数组
private void grow(int minCapacity) {

        // oldCapacity为当前数组大小  
        int oldCapacity = elementData.length;
        // newCapacity为新容量的大小等于旧容量的1.5倍大小
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩充后的容量还是比最少需要的容量还要小的话，就设置扩充容量为最小需要的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //判断最新的容量是否已经超出最大数组范围，溢出判断
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);


        // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间  
    // 并将elementData的数据复制到新的内存空间  
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

我们总结一下add操作的过程，首先我们先要判断是否需要扩容，在扩容判断里面，我们主要进行一些判断，如果当前所需要的容量和当前数组的容量进行比较，如果不够的话则进行扩容，在扩容的同时则需要判断是否溢出了，然后将旧的数据数组进行copy到新的容量大小的数组中，最后再将需要添加的数据添加到数组的最后一位。

我们接着分析add的另一个方法，重载add(int index, E element)方法，

//在指定的位置上面插入一个数据
 public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //需要将指定位置及其后面数据向后移动一位，然后在位置上面插入数据
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //插入数据
        elementData[index] = element;
        //大小改变
        size++;
    }

中心思想就是，首先判断指定位置index是否超出elementData的界限，之后调用ensureCapacity调整容量（若容量足够则不会拓展），调用System.arraycopy将elementData从index开始的size-index个元素复制到index+1至size+1的位置（即index开始的元素都向后移动一个位置），然后将index位置的值指向element，同时改变数组的大小。

2.5 addAll方法

接着我们分析一下addAll方法。

 public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //将a的第0位开始拷贝至elementData的size位开始，拷贝长度为numNew 
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

其实这个方法很好理解，首先将批量添加的数据转为数组，然后获取它的容量大小，判断一下，如果我们要在数组中插入这一批数据的话，是否需要扩容，经过这个扩容判断操作，我们的数组容量是足够了，然后我们开始批量导入数据，其中System.arraycopy(a, 0, elementData, size, numNew);意思就是，将需要导入的批数据从0开始，导入到数组从size位置开始，导入的大小数量就是需要导入的数量。这个时候，总的数组容量就变成了原先的容量加上导入的容量了。

addAll 还有一个重载方法，我们也来看看：

public boolean addAll(int index, Collection<? extends E> c) {
        //判断插入的位置是否越界
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

这个方法其实在add的方法基础上面修改而来，复制数组的时候主要进行两步复制，第一步，现将原数组在指定的位置上面向后移动需要的位数，然后第二步再将需要导进去的数据从index位置复制进去。

2.6 get方法

分析完了add方法，我们来分析分析get 方法内容，get方法也是比较简单的

public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }

首先判断需要返回的位置是否越界了，其次直接返回数组对应索引里面的值。非常简单，我们再看看其他方法。

2.7 其余方法

1、remove(int index)

我们来看看remove方法

  public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        //保存一下需要删除的数据
        E oldValue = (E) 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;
    }

同理，因为涉及到数组的问题，所以首先需要判断一下是否出现越界的问题，然后就开始将指定删除位置后面的数据都向前移动一位，然后将最后的一位设置为null，最后返回删除的数据。

删除一个数据，remove也有重载方法

2、remove(Object o)

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

删除一个数据，主要是遍历数组，看看数组中是否存在这个数据，如果存在的话则进行fastRemove，我们进入fastRemove中看看

3、fastRemove(int 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
    }

将指定位置index后面的数据全部向前移动一位，最后将最后一位回收掉。

另外我们看下全部删除数组中的数据方法clear

4、clear( )

public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

将数组中所有的数据都重置为null，等带回收。

5、removeRange(int fromIndex, int toIndex)

protected void removeRange(int fromIndex, int toIndex) {

        if (toIndex < fromIndex) {
            throw new IndexOutOfBoundsException("toIndex < fromIndex");
        }

        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

执行过程是将elementData从toIndex位置开始的元素向前移动到fromIndex，然后将toIndex位置之后的元素全部置空顺便修改size。

6、set(int index, E element)

public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

这个方法很简单，就是修改数组index里面的数据，并返回旧的数据。

7、indexOf(Object o)

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

返回在数组中第一次出现的值。如果找到这个值的话就返回index，找不到就返回-1。

8、lastIndexOf(Object o)

 public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

遍历数组，从后往前遍历，找出第一次出现值的索引，找到就返回index，找不到就返回-1。

9、trimToSize()

    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

由于elementData的长度会被拓展，size标记的是其中包含的元素的个数。所以会出现size很小但elementData.length很大的情况，将出现空间的浪费。trimToSize将返回一个新的数组给elementData，元素内容保持不变，length跟size相同，节省空间。

以上便是ArrayList的源码内容，总的来说不是很难，接下来我们来总结一下关于ArrayList的方方面面。

三、总结

1. ArrayList底层是基于数组来实现的，可以通过下标准确的找到目标元素，因此查找的效率高；但是添加或删除元素会涉及到大量元素的位置移动，效率低。
2. ArrayList提供了三种不同的构造方法，无参数的构造方法默认在底层生成一个长度为10的Object类型的数组，当集合中添加的元素个数大于10，数组会自动进行扩容，即生成一个新的数组，并将原数组的元素放到新数组中。
3. ensureCapacity方法对数组进行扩容，它会生成一个新数组，长度是原数组的1.5倍+1，随着向ArrayList中不断添加元素，当数组长度无法满足需要时，重复该过程。
4. ArrayList不是同步的（也就是说不是线程安全的，同HashMap、LinkedHashMap一样），如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步，在多线程环境下，可以使用Collections.synchronizedList方法声明一个线程安全的ArrayList，例如：List arraylist = Collections.synchronizedList(new ArrayList());

---

---

参考链接

1、http://www.cnblogs.com/hzmark/archive/2012/12/20/ArrayList.html
2、http://blog.csdn.net/u010305706/article/details/51007826
3、http://blog.csdn.net/ljcitworld/article/details/52041836
4、http://www.cnblogs.com/fangfuhai/p/5767056.html