歡迎光臨
每天分享高質量文章

遍歷集合時刪除元素,到底發生了什麼

點擊上方“芋道原始碼”,選擇“置頂公眾號”

技術文章第一時間送達!

原始碼精品專欄

 

當通過 for 迴圈遍歷集合時,一般禁止操作 (add or remove) 集合元素。雖然開發規範里寫的非常清楚,但最近還是有人掉坑裡導致出了一個小 BUG,那我們就一起看看這麼做到底會發生什麼?

小例子

代碼示例

  1. List<String> list = new ArrayList<>();

  2. list.add("e1");

  3. list.add("e2");

  4. for (String str : list) {

  5.    if ("e1".equals(str)) {

  6.        list.remove("e1");

  7.    }

  8.    if ("e2".equals(str)) {

  9.        System.out.println("element 2 fetched");

  10.    }

  11. }

運行結果:element 2 fetched 將不會被打印。

位元組碼中是如何處理的?

讓我們看看位元組碼是怎麼樣的,僅截圖了部分位元組碼。

如上面截圖的 #27、#34、#43,foreach 實際上是通過 Iterator 來處理的。最後通過 #87 的 goto指令進入下一次遍歷,併進行 hasNext()判斷。

class檔案反編譯後又是怎麼樣的?

再來看看將.class檔案反編譯後得到的代碼,實際上編譯器將 foreach 轉換成了用 Iterator來處理。

所以,眼見不一定為實,程式員開發時用的是高級語言,編碼怎麼簡單高效怎麼來,所以偶爾也可以看看反編譯class後的代碼以及位元組碼檔案,看看編譯器做了哪些優化。

  1. ArrayList list = new ArrayList();

  2. list.add("e1");

  3. list.add("e2");

  4. Iterator var2 = list.iterator();

  5. while(var2.hasNext()) {

  6.    String str = (String)var2.next();

  7.    if("e1".equals(str)) {

  8.        list.remove("e1");

  9.    }

  10.    if("e2".equals(str)) {

  11.        System.out.println("element 2 fetched");

  12.    }

  13. }

為什麼remove(e1)會導致無法獲取e2?

list.remove("e1")後,在 while(var2.hasNext()) 時,傳回結果將為 false,因此當迴圈一次後Iterator將認為list已經遍歷結束。

要弄清原因,需要看看ArrayList對於Iterator接口的實現,瞭解hasNext()、next()方法的實現。

先看看ArrayList中實現Iterator的內部類Itr

  1. private class Itr implements Iterator {

  2.    int cursor;       // index of next element to return

  3.    int lastRet = -1; // index of last element returned; -1 if no such

  4.    ...

  5. }  

cursor表示下一個傳回元素的下標,可以理解成 游標lastRet表示上一次傳回的元素下標。另ArrayList有個size屬性,表示ArrayList中的元素個數。

hasNext() 的判斷條件是cursor != size. 只要沒遍歷到最後一個元素,就傳回true.

  1. public boolean hasNext() {

  2.    return cursor != size;

  3. }

下麵是 next() 部分代碼。

  1. public E next() {

  2.    ...

  3.    int i = cursor; // cursor為當前需要傳回元素的下標

  4.    ...

  5.    cursor = i + 1; // cursor向後移動一個位置,指向下一個要傳回的元素

  6.    return (E) elementData[lastRet = i]; // 對lastRet賦值,然後傳回當前元素

  7. }

現在,看一下下麵代碼的運行情況:

  1. ArrayList list = new ArrayList();

  2. list.add("e1");

  3. list.add("e2");

  4. Iterator var2 = list.iterator();

  5. while(var2.hasNext()) {

  6.    String str = (String)var2.next();

  7.    if("e1".equals(str)) {

  8.        list.remove("e1");

  9.    }

  10. }

  • 第一次 呼叫var2.hasNext(),此時滿足條件 cursor(0) != size(2),然後執行 var2.next(),此時cursor=1

  • 執行 list.remove("e1"),此時,list的size將從2變為1

  • 當執行完第一次迴圈,進入第二次hasNext()判斷時,cursor=1而且size=1,導致Iterator認為已經遍歷結束,因此e2將被漏掉。

此時,過程已非常清楚。list本有2個元素,Iterator第一次獲取元素時,程式刪掉了當前元素,導致list的size變為1。Iterator第二次獲取元素時,開心說到:"list一共只有一個元素,我已經遍歷了一個,easy,輕鬆搞定!"。

矛盾點在於:hasNext() 是根據已fetch元素和被遍歷物件的size動態判斷的,一旦遍歷過程中被遍歷物件的size變化,就會出現以上問題。

用普通for迴圈進行處理

如果在普通for迴圈中進行如上操作,又會發生什麼呢?

  1. List<String> list = new ArrayList<>();

  2. list.add("e1");

  3. list.add("e2");

  4. for (int i = 0, length = list.size(); i < length; i++) {

  5.    if ("e1".equals(list.get(i))) {

  6.        list.remove("e1");

  7.    }

  8. }

運行後將報如下異常:

  1. java.lang.IndexOutOfBoundsException: Index: 1, Size: 1

原因:區域性變數length為list遍歷前的size,length=2;remove("e1")後,list的size變為1;因此,第二次進入迴圈執行list.get(1)時將出現上述異常

正確的姿勢

將remove操作交給Iterator來處理,使用Iterator接口提供的remove操作。

  1. List<String> list = new ArrayList<>();

  2. list.add("e1");

  3. list.add("e2");

  4. for (Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {

  5.    String str = iterator.next();

  6.    if ("e1".equals(str)) {

  7.        iterator.remove();

  8.    }

  9.    if ("e2".equals(str)) {

  10.        System.out.println("element 2 fetched");

  11.    }

  12. }

運行結果:element 2 fetched 被正常打印出來。

那Iterator的remove()又是怎麼做的?下麵是ArrayList中迭代器的remove方法。

  1. public void remove() {

  2.    if (lastRet < 0)

  3.        throw new IllegalStateException();

  4.    checkForComodification();

  5.    try {

  6.        ArrayList.this.remove(lastRet); // 呼叫ArrayList的remove移除元素,且size減1

  7.        cursor = lastRet; // 將游標回退一位

  8.        lastRet = -1; // 重置lastRet

  9.        expectedModCount = modCount;

  10.    } catch (IndexOutOfBoundsException ex) {

  11.        throw new ConcurrentModificationException();

  12.    }

  13. }

因為Iterator.remove()在執行集合本身的remove後,同時對游標進行了 "校準"

關於ConcurrentModificationException

以下Demo將丟擲該異常。

  1. private static List<String> list = new ArrayList<>();

  2. private static boolean isListUpdated = false;

  3. public static void main(String[] args) throws InterruptedException {

  4.    list.add("e1");

  5.    list.add("e2");

  6.    new Thread(() -> {

  7.        list.add("e3");

  8.        isListUpdated = true;

  9.    }).start();

  10.    for (Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {

  11.        while (!isListUpdated) {

  12.            Thread.sleep(1000);

  13.        }

  14.        iterator.next();

  15.    }

  16. }

在Java集合框架中,很多物件都不是執行緒安全的,例如:HashMap、ArrayList等。當Iterator在遍歷集合時,如果其他執行緒操作了集合中的元素,將丟擲該異常。

ArrayList中對於Iterator的實現類為Itr如下:

  1. private class Itr implements Iterator {

  2.    int cursor;       // index of next element to return

  3.    int lastRet = -1; // index of last element returned; -1 if no such

  4.    int expectedModCount = modCount;

  5. }    

其中有個重要的屬性 expectedModCount,表示本次期望修改的次數,初始值為modCount.

modCountAbstractList 的屬性,如下:

  1. protected transient int modCount = 0;

註意,它由transient修飾,保證了執行緒之間修改的可見性。對集合中物件的增加、刪除操作都會對modCount加1。

在next()、remove()操作中都會進行 checkForComodification() ,用於檢查迭代期間其他執行緒是否修改了被迭代物件。下麵是checkForComodification方法:

  1. final void checkForComodification() {

  2.    if (modCount != expectedModCount)

  3.        throw new ConcurrentModificationException();

  4. }

這是一種 Fail-Fast(快速失敗) 策略,只要被迭代物件發生變更,將滿足 modCount != expectedModCount 條件,從而丟擲ConcurrentModificationException。




如果你對 Dubbo 感興趣,歡迎加入我的知識星球一起交流。

知識星球

目前在知識星球(https://t.zsxq.com/2VbiaEu)更新瞭如下 Dubbo 原始碼解析如下:

01. 除錯環境搭建
02. 專案結構一覽
03. 配置 Configuration
04. 核心流程一覽

05. 拓展機制 SPI

06. 執行緒池

07. 服務暴露 Export

08. 服務取用 Refer

09. 註冊中心 Registry

10. 動態編譯 Compile

11. 動態代理 Proxy

12. 服務呼叫 Invoke

13. 呼叫特性 

14. 過濾器 Filter

15. NIO 服務器

16. P2P 服務器

17. HTTP 服務器

18. 序列化 Serialization

19. 集群容錯 Cluster

20. 優雅停機

21. 日誌適配

22. 狀態檢查

23. 監控中心 Monitor

24. 管理中心 Admin

25. 運維命令 QOS

26. 鏈路追蹤 Tracing

...
一共 60 篇++

赞(0)

分享創造快樂

© 2021 知識星球   网站地图