2023-08-20 11:07

关注

不会吧，都2023年了，你还搞不懂ArrayList吗？

ArrayList

在存储同类型数据的时候，我们第一反应就是使用 ArrayList。那么为什么要使用 ArrayList，亦或者说 ArrayList 的优势在哪里？下面我就以源码的角度去阅读 ArrayList，本篇文章的源码基于JDK 11，其他版本的源码基本一致，中心思维都是围绕扩容进行的。

类结构

类结构图

类结构解析

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

ArrayList 继承了 AbstractList，实现了 List 、RandomAccess 、Cloneable 和 Serializable 接口

ArrayList 实现了 RandomAccess 接口，表明了 ArrayList 支持快速随机访问
ArrayList 实现了 Cloneable 接口并重写了 clone 方法，表明了 ArrayList 可以被克隆
ArrayList 实现了 Serializable 接口，表明了 ArrayList 支持序列化

类属性

// 序列化版本UID
private static final long serialVersionUID = 8683452581122892189L;
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组，容量为0时置为EMPTY_ELEMENTDATA
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认大小空实例的共享空数组实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存放数据的数组
transient Object[] elementData;
// 元素个数
private int size;

ArrayList 将数据存放在数组中，这点与它的名字刚好对应上，那么 ArrayList 就具备了数组的特点，一段连续的内存空间并且支持元素下标进行查找。
ArrayList 的默认大小为10
通过 size 值可以获取元素个数

构造函数

ArrayList 有三个构造函数

// 不带参数的构造函数，将elementData置为默认空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 传入一个初始容量
public ArrayList(int initialCapacity) {
    // 根据容量大小创建数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
      // 容量为null时，置为空数组  
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 传入一个集合
public ArrayList(Collection<? extends E> c) {
    // 将集合转为数组
    elementData = c.toArray();
    // 集合不为空
    if ((size = elementData.length) != 0) {
        // 集合的元素类型不是object时，转为object数组
        // 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;
    }
}

ArrayList 的三个构造函数都是围绕着初始化 elementData

添加元素

添加元素的方法是 add，ArrayList 提供了两个方式添加元素

将元素插入到数组尾部
按索引插入到数组中

插入尾部

平时中使用的最多的就是这种方式，它会将元素插入到数组的尾部，类似于这样

public boolean add(E e) {
    // 保证元素可以插入到数组末尾，其实就是看需不需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将size位置的元素赋值，然后size自增1
    elementData[size++] = e;
    // 插入成功返回true
    return true;
}

按索引插入

ArrayList 允许我们通过索引插入元素，如果索引值大于数组长度时抛出数组越界异常

public void add(int index, E element) {
    // index大于size或者小于0时，抛出数组越界异常
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    // 保证元素可以插入到数组末尾，其实就是看需不需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将index位置之后的元素往后移
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 往index位置上插入元素
    elementData[index] = element;
    // size自增1
    size++;
}

按索引插入时，插入的索引并不是小于数组长度就可以了，它只支持中间插入和尾部插入，因为它要保证数组的连续性

我们从这两种插入方式可以看出，无论是尾部插入还是按索引插入，其中心都是围绕着需不需要扩容，如果可以插入该元素则不扩容，如果原数组无法插入该元素，则需要进行扩容后再进行插入。

那么我们来看下 ArrayList 的扩容机制吧

扩容机制

ArrayList 通过 ensureCapacityInternal 方法判断是否需要扩容

private void ensureCapacityInternal(int minCapacity) {
    // 如果elementData是默认空数组时，获取到容量的大小
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 默认容量是10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // modCount自增
    modCount++;

    // 需要的容量大小已经大于数组的长度时，进行扩容
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        // 真正的扩容操作
        grow(minCapacity);
}

elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，即 ArrayList 是通过无参构造函数创建并且还未进行扩容，那么将容量大小扩大为10
需要的容量大小已经大于数组的长度时，进行扩容，真正的扩容操作是 grow 方法

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code
    // 原数组的容量大小
    int oldCapacity = elementData.length;
    // 新数组的容量大小=原数组容量大小的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新数组的容量大小小于需要的最小容量时，将容量大小置于最小容量大小
    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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // ArrayList的容量最大也只能是Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

从上面的扩容机制我们可以得到以下信息

如果没有指定容量大小，那么首次扩容之后容量大小就是默认的容量大小10
每一次扩容之后，容量大小都是扩容前的1.5倍
ArrayList 最大容量是整数的最大值 Integer.MAX_VALUE

查找元素

ArrayList 查找方式与数组的查找方式一样都是基于元素索引，毕竟存放的数据都在数组里

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

    return (E) elementData[index];
}

索引大于等于 size 时，抛出数组越界异常，否则返回数组下标值

修改元素

ArrayList 提供了 set 方法供我们修改元素，修改成功后返回该位置的旧值

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

索引大于等于 size 时，抛出数组越界异常
获取该索引位置的值，将该位置的值替换，返回旧的值

删除元素

ArrayList 提供了多种删除元素的方式，这里我只讲常用到的两种方式，其他的方式小伙伴们可以自行查阅。

按索引删除

删除成功之后返回该位置的值

public E remove(int index) {
    // 索引大于size时，抛出数组越界异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    // 获取该位置的值
    E oldValue = (E) elementData[index];

    // 判断是不是末尾删除
    int numMoved = size - index - 1;
    // 如果不是末尾删除，那么需要将index之后的元素往前移
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将size自减1，将末尾的元素置为null
    elementData[--size] = null; // clear to let GC do its work

    // 返回该位置的值
    return oldValue;
}

如果是末尾删除，那么只需要将末尾的元素置为 null 即可
如果不是末尾删除，那么需要将 index 后面的元素往前移，最后将末尾的元素置为 null

按元素删除

如果删除成功，返回 true，否则返回 false

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++)
            // 元素不为空时，通过equals方法判断对象相等
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

如果元素不是 null ，通过元素的equals方法判断对象相等
遍历数组，获取该元素的索引，通过 fastRemove 删除

private void fastRemove(int index) {
    modCount++;
    // 判断是不是末尾删除    
    int numMoved = size - index - 1;
    // 如果不是末尾删除，那么需要将index之后的元素往前移
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将size自减1，将末尾的元素置为null
    elementData[--size] = null; // clear to let GC do its work
}

可以看到 fastRemove 的逻辑和 remove(int index) 完全一致

总结

上面说了那么多，现在我来做一个总结，面试中可能就会问到

ArrayList 底层基于数组，它的增删改查操作都是直接操作数组的
ArrayList 的默认容量是10，每次扩容之后的容量是上一次的1.5倍，最大容量不超过整数最大值，原数组的数据会存到新数组中
ArrayList 删除元素时，会判断是否是末尾删除，如果不是末尾删除那么需要将元素往前移，并且 ArrayList 不会减少容量，如果希望减少容量可以调用 trimToSize 方法
ArrayList 不是线程安全的，它的底层操作都是未加锁的，如果需要线程安全那么请使用 CopyOnWriteArrayList