Verschiedene Arten von thread-safe-Sets in Java

Scheint es eine Menge von verschiedenen Varianten und Möglichkeiten zu generieren, die thread-safe-Sets in Java.
Einige Beispiele sind

5) Andere Mengen erzeugt in einer Weise ähnlich zu (4)

Diese Beispiele kommen aus Muster von Parallelität: Gleichzeitige Set-Implementierungen in Java 6

Könnte jemand bitte einfach erklären Sie die Unterschiede, vor-und Nachteil, diese Beispiele und viele andere? Ich habe Probleme mit dem Verständnis und halten gerade alles aus der Java-Std-Docs.

InformationsquelleAutor Ben | 2011-07-16

187

1) Die CopyOnWriteArraySet ist eine Recht einfache Umsetzung - es hat im Grunde eine Liste von Elementen in einem array und beim ändern der Liste ist, kopiert das array. Iterationen und andere Zugänge, die in dieser Zeit weiterhin mit dem alten array, die Vermeidung der Notwendigkeit der Synchronisation zwischen Leser und Schreiber (obwohl das schreiben selbst synchronisiert werden muss). Die normalerweise schnelle set-Operationen (vor allem contains()) sind ziemlich langsam hier, wie die arrays gesucht werden, die in linearer Zeit.

Verwenden Sie diese nur für wirklich kleine Sätze, die gelesen werden (iterierten) oft und verändert selten. (Schaukeln Hörer-sets wäre ein Beispiel, aber diese sind nicht wirklich Sätze und sollte nur verwendet werden, der von der EDT sowieso.)

2) Collections.synchronizedSet einfach wickeln Sie einen synchronized-block, um jede Methode der ursprünglichen set. Sollten Sie keinen Zugriff auf das original-set direkt. Dies bedeutet, dass keine zwei Methoden des sets können gleichzeitig ausgeführt werden (eine wird blockiert, bis das andere beendet ist) - das ist thread-sicher, aber Sie haben nicht die Parallelität, wenn mehrere threads wirklich mit dem set. Wenn der iterator verwendet wird, Sie in der Regel noch synchronisieren müssen extern zu vermeiden ConcurrentModificationExceptions bei änderung der zwischen iterator aufruft. Die Leistung wird wie die Leistung der original-Satz (aber mit einigen Synchronisations-overhead, und blockieren, wenn gleichzeitig verwendet).

Verwenden Sie dies, wenn Sie nur geringe Parallelität und möchten sicher sein, alle änderungen sind sofort sichtbar für die anderen threads.

3) ConcurrentSkipListSet ist die gleichzeitige SortedSet Umsetzung, mit der die meisten grundlegenden Operationen in O(log n). Es ermöglicht gleichzeitige hinzufügen/entfernen und Lesen/iteration, wo die iteration kann oder kann nicht sagen, über änderungen seit der iterator erstellt wurde. Die bulk-Operationen sind einfach mehrere einzelne Anrufe, und nicht atomar - anderen threads beobachten können, nur einige von Ihnen.

Natürlich können Sie nur verwenden, wenn Sie haben einige totale Ordnung auf den Elementen.
Das sieht aus wie ein Idealer Kandidat für hohe Parallelität Situationen, für die nicht allzu großen Mengen (wegen der O(log n)).

4) Für die ConcurrentHashMap (und der Satz daraus abgeleitet): Hier werden die meisten grundlegenden Optionen sind (im Durchschnitt, wenn Sie eine gute und schnelle hashCode()) in O(1) - (aber ausarten könnte zu O(n)), wie für HashMap/HashSet. Es gibt eine begrenzte Parallelität für das schreiben (die Tabelle partitioniert ist, und schreib-Zugriff synchronisiert werden, auf die benötigte partition), während der Lesezugriff ist voll Auger auf sich selbst und das schreiben von threads (aber vielleicht noch nicht sehen, die Ergebnisse der Veränderungen, die zur Zeit geschrieben wird). Der iterator kann oder kann nicht sehen, die änderungen seit dem es erstellt wurde, und bulk-Operationen sind nicht atomar.
Größenänderung ist langsam (wie bei HashMap/HashSet), so versuchen, dies zu vermeiden, ist die Abschätzung der benötigten Größe auf die Bildung (und mit etwa 1/3 mehr, als es ändert, wenn 3/4 voll).

Verwenden Sie diese, wenn Sie große Mengen sind gut (und schnell) hash-Funktion und können eine Schätzung der Größe und benötigt Parallelität vor dem erstellen der Karte.

5) gibt es andere gleichzeitige anzeigen-Implementierungen könnte man hier benutzen?

Nur ein Augen-Korrektur in 1), der Prozess des Kopierens von Daten in das neue array muss gesperrt werden synchronisiert. Daher CopyOnWriteArraySet nicht völlig vermeiden, die Notwendigkeit der Synchronisation.
Auf ConcurrentHashMap Basis-set, "so versuchen, dies zu vermeiden, ist die Abschätzung der benötigten Größe auf die Bildung." Die Größe, die Sie geben die Karte an, sollte über 33% größer als Ihre Schätzung (oder bekannten Wert), da das set passt bei 75% Last. Ich benutze expectedSize + 4 / 3 + 1
Ich denke, die erste + soll ein *?
Natürlich... es sollte expectedSize * 4 / 3 + 1
Für ConcurrentMap (oder HashMap) in Java 8 ist die Anzahl der mapping-Einträge auf denselben bucket erreicht den Schwellenwert (ich glaube, es ist 16) und dann die Liste verändert wird, um einen binären such-Baum (rot-schwarz-Baum werden konkretisiert) und in diesem Fall suchen bis die Zeit wäre O(lg n) und nicht O(n).

InformationsquelleAutor Paŭlo Ebermann

Es ist möglich, kombinieren Sie die contains() Leistung HashSet mit der Parallelität-Eigenschaften der CopyOnWriteArraySet mithilfe der AtomicReference<Set> und ersetzen Sie den ganzen Satz auf jede änderung.

Umsetzung skizzieren:

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;
            }
        }
    }

}

Geniale Lösung, im Vergleich zu alles, was ich je gesehen habe in Bezug auf synchronisierte Listen. Danke!
Eigentlich AtomicReference markiert den Wert volatil. Es bedeutet, es macht sicher keinen thread liest sich veraltete Daten und stellt happens-before Garantie code können nicht neu angeordnet werden, indem der compiler. Aber Wenn Sie nur get - /set-Methoden der AtomicReference verwendet werden, dann sind wir eigentlich die Markierung der Variablen volatile in einer ausgefallenen Art und Weise.
Diese Antwort kann nicht genug von Ihnen positiv bewertet werden, weil (1), es sei denn, ich etwas verpasst, wird es Arbeit für alle collection-Typen (2) keiner der anderen Klassen bieten eine Möglichkeit, atomar aktualisieren Sie die gesamte Sammlung auf einmal... Das ist sehr nützlich.

InformationsquelleAutor Oleg Estekhin

10

Wenn die Javadocs nicht helfen, sollten Sie wahrscheinlich nur finden, ein Buch oder Artikel zu Lesen über die Daten-Strukturen. Auf einen Blick:
- CopyOnWriteArraySet macht eine neue Kopie der zugrunde liegenden array jedes mal, wenn Sie mutieren, der Sammlung, so schreibt langsam und Iteratoren sind schnell und konstant.
- Sammlungen.synchronizedSet() verwendet old-school-synchronized-Methode aufruft, um eine Reihe threadsicher sind. Dies wäre ein low-performing version.
- ConcurrentSkipListSet bietet performant schreibt mit inkonsistenten batch-Operationen (addAll, removeAll, etc.) und Iteratoren.
- Sammlungen.newSetFromMap(new ConcurrentHashMap()) die Semantik von ConcurrentHashMap, die ich glaube, ist nicht unbedingt optimiert für liest oder schreibt, sondern wie ConcurrentSkipListSet, hat inkonsistente batch-Operationen.
developer.com/java/article.php/10922_3829891_2/... < sogar besser als ein Buch )

InformationsquelleAutor Ryan Stewart
0

Gleichzeitige einstellen von schwachen Referenzen

Andere Wendung ist eine thread-sichere Reihe von schwache Referenzen.

Solch ein set ist praktisch für die Verfolgung von Abonnenten in eine pub-sub - Szenario. Wenn ein Teilnehmer geht aus dem Umfang, in anderen Orten, und daher in Richtung immer ein Kandidat für die garbage collection des Abonnenten müssen nicht mit belästigt werden ordnungsgemäß Abmelden. Der schwache Verweis kann der Teilnehmer für den kompletten übergang zu einem Kandidaten für die garbage-collection. Wenn der Müll irgendwann abgeholt, der Eintrag ist entfernt.

Während keine solche festgelegt ist, die direkt mit der mitgelieferten Klassen, die Sie erstellen können, mit ein paar Anrufe.

Zunächst beginnen wir mit der Herstellung eines Set von schwachen Referenzen durch die Nutzung der WeakHashMap Klasse. Dies ist gezeigt in der Klasse-Dokumentation für Sammlungen.newSetFromMap.
```
Set< YourClassGoesHere > weakHashSet = 
    Collections
    .newSetFromMap(
        new WeakHashMap< YourClassGoesHere , Boolean >()
    )
;
```
Den Wert der Karte, Boolean, ist hier irrelevant, da die Schlüssel der Karte lässt sich unser Set.

In einem Szenario wie pub-sub, brauchen wir thread-Sicherheit, wenn die Abonnenten und Verleger tätig sind, in separaten threads (sehr wahrscheinlich der Fall ist).

Gehen einen Schritt weiter, indem er als synchronisiert set zu diesem set thread-safe. Feed in einen Aufruf Sammlungen.synchronizedSet.
```
this.subscribers =
        Collections.synchronizedSet(
                Collections.newSetFromMap(
                        new WeakHashMap <>()  //Parameterized types `< YourClassGoesHere , Boolean >` are inferred, no need to specify.
                )
        );
```
Nun können wir hinzufügen und entfernen von Abonnenten aus unserem resultierende Set. Und alle "verschwundenen" Abonnenten werden schließlich automatisch entfernt, wenn die garbage collection ausgeführt wird. Bei dieser Ausführung tritt, hängt von Ihrer JVM den garbage-collector Umsetzung, und hängt von der Laufzeit situation im moment. Für die Erläuterung und ein Beispiel, Wann und wie die zugrunde liegenden WeakHashMap löscht abgelaufene Einträge, sehen Sie diese Frage, *WeakHashMap, wächst stetig, oder hat es klar aus dem Müll lösen?
*.

InformationsquelleAutor Basil Bourque

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.

Gleichzeitige einstellen von schwachen Referenzen