从源码看ArrayList的实现

在JAVA基础系列（五） 集合这篇文章中已经系统性的总结了JAVA中的集合体系，ArrayList是基于数组的List实现，查询快，增删慢，效率高，非线程安全。本文从源码的层面上来看一下ArrayList的构造，扩容与廋身，最后通过一个示例来加深理解。

1.构造方法

从下面的源码知道ArrayList内部是用Object数组来实现，Object的length()即ArrayList的容量，而ArrayList里面真实元素的个数反映在size里面。当调用无参构造方法时会得到一个空的Object数组，同时也可以指定容量调用有参的构造函数。

transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private int size;
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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);
        }
}

2.扩容

根据下面的源码和grow方法的调用层次图可以看到每当在ArrayList里面增加一个元素时，最后都会调用grow方法来保证容量。
如果我们用的无参构造函数来创建ArrayList对象，这时ArrayList的capacity和size都会0，当每一次往里面写入元素时，会调用ensureCapacityInternal(1),当进入这个方法时因elementData还是为空，所以minCapacity会赋值默认容量DEFAULT_CAPACITY即10，然后经过ensureExplicitCapacity(10)调用方法grow(10),经过一系列判断会执行grow方法里面的elementData = Arrays.copyOf(elementData, 10)，综上所述可知调用ArrayList无参构造函数时会创建一个空的Object数组，第一次往里面添加元素时才会得到默认容量为10的Object数组。
同时以后每次往ArrayList里面添加元素时发现容量不够了都会调用grow方法，通过int newCapacity = oldCapacity + (oldCapacity >> 1);实现了新的容量是旧的容量的1.5倍。

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

   private static final int DEFAULT_CAPACITY = 10;

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

        ensureExplicitCapacity(minCapacity);
    }

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

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

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

3.廋身

ArrayList里面有一个 trimToSize方法可以缩小它的容量，以节约空间。考虑到以下情形：当刚开始根据需要把ArrayList的容量扩充到10000左右，但后来通过remove操作使得size的大小只有100左右并且会保持这个状态很长一段时间，这时capacity还是维持在10000左右，这样势必造成很大的空间浪费，这样我们就可以显式的调用一下 trimToSize方法。通过下面的源码可以知道该方法会把ArrayList的capacity缩小致size大小。

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

4.示例

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;

import javax.xml.transform.Templates;
public class Main {
    public static void main(String[] args) throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException{
        ArrayList arrList = new ArrayList();
        //无参初始化，创建一个空的Object数组
        System.out.println(getObjArrLength(arrList,"elementData"));//0      
        
        //循环添加10000个元素，当ArrayList的容量发生改变时输出
        for (int i = 0; i < 10000; i++) {
            int oldCapacity = getObjArrLength(arrList,"elementData");
            arrList.add(1);
            int newCapacity = getObjArrLength(arrList,"elementData");
            if(newCapacity != oldCapacity) System.out.println(newCapacity);
        }
        
        //依次移除ArrayList末尾的9900个元素，剩下100个元素
        for(int i = 0; i < 9900; i++){          
            arrList.remove(arrList.size() - 1);         
        }
        
        System.out.println("Before trimToSize the capacity is " + getObjArrLength(arrList,"elementData"));
        arrList.trimToSize();//瘦身
        System.out.println("Ater trimToSize the capacity is " + getObjArrLength(arrList,"elementData"));
        
    }
    
    // 通过反射来得到ArrayList的容量，即Object数组的长度
    public static int getObjArrLength(Object arrList,String fieldName) throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException{
         Class c = ((Object)arrList).getClass();
         Field f = c.getDeclaredField(fieldName);
         f.setAccessible(true);
         Object[] o=(Object[]) f.get(arrList);
         return o.length;          
    }
}

效果如下：