Problems encountered in Java collection traversal

Black hole code 2021-01-14 16:28:26
problems encountered java collection traversal


Interview FAQ collection traversal encountered when the pit ConcurrentModificationException analysis

You may be asked the right question in the interview Java Knowledge of the collection , And in-depth collection of the underlying source code , And if you encounter any pitfalls when using collections —— At this time, I want to see if you are careful in your daily work , It is generally not recommended to say , There was no pit , Because this will give the interviewer the feeling that we are not careful in our work , Not carefully .

today ConcurrentModificationException It should be a common exception . Especially for some students who have just joined the work , You may often meet . that , Have you had a detailed understanding of the underlying causes of this anomaly ?

Voice over , If you answer this question during the interview , It's very likely to face deep-seated problems about Java A group interview .

1. ordinary demo

Let's write a simple set traversal demo, To create a situation where ConcurrentModificationException An unusual scene .

/** * @Author One like you * @Date 2018/8/25 * @Description ConcurrentModificationException Abnormal explanation */ public class ConcurrentModificationExceptionDemo { public static void main(String[]args) { // Define a list List<String> list = new ArrayList<>(); // Add some elements list.add(" Zhang San "); list.add(" Li Si "); list.add(" Wang Wu "); list.add(" Zhao Liu "); // Get the iterator Iterator<String> iterator = list.iterator(); // Traverse list The elements in while (iterator.hasNext()) { // Each element in the collection String element = iterator.next(); // Delete Li Si if (" Li Si ".equals(element)) { list.remove(element); } } } }

function demo, You get the following exception :

2. The cause of the exception is decrypted

2.1 ArrayList.iterator()

Take a look first ArrayList Class iterator() Method implementation , Source code is as follows :

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

You can see from the source code ,iterator() The method is to return a Itr Class object . Look at the below Itr The specific implementation is as follows :

/**
* 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 This class is not very complicated ,Itr Class is ArrayList One of the classes Private inner class . So you could say ,ArrayList Of iterator() The way is through Itr Class to work .

2.2 Inner class Itr analysis

Itr Class member variable parsing :

·cursor: Represents the index of the next element to be accessed , from next() The concrete implementation of the method shows that .

·lastRet: Represents the index of the last accessed element .

·expectedModCount: Said to ArrayList Number of changes The expectation of , its The initial value is equal to modCount.

·modCount yes AbstractList A member variable in a class .PS: ArrayList Integrated AbstractList;Itr yes ArrayList The inner class of a class .

protected transient int modCount = 0;

This value is for ArrayList The number of changes , It can be found in add() and remove() In the method , Will be modified modCount.

Itr Class hasNext() Methods to analyze :

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

If the subscript of the next accessed element is not equal to ArrayList Size , It means that there are elements that need to be accessed , This is easy to understand , If the subscript of the next access element equals ArrayList Size , Means to arrive ArrayList At the end .

Itr Class next() Methods to analyze :

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

This is a very critical place : First, in the next() Method is called checkForComodification() Method , And then according to cursor Gets the value of the element , Also on cursor Add... To the value of 1 operation , And then cursor+1 The value of the previous original value is assigned to lastRet,. At the beginning ,cursor by 0,lastRet by -1, So after one call ,cursor The value of is 1,lastRet The value of is 0.

In this case , Into the next() The state after the method is shown in the following figure : Note that this time ,modCount by 4,expectedModCount Also for the 4.

2.3 ArrayList.remove()

ArrayList.remove() The source code of the method is as follows :

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

You can see from the source code , Where element deletion is performed directly is not in this method , But in fastRemove() in . Look at the below fastRemove() Method source code :

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
}

stay fastRemove() In the method , First of all, modCount add 1 operation ( Because there was a change to the set ), Then the next step is to delete the element , The final will be size Make a reduction 1 operation , And set the reference to null In order to facilitate the garbage collector for recycling work .

So in this case , The program is running remove() After the method , Notice the values of the variables at this point : about iterator, Its expectedModCount by 4,cursor The value of is 1,lastRet The value of is 2.

2.4 checkForModification()

After execution list.remove() after , Will enter... Again while loop , Iterate over the next element .

PS: Be careful ! here ,Itr Medium expectedModCount yes 4, however ,ArrayList inherited AbstractList Medium modCount = 5 了 !

look down checkForComodification() The method is implemented as follows :

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

The source code is very simple , Namely modCount and expectedModCount Throw one when it's not equal ConcurrentModificationException abnormal .

summary : call list.remove() Methods lead to modCount and expectedModCount Is inconsistent . Be careful , Like use for-each It's actually the same problem with iterations .

3. Solution

Itr There is also a remove() Method , There will be no problem with this method . Look at the implementation of this method as follows :

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

This method is actually called ArrayList Of remove() Method , But the key thing is : This method executes the last line ,expectedModCount = modCount The equivalence between them is modified .

therefore , If you want to delete an element in the iterator , Need to call Itr Class remove Method . Here's a good example :

4. Expand

The first 3 The solution in this section is to solve the problem of single thread , But in the case of threads , Again, there will be anomalies , Multithreading Demo demo The code is as follows :

Two threads are used to traverse list, The thread 2 Yes list Deleted , Look at the results of the test :

The conclusion is that : multithreading , Use iterator.remove() Or throw out ConcurrentModificationException abnormal .

Maybe some students said ArrayList It's a non thread safe container , Switch to Vector That's fine , In fact, instead of Vector There will still be this kind of mistake . although Vector The method adopted in this paper is synchronized Synced , But because of Vector Is inherited AbstarctList, So by Iterator To access the container , In fact, you don't need to get a lock to access . So clearly , Due to the use iterator Access to the container does not require a lock , In multithreading, when a thread deletes an element , because modCount yes AbstarctList Member variables of , So it can lead to in other threads modCount and expectedModCount It's not worth it . Interested students can try to use Vector modified , Here is the class diagram , No more code demonstrations .

5. extend

If a classmate is in an interview , Answer the above key points to , So congratulations , You can get this question 50 branch 了 .

Why only 50 branch ??? because , Next, the interviewer will talk to you about multithreading concurrent containers .

How to solve this problem in the case of multithreading ???

Unparalleled teacher gives ideas :

(1) When using iterators , Use synchronized perhaps Lock To synchronize

(2) Using concurrency containers CopyOnWriteArrayList Instead of ArrayList or Vector

This article is from WeChat official account. - The snail flying in the fallen leaves (A_GallopingSnail) , author : The supernatural snail

The source and reprint of the original text are detailed in the text , If there is any infringement , Please contact the yunjia_community@tencent.com Delete .

Original publication time : 2018-08-25

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

版权声明
本文为[Black hole code]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210114162621271m.html

  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 趟过巨坑