Eine Geschichte zweier Iteratoren: Wettbewerbsfähige Modifikationsstrategien in Java

Der Autor der Notiz ist Grzegorz Mirek, ein Softwareentwickler aus Krakau (Polen). Er begann vor etwa sechs Jahren, noch während seines Studiums, mit der Entwicklung in Java und verfeinerte seitdem unermüdlich seine Fähigkeiten in diesem Bereich. Sein besonderes Interesse gilt der JVM-Leistung und -Optimierung, worüber er hauptsächlich in seinem Blog schreibt . Zu den beliebtesten Java-Interviewfragen gehören: Was ist der Unterschied zwischen ausfallsicheren und ausfallsicheren Iteratoren? Die einfachste Antwort darauf lautet: Ein ausfallsicherer Iterator löst eine ConcurrentModificationException aus, wenn sich die Sammlung während der Iteration ändert, ein ausfallsicherer Iterator jedoch nicht. Obwohl dies durchaus bedeutungsvoll klingt, bleibt unklar, was der Interviewer mit „ausfallsicher“ meint. Die Java-Sprachspezifikationen definieren diesen Begriff nicht in Bezug auf Iteratoren. Es gibt jedoch vier wettbewerbsfähige Modifikationsstrategien.

Wettbewerbsfähige Modifikation

Definieren wir zunächst, was eine kompetitive (oder parallele) Modifikation ist. Nehmen wir an, wir haben eine Sammlung und wenn der Iterator aktiv ist, treten einige Änderungen auf, die nicht von diesem Iterator stammen. In diesem Fall erhalten wir eine wettbewerbsfähige Modifikation. Lassen Sie mich ein einfaches Beispiel geben: Nehmen wir an, wir haben mehrere Threads. Der erste Thread iteriert und der zweite Thread fügt Elemente aus derselben Sammlung ein oder entfernt sie. Bei der Ausführung in einer Single-Threaded-Umgebung kann es jedoch zu einer ConcurrentModificationException kommen:

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

Ausfallsicher

Das obige Codefragment ist ein Beispiel für einen ausfallsicheren Iterator. Wie Sie sehen können, wurde eine ConcurrentModificationException ausgelöst, als versucht wurde, das zweite Element vom Iterator abzurufen . Woher weiß ein Iterator, dass die Sammlung seit ihrer Erstellung geändert wurde? Beispielsweise könnte die Sammlung einen Datums-/Zeitstempel haben, beispielsweise lastModified . Beim Erstellen eines Iterators sollten Sie dieses Feld kopieren und in einem Iteratorobjekt speichern. Dann vergleichen Sie jedes Mal, wenn Sie die next()- Methode aufrufen , einfach den lastModified- Wert aus der Sammlung mit der Kopie aus dem Iterator. Ein ganz ähnlicher Ansatz wird beispielsweise bei der Implementierung der ArrayList- Klasse verwendet . Es verfügt über eine Instanzvariable modCount , die die Häufigkeit speichert, mit der die Liste geändert wurde:

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

Es ist wichtig zu beachten, dass ausfallsichere Iteratoren auf Best-of-Breed-Basis arbeiten, was bedeutet, dass es keine Garantie dafür gibt, dass im Falle einer gleichzeitigen Änderung eine ConcurrentModificationException ausgelöst wird. Man sollte sich also nicht auf sie verlassen, sondern vielmehr zur Fehlererkennung nutzen. Die meisten nicht gleichzeitigen Sammlungen bieten ausfallsichere Iteratoren.

Schwache Konsistenz

Die meisten gleichzeitigen Sammlungen im Paket java.util.concurrent (z. B. ConcurrentHashMap und die meisten Queue ) stellen schwach konsistente Iteratoren bereit. Die Bedeutung dieses Begriffs wird in der Dokumentation sehr gut erklärt :

• Sie können gleichzeitig mit anderen Vorgängen verarbeitet werden
• Sie lösen niemals eine ConcurrentModificationException aus
• Es ist garantiert, dass sie zum Zeitpunkt der Erstellung des Iterators vorhandene Elemente genau einmal durchlaufen, und sie können (müssen aber nicht) nachfolgende Änderungen widerspiegeln.

Schnappschuss

Bei dieser Strategie wird der Iterator mit dem Zustand der Sammlung zum Zeitpunkt ihrer Erstellung verknüpft – dies ist eine Momentaufnahme der Sammlung. Alle an der ursprünglichen Sammlung vorgenommenen Änderungen führen zur Erstellung einer neuen Version der zugrunde liegenden Datenstruktur. Dadurch bleibt unser Snapshot unverändert, sodass er keine Änderungen an der Sammlung widerspiegelt, die nach der Erstellung des Iterators vorgenommen wurden. Dies ist die gute alte COW-Technik (Copy-on-Write) . Dadurch wird das Problem gleichzeitiger Änderungen vollständig gelöst, sodass bei diesem Ansatz keine ConcurrentModificationException generiert wird. Darüber hinaus unterstützen Iteratoren keine Operationen, die Elemente ändern. Die Verwendung von Copy-on-Write-Sammlungen ist in der Regel zu teuer, aber es ist sinnvoll, sie zu verwenden, wenn Änderungen viel seltener auftreten als Iteratordurchläufe. Beispiele sind die Klassen CopyOnWriteArrayList und CopyOnWriteArraySet .

Undefiniertes Verhalten

Bei älteren Sammlungstypen wie Vector und Hashtable kann es zu undefiniertem Verhalten kommen . Beide verfügen über standardmäßige Fail-Fast- Iteratoren, ermöglichen aber darüber hinaus die Verwendung von Implementierungen der Enumeration- Schnittstelle und wissen nicht, wie sie sich bei gleichzeitiger Änderung verhalten sollen. Es kann vorkommen, dass einige Elemente wiederholt werden oder fehlen oder sogar seltsame Ausnahmen auftreten. Es ist besser, nicht mit ihnen zu spielen!