Java集合遍历时遇到的坑

黑洞代码 2021-01-14 16:26:38
java 集合 遍历 遇到 历时


面试常见问题之集合遍历时遇到的坑ConcurrentModificationException解析

面试题中可能会被问到对Java集合的了解情况,并深入集合底层的源码,以及使用集合的时候有没有遇到坑——这时候其实是想考察大家在日常工作中是否细心,一般不建议说,没有遇到坑,因为这样会给面试官感觉大家在工作中不细心,不仔细。

今天ConcurrentModificationException应该是比较常见的一个异常。尤其是对一些刚参加工作的同学,可能会经常遇见。那么,各位同学有没有详细了解过这个异常的底层原因呢?

画外音,如果各位同学在面试过程中回答上了这个问题,极有可能面临跟深层次的关于Java集合的面试。

1. 简单的demo

我们写一个简单的集合遍历的demo,来造成一个会出现ConcurrentModificationException异常的场景。

/** * @Author 无双 * @Date 2018/8/25 * @Description ConcurrentModificationException异常讲解 */ public class ConcurrentModificationExceptionDemo { public static void main(String[]args) { //定义一个list List<String> list = new ArrayList<>(); //添加一些元素 list.add("张三"); list.add("李四"); list.add("王五"); list.add("赵六"); //得到迭代器 Iterator<String> iterator = list.iterator(); //遍历list中的元素 while (iterator.hasNext()) { //集合中的每个元素 String element = iterator.next(); //删除李四 if ("李四".equals(element)) { list.remove(element); } } } }

运行demo,会得到如下的异常:

2. 异常原因解密

2.1 ArrayList.iterator()

首先看下ArrayList类的iterator()方法的实现,源码如下:

/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}

从源码可以看出,iterator()方法是返回了一个Itr类的对象。下面看下Itr的具体实现如下:

/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
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();
}
}

Itr这个类不是很很复杂,Itr类是ArrayList类中的一个私有内部类。所以可以说,ArrayList的iterator()方法是通过Itr类的对象来工作的。

2.2 内部类Itr解析

Itr类成员变量解析:

·cursor:表示下一个要访问的元素的索引,从next()方法的具体实现就可看出。

·lastRet:表示上一个访问的元素的索引。

·expectedModCount:表示对ArrayList修改次数的期望值,它的初始值等于modCount

·modCount是AbstractList类中的一个成员变量。PS: ArrayList集成了AbstractList;Itr是ArrayList类的内部类。

protected transient int modCount = 0;

这个值表示对ArrayList的修改次数,可以发现在add()和remove()方法中,都会修改modCount。

Itr类中hasNext()方法分析:

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

如果下一个访问的元素下标不等于ArrayList的大小,就表示有元素需要访问,这个很容易理解,如果下一个访问元素的下标等于ArrayList的大小,则说明到达ArrayList末尾了。

Itr类中next()方法分析:

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

这里是非常关键的地方:首先在next()方法中会调用checkForComodification()方法,然后根据cursor的值获取到元素,并对cursor的值进行加1操作,接着将cursor+1之前的原值的值赋给lastRet,。初始时,cursor为0,lastRet为-1,那么调用一次之后,cursor的值为1,lastRet的值为0。

对应本例中,进入了next()方法后的状态如下图:注意此时,modCount为4,expectedModCount也为4。

2.3 ArrayList.remove()

ArrayList.remove()方法的源码如下:

public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}

从源码可以看到,直接执行元素删除的地方不在这个方法中,而是在fastRemove()中。下面看下fastRemove()方法的源码:

private void fastRemove(int index) {
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
}

在fastRemove()方法中,首先对modCount进行加1操作(因为对集合修改了一次),然后接下来就是删除元素的操作,最后将size进行减1操作,并将引用置为null以方便垃圾收集器进行回收工作。

那么在本例中,程序运行了remove()方法后,注意此时各个变量的值:对于iterator,其expectedModCount为4,cursor的值为1,lastRet的值为2。

2.4 checkForModification()

执行完list.remove()后,会再次进入while循环,迭代下一个元素。

PS: 注意!此时,Itr中的 expectedModCount是4,但是,ArrayList继承的AbstractList中的modCount = 5了!

看下checkForComodification()方法的实现如下:

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

源码很简单,就是modCount和expectedModCount不相等的时候就抛一个ConcurrentModificationException异常。

总结:调用list.remove()方法导致modCount和expectedModCount的值不一致。注意,像使用for-each进行迭代实际上也会出现这种问题。

3. 解决方案

Itr类中也有一个remove()方法,用这个方法就不会有问题。看下这个方法的实现如下:

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

这个方法最其实还是调用ArrayList的remove()方法,但是最关键的地方在于:这个方法执行最后一行,expectedModCount = modCount修改了两者的等价关系。

因此,在迭代器中如果要删除元素的话,需要调用Itr类的remove方法。下面给出正确的示范:

4. 扩展

第3节中解决方案是可以解决单线程下的问题,但是在做线程情况下,同样还是会出现异常,多线程演示demo代码如下:

分别用两个线程遍历list,其中线程2对list进行了删除操作,看下测试的结果如下:

结论是:多线程情况下,使用iterator.remove()还是会抛出ConcurrentModificationException异常。

有可能有同学说ArrayList是非线程安全的容器,换成Vector就没问题了,实际上换成Vector还是会出现这种错误。虽然Vector的方法采用了synchronized进行了同步,但是由于Vector是继承的AbstarctList,因此通过Iterator来访问容器的话,事实上是不需要获取锁就可以访问。那么显然,由于使用iterator对容器进行访问不需要获取锁,在多线程中就会造成当一个线程删除了元素,由于modCount是AbstarctList的成员变量,因此可能会导致在其他线程中modCount和expectedModCount值不等。有兴趣的同学可以自己尝试用Vector改造一下,这里给出相关类图,就不再用代码进行演示了。

5. 延伸

如果同学在面试的时候,将以上关键点回答到,那么恭喜你,这个问题你可以拿到50分了。

为什么只有50分???因为,接下来面试官将会跟你多线程并发容器的问题了。

多线程情况下如何解决这个问题呢???

无双老师给出思路:

(1)在使用迭代器的时候,使用synchronized或者Lock以同步

(2)使用并发容器CopyOnWriteArrayList代替ArrayList或Vector

本文分享自微信公众号 - 落叶飞翔的蜗牛(A_GallopingSnail) ,作者:超神的蜗牛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间: 2018-08-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

版权声明
本文为[黑洞代码]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/1773773

  1. To what extent can I go out to work?
  2. Java 使用拦截器无限转发/重定向无限循环/重定向次数过多报错(StackOverflowError) 解决方案
  3. Implementation of rocketmq message sending based on JMeter
  4. How to choose the ticket grabbing app in the Spring Festival? We have measured
  5. Implementation of rocketmq message sending based on JMeter
  6. My programmer's Road: self study java
  7. My programmer's Road: self study java
  8. All in one, one article talks about the use of virtual machine VirtualBox and Linux
  9. All in one, one article talks about the use of virtual machine VirtualBox and Linux
  10. Java 使用拦截器无限转发/重定向无限循环/重定向次数过多报错(StackOverflowError) 解决方案
  11. [Java training project] Java ID number recognition system
  12. How does serverless deal with the resource supply demand of k8s in the offline scenario
  13. Detailed explanation of HBase basic principle
  14. Explain the function of thread pool and how to use it in Java
  15. Kubernetes official java client 8: fluent style
  16. 010_MySQL
  17. Vibrant special purchases for the Spring Festival tiktok section, hundreds of good things to make the year more rich flavor.
  18. 010_MySQL
  19. Of the 4 million docker images, 51% have high-risk vulnerabilities
  20. Rocketmq CPP client visual studio 2019 compilation
  21. Rocketmq CPP client visual studio 2019 compilation
  22. Usage of data custom attribute in jquery
  23. Common decompression in Linux
  24. Upload large files in Java
  25. Sentry (v20.12.1) k8s cloud native architecture exploration, sentry for JavaScript manual capture event basic usage
  26. Sentry (v20.12.1) k8s cloud native architecture exploration, sentry for JavaScript manual capture event basic usage
  27. Docker + MySQL Cluster + read / write separation + MYCAT Management + vertical sub database + load balancing
  28. Docker + MySQL Cluster + read / write separation + MYCAT Management + vertical sub database + load balancing
  29. Java use interceptor infinite forwarding / redirection infinite loop / redirection times too many error (stack overflow error) solution
  30. Java use interceptor infinite forwarding / redirection infinite loop / redirection times too many error (stack overflow error) solution
  31. 010_ MySQL
  32. 010_ MySQL
  33. Fast integration of imsdk and Huawei offline push
  34. 消息队列之RabbitMQ
  35. Rabbitmq of message queue
  36. 初学java进制转换方面补充学习
  37. Learn java base conversion supplementary learning
  38. 了解一下RPC,为何诞生RPC,和HTTP有什么不同?
  39. 了解一下RPC,为何诞生RPC,和HTTP有什么不同?
  40. 初学java进制转换方面补充学习
  41. Learn about RPC, why RPC was born, and what's the difference between RPC and HTTP?
  42. Learn about RPC, why RPC was born, and what's the difference between RPC and HTTP?
  43. Learn java base conversion supplementary learning
  44. JDBC测试连接数据库
  45. JDBC test connection database
  46. 大厂面试官竟然这么爱问Kafka,一连八个Kafka问题把我问蒙了?
  47. The interviewers of big factories love to ask Kafka so much. I'm blinded by eight Kafka questions in a row?
  48. 安卓开发和java开发有什么区别!2021年BATJ30套大厂Android经典高频面试题,面试必问
  49. Spring Security OAuth2.0認證授權四:分散式系統認證授權
  50. What's the difference between Android development and java development! 2021 batj30 Android classic high frequency interview questions
  51. Spring security oauth2.0 authentication and authorization 4: distributed system authentication and authorization
  52. Java微服务 vs Go微服务,究竟谁更强!?
  53. 大厂面试官竟然这么爱问Kafka,一连八个Kafka问题把我问蒙了?
  54. Who is stronger, Java microservice vs go microservice!?
  55. Java微服务 vs Go微服务,究竟谁更强!?
  56. The interviewers of big factories love to ask Kafka so much. I'm blinded by eight Kafka questions in a row?
  57. Who is stronger, Java microservice vs go microservice!?
  58. springboot异常处理之404
  59. Spring boot exception handling 404
  60. Spring Boot Security 国际化 多语言 i18n 趟过巨坑