面試題:寫一個遍歷ArrayList的時候,刪除一個元素的例子?并說說原理。
代碼實現
方法一:for循環
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("ab");
list.add("abc");
list.add("abc");
list.add("abcr");
list.add("abc");
list.add("abcf");
list.add("abc");
list.add("abdc");
for(int i=0;i<list.size();i++) {
if(list.get(i).equals("abc")) {
System.out.println(i+":"+list.get(i));
list.remove(i); // 刪除后 下標調整 導致漏刪
}
}
System.out.println(list);
}
結果:漏刪!
2:abc
4:abc
5:abc
[a, ab, abc, abcr, abcf, abdc]
方法二: Iterator遍歷,并使用自身的remove()刪除元素
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("ab");
list.add("abc");
list.add("abc");
list.add("abcr");
list.add("abc");
list.add("abcf");
list.add("abc");
list.add("abdc");
Iterator<String> iter = list.iterator();
while(iter.hasNext()){
if(iter.next().equals("abc")){
iter.remove();
}
}
}
結果:
[a, ab, abcr, abcf, abdc]
原理
上述的兩種方法,第一種方法導致漏刪。第二種方法是正確的。那么為什么在用for循環遍歷的時候刪除元素,會導致漏刪的情況呢?這是因為在for循環時,數組會調整數組的下標,會導致漏刪。由上述代碼可以看出,由于下標位置在不斷調整,而i也在++ ,所有導致i=3位置的元素被跳過了。從而漏刪。所以我們不能用for循環遍歷的同時刪除元素。正確的做法是利用for循環從后往前遍歷,或者使用Iterator遍歷,并調用自身的remove方法刪除。Iterator.remove() 方法會在刪除當前迭代對象的同時維護索引的一致性!
需要注意的是,使用Iterator遍歷的時候,不能不允許并發調用ArrayList的remove/add操作進行修改,否則會拋出異常。這時為什么呢?
原理是:Iterator是工作在一個獨立的線程中,而且擁有一個mutex鎖。Iterator在建立后會創建一個指向原來對象的單索引鏈表。當原來的對象元素發生改變(增加或者刪除一個元素),這個索引表是不會同步改變的。所以當索引指針往后移動的時候就找不到要迭代的對象,這時候就會觸發fast-fail快速失敗機制。
fail-fast 機制,即快速失敗機制,是java集合(Collection)中的一種錯誤檢測機制。當在迭代集合的過程中該集合在結構上發生改變的時候,就有可能會發生fail-fast,即拋出 ConcurrentModificationException異常。那么,如果你在遍歷的時候,調用list的add()或者remove(),使得集合的結構發生改變。Iterator 會馬上拋出 java.util.ConcurrentModificationException 異常。
讓我們看看源碼,為什么會拋出這個并發修改異常?
從源碼知道,每次調用next()方法,在實際訪問元素前,都會調用checkForComodification方法,該方法源碼如下:
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
此時,需要去看看ArrayList的源碼。
可以看出,該方法才是判斷是否拋出ConcurrentModificationException異常的關鍵。在該段代碼中,當modCount != expectedModCount
時,就會拋出該異常。但是在一開始的時候,expectedModCount初始值默認等于modCount,為什么會出現modCount != expectedModCount,很明顯expectedModCount在整個迭代過程除了一開始賦予初始值modCount外,并沒有再發生改變,所以可能發生改變的就只有modCount,在前面關于ArrayList擴容機制的分析中,可以知道在ArrayList進行add,remove,clear等涉及到修改集合中的元素個數的操作時,modCount就會發生改變(如modCount ++),所以當另一個線程(并發修改)或者同一個線程遍歷過程中,調用add/remove()使集合的個數發生改變,就會使modCount發生變化,這樣在checkForComodification方法中就會拋出ConcurrentModificationException異常。從而觸發fast-fail機制。
避免fast-fail
方法一
在單線程的遍歷過程中,如果要進行remove操作,可以調用迭代器的remove方法而不是集合類的remove方法。
方法二
使用java并發包(java.util.concurrent)中的類來代替 ArrayList 和hashMap。比如CopyONWriterArrayList, CopyOnWriterArrayList在是使用上跟 ArrayList幾乎一樣, CopyOnWriter是寫時復制的容器(COW),在讀寫時是線程安全的。該容器在對add和remove等操作時,并不是在原數組上進行修改,而是將原數組拷貝一份,在新數組上進行修改,待完成后,才將指向舊數組的引用指向新數組,所以對于 CopyOnWriterArrayList在迭代過程并不會發生fail-fast現象。但 CopyOnWrite容器只能保證數據的最終一致性,不能保證數據的實時一致性。
對于HashMap,可以使用ConcurrentHashMap, ConcurrentHashMap采用了鎖機制,是線程安全的。在迭代方面,ConcurrentHashMap使用了一種不同的迭代方式。在這種迭代方式中,當iterator被創建后集合再發生改變就不再是拋出ConcurrentModificationException,取而代之的是在改變時new新的數據從而不影響原有的數據 ,iterator完成后再將頭指針替換為新的數據 ,這樣iterator線程可以使用原來老的數據,而寫線程也可以并發的完成改變。即迭代不會發生fail-fast,但不保證獲取的是最新的數據。
參考鏈接:https://blog.csdn.net/zymx14/article/details/78394464

浙公網安備 33010602011771號