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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

由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

1
2
3
4
5
6
7
8

这就是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;
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

ArrayList提供了三个构造器：

• 空的构造器

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

使用该构造器创建一个ArrayList时，统一使用默认的空的一个数组来初始化elementData
1

• 指定容量

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);
  }
}
1
2
3
4
5
6
7
8
9
10

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

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

• 通过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;
    }
1
2
3
4
5
6

这里的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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

这里的操作也比较常规，就是将数组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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

修改数据

    public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
1
2
3
4
5
6

没什么说的

查找

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

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}
1
2
3
4
5
6
7
8

扩容操作

从上面有些方法的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)];
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这里的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);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

• 如果参考长度(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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11

• 实际需要的长度大于SOFT_MAX_ARRAY_LENGTH，要多少给多少

总结

通过简单分析ArrayList的源码，学习了Java中ArrayList的一些通用操作，增删改查以及扩容，当然，翻看源码还可以发现，ArrayList还提供了很多批量操作的API，其逻辑也不复杂。

ArrayList内部包含了一个实现了Iterator接口的内部类，用于遍历操作，但是Java的集合框架中，迭代器是一个通用的操作接口，后面再独立拿出来进行分析。

ArrayList中，扩容操作涉及到内存的分配和数据迁移操作，如果程序频繁发生扩容将会降低程序的性能，此时可以考虑提前预估ArrayList的大小，提前进行内存分配，减少内存重分配发生的次数。

ArrayList的查找和插入操作的平均时间复杂度是O(N), 如果在频繁插入和查找的场景可以尝试使用更高效的数据结构来代替。