ArrayList

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

类结构

类结构图

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

类结构解析

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 供给了两个办法增加元素

  1. 将元素刺进到数组尾部
  2. 按索引刺进到数组中

刺进尾部

平常中运用的最多的便是这种办法，它会将元素刺进到数组的尾部，类似于这样

不会吧，都2023年了，你还搞不懂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);
}
  1. elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，即 ArrayList 是经过无参结构函数创立而且还未进行扩容，那么将容量巨细扩大为10
  2. 需求的容量巨细现已大于数组的长度时，进行扩容，真实的扩容操作是 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;
}

从上面的扩容机制咱们能够得到以下信息

  1. 假如没有指定容量巨细，那么首次扩容之后容量巨细便是默许的容量巨细10
  2. 每一次扩容之后，容量巨细都是扩容前的1.5倍
  3. 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;
}
  1. 索引大于等于 size 时，抛出数组越界反常
  2. 获取该索引方位的值，将该方位的值替换，回来旧的值

删去元素

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;
}
  1. 假如是结尾删去，那么只需求将结尾的元素置为 null 即可
  2. 假如不是结尾删去，那么需求将 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;
}
  1. 假如元素不是 null ，经过元素的equals办法判别目标持平
  2. 遍历数组，获取该元素的索引，经过 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) 完全共同

总结

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

  1. ArrayList 底层根据数组，它的增删改查操作都是直接操作数组的
  2. ArrayList 的默许容量是10，每次扩容之后的容量是上一次的1.5倍，最大容量不超越整数最大值，原数组的数据会存到新数组中
  3. ArrayList 删去元素时，会判别是否是结尾删去，假如不是结尾删去那么需求将元素往前移，而且 ArrayList 不会削减容量，假如期望削减容量能够调用 trimToSize 办法
  4. ArrayList 不是线程安全的，它的底层操作都是未加锁的，假如需求线程安全 那么请运用 CopyOnWriteArrayList