死磕Jdk源码之ArrayList:

本博客目前所有 死磕 Jdk 源码系列都是使用 jdk1.8版本。

简介

List接口的可调整大小的数组实现。实现所有可选的列表操作,并允许所有元素,包括null。除了实现List接口之外,该类还提供了一些方法来操作数组的大小,该数组在内部用于存储List。(这个类大致相当于Vector,只是它是不同步的。)
sizeisEmptygetsetiteratorlistIterator操作在常数时间内运行。添加操作在平摊常数时间内运行,也就是说,添加n个元素需要O(n)个时间。所有其他操作都在线性时间内运行(粗略地说)。与LinkedList实现相比,常量因子较低。

以上是官方docsArrayList的描述

特性

  1. ArrayList实现List,得到了List集合框架基础功能
  2. ArrayList实现RandomAccess,获得了快速随机访问存储元素的功能,RandomAccess是一个标记接口,没有任何方法
  3. ArrayList实现Cloneable,得到了clone()方法,可以实现克隆功能
  4. ArrayList实现Serializable,表示可以被序列化,通过序列化去传输,典型的应用就是hessian协议。

它具有如下特点:

  • 容量不固定,随着容量的增加而动态扩容(阈值基本不会达到)
  • 有序集合(插入的顺序 == 输出的顺序)
  • 插入的元素可以为null
  • 增删改查效率更高(相对于LinkedList来说)
  • 线程不安全

数据结构

ArrayList的底层数据结构就是一个数组,对ArrayList的所有操作底层都是基于数组的。

线程安全性

如果非要在多线程的环境下使用ArrayList,就需要保证它的线程安全性,通常有两种解决办法:

  1. 使用synchronized关键字
  2. 使用Collections类中的静态方法synchronizedList()ArrayList进行调用即可。

成员变量

ArrayList有两个关键的成员变量

还有一个记录集合修改次数的变量,由iteratorlistIterator,如果在迭代过程中,modCount的值变更,就会抛出ConcurrentModificationException异常。

1
protected transient int modCount = 0;
  • elementData

存储ArrayList元素的数组缓冲区。ArrayList的容量是这个数组缓冲区的长度。任何空ArrayListelementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA,将在添加第一个元素时扩展为DEFAULT_CAPACITY

elementData就是实际维护的数组,对于一个空ArrayList来说,elementData就是一个空数组。会在第一次add元素时扩容为长度为DEFAULT_CAPACITY的数组。

  • size

ArrayList的大小(它包含的元素的数量)。这里的size指的是元素的个数,而不是数组的大小。

死磕源码

构造函数

无参构造函数,elementData 等于默认的空数组

1
2
3
4
5
6
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

根据给定的初始化容量大小创建ArrayList

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

从一个Collection集合创建ArrayList

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

添加元素

ArrayList提供两个方法添加单个元素,一个可以指定索引的添加元素方法,一个不需要指定索引的添加元素方法。

  • add(E e)

将指定的元素追加到此列表的末尾。

1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

ensureCapacityInternal方法中对modCount成员变量 +1,表示集合的修改次数,检查数组容量,是否需要扩容。

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

calculateCapacity方法是为了计算最小扩容量

1
2
3
4
5
6
7
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 也就是当前数组是个默认空数组,集合内无元素,此时返回 DEFAULT_CAPACITY 和 minCapacity 的最大值,否则就返回 minCapacity
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

ensureExplicitCapacity方法需要判断数组是否需要扩容

1
2
3
4
5
6
7
8
9
private void ensureExplicitCapacity(int minCapacity) {
// modCount + 1 记录修改次数
modCount++;

// 判断数组容量是否溢出
if (minCapacity - elementData.length > 0)
// 这里对数组进行扩容
grow(minCapacity);
}

grow方法,ArrayList扩容的核心方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void grow(int minCapacity) {
// 获取当前数组大小
int oldCapacity = elementData.length;
// 计算新的容量大小 = oldCapacity * 1.5 (右移一位 相当于 oldCapacity / 2)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 计算的新容量小于 minCapacity,就取 minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE,取 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);
}
  • add(int index, E element)

将指定元素插入其中的指定位置列表。移动当前处于该位置的元素(如果有)并向右的任何后续元素(将一个元素添加到它们的索引中)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void add(int index, E element) {

// 检查 index 是否合法
rangeCheckForAdd(index);

// 同 add(E e)
ensureCapacityInternal(size + 1); // Increments modCount!!

// 这里使用数组拷贝,把添加位置后的元素往后移,目的是为了空出当前索引位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 将元素插入指定的索引位
elementData[index] = element;
size++;
}

移除元素

  • remove(int index)

根据指定索引移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public E remove(int index) {

// 检查索引是否合法
rangeCheck(index);

// modCount 修改次数 +1
modCount++;

// 根据索引从数组中获取元素
E oldValue = elementData(index);

// 计算需要拷贝的数组长度
int numMoved = size - index - 1;
if (numMoved > 0)
// 对移除元素之后的元素进行数组拷贝,就是将被移除位之后的元素前移
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 集合的最后一位元素置空
elementData[--size] = null; // clear to let GC do its work

// 返回被移除的元素
return oldValue;
}
  • 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) {
// 如果 o 为 null,就删除第一个空元素
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
}
// 否则就移除第一个 equals o 的元素
else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}

remove(int index)方法逻辑相同,只是这里没有进行索引检查,因为索引本来就是从数组中遍历出来的

1
2
3
4
5
6
7
8
9
10
11
private void fastRemove(int index) {
// modCount 修改次数 +1
modCount++;
// 计算需要拷贝的数组长度
int numMoved = size - index - 1;
if (numMoved > 0)
// 对移除元素之后的元素进行数组拷贝,就是将被移除位之后的元素前移
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 集合的最后一位元素置空
elementData[--size] = null; // clear to let GC do its work
}

总结

  1. ArrayList底层维护一个数组
  2. ArrayList默认数组是一个空数组 {}
  3. ArrayList第一次添加元素时才会扩容到 capacity 大小
  4. ArrayList扩容为原容量到 1.5
  5. ArrayList通过索引添加元素可能会导致内存拷贝
  6. ArrayList移除元素可能需要内存拷贝

所以尽量不要使用索引去添加元素,索引添加元素的效率取决于索引的位置。理论上 size - index 的值越大,效率越低,因为需要拷贝的元素越多。(移除元素同理)