ArrayList源码分析

ArrayList是Java集合中最常用的，基于一个数组实现的，容量可以动态增长。

ArrayList不是线程安全的，只能在单线程环境下使用。

本文以jdk1.8的源码为例，分析其实现机制。

一、基本属性与构造函数

public class ArrayList<E> extends AbstractList<E>  
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable  
{  
    private static final long serialVersionUID = 8683452581122892189L;//序列版本号  
  
    private static final int DEFAULT_CAPACITY = 10;//默认的初始容量  
     
    private static final Object[] EMPTY_ELEMENTDATA = {}; //公有的空数组  
      
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//也是空数组，和上面区别在于在第一次add元素的时候会判断  
  
      
    /* 
     * ArrayList的两个私有属性 
     */  
    transient Object[] elementData; // 基于该数组实现，用于保存数据  
    private int size;//size表示容器内元素的个数  
      
      
    /* 
     * 三个构造函数 
     */  
      
    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);  
        }  
    }  
  
    public ArrayList() {//无参构造函数，  
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
    }  
  
    public ArrayList(Collection<? extends E> c) {//创建一个包含collection的ArrayList  
        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;  
        }  
    }     
}

1、私有属性

可以看出ArrayList只有两个私有属性，即用于存储元素的数组elementData和表示元素个数的size

1. elementData数组是Object类型的而不是泛型。
2. size表示元素的个数，它与数组的长度是有区别的。在没有添加元素的时候，虽然有数组，但是它的size却是0

2、DEFAULT_CAPACITY与EMPTY_ELEMENTDATA

DEFAULT_CAPACITY = 10表示默认的初始容量，而下面有两个final的空数组：

• EMPTY_ELEMENTDATA空数组表示在构造函数中制定初始化容量为0时，指向这个数组。

  即List\ list=new ArrayList\(0);

• 而DEFAULTCAPACITY_EMPTY_ELEMENTDATA是用于无参构造函数的默认大小的空数组。

  即List\ list=new ArrayList\();

• 这两者的关系在说明中给出了解释，We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added. 即在第一次添加元素的时候。

3、构造函数

1. 第一个构造函数用initialCapacity来初始化elementData数组，
   • 如果initialCapacity为0，则直接指向EMPTY_ELEMENTDATA。
   • 如果不为0，那么直接新建数组。
2. 第二个是无参构造函数，elementData指向默认的空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA。貌似以前的版本是this(10)，即默认初始化大小为10，但是1.8版本清清楚楚写明白了是指向空数组，很多博客都乱写，虽然新版本默认大小也是10，但那是在第一次添加元素时才初始化的长度为10的数组，而不是在构造函数直接初始化数组。
3. 第三个构造函数可以指定一个Collection<? extends E> c，说明类型必须是继承自前面泛型的类型。转换成数组并返回给elementData，如果不是Object[]将会调用 Arrays.copyOf方法将其转换为Object[]，因为上面提到elementData是Object类型的数组。

4、初始化

在新建一个list的时候，经常需要将一个数组包装进去，这时候就可以用到第三个构造函数。但是构造函数中的参数必须是一个list，所以就需要用到Arrays.asList方法，将一个数组转换为List。关于这个返回List的类型，根据getClass方法的输出class java.util.Arrays$ArrayList可以看出是Arrays中的内部类，而根据源码可以发现，这个内部类是继承自AbstractList。（注意，它和java.util.ArrayList是不一样的，如果直接对它进行操作会抛出异常）。

List<Integer> list=new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6));

/*
 * 因为int数组本身就是一个类型，所以该方法会把它当作只有一个int数组类型的参数
 * 而如果前面泛型定义为Integer的话，自然就会报错，所以在数组初始化的时候要定义为Integer[]类型的
 */
Integer[] num={2,3,4,5};  
 	List<Integer> list2=new ArrayList<Integer>(Arrays.asList(num));

在阿里开源的阿里巴巴Java开发手册中也提到，使用工具类 Arrays.asList()把数组转换成集合时，不能使用其修改集合相关的方法，它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。
说明： asList 的返回对象是一个 Arrays 内部类，并没有实现集合的修改方法。Arrays.asList体现的是适配器模式，只是转换接口，后台的数据仍是数组 。

二、数组大小的调整

ArrayList其实就是一个可以自动调整大小的数组，下面来看一下它是如何自动调节数组大小的。

/* 
 * 确保数组的大小 
 * 根据现有数组的大小计算出minCapacity 
 * 二者最终都会调用ensureExplicitCapacity(minCapacity); 
 */  
public void ensureCapacity(int minCapacity) {  
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)  
        // any size if not default element table  
        ? 0  
        // larger than default for default empty table. It's already  
        // supposed to be at default size.  
        : DEFAULT_CAPACITY;  
  
    if (minCapacity > minExpand) {  
        ensureExplicitCapacity(minCapacity);  
    }  
}  
  
private void ensureCapacityInternal(int minCapacity) {  
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  
    }  
  
    ensureExplicitCapacity(minCapacity);  
}  
  
private void ensureExplicitCapacity(int minCapacity) {//如果现有elementData的长度不够满足需求的大小，那么就扩大现有的数组  
    modCount++;  
  
    // overflow-conscious code  
    if (minCapacity - elementData.length > 0)  
        grow(minCapacity);  
}  
  
  
  
  
/* 
 * 增加数组的长度以确保minCapacity个存储空间 
 */  
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;// 数组的最大长度  
  
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;  
}

1. 主要分为两部分，前部分的三个函数主要用于计算，ensureCapacity与ensureCapacityInternal函数，根据传来的minCapacity，计算出需要的最小空间，然后调用ensureExplicitCapacity，如果现有的elementData数组的长度能够满足计算出的最小空间，那么就什么都不用做，但是如果不能满足，那么就必须调用下面的grow函数来进行扩容了。
2. grow函数用于扩展数组的长度，根据代码可以看出它的扩容机制。首先获取原有elementData数组的长度，并将其乘以1.5，然后再判断是否能满足给定的需求，如果还是不能满足，那么直接创建一个给定需求的数组。然后再将缘由元素拷贝到新数组中。
3. 由此我们可以看出，随着向ArrayList中不断加入元素，当现有数组存满以后，就会自动将数组容量扩大1.5倍，当然每次扩容都会有数组的拷贝，因此这也是影响性能的关键因素。

三、基本操作

接下来就是最基本的增删改查操作

1、增

向ArrayList中增加新的元素。主要是add与addAll方法。

//在指定位置插入元素或集合中元素时，首先调用该方法判断指定的位置是否合法  
private void rangeCheckForAdd(int index) {  
    if (index > size || index < 0)  
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
}  
  
private String outOfBoundsMsg(int index) {  
    return "Index: "+index+", Size: "+size;  
}  
  
/* 
 * add与addAll 
 */  
public boolean add(E e) {//在容器末尾加入一个指定新的元素  
    ensureCapacityInternal(size + 1);  // Increments modCount!!  
    elementData[size++] = e;  
    return true;  
}  
  
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++;  
}  
  
public boolean addAll(Collection<? extends E> c) {//在容器末尾加入一个指定集合中的所有的元素  
    Object[] a = c.toArray();  
    int numNew = a.length;  
    ensureCapacityInternal(size + numNew);  // Increments modCount  
    System.arraycopy(a, 0, elementData, size, numNew);  
    size += numNew;  
    return numNew != 0;  
}  
  
public boolean addAll(int index, Collection<? extends E> c) {//在指定位置插入一个指定集合的所有的元素  
    rangeCheckForAdd(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;  
}

可以看出，向ArrayList中加入元素的效率并不是很高，向指定位置插入的时候，会调用System.arraycopy()方法将该元素后面的元素整体向后移动。

2、读

get方法

private void rangeCheck(int index) {//在set、get和remove方法之前调用该方法检查给定位置是否合法  
    if (index >= size)  
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
}  
  
@SuppressWarnings("unchecked")  
E elementData(int index) {  
    return (E) elementData[index];  
}  
  
public E get(int index) {//返回指定位置的元素  
    rangeCheck(index);  
  
    return elementData(index);  
}

读即获取指定位置的元素，由于ArrayList是基于数组实现的，所以该操作可以在O(1)的时间内完成。上面提到过，用于存储元素的elementData的数组是Object数组，所以返回的时候会加上类型转换，向下转型。

3、查

ArrayList的查主要是查找容器中是否包含某个元素，这里也加入了一些容器基本信息的查询

//返回容器中持有元素的个数  
public int size() {  
    return size;  
}  
  
//返回容器是否为空，即没有元素  
public boolean isEmpty() {  
    return size == 0;  
}  
  
/* 
 * 查找给定元素 
 */  
public boolean contains(Object o) {//返回容器中是否包含某个元素  
    return indexOf(o) >= 0;  
}      
  
public int indexOf(Object o) {//返回某个元素第一次出现的位置，如果没有则返回-1  
    if (o == null) {//注意null和非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;  
}  
  
  
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;  
}

4、改

public E set(int index, E element) {//将指定位置的元素改为输入的元素  
    rangeCheck(index);  
  
    E oldValue = elementData(index);  
    elementData[index] = element;  
    return oldValue;  
}

该方法同样也只需要O(1)的时间。

5、删

删除操作，包括remove、clear等方法。

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;  
}  
  
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  
}  
  
public boolean remove(Object o) {//首先查找指定元素是否存在，如果存在将其删除并返回true，如果不存在返回false  
    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;  
}  
  
public void clear() {//删除容器内所有的元素，将其变为空  
    modCount++;  
  
    // clear to let GC do its work  
    for (int i = 0; i < size; i++)  
        elementData[i] = null;  
  
    size = 0;  
}  
  
protected void removeRange(int fromIndex, int toIndex) {//删除指定区间内的所有元素  
    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;  
}

可以看出，两个remove方法都需要调用System.arraycopy方法将删除元素后面的元素向前移，效率同样不高。

6、总结

本节介绍了ArrayList的常用基本操作。

1. 在这些操作中，不管是add还是remove方法，只要是数组中增加或者减少一个或多个元素，就要调用System.arraycopy方法来拷贝大量元素。
2. 查找元素采用最原始的顺序查找，所以效率为O(n)。
3. 而get和set方法则只需要O(1)时间就可以直接读取或者更改数组中的元素。
4. 综上所述，ArrayLis使用与读取与修改频繁而插入删除操作较少的情况。

四、其他方法

1、System.arraycopy与Arrays.copyOf

在源码中，出现了很多次System.arraycopy和Arrays.copyOf方法，在此总结一下他们之间的关系。

1.1、System.arraycopy

上面提到，不管是add还是remove方法，只要是数组中增加或者减少一个或多个元素，就要调用System.arraycopy方法来拷贝大量元素。

public static native void arraycopy(Object src,  int  srcPos,  
                                    Object dest, int destPos,  
                                    int length);

可以看出，该方法就将制定长度的数组复制到另一个数组中。声明为native关键字，调用的为C++编写的底层函数，在JDK中看不到源码。

貌似在openJDK中可以看见源码，实际上调用了c语言的memmove()函数，可以保证同一个数组内元素的正确复制和移动，比一般复制方法的效率高很多，适合用来批量处理数组。java强烈推荐在复制大量数组元素时使用该方法，在次也再次意识到C和C++对于底层操作的优越性。

1.2、Arrays.copyOf

Arrays.copyOf是Arrays类中的静态方法，它有很多重载版本，但是最后都调用了一个方法

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {  
    @SuppressWarnings("unchecked")  
    T[] copy = ((Object)newType == (Object)Object[].class)  
        ? (T[]) new Object[newLength]  
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);  
    System.arraycopy(original, 0, copy, 0,  
                     Math.min(original.length, newLength));  
    return copy;  
}

T为指定的类型，他的原理就是在内部创建一个新的指定类型的数组，然后调用System.arraycopy方法将原数组中的元素复制过去，然后返回新建的数组。

2、toArray方法

ArrayList有两个转化为静态数组的toArray方法。

2.1

public Object[] toArray() {  
    return Arrays.copyOf(elementData, size);  
}

第一个，直接调用Arrays.copyOf方法，将elementData内元素全部复制到一个新的数组然后返回新数组，因为elementData是Object的，所以返回的数组也是Object的，需要自己转换类型。

Integer[] num={2,3,4,5};  
List<Integer> list=new ArrayList<Integer>(Arrays.asList(num)); 

Object[] o=list.toArray();
Integer[] i=(Integer[]) list.toArray();

2.2

@SuppressWarnings("unchecked")  
public <T> T[] toArray(T[] a) {  
    if (a.length < size)  
        // Make a new array of a's runtime type, but my contents:  
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());  
    System.arraycopy(elementData, 0, a, 0, size);  
    if (a.length > size)  
        a[size] = null;  
    return a;  
}

第二个，可以传入一个指定的数组

如果数组的长度小于size也就是说不足够容纳elementData中的元素，那么就会创建一个新的数组并将size个元素拷贝到新的数组中然后返回新建的数组。

• 如果数组长度与size相等，那么直接将elementData中元素拷贝到传入的数组中。
• 如果数组长度大于size，复制以后还会把第size个元素置为null。

Integer[] num={2,3,4,5};  //
List<Integer> list=new ArrayList<Integer>(Arrays.asList(num)); 
Integer[] i=new Integer[0];
i=list.toArray(i);
System.out.println(Arrays.toString(i));

output: [2, 3, 4, 5]

该方法与第一个方法的区别就是，无论是返回新建的数组还是复制到传入的数组，返回的数组类型都是和传入数组相同的，而不是上面的Object。