ArrayList 源码分析

ArrayList 是最常用的 List 实现类,今天我们从源码角度来分析一下这个类。

一、基本结构

首先,我们来看一下 ArrayList 的继承关系,这是一个 UML 图:

file

对于 ArrayList,我们通常是这样使用的:

1
List<Object> list = new ArrayList<>();

下面我们简单看一下接口概要:

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

ArrayList 继承了 AbstractList 这个抽象类,实现了 List,RandomAccess,Cloneable 和序列化接口。

这里需要注意一下 RandomAccess 接口,这个接口没有任何方法,实现这个接口即意味着支持快速随机访问(下标访问)。快速随机访问速度 > 迭代器遍历速度。

快速随机访问的速度是固定的,比如 ArrayList 的 set(i, e), get(i) 等方法,其时间复杂度都是 O(1)


二、属性

查看 ArrayList 源码,我们看到它主要有如下一些属性,关于这些属性的描述都标注下面了:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认大小空实例的共享空数组实例,与 EMPTY_ELEMENTDATA 的区别在于前者知道当第一个元素插入时该如何扩充数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储这个 ArrayList 元素的数组。ArrayList 的容量就是这个数组的长度。任何空 ArrayList,如果其 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA,则当添加第一个元素时,ArrayList 会扩容到 DEFAULT_CAPACITY 大小。
transient Object[] elementData;
// ArrayList 的大小,指元素的个数
private int size;
// 数组可分配的最大大小
// 某些虚拟机在一个数组里保留了一些标题字。尝试分配更大的数组可能会导致 OutOfMemoryError
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

从基本属性可以看出, ArrayList 的底层是基于数组的!

Object[] elementData 这个属性

这里需要注意一点:

  • size 是实际元素数量,即 list.size()
  • elementData.length 是存储元素的数组的长度,一般是 >= size 的

三、三个构造器

平时使用 ArrayList,我个人习惯这样构造:

1
List<Integer> list = new ArrayList<>();

实际上,ArrayList 有三个构造器:默认构造器、带初始化容量参数的构造器、带集合参数的构造器

  • 默认构造器

    1
    2
    3
    4
    5
    // 使用默认容量 10 构造一个空的 List 
    public ArrayList() {
    // 这里可以看到使用了属性 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
  • 带初始化容量的构造器

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
    // 构建指定容量的数组
    this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
    // 使用 EMPTY_ELEMENTDATA
    this.elementData = EMPTY_ELEMENTDATA;
    } else {
    // 负数,抛出 IllegalArgumentException
    throw new IllegalArgumentException("Illegal Capacity: "+
    initialCapacity);
    }
    }
  • 带集合参数的构造器

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 构造一个包含指定集合元素的 list,元素顺序按照集合的迭代器返回的顺序
    public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
    // 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;
    }
    }

EMPTY_ELEMENTDATA 与 DEFAULT_EMPTY_ELEMENTDATA

两者的区别在于,使用前者时,当添加第一个元素时,elementData.length = 1;而当使用后者时,会调用 ensureCapacityInternal 方法,使 elmentData.length = DEFAULT_CAPACITY = 10

注意,扩容发生在实际插入元素的时候!使用前两个构造器,elementData 还是空数组。

下面重点总结一下 ArrayList 的扩容机制。


四、扩容机制

4.1 为什么要扩容?

个人理解是,当初始化 ArrayList 时,JVM 并不知道程序会存多少数据进去,而数组又必须在初始化时就声明其容量,这样就造成一个问题,最迟在第一个元素插入时,必须指定数组容量大小、初始化数组以容纳元素。(ArrayList 实际上也正是这么做的!)

那么,程序怎么知道你到底需要多大的容量呢?1 还是 100w ?

最好的办法是可以动态扩容!

ArrayList 就实现了这个扩容功能,我们可以调用方法主动扩容,也可以让 ArrayList 自己扩容。下面来讲一下 ArrayList 的扩容具体是怎么实现的。这个讲解主要是针对源码的分析。

4.2 扩容的实现

ArrayList 的扩容是由下面这段代码实现的,我已经加上了注释:

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
   // 扩容 ArrayList 实例,使其至少能放下 minCapacity 个元素
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 确保明确的容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 注意,这里递增了 modCount

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity); // 正式扩容
}

// 扩容,以确保该 elementData 数组的大小至少能容纳 minCapacity 个元素
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 即扩容到 1.5 倍,等价于 n = o + o/2
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}

// 可以扩容的最大容量,当想要扩容的容量大于 MAX_ARRAY_SIZE 时调用
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

可以看到,实际扩容方法是:grow(int minCapacity)。最关键的一行代码是:

1
int newCapacity = oldCapacity + (oldCapacity >> 1); // 等价于 n = o + o/2

这里使用位运算,它的速度非常快!

总结,ArrayList 的扩容是每次扩容到原大小的 1.5 倍。

那么,何时进行扩容呢?

4.3 何时扩容

public void ensureCapacity(int minCapacity) 可以看出,我们可以主动调用该方法进行扩容。

此外,在调用 add/addAll 等添加元素的方法时,ArrayList 也会调用内部扩容方法(ensureCapacityInternal)来主动扩容。以 add 方法为例:

1
2
3
4
5
6
// 追加元素 e 到 list 的末尾
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 我们主要,ensureCapacityInternal 这个方法会调用 ensureExplicitCapacity 这个方法,后者中一行代码 modCount++
elementData[size++] = e;
return true;
}

在上面的扩容方法,以及后面会提到的 add 等方法中,都利用了数组的底层方法。毕竟 ArrayList 是基于数组的嘛!下面我们来看一下这个数组的底层方法具体是什么意思?


五、数组底层方法

我们在 ArrayList 的源码中可以看到出现了两个有关数组复制操作的方法,一个是 Arrays 类中的 Arrays.copyOf 方法,一个是 System.arraycopy 方法,观察源码,前者是基于后者的:

5.1 Arrays.copyOf 方法

1
2
3
4
5
6
7
8
9
10
11
12
// 复制指定的数组,截断或填充 null 值使其达到指定长度
// 返回值与 original 数组具有相同的值
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 方法
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}

5.2 System.arraycopy 方法

1
2
3
public static native void arraycopy(Object src,  int  srcPos,
Object dest, int destPos,
int length);

详细解释一下:

  • 从原数组指定位置,拷贝数据到目标数组。拷贝从原数组的 srcPos 位置开始,拷贝到目标数组的 destPos 位置,拷贝长度为 length,即拷贝从原数组的 srcPos 到 srcPos+length-1,拷贝到目标数组的 destPos 到 destPos+length-1
  • 如果原数组和目标数组指向同一个数组对象,则首先拷贝到一个临时数组,然后把临时数组拷贝到原数组中
  • 参数:src - 原数组,srcPos - 原数组的拷贝开始位置;dest - 目标数组, destPos - 拷贝到目标数组的开始位置,length - 要拷贝的数组元素的数量

六、一个问题

看敖冰冰的文章,里面提到了这样一个问题:使用 public ArrayList(int initialCapacity) 这个构造器构建 ArrayList 时,何时初始化数组?

通过源码可以看到,在构造器被调用时,就初始化了数组 !

1
this.elementData = new Object[initialCapacity];

但是,我们需要注意了!这个时候还不能调用 list.get(i) 和 set(i, e) 方法。

嗯?嗯?嗯?!!

原因很简单,list 的 size 此时还是 0 !

而 ArrayList 添加元素、获取元素的操作都会对数组的边界值(index 和 size 的关系)进行检查。

比如 get(i) 方法:

1
2
3
4
public E get(int index) {
rangeCheck(index);
return elementData(index);
}

rangCheck 方法会检查 index 和 size 之间的关系,如果 index >= size,就会抛出异常:

1
2
3
4
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

比如:

1
2
3
4
5
public static void main(String[] args) {
List<Integer> list = new ArrayList<>(10);
Integer a = list.get(0);
System.out.println(a);
}

运行这段代码,会报以下异常:

1
2
3
4
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
at java.util.ArrayList.rangeCheck(ArrayList.java:657)
at java.util.ArrayList.get(ArrayList.java:433)
at com.aegis.MapTest.main(MapTest.java:13)

下面我们来总结一下 ArrayList 里的常用方法:


七、常用方法

下面是 ArrayList 源码中 public 方法的总结,目前不涉及 JDK 8 相关部分。

7.1 基本

void trimToSize()

  • 修改 ArrayList 实例的容量为当前 list.size(),即当前元素个数。使用这个方法可以使得 ArrayList 容量最小化
1
2
3
4
5
6
7
8
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

int size()

  • 返回 ArrayList 的大小。指具体元素的大小,而不是 elementData 数组的大小!
1
2
3
public int size() {
return size;
}

boolean isEmpty()

  • 如果 list 中没有元素,返回 true
1
2
3
public boolean isEmpty() {
return size == 0;
}

boolean contains(Object o)

  • 判定是否包括某个元素;调用了 indexOf 方法来判定
1
2
3
public boolean contains(Object o) {
return indexOf(o) >= 0;
}

int indexOf(Object o)

  • 返回指定元素出现的第一个位置 index;如果不存在,则返回 -1
1
2
3
4
5
6
7
8
9
10
11
12
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

int lastIndexOf(Object o)

  • 返回指定元素最后一次出现的位置;如果不存在,就返回 -1
  • 实际上是数组的倒序遍历
1
2
3
4
5
6
7
8
9
10
11
12
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

Object clone()

  • 返回一个数组的浅拷贝
  • 这里的浅拷贝不是指 List 本身,而是 List 中的元素。这里的浅拷贝是 Arrays.copyof 方法造成的。
1
2
3
4
5
6
7
8
9
10
11
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// 这是不应该发生的,因为 ArrayList 实现了 Clone 接口,即 Cloneable 的
throw new InternalError(e);
}
}

public void clear()

  • 从 list 中删除所有元素
1
2
3
4
5
6
7
8
9
public void clear() {
modCount++;

// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}

7.2 toArray

Object[] toArray()

  • 返回包括这个 list 中所有元素的数组,元素的顺序以 Iterator 返回的顺序为准。
  • 这个方法是 array 和 collection 相互转换的桥梁
1
2
3
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}

T[] toArray(T[] a)

  • 以指定数组的类型返回包括这个 list 中所有元素的数组
  • 如果数组 a 能够容纳这个 list 的元素,则将元素拷贝到这个数组中;否则,拷贝元素到一个新数组,其运行时类型由指定数组确定。
  • 如果数组 a 大于 list ,则 a[list.size()] = null
1
2
3
4
5
6
7
8
9
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);
if (a.length > size)
a[size] = null;
return a;
}

7.3 get/set/remove

E get(int index)

  • 获取 list 中指定位置的元素
1
2
3
4
5
6
public E get(int index) {
// 范围检查,如果 index 超出 list 大小,就抛出 IndexOutOfBoundsException
rangeCheck(index);

return elementData(index);
}

E set(int index, E element)

  • 使用指定元素 element 替换指定位置 index 处的元素
  • 返回原来的元素
1
2
3
4
5
6
7
8
9
10
public E set(int index, E element) {
// 检查边界
rangeCheck(index);

// 旧的元素
E oldValue = elementData(index);
// 设置 index 处为新元素 element
elementData[index] = element;
return oldValue;
}

boolean add(E e)

  • 在 list 末尾添加元素。如果成功就返回 true
1
2
3
4
5
6
7
public boolean add(E e) {
// 检查容量 - 即是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将 size 位置设为
elementData[size++] = e;
return true;
}

void add(int index, E element)

  • 在指定位置插入元素,并将原来的元素和其后的元素全部后移一位(index++)
1
2
3
4
5
6
7
8
9
10
11
12
13
public void add(int index, E element) {
// 检查边界
rangeCheckForAdd(index);

// 检查容量 - 如需要则扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将数组中 index 位置开始的数据,拷贝到 index+1 到 size 位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将 index 位置设为新元素
elementData[index] = element;
size++;
}

E remove(int index)

  • 移除指定位置的元素,将后面的元素左移一位(index–)
  • 返回删除的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E remove(int index) {
// 检查边界
rangeCheck(index);

// 修改 modCount,以便 fail-fast 机制生效
modCount++;
// 获取 index 位置的元素 -- 即要被删除的元素
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
// 向左移动元素
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将原先的最后一位设为 null
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

boolean remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean remove(Object o) {
if (o == null) {
// 要删除的对象为 null,则寻找第一个 null 值
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 调用 fastRemove
fastRemove(index);
return true;
}
} else {
//
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}

7.4 集合关联操作

boolean addAll(Collection<? extends E> c)

  • 将集合中所有元素按照迭代器返回的顺序,添加在 list 的末尾
  • 如果 list 被改变,就返回 true
1
2
3
4
5
6
7
8
9
10
11
public boolean addAll(Collection<? extends E> c) {
// 集合转数组
Object[] a = c.toArray();
int numNew = a.length;
// 确保容量
ensureCapacityInternal(size + numNew); // Increments modCount
// 从数组拷贝元素到 list 中
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

boolean addAll(int index, Collection<? extends E> c)

  • 从指定位置开始插入集合 c 中的元素,这些新元素的位置是按照集合的迭代器的返回顺序,直到所有元素插入完毕。并将之前的元素后移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean addAll(int index, Collection<? extends E> c) {
// 边界值检查
rangeCheckForAdd(index);

// 要插入的元素和数量
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;
if (numMoved > 0)
// 首先,后移之前的元素
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 然后插入新元素
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

boolean removeAll(Collection<?> c)

  • 删除集合 c 中在 list 中的相同元素。如果 list 发生改变,就返回 true
1
2
3
4
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}

boolean retainAll(Collection<?> c)

  • 删除 list 中不包括在集合 c 中的所有元素
1
2
3
4
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}

7.5 迭代器

List 返回的迭代器是 ListIterator 接口,比默认的 Iterator,多出了 hasPrevious 和 previous 方法。

ArrayList 中有两个 ListIterator 的实现类:ListItr 和 Itr。区别就是前者具有修改元素的 set 和 add 方法

listIterator

  • 返回这个 list 的元素的一个 list 迭代器,元素开始于指定位置。
1
2
3
4
5
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
  • 返回这个 list 的元素的一个 list 迭代器,元素从 0 位置开始
1
2
3
public ListIterator<E> listIterator() {
return new ListItr(0);
}

iterator

  • 返回这个 list 的迭代器
1
2
3
public Iterator<E> iterator() {
return new Itr();
}

ListItr 和 Itr 内部类

  • Itr 和 ListItr 的区别就是后者具有修改元素的方法 set 和 add

7.6 subList

  • 返回这个这个 list 的子视图,[fomIndex, toIndex)
  • 注意,subList 返回的子 list 和原 ArrayList 指向的是同一个数组。即,对子 list 的操作也会同步映射在原 ArrayList 上,反之亦然。
1
2
3
4
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}

八、总结

  • 基于数组,元素有序,支持快速随机访问,即下标访问。

  • 实现了动态扩容机制,每次扩容会增大到 1.5 倍

  • 元素可以为 null

  • 线程不安全。在多线程情况下,请使用 Collections.synchronizedList 方法把 ArrayList 包装为线程安全版本,或直接使用古老的 Vector


参考资料:

Java 集合深入理解之 AbstractList —— CSDN 拭心

Java 集合深入理解之 ArrayList —— CSDN 拭心

ArrayList 源码解析 —— JavaGuide

ArrayList 详细介绍 —— skywang12345

《吊打面试官》系列 - ArrayList —— 敖丙

空夜 wechat
欢迎扫一扫上面的微信公众号,第一时间订阅我的博客!