Java集合框架之ArrayList源码分析-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java集合框架之ArrayList源码分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

简介

ArrayList是Java提供的线性集合，本篇笔记将从源码(java SE 17)的角度学习ArrayList：

什么是ArrayList？
ArrayList底层数据结构是怎么实现的？
作为一个容器，分析增删改查的过程
ArrayList的扩容机制

ArrayList底层数据结构

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    @java.io.Serial
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;
    ...
 }

由ArrayList的定义可知，ArrayList继承了AbstractList抽象类，实现了List、RandomAccess、Cloneable、Serializable接口

通过这一行：

/**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

这就是ArrayList维护的底层数据结构，用于存放元素，是一个Object数组。还注意到使用了一个关键字：transient ，该关键字是在对ArrayList进行序列化时，禁止对该字段进行序列化。该字段是默认访问权限

初始化

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList提供了三个构造器：

空的构造器

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

使用该构造器创建一个ArrayList时，统一使用默认的空的一个数组来初始化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);
  }
}

当使用一个整型变量初始化ArrayList时，根据initialCapacity的大小：

- 小于0会抛出非法参数异常
- 等于0使用内部维护的EMPTY_ELEMENTDATA来创建
- 大于0，此时创建一个指定大小的Object数组

通过Collection来创建，主要用于从其他类型的集合创建ArrayList

集合操作

ArrayList源码中提供了一堆add函数，但是可以将添加元素的操作分为两类：

追加元素
插入元素

追加元素

在末尾追加数据调用的都是同一个方法

    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

这里的elementData.length其实就是当前数组的容量，s这里传入的是size，也就是当前数组中实际元素的个数，首先会判断是否需要扩容,然后将数据追加到数组末尾。

插入数据

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }

这里的操作也比较常规，就是将数组index后面的元素向后面一次迁移，然后将index的位置设置为指定元素

删除数据

    public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }
    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }

逻辑也很简单，没啥说的，就是使用后面的数据覆盖掉index位置的数据

修改数据

    public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

没什么说的

查找

E elementData(int index) {
    return (E) elementData[index];
}

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

扩容操作

从上面有些方法的API中看到，如果向集合中添加元素时，此时会检查ArrayList的容量，如果容量不足会引发扩容，主要调用grow方法

    private Object[] grow() {
        return grow(size + 1);
    }
    
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

这里的preferred growth(参考增量)是原数组大小的一半，minGrowth是最小增量。

扩容可以分为四种情况：

如果原数组长度为0或者为默认的空数组对象

其实就是第一次向一个空的ArrayList添加元素，此时返回一个默认容量的数组, 默认容量为 10
如果根据计算得到的参考分配长度小于等于SOFT_MAX_ARRAY_LENGTH ,就返回该参考长度(这里我看网上很多文章说是扩容1.5倍，这其实是当最小增量小于原长度的一半时才发生的，所以并不准确，或者通过for循环依次追加时会发生，但是当批量添加时并不一定是1.5倍)

    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // preconditions not checked because of inlining
        // assert oldLength >= 0
        // assert minGrowth > 0

        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
    }

如果参考长度(prefLength)大于SOFT_MAX_ARRAY_LENGTH , 如果实际需要的容量小于SOFT_MAX_ARRAY_LENGTH，就分配SOFT_MAX_ARRAY_LENGTH

    private static int hugeLength(int oldLength, int minGrowth) {
        int minLength = oldLength + minGrowth;
        if (minLength < 0) { // overflow
            throw new OutOfMemoryError(
                "Required array length " + oldLength + " + " + minGrowth + " is too large");
        } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
            return SOFT_MAX_ARRAY_LENGTH;
        } else {
            return minLength;
        }
    }