竟然还有人说ArrayList是2倍扩容，今天带你手撕ArrayList源码

ArrayList是我们开发中最常用到的集合，但是很多人对它的源码并不了解，导致面试时，面试官问的稍微深入的问题，就无法作答，今天我们一起来探究一下ArrayList源码。

1. 简介

• ArrayList底层是数组，允许元素是null，能够动态扩容
• size、isEmpty、get、set、add 等方法时间复杂度都是 O (1)
• 非线程安全，并发修改时，会抛出ConcurrentModificationException

2. 初始化

// 初始容量private static final int DEFAULT_CAPACITY = 10;// 空数组private static final Object[] EMPTY_ELEMENTDATA = {};// 默认空数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 存储元素的数组transient Object[] elementData;// 无参初始化，默认是空数组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);    }}

切记：无参初始化的时候，默认是空数组，并没有初始化容量大小，容量是在第一次添加元素的才进行初始化。

3. 添加元素

public boolean add(E e) {  // 确保数组容量够用，size是元素个数  ensureCapacityInternal(size + 1);  // 直接赋值  elementData[size++] = e;  return true;}// 确保数组容量够用private void ensureCapacityInternal(int minCapacity) {    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}// 计算所需最小容量private static int calculateCapacity(Object[] elementData, int minCapacity) {  	// 如果数组等于空数组，最小容量为10    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        return Math.max(DEFAULT_CAPACITY, minCapacity);    }    return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {    modCount++;  	// 如果所需最小容量大于数组长度，就进行扩容    if (minCapacity - elementData.length > 0)        grow(minCapacity);}

看一下扩容逻辑：

// 扩容，就是把旧数据拷贝到新数组里面private void grow(int minCapacity) {  int oldCapacity = elementData.length;  // oldCapacity >> 1 是把oldCapacity除以2，意思是1.5倍扩容  int newCapacity = oldCapacity + (oldCapacity >> 1);  // 如果扩容后的容量小于最小容量，扩容后的容量就等于最小容量  if (newCapacity - minCapacity < 0)    newCapacity = minCapacity;  // 如果扩容后的容量大于Integer的最大值，就用Integer最大值  if (newCapacity - MAX_ARRAY_SIZE > 0)    newCapacity = hugeCapacity(minCapacity);   // 扩容并赋值给原数组  elementData = Arrays.copyOf(elementData, newCapacity);}

可以看到：

• 扩容是以原容量的1.5倍扩容，并不是翻倍扩容
• 最大容量是Integer的最大值
• 添加元素时，没有对元素校验，可以是null

再看一下数组拷贝的逻辑，这里都是Arrays类里面的方法了：

/** * @param original  原数组 * @param newLength 新的容量大小 */public static <T> T[] copyOf(T[] original, int newLength) {    return (T[]) copyOf(original, newLength, original.getClass());}public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {    // 创建一个新数组，容量是新的容量大小    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;}

最终调用了System类的数组拷贝方法，是native方法：

/** * @param src     原数组 * @param srcPos  原数组的开始位置 * @param dest    目标数组 * @param destPos 目标数组的开始位置 * @param length  被拷贝的长度 */public static native void arraycopy(Object src,  int  srcPos,                                    Object dest, int destPos,                                    int length);

4. 删除单个元素

public boolean remove(Object o) {  	// 判断要删除的元素是否为null    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;}// 删除该位置上的元素private void fastRemove(int index) {    modCount++;  	// 计算需要移动的元素的个数    int numMoved = size - index - 1;    if (numMoved > 0)      	// 从index+1位置开始拷贝，也就是后面的元素整体向左移动一个位置        System.arraycopy(elementData, index+1, elementData, index, numMoved);  	// 数组最后一个元素赋值为null，防止会导致内存泄漏    elementData[--size] = null;}

可以知道，删除元素，就是遍历数组，循环比较是否等于目标值。如果相等，就把该位置后面的元素整体向左移动一个位置，再把数组最后一个元素赋值为null。

5. 批量删除

// 批量删除ArrayList和集合c都存在的元素public boolean removeAll(Collection<?> c) {    // 非空校验    Objects.requireNonNull(c);    // 批量删除    return batchRemove(c, false);}private boolean batchRemove(Collection<?> c, boolean complement){    final Object[] elementData = this.elementData;    int r = 0, w = 0;    boolean modified = false;    try {        for (; r < size; r++)            if (c.contains(elementData[r]) == complement)                // 把需要保留的元素左移                elementData[w++] = elementData[r];    } finally {				// 当出现异常的时候，可能不相等        if (r != size) {            // 1：可能是上面的for循环出现了异常            // 2：可能是其它线程添加了元素            System.arraycopy(elementData, r,                             elementData, w,                             size - r);            w += size - r;        }      	// 把不需要保留的元素赋值为null        if (w != size) {            for (int i = w; i < size; i++)                elementData[i] = null;            modCount += size - w;            size = w;            modified = true;        }    }    return modified;}

可以知道，批量删除的时候，只会进行一次数组拷贝，比用for循环单个删除效率更高，所以删除一批元素的时候，尽量用removeAll()方法。

5. 总结

本文分析了ArrayList的初始化、put、add、remove、动态扩容等方法的底层源码，相信大家对于ArrayList有了更深层次的了解，下篇一块学习一下LinkedList的源码。