兩個迭代器的故事：Java 中的競爭性修改策略

該說明的作者是來自克拉科夫（波蘭）的軟體開發人員 Grzegorz Mirek。大約 6 年前，他還在讀大學時就開始使用 Java 進行開發，從那時起，他就一直不知疲倦地磨練自己在該領域的技能。他對 JVM 性能和優化特別感興趣，這是他在部落格上主要寫的內容。 一些最受歡迎的 Java 面試問題包括： 快速失敗迭代器和故障安全迭代器之間有什麼區別？ 對此最簡單的答案是： 如果集合在迭代期間發生更改，快速失敗迭代器將引發 ConcurrentModificationException，但故障安全迭代器不會。 雖然這聽起來很有意義，但仍不清楚面試官所說的「故障安全」是什麼意思？Java 語言規範沒有定義與迭代器相關的術語。然而，有四種競爭性修改策略。

競賽改裝

首先，讓我們定義什麼是競爭（或並行）修改。假設我們有一個集合，當迭代器處於活動狀態時，會發生一些並非來自該迭代器的變更。在這種情況下，我們得到了競爭性的修改。讓我給你一個簡單的例子：假設我們有幾個線程。第一個執行緒進行迭代，第二個執行緒從同一集合中插入或刪除元素。然而，在單執行緒環境中執行時， 我們可能會得到ConcurrentModificationException ：

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

快速失敗

上面的程式碼片段是快速失敗迭代器的範例。正如您所看到的，當嘗試從迭代器檢索第二個元素時，拋出了ConcurrentModificationException。迭代器如何知道集合自創建以來已修改？例如，集合可能有一個日期/時間戳，例如lastModified。建立迭代器時，應該複製該欄位並將其儲存在迭代器物件中。然後，每次呼叫next()方法時，您只需將集合中的LastModified值與迭代器中的副本進行比較即可。例如，在ArrayList類別的實作中使用了非常相似的方法。它有一個實例變數modCount儲存清單被修改的次數：

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

需要注意的是，快速失敗迭代器在最佳組合的基礎上運行，這意味著不能保證在並發修改時會拋出ConcurrentModificationException 。因此您不應該依賴它們 - 相反，它們應該用於檢測錯誤。大多數非並發集合提供快速失敗迭代器。

弱一致性

java.util.concurrent套件中的大多數並發集合（例如ConcurrentHashMap和大多數Queue）都提供弱一致迭代器。該術語的含義在文檔中有很好的解釋：

• 它們可以與其他操作同時處理
• 他們從不拋出ConcurrentModificationException
• 它們保證在迭代器建立時遍歷現有元素一次，並且可以（但不要求）反映後續修改。

快照

透過這種策略，迭代器與集合創建時的狀態相關聯——這是集合的快照。對原始集合所做的任何更改都會導致創建基礎資料結構的新版本。這使我們的快照保持不變，因此它不會反映創建迭代器後發生的集合變更。這是古老的寫時複製 (COW) 技術。它完全解決了並發修改的問題，因此這種方法不會產生ConcurrentModificationException 。此外，迭代器不支援更改元素的操作。寫入時複製集合的使用成本往往太高，但如果更改發生的頻率遠低於迭代器遍歷，則使用它們是有意義的。範例包括CopyOnWriteArrayList和CopyOnWriteArraySet類別。

未定義的行為

您可能會在舊集合類型（例如Vector和Hashtable ）中遇到未定義的行為。兩者都有標準的快速失敗迭代器，但除此之外，它們還允許使用Enumeration介面的實現，並且它們不知道在並發修改的情況下如何表現。你可能會遇到一些元素被重複或缺失，甚至一些奇怪的異常。最好不要和他們一起玩！