Il semble y avoir beaucoup d'implémentations et de façons différentes de générer des ensembles thread-safe en Java. Quelques exemples incluent

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (ensemble d'ensemble)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap (nouveau ConcurrentHashMap ())

5) Autres ensembles générés d'une manière similaire à (4)

Ces exemples proviennent de Concurrency Pattern: Implémentations de jeux simultanés dans Java 6

Quelqu'un pourrait-il expliquer simplement les différences, les avantages et les inconvénients de ces exemples et d'autres? J'ai du mal à comprendre et à garder tout droit de la documentation Java Std.

1) Le CopyOnWriteArraySetest une implémentation assez simple - il a essentiellement une liste d'éléments dans un tableau, et lors de la modification de la liste, il copie le tableau. Les itérations et autres accès qui sont en cours à ce moment continuent avec l'ancien tableau, évitant la nécessité d'une synchronisation entre les lecteurs et les écrivains (bien que l'écriture elle-même doive être synchronisée). Les opérations de réglage normalement rapides (en particulier contains()) sont assez lentes ici, car les tableaux seront recherchés en temps linéaire.

Utilisez ceci uniquement pour de très petits ensembles qui seront lus (itérés) souvent et rarement modifiés. (Les ensembles d'écouteurs Swings seraient un exemple, mais ce ne sont pas vraiment des ensembles et ne devraient de toute façon être utilisés qu'à partir de l'EDT.)

2) Collections.synchronizedSetenroulera simplement un bloc synchronisé autour de chaque méthode de l'ensemble d'origine. Vous ne devez pas accéder directement à l'ensemble d'origine. Cela signifie qu'aucune méthode de l'ensemble ne peut être exécutée simultanément (l'une se bloquera jusqu'à ce que l'autre se termine) - c'est thread-safe, mais vous n'aurez pas de concurrence si plusieurs threads utilisent vraiment l'ensemble. Si vous utilisez l'itérateur, vous devez généralement toujours effectuer une synchronisation externe pour éviter les exceptions ConcurrentModificationExceptions lors de la modification de l'ensemble entre les appels d'itérateur. Les performances seront similaires à celles de l'ensemble d'origine (mais avec une surcharge de synchronisation et un blocage si elles sont utilisées simultanément).

Utilisez cette option si vous n'avez qu'une faible concurrence d'accès et que vous voulez vous assurer que toutes les modifications sont immédiatement visibles pour les autres threads.

3) ConcurrentSkipListSetest l' SortedSetimplémentation simultanée , avec la plupart des opérations de base en O (log n). Il permet l'ajout / suppression et la lecture / itération simultanés, où l'itération peut ou non indiquer les changements depuis la création de l'itérateur. Les opérations en bloc sont simplement de multiples appels uniques, et non de manière atomique - d'autres threads peuvent n'en observer que certains.

Évidemment, vous ne pouvez l'utiliser que si vous avez une commande totale sur vos éléments. Cela ressemble à un candidat idéal pour les situations à forte concurrence, pour des ensembles pas trop grands (à cause du O (log n)).

4) Pour le ConcurrentHashMap(et l'ensemble qui en dérive): Ici, la plupart des options de base sont (en moyenne, si vous avez un bon et rapide hashCode()) dans O (1) (mais peuvent dégénérer en O (n)), comme pour HashMap / HashSet. Il y a une concurrence limitée pour l'écriture (la table est partitionnée et l'accès en écriture sera synchronisé sur la partition nécessaire), tandis que l'accès en lecture est entièrement simultané avec lui-même et les threads d'écriture (mais il se peut que les résultats des modifications actuellement en cours ne soient pas encore visibles. écrit). L'itérateur peut ou non voir les changements depuis sa création et les opérations en bloc ne sont pas atomiques. Le redimensionnement est lent (comme pour HashMap / HashSet), essayez donc d'éviter cela en estimant la taille nécessaire à la création (et en utilisant environ 1/3 de plus, car il est redimensionné lorsqu'il est plein aux 3/4).

Utilisez-le lorsque vous avez de grands ensembles, une bonne (et rapide) fonction de hachage et pouvez estimer la taille de l'ensemble et la concurrence nécessaire avant de créer la carte.

5) Y a-t-il d'autres implémentations de cartes concurrentes que l'on pourrait utiliser ici?

Il est possible de combiner les contains()performances de HashSetavec les propriétés liées à la concurrence de CopyOnWriteArraySeten utilisant le AtomicReference<Set>et en remplaçant l'ensemble complet à chaque modification.

L'esquisse de mise en œuvre:

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

}

Si les Javadocs ne vous aident pas, vous devriez probablement simplement trouver un livre ou un article à lire sur les structures de données. En un coup d'oeil:

• CopyOnWriteArraySet crée une nouvelle copie du tableau sous-jacent à chaque fois que vous modifiez la collection, les écritures sont donc lentes et les itérateurs sont rapides et cohérents.
• Collections.synchronizedSet () utilise des appels de méthode synchronisée à l'ancienne pour rendre un Set threadsafe. Ce serait une version peu performante.
• ConcurrentSkipListSet offre des écritures performantes avec des opérations par lots incohérentes (addAll, removeAll, etc.) et des itérateurs.
• Collections.newSetFromMap (new ConcurrentHashMap ()) a la sémantique de ConcurrentHashMap, qui, je crois, n'est pas nécessairement optimisée pour les lectures ou les écritures, mais comme ConcurrentSkipListSet, a des opérations par lots incohérentes.

Ensemble simultané de références faibles

Une autre torsion est un ensemble de références faibles thread-safe .

Un tel ensemble est pratique pour suivre les abonnés dans un scénario pub-sub . Lorsqu'un abonné est hors de portée à d'autres endroits, et se dirige donc vers le candidat pour le ramassage des ordures, l'abonné n'a pas besoin de se désabonner gracieusement. La référence faible permet à l'abonné d'achever sa transition pour devenir un candidat au garbage collection. Lorsque le garbage est finalement collecté, l'entrée de l'ensemble est supprimée.

Bien qu'aucun tel ensemble ne soit directement fourni avec les classes groupées, vous pouvez en créer un avec quelques appels.

Nous commençons par créer Setdes références faibles en tirant parti de la WeakHashMapclasse. Ceci est montré dans la documentation de classe pour Collections.newSetFromMap.

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

La valeur de la carte Booleann'est pas pertinente ici car la clé de la carte constitue notre Set.

Dans un scénario tel que pub-sub, nous avons besoin de la sécurité des threads si les abonnés et les éditeurs fonctionnent sur des threads séparés (très probablement le cas).

Allez un peu plus loin en enveloppant comme un ensemble synchronisé pour rendre cet ensemble thread-safe. Participez à un appel à Collections.synchronizedSet.

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

Nous pouvons maintenant ajouter et supprimer des abonnés de notre résultat Set. Et tous les abonnés «disparaissant» seront finalement automatiquement supprimés après l'exécution du ramasse-miettes. Le moment où cette exécution se produit dépend de l'implémentation du garbage collector de votre JVM et de la situation d'exécution actuelle. Pour une discussion et un exemple de quand et comment le sous-jacent WeakHashMapefface les entrées expirées, voir cette question, * WeakHashMap est-il en constante croissance ou efface-t-il les clés de garbage? * .