ArrayList的 fast-fail(快速失败) 机制

本文主要讲了 ArrayList的 fast-fail(快速失败)机制。

为什么集合可以使用 foreach 循环

我们发现,在java中,我们使用集合都可以通过foreach来遍历,就像下面的代码一样

1
2
3
4
5
6
List<Integer> list = new ArrayList<>();
list.add(1);
for (Integer integer : list) {
// 循环体内代码
System.out.println(integer);
}

上面那种迭代方法去除语法糖之后实际等价于以下写法

1
2
3
4
5
6
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer integer = iterator.next();
// 循环体内代码
System.out.println(integer);
}

其原理其实很简单,这是一个java的语法糖,只要类实现了接口 Iterable 就可以。因为所有的集合都实现了一个父接口 Collection,而 Collection 继承了 Iterable。所有只要在 iterator() 方法中返回一个 Iterator,foreach 会自动调用这个 Iterator 的方法去遍历这个接口。因此所有的集合都能通过 foreach 来遍历。以下 Iterable 的源码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Iterable<T> {

Iterator<T> iterator();

default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}

default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}

知道了原理,我们自己可以动手试一试,自己实现一个队列或者栈,通过实现这个接口来达到被 foreach 遍历的功能。

为什么在 foreach 的时候 调用 remove 会抛出异常

既然我们知道了上面的原理,那要找到原因我们只需要看 ArrayList 的 iterator() 方法返回的迭代器实现的方法即可。翻阅源码我们看到以下代码。

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
public Iterator<E> iterator() {
return new Itr();
}


private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
// 复制集合的修改次数并保存
int expectedModCount = modCount;

Itr() {}

public boolean hasNext() {
return cursor != size;
}

@SuppressWarnings("unchecked")
public E next() {
// 快速失败的核心代码
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}

final void checkForComodification() {
// 如果集合的修改次数不等于迭代器创建时,则抛出并发修改异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

在此之前我们需要讲一讲这个 modcount 是什么,其实这个很简单,就是集合内部的一个修改记录的变量,只要执行集合的 add、remove、sort 等方法,都会执行 modCount++ 来记录一下集合的修改次数。

上一节我们知道,foreach 方法等价于执行 while 迭代器的操作。我们可以看到,Iterator 的 next() 方法中,调用了 checkForComodification() 方法,而此方法的唯一作用就是判断 modCount 是否等于创建迭代器时候保存的 expectedModCount,如果不等于则抛出并发修改异常。而在什么时候会不等于呢,那就是创建迭代器后,对集合进行了会递增 modcount 的操作。而 add、remove、sort 都会对集合进行操作记录(也就是 modcount++)因此只要在 foreach 中对原集合执行这些方法,都会导致异常的产生。

另一种 foreach 循环

之前 Iterable 接口的方法,我们看到了一个 default 的 forEach 方法。这是在 java8 中新增的方法,其本质也是利用了函数式编程简化了一下我们对 foreach 的调用,本质并无区别。但是 ArrayList 对这个方法进行了重写,改用成最基本的 for 循环实现,判断快速失败的机制与迭代器并无二样,都是通过记录 modcount 并判断是否一致来确保迭代过程是否修改过原集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

对 Iterator 的一些补充

ArrayList 中,除了实现了继承而来的 iterator() 方法,也有一些其他的 iterator,例如 spliterator 和 listIterator。foreach 调用的只有继承而来的 iterator() 方法返回的迭代器的方法,其他的迭代器只是增加了一些迭代器的功能,因为和本文无关,有兴趣的可以自己去了解一下。