当前位置： 首页>编程语言>正文

Java集合框架中，通过modCount来实现Fail-Fast机制

编程语言2024-11-29 19:10:05

一、Fail-Fast与Fail-Safe

1. Fail-Fast

即是快速失败机制。
遍历集合元素时候，如果集合结构发生了修改，立即抛出异常，以防止继续遍历。

2. Fail-Safe

相对于Fail-Fast来讲，不会抛出异常。它会将集合复制出一份以进行操作，存在缺点如下：

  1. 复制过程的额外时间和空间开销。
  2. 不能保证遍历的是最新的内容。

二、Fail-Fast案例

1. 案例一：增强for循环中调用list对象的remove方法移除元素

public class FailFastTest {

    @Test
    @SuppressWarnings("all")
    public void testFail() {
        List<Integer> ints = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6));
        for (Integer anInt : ints) {
            if (anInt % 3 == 0) {
                // 在用增强for循环遍历的时候，修改集合结构，会抛出ConcurrentModificationException
                ints.remove(anInt);
            }
        }
        ints.forEach(System.out::println);
    }
}

运行结果即是，抛出了并发修改异常。
增强for循环的具体实现，其实是迭代器。所以我们继续看案例二。

java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911)
    at java.util.ArrayList$Itr.next(ArrayList.java:861)
    at com.se.FailFastTest.testFail(FailFastTest.java:24)

2. 案例二：迭代器中调用list对象的remove方法移除元素

public class FailFastTest {

    @Test
    @SuppressWarnings("all")
    public void testFail2() {
        // 两种实现交替打开，以观察运行结果
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6));
//        List<Integer> list = new CopyOnWriteArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6));

        Iterator<Integer> iterator = list.iterator();
        while(iterator.hasNext()){
            Integer next = iterator.next();
            if (next % 3 == 0) {
                list.remove(next);
            }
        }
        list.forEach(System.out::println);
    }
}

不出意外，运行结果和以上一致，抛出并发修改异常。

三、Fail-Fast实现机制分析

1. 报错源定位

报错的方法，即是【ArrayList类】的【内部类迭代器Itr】的checkForComodification方法。我们来看看代码。

private class Itr implements Iterator<E> {
    // ...省略其他属性
    
    // 【期待修改次数】
    int expectedModCount = modCount;

    @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];
    }

    final void checkForComodification() {
        // 修改次数不一致则抛出异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

    // ...省略其他方法
}

当modCount与expectedModCount不一致时候，则抛出了并发修改异常。

  1. expectedModCount变量，是内部类迭代器维护的属性。
  2. modCount呢？

2. 相关变量来源及定义——modCount。

modCount是ArrayList抽象类【AbstractList】的属性。用于记录结构修改（如添加、删除）的次数。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    
    // 省略其他属性和方法
    
    protected transient int modCount = 0;
}

实例类ArrayList进行【添加和移除】等操作的时候，会将此属性进行自增操作，标记我们对集合进行了结构修改。以添加为例：

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

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    // ...省略其属性和方法
}

3. 机制分析

迭代时，不论是增强for还是forEach，还是iterator，都会创建一个内部迭代器对象。将modCount的值，赋值给expectedModCount。
这个值在该迭代器生命周期内，是不会修改的。

重新看我们的代码。

public class FailFastTest {

    @Test
    @SuppressWarnings("all")
    public void testFail2() {
        // 两种实现交替打开，以观察运行结果
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6));
//        List<Integer> list = new CopyOnWriteArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6));

        Iterator<Integer> iterator = list.iterator();
        while(iterator.hasNext()){
            Integer next = iterator.next();
            if (next % 3 == 0) {
                list.remove(next);
            }
        }
        list.forEach(System.out::println);
    }
}
  1. 报错的行数是第12行next方法。说明检测到了modCount与expectedModCount不一致。
  2. 进行代码调试时发现。
    1. list移除第3个元素list[2]已经成功；
    2. 迭代下一个元素list[3] = 4时，抛出异常。

4. Fail-Fast理解

  1. 移除元素已经成功；
  2. 通过标记变量可以发现它是在迭代时修改，所以阻止了它继续执行，果然是快速失败。

5. 优化替代方案

1) 通过迭代器的remove方法进行移除

迭代器中的remove()方法不带参数，内部维护索引，看它的实现。

private class Itr implements Iterator<E> {
    // ...省略其他属性
    
    // 【期待修改次数】
    int expectedModCount = modCount;

    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();
        }
    }

    // ...省略其他方法
}

该方法每次执行时，会同步list的修改次数到迭代器中，保证一致。所以在进行next迭代时候，不会抛出异常。

2) 通过CopyOnWriteArrayList替代ArrayList

CopyOnWriteArrayList

  1. 当你想要对一块内存进行修改时，我们不在原有内存块中进行写操作，而是将内存拷贝一份，在新的内存中进行写操作；
  2. 写完之后呢，就将指向原来内存指针指向新的内存，原来的内存就可以被回收掉。

具体实现细节不再本文赘述。


https://www.xamrdz.com/lan/5gn2016543.html

相关文章：