今天在做算法题的时候,碰到的如下问题,记录下来加深记忆。很多时候我们都有这样一个需求,在迭代的时候(满足某个给定的条件)添加或者删除元素。结果却是等来了java.util.ConcurrentModificationException这个异常,追踪其原因,就是有些容器是Fail-Safe,Fail-First的
1. Fail-Safe,Fail-First概念。
在ArrayList的里面有个内部类Itr。当我们获取到迭代器的时候,就会对这个类进行初始化,来看下这个类的源码,分析初始化做了些什么。
在初始化的时候,它会让expectedModCount = modCount,modCount在AbstractList,每次对ArrayList的结构性改变(remove,add)都会使得modCount相应的减1或者加1。来分析下我们刚开始出现问题的代码。当我们获取到迭代器的时候,此时expectedModCount = modCount。当remove的时候,modCount会加1,但是expectedModCount却不变,当执行Itr的next()操作时候,会执行上述源码中的checkForComodification()来检查expectedModCount = modCount,若不相等,则会throw ConcurrentModificationException。
所以就不难分析出上述问题。
FailFirst:当我们在迭代获取集合元素的时候,在迭代器创建之后,对集合做一些结构性的改变(remove,add操作),那么FailFirst容器首先会抛出 ConcurrentModificationException。
2. 如何解决上述问题。
|
|
上述这个办法好,但是却占额外空间。
这样就不占额外的空间,是更好的办法。 iterator.remove()为啥不会抛异常,看看源码
expectedModCount = modCount;这句起作用,它删除元素后它会强制满足条件。所以不会抛异常。
3. Fail-Safe的出场 。
将刚开始的代码换成如下的形式,问题迎刃而解。
像CopyOnWriteArrayList这类容器就属于Fail-Safe容器。当集合结构改变的时候不会抛出异常,这是因为他们只是原始集合的复制,它用snapshot这个数组来保存集合。所以你原始集合的修改只会让原来的引用指向新的数组,而旧的引用还是被迭代器的snapshot所引用。因而他们属于Fail-Safe容器。看看其源码
从上面可以看出每次添加元素都是线程安全的,因为加了锁。另外,每添加一个元素,都会把原来的引用指向一个新的数组。所以对他进行操作没问题。所以使用Fail-Safe容器也是一种很好的解决办法。