从源码上分析 ArrayList

前言

ArrayList 是 List 接口的一个实现类，那么 ArrayList 的底层是如何实现的呢？让我们来一探究竟。

源码分析

属性

先来看看 ArrayList 中比较重要的两个属性：

1
2
3

transient Object[] elementData; 

private int size;

elementData 用来存储 ArrayList 中的元素，其实 ArrayList 的底层是用 Object[] 数组来实现的。
size 指的是的逻辑长度，就好像一个水杯，容量是 600 毫升，但杯中只有 200 毫升的水，ArrayList 容器就是水杯，这个 size 属性表示的就是水杯中水的容积。

构造方法

无参构造方法：

1
2
3

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

很简单，就一行语句，elementData 在上面我们已经知道是什么了，那 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 又是什么呢？

1	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

原来只是一个空的 Object[]。

指定容量的构造方法：

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

也很简单，就是为 ArrayList 指定初始容量。这里主要对传入的容量做了有效性验证，当传入的参数小于 0 时，抛出异常。当参数等于 0 时，则用一个空的数组常量 EMPTY_ELEMENTDATA 来初始化。

用一个 Collection 对象进行构造的的构造方法：

public ArrayList(Collection<? extends E> c) {
    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;
    }
}

首先将传入的参数转为对象数组赋值给 elementData ，如果传入的 Collection 参数的长度为 0，则就将空的常量数组对象 EMPTY_ELEMENTDATA 赋给了 elementData。

常用方法

add

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

调用了 ensureCapacityInternal 函数:

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

    ensureExplicitCapacity(minCapacity);
}

这里判断 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 表示如果如果为没有初始化容量时，用默认容量 DEFAULT_CAPACITY 也就是 10，来开启空间，也就是上面我们说的水杯的容量。

接下来看 ensureExplicitCapacity 方法：

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

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

继续看 grow 方法:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    
    // 对 ArrayList 容量进行 1.5 倍扩容。
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 如果扩容后的容量还不够实际占用的容量，那么需要扩容到实际占用容量的大小。
    // 如当前 newCapacity 为 10，扩容后为 15，
    // 但现在实际的元素数量为 16 个，那么至少应该先装下这 16 个。
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 防止阔中的过大，过大时，则使用 Integer.MAX_VALUE 代替。
    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);
}

其实这段代码也很简单，就是动态扩容 ArrayList 的大小，每次扩容都为当前容量的 1.5 倍，当然也进行了扩容过大或过小的限制。
其扩容原理就是创建一个容量为当前容量 1.5 倍的新数组，将旧数组的内容拷贝给新数组。

add(int index, E element)

public void add(int index, E element) {
    // 判断要插入的位置不小于 0 且不大于当前最大位置
    rangeCheckForAdd(index);
    
    // 容量扩容检测，具体参见 add(E e) 方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

看过了 add(E e) 的源码，这里也就很好理解了，先进行插入位置有效性判断，然后判断容量是否需要扩容，然后先将插入位置开始的所有元素向后移动一位，最后将需要插入的元素插入指定位置。

get

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

    return elementData(index);
}

ArrayList 的底层是用数组实现的，那么获取元素也就很方便了，判断获取位置合法后，直接用下标获取即可。

set

public E set(int index, E element) {
    rangeCheck(index);

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

这个方法其实就是修改指定位置的元素，先拿到要覆盖的元素，然后将新元素赋值上去，最后返回覆盖的元素即可。

remove

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

先进行有效性判断，然后从要删除的元素开始的所有元素都向前拷贝一位，并将最后一位设值为 null。

indexOf

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

如果要找的内容 null，则依次用 == 判断是否为要找的元素，如果不为 null，则用 equals 来依次判断。

总结

根据上方的源码分析，我们可以得出 ArrayList 的一些特性：

ArrayList 底层数据结构是对象数组，如不指定长度，则初始容量为 10。
底层的对象数组是在第一次添加元素的时候才进行初始化的。
每次扩容为原来容量的 1.5 倍，扩容原理是将原来的数据拷贝到新数组中。

所以我们在使用时要注意：

如知道大概要存多少个数据，最好指定初始化容量，这样可以提高程序性能。
ArrayList 查找元素很快，但删除元素和添加元素的效率相对较差。