Es scheint viele verschiedene Implementierungen und Möglichkeiten zu geben, threadsichere Sets in Java zu generieren. Einige Beispiele sind

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (Set set)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap (neue ConcurrentHashMap ())

5) Andere Sätze, die auf ähnliche Weise wie (4) erzeugt wurden

Diese Beispiele stammen aus Implementierungen von Concurrency Pattern: Concurrent Set in Java 6

Könnte jemand bitte einfach die Unterschiede, Vor- und Nachteile dieser und anderer Beispiele erklären? Ich habe Probleme, alles aus den Java Std Docs zu verstehen und klar zu halten.

1) Das CopyOnWriteArraySetist eine recht einfache Implementierung - es enthält im Grunde eine Liste von Elementen in einem Array, und beim Ändern der Liste wird das Array kopiert. Iterationen und andere Zugriffe, die zu diesem Zeitpunkt ausgeführt werden, werden mit dem alten Array fortgesetzt, wodurch die Notwendigkeit einer Synchronisierung zwischen Lesern und Schreibern vermieden wird (obwohl das Schreiben selbst synchronisiert werden muss). Die normalerweise schnell eingestellten Operationen (insbesondere contains()) sind hier ziemlich langsam, da die Arrays in linearer Zeit durchsucht werden.

Verwenden Sie dies nur für wirklich kleine Mengen, die häufig gelesen (iteriert) und selten geändert werden. (Swings Listener-Sets wären ein Beispiel, aber dies sind keine wirklichen Sets und sollten sowieso nur vom EDT verwendet werden.)

2) Collections.synchronizedSetwickelt einfach einen synchronisierten Block um jede Methode des ursprünglichen Satzes. Sie sollten nicht direkt auf das Originalset zugreifen. Dies bedeutet, dass keine zwei Methoden des Satzes gleichzeitig ausgeführt werden können (eine wird blockiert, bis die andere beendet ist) - dies ist threadsicher, aber Sie haben keine Parallelität, wenn mehrere Threads den Satz tatsächlich verwenden. Wenn Sie den Iterator verwenden, müssen Sie normalerweise noch extern synchronisieren, um ConcurrentModificationExceptions zu vermeiden, wenn Sie den Satz zwischen Iteratoraufrufen ändern. Die Leistung entspricht der Leistung des ursprünglichen Satzes (jedoch mit etwas Synchronisationsaufwand und Blockierung bei gleichzeitiger Verwendung).

Verwenden Sie diese Option, wenn Sie nur eine geringe Parallelität haben und sicherstellen möchten, dass alle Änderungen für die anderen Threads sofort sichtbar sind.

3) ConcurrentSkipListSetist die gleichzeitige SortedSetImplementierung mit den meisten grundlegenden Operationen in O (log n). Es ermöglicht das gleichzeitige Hinzufügen / Entfernen und Lesen / Iterieren, wobei die Iteration möglicherweise über Änderungen seit der Erstellung des Iterators informiert oder nicht. Die Massenoperationen sind einfach mehrere Einzelaufrufe und nicht atomar - andere Threads beobachten möglicherweise nur einige von ihnen.

Natürlich können Sie dies nur verwenden, wenn Sie eine Gesamtreihenfolge für Ihre Elemente haben. Dies scheint ein idealer Kandidat für Situationen mit hoher Parallelität zu sein, für nicht zu große Mengen (aufgrund des O (log n)).

4) Für die ConcurrentHashMap(und die daraus abgeleitete Menge): Hier sind die meisten grundlegenden Optionen (im Durchschnitt, wenn Sie eine gute und schnelle haben hashCode()) in O (1) (können aber zu O (n) degenerieren), wie für HashMap / HashSet. Es gibt eine begrenzte Parallelität zum Schreiben (die Tabelle ist partitioniert und der Schreibzugriff wird auf der erforderlichen Partition synchronisiert), während der Lesezugriff vollständig gleichzeitig mit sich selbst und den Schreibthreads erfolgt (die Ergebnisse der aktuellen Änderungen werden jedoch möglicherweise noch nicht angezeigt geschrieben). Der Iterator kann Änderungen seit seiner Erstellung sehen oder nicht, und Massenoperationen sind nicht atomar. Die Größenänderung ist langsam (wie bei HashMap / HashSet). Versuchen Sie daher, dies zu vermeiden, indem Sie die erforderliche Größe bei der Erstellung schätzen (und etwa 1/3 mehr davon verwenden, da die Größe geändert wird, wenn 3/4 voll ist).

Verwenden Sie diese Option, wenn Sie große Mengen und eine gute (und schnelle) Hash-Funktion haben und die Satzgröße und die erforderliche Parallelität vor dem Erstellen der Karte schätzen können.

5) Gibt es andere gleichzeitige Kartenimplementierungen, die hier verwendet werden könnten?

Es ist möglich, die contains()Leistung von HashSetmit den parallelen Eigenschaften von zu kombinieren, indem bei jeder Änderung der gesamte Satz CopyOnWriteArraySetverwendet AtomicReference<Set>und ersetzt wird.

Die Implementierungsskizze:

public abstract class CopyOnWriteSet<E> implements Set<E> {

    private final AtomicReference<Set<E>> ref;

    protected CopyOnWriteSet( Collection<? extends E> c ) {
        ref = new AtomicReference<Set<E>>( new HashSet<E>( c ) );
    }

    @Override
    public boolean contains( Object o ) {
        return ref.get().contains( o );
    }

    @Override
    public boolean add( E e ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( current.contains( e ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.add( e );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

    @Override
    public boolean remove( Object o ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( !current.contains( o ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.remove( o );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

}

Wenn die Javadocs nicht helfen, sollten Sie wahrscheinlich nur ein Buch oder einen Artikel finden, um über Datenstrukturen zu lesen. Auf einen Blick:

• CopyOnWriteArraySet erstellt jedes Mal, wenn Sie die Sammlung mutieren, eine neue Kopie des zugrunde liegenden Arrays, sodass die Schreibvorgänge langsam und die Iteratoren schnell und konsistent sind.
• Collections.synchronizedSet () verwendet synchronisierte Methodenaufrufe der alten Schule, um einen Thread threadsicher zu machen. Dies wäre eine Version mit geringer Leistung.
• ConcurrentSkipListSet bietet performante Schreibvorgänge mit inkonsistenten Stapeloperationen (addAll, removeAll usw.) und Iteratoren.
• Collections.newSetFromMap (neue ConcurrentHashMap ()) hat die Semantik von ConcurrentHashMap, die meiner Meinung nach nicht unbedingt für Lese- oder Schreibvorgänge optimiert ist, aber wie ConcurrentSkipListSet inkonsistente Stapeloperationen aufweist.

Gleichzeitiger Satz schwacher Referenzen

Eine weitere Wendung ist ein fadensicherer Satz schwacher Referenzen .

Ein solches Set ist praktisch, um Abonnenten in einem Pub-Sub- Szenario zu verfolgen . Wenn ein Abonnent an anderen Orten den Geltungsbereich verlässt und daher auf dem Weg ist, ein Kandidat für die Speicherbereinigung zu werden, muss der Abonnent nicht die Mühe haben, sich ordnungsgemäß abzumelden. Die schwache Referenz ermöglicht es dem Abonnenten, seinen Übergang zum Kandidaten für die Speicherbereinigung abzuschließen. Wenn der Müll schließlich gesammelt wird, wird der Eintrag im Set entfernt.

Während ein solcher Satz nicht direkt mit den gebündelten Klassen bereitgestellt wird, können Sie mit wenigen Aufrufen einen erstellen.

Zuerst beginnen wir damit, Setschwache Referenzen zu erstellen, indem wir die WeakHashMapKlasse nutzen. Dies wird in der Klassendokumentation für gezeigt Collections.newSetFromMap.

Set< YourClassGoesHere > weakHashSet = 
    Collections
    .newSetFromMap(
        new WeakHashMap< YourClassGoesHere , Boolean >()
    )
;

Der Wert der Karte Booleanist hier irrelevant, da der Schlüssel der Karte unsere ist Set.

In einem Szenario wie pub-sub benötigen wir Thread-Sicherheit, wenn die Abonnenten und Herausgeber auf separaten Threads arbeiten (sehr wahrscheinlich).

Gehen Sie noch einen Schritt weiter, indem Sie als synchronisierten Satz einwickeln, um diesen Satz threadsicher zu machen. In einen Anruf einspeisen Collections.synchronizedSet.

this.subscribers =
        Collections.synchronizedSet(
                Collections.newSetFromMap(
                        new WeakHashMap <>()  // Parameterized types `< YourClassGoesHere , Boolean >` are inferred, no need to specify.
                )
        );

Jetzt können wir Abonnenten zu unseren Ergebnissen hinzufügen und daraus entfernen Set. Und alle "verschwindenden" Abonnenten werden schließlich automatisch entfernt, nachdem die Speicherbereinigung ausgeführt wurde. Wann diese Ausführung erfolgt, hängt von der Garbage-Collector-Implementierung Ihrer JVM und von der aktuellen Laufzeitsituation ab. Eine Diskussion und ein Beispiel dafür, wann und wie der Basiswert WeakHashMapdie abgelaufenen Einträge löscht, finden Sie in dieser Frage: * Wächst WeakHashMap ständig oder werden die Müllschlüssel gelöscht? * .