java集合類遍歷的同時進(jìn)行刪除操作
1. 背景
在使用java的集合類遍歷數(shù)據(jù)的時候，在某些情況下可能需要對某些數(shù)據(jù)進(jìn)行刪除。往往操作不當(dāng)，便會拋出一個ConcurrentModificationException，本方簡單說明一下錯誤的示例，以及一些正確的操作并簡單的分析下原因。
P.S. 示例代碼和分析是針對List的實(shí)例類ArrayList，其它集合類可以作個參考。
2. 代碼示例
示例代碼如下，可以根據(jù)注釋來說明哪種操作是正確的：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
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); // 操作1：錯誤示范，不觸發(fā)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); // 操作2：錯誤示范，使用for each觸發(fā)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(); } // 操作3：錯誤示范，使用iterator觸發(fā)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(); } // 操作4： 正確操作 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--; // 應(yīng)當(dāng)有此操作 } } print(list4); // 操作5： 正確操作 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. 上面的示例代碼中，操作1、2、3都是不正確的操作，在遍歷的同時進(jìn)行刪除，操作4、5能達(dá)到預(yù)期效果，推建使用第5種寫法。
3. 分析
首先，需要先聲明3個東東：
- 1. for each底層采用的也是迭代器的方式（這個我并沒有驗(yàn)證，是查找相關(guān)資料得知的），所以對for each的操作，我們只需要關(guān)注迭代器方式的實(shí)現(xiàn)即可。
- 2. AraayList底層是采用數(shù)組進(jìn)行存儲的，所以操作4實(shí)現(xiàn)是不同于其它（1、2、3、5）操作的，他們用的都是迭代器方式。
- 3. 鑒于1、2點(diǎn)，其實(shí)本文重點(diǎn)關(guān)注的是采用迭代器的remove（操作5）為什么沒有問題，而采用集合的remove(操作1、2、3）就不行。
3.1 為什么操作4沒有問題
|
1
2
3
4
5
6
7
8
9
|
// 操作4： 正確操作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--; // 應(yīng)當(dāng)有此操作 }} |
這個其實(shí)沒什么太多說的，ArrayList底層采用數(shù)組，它刪除某個位置的數(shù)據(jù)實(shí)際上就是把從這個位置下一位開始到最后位置的數(shù)據(jù)在數(shù)組里整體前移一位（基本知識，不多說明）。所以在遍歷的時候，重點(diǎn)其實(shí)是索引值的大小，底層實(shí)現(xiàn)是需要依賴這個索引 的，這也是為什么最后有個i--，因?yàn)槲覀儎h除2的時候，索引值i為1,刪除的時候，就把索引為2到list.size()-1的數(shù)據(jù)都前移一位，如果不把i-1，那么下一輪循環(huán)時，i的值就為2，這樣就把原來索引值為2,而現(xiàn)在索引值為1的數(shù)據(jù)給漏掉了，這個地方需要注意一下。比如，如果原數(shù)據(jù)中索引1、2的數(shù)據(jù)都為2，想把2都刪除掉，如果不進(jìn)行i--，那么把索引1處的2刪除掉后，下一次循環(huán)判斷時，就會把原來索引為2,現(xiàn)在索引為1的這個2給遺漏掉了。
3.2 采用迭代時ConcurrentModificationException產(chǎn)生的原因
其實(shí)這個異常是在迭代器的next()方法體調(diào)用checkForComodification()時拋出來的：
看下迭代器的這兩個方法的源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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() { // 問題就在modCount與expectedModCount的值 if (modCount != expectedModCount) throw new ConcurrentModificationException(); } |
1. 首先說明，modCount這個值是ArrayList的一個變量，而expectedModCount是迭代器的一個變量。
modCount：該值是在集合的結(jié)構(gòu)發(fā)生改變時（如增加、刪除等）進(jìn)行一個自增操作，其實(shí)在ArrayList中，只有刪除元素時這個值才發(fā)生改變。
expectedModCount：該值在調(diào)用集合的iterator()方法實(shí)例化迭代器的時候，會將modCount的值賦值給迭代器的變量 expectedModCount。也就是說，在該迭代器的迭代操作期間，expectedModCount的值在初始化之后便不會進(jìn)行改變，而modCount的值卻可能改變（比如進(jìn)行了刪除操作），這也是每次調(diào)用next()方法的時候，為什么要比較下這兩個值是否一致。
其實(shí)，我是把它們看作類似于CAS理論的實(shí)現(xiàn)來理解的，其實(shí)在迭代器遍歷的時候調(diào)用集合的remove方法，代碼上看起來是串行的，但是可以認(rèn)為是兩個不同線程的并行操作這個ArrayList對象（我也是看了下其它資料，才試著這樣去理解）。
3.3 為什么在遍歷時使用迭代器的remove沒有問題
依據(jù)3.2條，我們知道，既然使用ArrayList的remove方法出現(xiàn)ConcurrentModificationException的原因在于modCount與expectedCount的值，那么問題就很明晰了，先看下迭代器的remove方法的源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public void remove() { if (lastRet < 0) throw new IllegalStateException(); // 雖然這里也調(diào)用了這方法，但是本次我們可以先忽略，因?yàn)檫@個remove()方法是 //iterator自已的，也就是可以看作遍歷和刪除是串行發(fā)生的，目前我們尚未開始進(jìn)行移除 //操作，所以這里的校驗(yàn)不應(yīng)該拋出異常，如果拋出了ConcurrentModificationException， //那只能是其它線程改了當(dāng)前集合的結(jié)構(gòu)導(dǎo)致的，并不是因?yàn)槲覀儽敬紊形撮_始的移除操作 checkForComodification(); try { // 這里開始進(jìn)行移除 ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; // 重新賦值，使用expectedModCount與modCount的值保持一致 expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }} |
注意看下我的注釋，在調(diào)用迭代器的remove方法時，雖然也是在調(diào)用集合的remove方法 ，但是因?yàn)檫@里保持了modCount與expectedModCount的數(shù)據(jù)一致性，所以在下次調(diào)用next()方法，調(diào)用checkForComodification方法時，也就不會拋出ConcurrentModificationException了。
3.4 為什么操作1沒有拋出ConcurrentModificationException
其實(shí)操作1雖然使用for each但是上面說過，其實(shí)底層依然是迭代器的方式，這既然是迭代器，然而采用集合的remove方法，卻沒有拋出ConcurrentModificationException， 這是因?yàn)橐瞥脑厥堑箶?shù)第二個元素的原因。
迭代器迭代的時候，調(diào)用hasNext()方法來判斷是否結(jié)束迭代，若沒有結(jié)束，才開始調(diào)用next()方法，獲取下一個元素，在調(diào)用next()方法的時候，因?yàn)檎{(diào)用 checkForComodification方法時拋出了ConcurrentModificationException。
所以，如果在調(diào)用hasNext()方法之后結(jié)束循環(huán)，不調(diào)用next()方法，就不會發(fā)生后面的一系列操作了。
既然還有最后一個元素，為什么會結(jié)束循環(huán)，問題就在于hasNext()方法，看下源碼：
|
1
2
3
|
public boolean hasNext() { return cursor != size;} |
其實(shí)每次調(diào)用next()方法迭代的時候，cursor都會加1,cursor就相當(dāng)于一個游標(biāo)，當(dāng)它不等于集合大小size的時候，就會一直循環(huán)下去，但是因?yàn)椴僮?移除了一個元素，導(dǎo)致集合的size減一，導(dǎo)致在調(diào)用hasNext()方法，結(jié)束了循環(huán)，不會遍歷最后一個元素，也就不會有后面的問題了。
java集合中的一個移除數(shù)據(jù)陷阱
遍歷集合自身并同時刪除被遍歷數(shù)據(jù)
使用Set集合時：遍歷集合自身并同時刪除被遍歷到的數(shù)據(jù)發(fā)生異常
|
1
2
3
4
5
6
|
Iterator<String> it = atomSet.iterator(); while (it.hasNext()) { if (!vars.contains(it.next())) { atomSet.remove(it.next()); } } |
拋出異常：
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)
異常本質(zhì)原因
Iterator 是工作在一個獨(dú)立的線程中，并且擁有一個 mutex 鎖。 Iterator 被創(chuàng)建之后會建立一個指向原來對象的單鏈索引表，當(dāng)原來的對象數(shù)量發(fā)生變化時，這個索引表的內(nèi)容不會同步改變，所以當(dāng)索引指針往后移動的時候就找不到要迭代的對象，所以按照 fail-fast 原則 Iterator 會馬上拋出 java.util.ConcurrentModificationEx ception 異常。
所以 Iterator 在工作的時候是不允許被迭代的對象被改變的。但你可以使用 Iterator 本身的方法 remove() 來刪除對象， Iterator.remove() 方法會在刪除當(dāng)前迭代對象的同時維護(hù)索引的一致性。
解決
使用Iterator的remove方法
|
1
2
3
4
5
6
|
Iterator<String> it = atomVars.iterator(); while (it.hasNext()) { if (!vars.contains(it.next())) { it.remove(); } } |
代碼能夠正常執(zhí)行。
以上為個人經(jīng)驗(yàn)，希望能給大家一個參考，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/x763795151/article/details/84028314
