How to delete an java collection class while traversing
- 2021-11-13 01:51:06
- OfStack
Delete while java collection class is traversed
1. Background
When traversing data using java's collection classes, there may be situations where some data may need to be deleted. Often improper operation, will throw out 1 ConcurrentModificationException, we simply explain 1 error example, as well as 1 correct operation and simple analysis of the reasons.
P. S. Sample code and analysis is for List instance class ArrayList, other collection classes can be a reference.
2. Code sample
The sample code is as follows, and you can explain which operation is correct according to comments:
public class TestIterator {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
print(list);
// Operation 1 Error demonstration, not triggered ConcurrentModificationException
System.out.println("NO.1");
List<String> list1 = new ArrayList<>(list);
for(String str:list1) {
if ("4".equals(str)) {
list1.remove(str);
}
}
print(list1);
// Operation 2 Error demonstration, using for each Trigger ConcurrentModificationException
System.out.println("NO.2");
try{
List<String> list2 = new ArrayList<>(list);
for(String str:list2) {
if ("2".equals(str)) {
list2.remove(str);
}
}
print(list1);
}catch (Exception e) {
e.printStackTrace();
}
// Operation 3 Error demonstration, using iterator Trigger ConcurrentModificationException
try{
System.out.println("NO.3");
List<String> list3 = new ArrayList<>();
Iterator<String> iterator3 = list3.iterator();
while (iterator3.hasNext()) {
String str = iterator3.next();
if ("2".equals(str)) {
list3.remove(str);
}
}
print(list3);
}catch (Exception e){
e.printStackTrace();
}
// Operation 4 : Correct operation
System.out.println("NO.4");
List<String> list4 = new ArrayList<>(list);
for(int i = 0; i < list4.size(); i++) {
if ("2".equals(list4.get(i))) {
list4.remove(i);
i--; // You should have this action
}
}
print(list4);
// Operation 5 : Correct operation
System.out.println("NO.5");
List<String> list5 = new ArrayList<>(list);
Iterator<String> iterator = list5.iterator();
while (iterator.hasNext()) {
String str = iterator.next();
if ("2".equals(str)) {
iterator.remove();
}
}
print(list5);
}
public static void print(List<String> list) {
for (String str : list) {
System.out.println(str);
}
}
}P. S. In the above example code, operations 1, 2 and 3 are incorrect operations, which are deleted while traversing. Operations 4 and 5 can achieve the expected effect, and the fifth writing method is used for pushing construction.
3. Analysis
First of all, you need to declare three things:
1. The bottom layer of for each also adopts iterator mode (I didn't verify this, but found relevant data), so we only need to pay attention to the implementation of iterator mode for the operation of for each. 2. AraayList is stored in arrays, so the implementation of Operation 4 is different from other (1, 2, 3, 5) operations, which are all iterators. 3. In view of points 1 and 2, the focus of this article is actually on why remove with iterators (operation 5) is fine, while remove with sets (operations 1, 2, 3) is not.3.1 Why there is nothing wrong with Operation 4
// Operation 4 : Correct operation
System.out.println("NO.4");
List<String> list4 = new ArrayList<>(list);
for(int i = 0; i < list4.size(); i++) {
if ("2".equals(list4.get(i))) {
list4.remove(i);
i--; // You should have this action
}
}In fact, there is not much to say about this. ArrayList uses an array at the bottom. It deletes the data at a certain position, which actually moves the data from the next 1 bit to the last position forward by 1 bit in the array (basic knowledge, not much explanation). So when traversing, The point is actually the size of the index value, The underlying implementation needs to rely on this index, This is why there is an i in the end, because when we delete 2, the index value i is 1, and when we delete it, the data from index 2 to list. size ()-1 will be moved forward by 1 bit. If i-1 is not taken, the value of i will be 2 in the next round of loop, so the original index value is 2, but now the index value is 1. For example, if the data of indexes 1 and 2 in the original data are both 2, and you want to delete both 2, if you don't do i--, then after deleting the 2 at index 1, the 2 with the original index of 2 and the current index of 1 will be omitted in the next round of judgment.
3.2 Causes of ConcurrentModificationException when iteration is adopted
In fact, this exception is thrown when the iterator's next () method body calls checkForComodification ():
Look at the source code of these two methods of the iterator:
public E next() {
checkForComodification();// Notice this method, which throws the
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() {
// The problem is modCount And expectedModCount Value of
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}1. First of all, the value modCount is a variable of ArrayList, and expectedModCount is a variable of iterator.
modCount: This value is a self-increment operation when the structure of the collection changes (such as adding, deleting, etc.). In fact, in ArrayList, this value only changes when the element is deleted.
expectedModCount: This value assigns the value of modCount to the iterator's variable expectedModCount when the collection's iterator () method is called to instantiate the iterator. That is, during the iterative operation of the iterator, the value of expectedModCount will not change after initialization, while the value of modCount may change (such as deletion operation), which is why we should compare whether these two values are 1 every time we call the next () method.
In fact, I understand them as similar to the implementation of CAS theory. In fact, when the iterator traverses, it calls the remove method of the collection, which looks serial in code, but can be regarded as the parallel operation of two different threads on this ArrayList object (I also looked at other materials before trying to understand it this way).
3.3 Why there is no problem with remove using iterators during iteration
According to Article 3.2, we know that since the reason for ConcurrentModificationException in remove method using ArrayList lies in the values of modCount and expectedCount, the problem is very clear. First, look at the source code of remove method of iterator:
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
// Although this method is called here, we can ignore it this time, because this remove() The method is
//iterator Self-contained, that is, traversal and deletion can be regarded as serial occurrence, and we have not started to remove it yet
// Operation, so the validation here should not throw an exception, if it throws ConcurrentModificationException ,
// That can only be caused by other threads changing the structure of the current collection, not because of the removal operation we have not started yet
checkForComodification();
try {
// The removal begins here
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// Re-assign, using expectedModCount And modCount Retains the value of 1 To
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}Take note of my comment. When you call the remove method of the iterator, you are also calling the remove method of the collection, but because the data uniformity between modCount and expectedModCount is maintained here, the next time you call the next () method and call the checkForComodification method, you will not throw ConcurrentModificationException.
3.4 Why does Operation 1 not throw ConcurrentModificationException
In fact, although operation 1 uses for each, as mentioned above, the bottom layer is still an iterator. Since this is an iterator, ConcurrentModificationException is not thrown by using the set remove method, which is because the removed element is the penultimate element.
When the iterator iterates, it calls hasNext () method to judge whether to end the iteration. If it does not end, it starts to call next () method to get the next element. When calling next () method, ConcurrentModificationException is thrown when calling checkForComodification method.
So, if you end the loop after calling the hasNext () method and don't call the next () method, the next 1 series of operations won't happen.
Since there is one last element, why does the loop end? The problem lies in the hasNext () method. Look at the source code:
public boolean hasNext() {
return cursor != size;
}In fact, every time the next () method is called for iteration, cursor will be added with 1, and cursor is equivalent to a cursor. When it is not equal to the set size size, it will go straight through with 1. However, because operation 1 removes one element, the size of the set is minus 1, which leads to the end of the loop when calling hasNext () method.
1 Remove Data Trap in java Collection
Traversing the collection itself and deleting the traversed data at the same time
When using Set collection: Exception occurs when traversing the collection itself and deleting the traversed data at the same time
Iterator<String> it = atomSet.iterator();
while (it.hasNext()) {
if (!vars.contains(it.next())) {
atomSet.remove(it.next());
}
} Throw an exception:
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(HashMap.java:793)
at java.util.HashMap$KeyIterator.next(HashMap.java:828)
at test2.Test1.main(Test1.java:16)
Abnormal essential cause
Iterator works in a separate thread and has an mutex lock. After Iterator is created, a single-linked index table pointing to the original object will be established. When the number of original objects changes, the contents of this index table will not change synchronously, so when the index pointer moves backward, the object to be iterated cannot be found. Therefore, according to fail-fast principle, Iterator will immediately throw java. util. ConcurrentModificationEx ception exception.
Therefore, Iterator does not allow the iterated objects to be changed when it works. However, you can use Iterator's own method, remove (), to delete objects, and the Iterator. remove () method maintains the index's uniformity while deleting the current iteration object.
Solve
remove method using Iterator
Iterator<String> it = atomVars.iterator();
while (it.hasNext()) {
if (!vars.contains(it.next())) {
it.remove();
}
} The code can execute normally.