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

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

ArrayList

类结构

类结构图

类结构解析

类属性

结构函数

增加元素

刺进尾部

按索引刺进

扩容机制

查找元素

修正元素

删去元素

按索引删去

按元素删去

总结

作者信息

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

ArrayList

类结构

类结构图

类结构解析

类属性

结构函数

增加元素

刺进尾部

按索引刺进

扩容机制

查找元素

修正元素

删去元素

按索引删去

按元素删去

总结

相关文章

这个超时问题难住了我至少三位同事

区块链技术原理

OOP 思想在 TCC/APIX/GORM 源码中的应用

Compose 中嵌套原生 View 原理

作者信息