Java集合之ArrayList类源码剖析

ArrayList类源码剖析

一、ArrayList类的简介

ArrayList的底层是数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的次数。ArrayList中可以存储任何类型的对象，包括null值。不过，不建议向ArrayList中添加null值，因为null值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。ArrayList的size、isEmpty、get、set、iterator和listIterator方法都是常量时间复杂度，而add方法则是均摊常量时间复杂度，也就是说，连续添加n个元素所需的时间为0(n)。所有其他方法的时间复杂度粗略算则都是线性时间复杂度。

需要注意：ArrayList的实现是非同步的，如果多个线程并发访问ArrayList实例，并且至少有一个线程对该实例做结构性修改(结构性修改指的是添加或删除一个或多个元素或显式调整数组大小的任何操作;仅设置元素的值不是结构性修改)，则ArrayList实例必须被外部同步。这通常是通过在自然封装列表的某个对象上进行同步来实现的。如果不存在此类对象，则应使用Collections.synchronizedList方法包装列表。最好在创建时执行此操作，以防止意外地对列表进行不同步访问。

List list = Collections.synchronizedList(new ArrayList(…));

此类的iterator和listIterator方法返回的迭代器是fail-fast(快速失败)的：如果在创建迭代器后的任何时间对列表进行结构性修改，则除了通过迭代器自己的remove或add方法之外，迭代器将抛出ConcurrentModificationException。因此，面对并发修改，迭代器会快速而干净地失败，而不是冒着在未来不确定的时间出现任意、非确定性行为的风险。

请注意，迭代器的快速失败行为无法得到保证，因为一般来说，在存在不同步并发修改的情况下不做出任何强保证。快速失败迭代器会尽力抛出ConcurrentModificationException。因此，编写依赖于此异常来确保其正确性的程序是错误的：==迭代器的快速失败行为应该仅用于检测错误==。

ArrayList继承于AbstractList，实现了List,RandomAccess,Cloneable,java.io.Serializable这些接口。

1
2
3
4
public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

}

  • List:表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。

  • RandomAccess:这是一个标志接口，表明实现这个接口的List集合是支持快速随机访问的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。

  • Cloneable:表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。

  • Serializable:表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

ArrayList 类图

二、ArrayList类的比较

  • 是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全；

  • 底层数据结构：ArrayList底层使用的是Object数组；LinkedList底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）

  • 插入和删除是否受元素位置的影响：

    • ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候，ArrayList会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置i插入和删除元素的话(add(int index, E element))，时间复杂度就为O(n)。因为在进行上述操作的时候集合中第i和第i个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
    • LinkedList采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响(add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、removeLast())，时间复杂度为O(1)，如果是要在指定位置i插入和删除元素的话(add(int index, E element)，remove(Object o),remove(int index))，时间复杂度为O(n)，因为需要先移动到指定位置再插入和删除。

  • 是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList(实现了RandomAccess接口)支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

  • 内存空间占用：ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据)。

三、ArrayList类的重要字段

1
2
3
4
5
6
7
8
9
10
// 默认的初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 用于空实例的共享空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认容量的空实例的共享空数组，我们将其与EMPTY_ELEMENTDATA区分开来，以明确添加第一个元素时要扩展多少空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 实际存放ArrayList数据的数组缓冲区，其长度就是ArrayList的容量
transient Object[] elementData; // non-private to simplify nested class access
// 包含的元素的数量
private int size;

四、ArrayList类的构造方法

该构造方法构造一个初始容量为10的空列表。当第一次添加元素时，内部的数组缓冲区会自动扩展到容量为10。

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

该构造方法构造一个初始容量为initialCapacity的空列表。注意：ArrayList()与ArrayList(0)的效果有所不同，具体表现在扩容时情况，前者会直接扩容为容量10，后者则会逐步扩容为容量1、2、3、4、6、9、13等等。

1
2
3
4
5
6
7
8
9
10
11
12
13
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 指定初始容量大于0，创建对应大小的底层Object数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 指定初始容量等于0，底层Object数组指向空实例的共享空数组EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 指定初始容量小于0，抛出IllegalArgumentException
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

该构造方法构造一个包含指定集合的元素的列表，按照集合迭代器返回这些元素的顺序进行排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ArrayList(Collection<? extends E> c) {
    // 按照集合迭代器的遍历顺序返回的Object数组
    Object[] a = c.toArray();
    // 更新集合的size
    if ((size = a.length) != 0) {
        // 更新elementData
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

五、ArrayList类的扩容机制

当我们使用无参构造函数构造出一个ArrayList的空实例后，默认没有创建Object数组，直到我们第一次调用add方法往ArrayList实例中添加元素，此时会发现底层数组自动创建。

1
2
3
4
5
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

modCount字段是父类AbstractList的保护字段，在iterator和listIterator方法返回的迭代器和列表迭代器中使用，主要用于fail-fast(快速失败)机制，后面会专门谈到。add(E e)内部会调用私有重载方法add(E e, Object[] elementData, int s)。

1
2
3
4
5
6
7
8
9
private void add(E e, Object[] elementData, int s) {
    // 如果容量已满则需要扩容
    if (s == elementData.length)
        elementData = grow();
    // 指定位置添加元素
    elementData[s] = e;
    // 正常情况下传入的参数s是原先的size，发生的是末尾插入
    size = s + 1;
}

重点内容是grow方法，会增加ArrayList实例的容量，确保至少能容纳minCapacity数量的元素。

1
2
3
4
5
6
7
8
private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

具体扩容的策略则集中体现在newCapacity方法中，基本的逻辑就是==新容量=Max(1.5*oldCapacity, minCapacity)==，当然需要额外考虑一些溢出的情况（元素过多），此时可能会抛出OutOfMemoryError或者计算==新容量=minCapacity>MAX_ARRAY_SIZE?Integer.MAX_VALUE:Max_ARRAY_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
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 位运算操作相对除法高效，默认扩容1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        // 无参构造函数的ArrayList实例默认第一次扩容到容量为10即DEFAULT_CAPACITY
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        // 数组大小溢出，抛出OutOfMemoryError
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    // 当newCapacity没有超出上界时正常扩容，否则使用hugeCapacity重新计算新容量
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果上界能够容纳minCapacity数量的元素，则使用上界MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)，否则只能使用Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

基本上扩容前期都是走扩容1.5倍的逻辑，直到列表内容过多，再次扩容时发现oldCapacity*1.5溢出了，直接扩容到容量为MAX_ARRAY_SIZE，如果最后列表大小到达MAX_ARRAY_SIZE时再次扩容到Integer.MAX_VALUE，如果继续添加元素直至超出最大限制则发生OOM。

最终的新数组扩容拷贝调用了工具方法Arrays.copyOf，复制指定的数组，截断或用空值填充（如有必要），以便副本具有指定的长度。对于在原始数组和副本中均有效的所有索引，这两个数组将包含相同的值。对于在副本中有效但在原始数组中无效的任何索引，副本将包含null。

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
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

/**
 * 复制数组
 * @param src 源数组
 * @param srcPos 源数组中的起始位置
 * @param dest 目标数组
 * @param destPos 目标数组中的起始位置
 * @param length 要复制的数组元素的数量
 */
public static native void arraycopy(Object src,  int srcPos,
                                    Object dest, int destPos,
                                    int length);

arraycopy()需要目标数组，将源数组拷贝到目标数组中，而且可以选择拷贝的起点和长度以及放入新数组中的位置，copyOf()是系统自动在内部新建一个数组，并返回该数组。看两者源代码可以发现copyOf()内部实际调用了System.arraycopy()方法。

六、ArrayList类的快速失败机制

要想理解ArrayList类的快速失败机制，我们首先需要先了解父类AbstractList类的modCount字段的含义。modCount字段的值表示此列表在结构上被修改的次数。结构性修改是那些改变列表大小的修改，或者以其他方式扰乱列表的修改，以致正在进行的迭代可能会产生不正确的结果。该字段由iterator和listIterator方法返回的迭代器和列表迭代器实现使用。如果该字段的值意外更改，迭代器(或列表迭代器)将抛出ConcurrentModificationException来响应next、remove、previous、set或add操作。这提供了快速失败行为，而不是在迭代过程中面对并发修改时的非确定性行为。

AbstractList子类对该字段的使用是可选的。如果子类希望提供快速失败迭代器（和列表迭代器），那么它只需在其add(int E)和remove(int)方法（以及它覆盖的导致结构性修改的任何其他方法）中增加此字段。对add(int E)或remove(int)的单次调用必须向该字段添加不超过1，否则迭代器（和列表迭代器）将抛出虚假的ConcurrentModificationExceptions。如果实现不希望提供快速失败迭代器，则可以忽略该字段。

1
protected transient int modCount = 0;

前面提到ArrayList类的快速失败机制在iterator和listIterator方法返回的迭代器和列表迭代器中集中实现，我们简单看一个iterator方法的内容，发现其返回一个构造的Itr内部类的实例对象。

1
2
3
public Iterator<E> iterator() {
    return new Itr();
}

观察Itr内部类的源码，发现ArrayList类应用了modCount字段实现快速失败机制，在迭代器的操作中一旦发现并发的结构性修改，会尽可能地抛出ConcurrentModificationException中止后续的任何操作，防止出现不确定的行为。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    // 记录创建迭代器对象时ArrayList实例的结构性修改次数，类比于记录快照
    int expectedModCount = modCount;

    // prevent creating a synthetic constructor
    Itr() {
    }

    // 判断是否还有下一个元素
    public boolean hasNext() {
        // 遍历下一个元素直到末尾
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        // 检查ArrayList结构一致性，快速失败机制
        checkForComodification();
        int i = cursor;
        // size及后面的元素都是无效元素
        if (i >= size)
            throw new NoSuchElementException();
        // 外部类对象即ArrayList实例的Object数组
        Object[] elementData = ArrayList.this.elementData;
        // 超出容量限制
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // 下一个待遍历的元素索引cursor后移一位
        cursor = i + 1;
        // 更新最后返回元素的索引lastRet
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        // lastRet==-1
        if (lastRet < 0)
            throw new IllegalStateException();
        // 检查ArrayList结构一致性
        checkForComodification();
        try {
            // 删除迭代器最后返回的元素（modCount会加一）
            ArrayList.this.remove(lastRet);
            // 下一个待遍历的元素索引cursor前移一位至lastRet
            cursor = lastRet;
            // 重置最后返回元素的索引lastRet
            lastRet = -1;
            // 更新迭代器中保存的结构性修改次数
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            // 对ArrayList对象并发的结构性修改如remove可能会导致数组越界异常
            throw new ConcurrentModificationException();
        }
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i < size) {
            final Object[] es = elementData;
            if (i >= es.length)
                throw new ConcurrentModificationException();
            // 遍历迭代器后续的所有元素
            for (; i < size && modCount == expectedModCount; i++)
                action.accept(elementAt(es, i));
            // update once at end to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
    }

    final void checkForComodification() {
        // 如果发现此时的modCount改变了，说明期间ArrayList实例发生了结构性修改
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

ListItr是Itr的进一步子类，不过增加了一些新特性如可以往前遍历、设置元素、添加元素等，逻辑跟Itr基本类似。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        // 初始化Itr父类
        super();
        // 开始的索引位置确定为index
        cursor = index;
    }

    public boolean hasPrevious() {
        // cursor-1表示下一个向前待遍历的元素
        return cursor != 0;
    }

    public int nextIndex() {
        // 【向后】待遍历的下一个元素索引
        return cursor;
    }

    public int previousIndex() {
        // 【向前】待遍历的下一个元素索引
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        // 检查ArrayList结构一致性
        checkForComodification();
        // 前置元素的索引
        int i = cursor - 1;
        // 首元素前的都是无效元素
        if (i < 0)
            throw new NoSuchElementException();
        // 外部类对象即ArrayList实例的Object数组
        Object[] elementData = ArrayList.this.elementData;
        // 超出容量
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // cursor前移一位
        cursor = i;
        // 更新最后返回元素的索引lastRet
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        // lastRet==-1
        if (lastRet < 0)
            throw new IllegalStateException();
        // 检查ArrayList结构一致性
        checkForComodification();
        try {
            // 设置ArrayList实例对象在迭代器最后返回元素索引处的值
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            // 对ArrayList对象并发的结构性修改如remove可能会导致数组越界异常
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        // 检查ArrayList结构一致性
        checkForComodification();
        try {
            int i = cursor;
            // 在指定索引处添加元素（modCount会加一）
            ArrayList.this.add(i, e);
            // 待遍历的元素位置后移一位
            cursor = i + 1;
            // 重置最后返回元素的索引lastRet
            lastRet = -1;
            // 更新列表迭代器中保存的结构性修改次数
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            // 对ArrayList对象并发的结构性修改如remove可能会导致数组越界异常
            throw new ConcurrentModificationException();
        }
    }
}

七、ArrayList类的常用方法

ArrayList作为开发者最常用的集合类之一，我们有必要研究一下它的常用方法的实现原理，其实也不难，毕竟ArrayList底层就是一个Object数组，所有对外开放的方法都是对该数组操作的一些封装而已，下面我们按照经典CRUD的思想简单粗暴地把ArrayList类的方法划分为增删改查四大类。

相关的查找方法

get方法作为最常用的查找方法，首先需要通过checkIndex方法检查索引参数的有效性，如果index < 0 || index >= size则抛出outOfBoundsCheckIndex，参数校验通过后elementData方法获取底层数组相应索引位置处的元素。

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

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

indexOf方法用于查找指定对象在ArrayList中第一次出现的位置，如果没有则返回-1。更正式地说，返回满足Objects.equals(o, get(i))的最低索引i，如果没有这样的索引，则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        // null采用==比较
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        // 非null采用equals方法比较
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

lastIndexOf方法用于查找指定对象在ArrayList中最后一次出现的位置，如果没有则返回-1。更正式地说，返回满足Objects.equals(o, get(i))的最高索引i，如果没有这样的索引，则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int lastIndexOf(Object o) {
    return lastIndexOfRange(o, 0, size);
}

int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        // null采用==比较
        for (int i = end - 1; i >= start; i--) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        // 非null采用equals方法比较
        for (int i = end - 1; i >= start; i--) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

相关的修改方法

trimToSize方法将此ArrayList实例的容量修剪为列表的当前大小。应用程序可以使用此操作来最小化ArrayList实例的存储空间。

1
2
3
4
5
6
7
8
9
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        // 裁剪ArrayList实例的容量，空实例需要额外注意
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

set方法设置指定索引位置处的元素为新值，并返回原来的元素oldValue。

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

相关的增加方法

add方法在此列表中的指定位置插入指定元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动（将其索引加一）。首先使用rangeCheckForAdd方法检查索引参数的有效性，当index < 0 || index > size时抛出IndexOutOfBoundsException；通过参数校验后，如果底层数组已满则需要扩容，否则使用System.arraycopy方法移动index及后续所有元素，最终在index索引处添加指定元素element，更新当前size。

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

相关的删除方法

remove方法删除此列表中指定位置的元素。将所有后续元素向左移动（从索引中减去 1）。同样的先检查索引参数有效性，如果index < 0 || index >= size则抛出IndexOutOfBoundsException，参数校验通过后取出指定位置的元素最后返回，真正的删除操作在fastRemove中实现。fastRemove方法是私有删除方法，跳过边界检查并且不返回删除的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
    // 如果删除的是最后一个元素即es[size - 1],则不需要进行数组的拷贝移动
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    // 无效元素的界限
    es[size = newSize] = null;
}

其他的常用方法

ArrayList 源码中有一个 ensureCapacity 方法不知道大家注意到没有，这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，那么这个方法有什么作用呢？理论上来说，最好在向 ArrayList 添加大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数。

1
2
3
4
5
6
7
8
9
public void ensureCapacity(int minCapacity) {
    // 其实含义就是传入的minCapacity大于后续初始化的默认扩容容量大于当前数组容量，并且【如果数组使用默认无参构造还未初始化时，minCapacity大于后续初始化的默认扩容容量DEFAULT_CAPACITY】
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

我们通过下面的代码实际测试以下这个方法的效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class EnsureCapacityTest1 {
	public static void main(String[] args) {
		ArrayList<Object> list = new ArrayList<Object>();
		final int N = 10000000;
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < N; i++) {
			list.add(i);
		}
		long endTime = System.currentTimeMillis();
		System.out.println("使用ensureCapacity方法前："+(endTime - startTime));

	}
}

image-20230927111929285

1
2
3
4
5
6
7
8
9
10
11
12
13
public class EnsureCapacityTest2 {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1));
    }
}

image-20230927112048202

通过运行结果，我们可以看出向 ArrayList 添加大量元素之前使用ensureCapacity 方法可以提升性能。不过，这个性能差距几乎可以忽略不计。而且，实际项目根本也不可能往 ArrayList 里面添加这么多元素。

toArray方法返回一个数组，其中按正确顺序（从第一个元素到最后一个元素）包含此列表中的所有元素。返回的数组将是“安全的”，因为该列表不维护对它的引用（换句话说，这个方法必须分配一个新的数组）。因此，调用者可以自由修改返回的数组。此方法充当基于数组的API和基于集合的API之间的桥梁。

1
2
3
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

toArray泛型方法返回一个数组，其中按正确顺序（从第一个元素到最后一个元素）包含此列表中的所有元素；返回数组的运行时类型是指定数组的运行时类型。如果列表适合指定的数组，则将列表内容拷贝到数组中。否则，将使用指定数组的运行时类型和此列表的大小分配一个新数组。如果列表适合指定的数组，并且有空闲空间（即数组的元素比列表多），则数组中紧随集合末尾的元素将设置为 null。（仅当调用者知道列表不包含任何空元素时，这对于确定列表的长度很有用。）

1
2
3
4
5
6
7
8
9
10
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    // 多余的空间用null做界限划分
    if (a.length > size)
        a[size] = null;
    return a;
}

sort方法根据传入的比较器对象对底层的Object数组进行排序操作，如果在排序过程中发生了并发的结构性修改，会抛出ConcurrentModificationException，否则递增modCount的值。

1
2
3
4
5
6
7
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    modCount++;
}

参考文章：ArrayList源码分析