Parece que hay muchas implementaciones diferentes y formas de generar conjuntos seguros para subprocesos en Java. Algunos ejemplos incluyen

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (conjunto de conjuntos)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap (nuevo ConcurrentHashMap ())

5) Otros conjuntos generados de forma similar a (4)

Estos ejemplos provienen del Patrón de concurrencia: implementaciones de conjuntos concurrentes en Java 6

¿Podría alguien simplemente explicar las diferencias, ventajas y desventajas de estos ejemplos y otros? Tengo problemas para entender y mantener todo en orden desde los documentos estándar de Java.

1) La CopyOnWriteArraySetimplementación es bastante simple: básicamente tiene una lista de elementos en una matriz y, al cambiar la lista, copia la matriz. Las iteraciones y otros accesos que se están ejecutando en este momento continúan con la matriz anterior, evitando la necesidad de sincronización entre lectores y escritores (aunque la escritura misma debe sincronizarse). Las operaciones de configuración normalmente rápidas (especialmente contains()) son bastante lentas aquí, ya que las matrices se buscarán en tiempo lineal.

Use esto solo para conjuntos realmente pequeños que se leerán (iterarán) con frecuencia y se cambiarán raramente. (Swing listener-sets sería un ejemplo, pero estos no son realmente sets, y de todos modos solo deberían usarse desde el EDT).

2) Collections.synchronizedSetsimplemente envolverá un bloque sincronizado alrededor de cada método del conjunto original. No debe acceder al conjunto original directamente. Esto significa que no se pueden ejecutar simultáneamente dos métodos del conjunto (uno se bloqueará hasta que el otro termine): esto es seguro para subprocesos, pero no tendrá concurrencia si varios subprocesos realmente están usando el conjunto. Si usa el iterador, generalmente aún necesita sincronizar externamente para evitar ConcurrentModificationExceptions al modificar el conjunto entre llamadas de iterador. El rendimiento será como el rendimiento del conjunto original (pero con cierta sobrecarga de sincronización y bloqueo si se usa simultáneamente).

Use esto si solo tiene poca concurrencia y desea asegurarse de que todos los cambios sean visibles de inmediato para los otros subprocesos.

3) ConcurrentSkipListSetes la SortedSetimplementación concurrente , con la mayoría de las operaciones básicas en O (log n). Permite agregar / eliminar y leer / iterar simultáneamente, donde la iteración puede o no informar sobre los cambios desde que se creó el iterador. Las operaciones masivas son simplemente llamadas individuales múltiples, y no atómicamente; otros subprocesos pueden observar solo algunas de ellas.

Obviamente, puede usar esto solo si tiene un orden total en sus elementos. Esto parece un candidato ideal para situaciones de alta concurrencia, para conjuntos no demasiado grandes (debido a la O (log n)).

4) Para el ConcurrentHashMap(y el Conjunto derivado de él): Aquí las opciones más básicas son (en promedio, si tiene un buen y rápido hashCode()) en O (1) (pero podría degenerar en O (n)), como para HashMap / HashSet. Hay una concurrencia limitada para la escritura (la tabla está particionada, y el acceso de escritura se sincronizará en la partición necesaria), mientras que el acceso de lectura es totalmente concurrente para sí mismo y los hilos de escritura (pero es posible que aún no vean los resultados de los cambios que se están realizando actualmente escrito). El iterador puede ver o no cambios desde que se creó, y las operaciones masivas no son atómicas. El cambio de tamaño es lento (como para HashMap / HashSet), por lo tanto, trate de evitar esto estimando el tamaño necesario en la creación (y usando aproximadamente 1/3 más de eso, ya que cambia el tamaño cuando está 3/4 lleno).

Use esto cuando tenga conjuntos grandes, una función hash buena (y rápida) y pueda estimar el tamaño del conjunto y la concurrencia necesaria antes de crear el mapa.

5) ¿Hay otras implementaciones de mapas concurrentes que uno podría usar aquí?

Es posible combinar el contains()rendimiento de HashSetcon las propiedades relacionadas con la concurrencia de CopyOnWriteArraySetmediante el uso AtomicReference<Set>y la sustitución de todo el conjunto en cada modificación.

El boceto de implementación:

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 los Javadocs no ayudan, probablemente debería encontrar un libro o artículo para leer sobre las estructuras de datos. De un vistazo:

• CopyOnWriteArraySet realiza una nueva copia de la matriz subyacente cada vez que muta la colección, por lo que las escrituras son lentas y los iteradores son rápidos y consistentes.
• Collections.synchronizedSet () usa llamadas a métodos sincronizados de la vieja escuela para hacer un Set threadsafe. Esta sería una versión de bajo rendimiento.
• ConcurrentSkipListSet ofrece escrituras efectivas con operaciones discontinuas inconsistentes (addAll, removeAll, etc.) e Iteradores.
• Collections.newSetFromMap (new ConcurrentHashMap ()) tiene la semántica de ConcurrentHashMap, que creo que no está necesariamente optimizado para lecturas o escrituras, pero al igual que ConcurrentSkipListSet, tiene operaciones por lotes inconsistentes.

Conjunto concurrente de referencias débiles

Otro giro es un conjunto seguro de hilos de referencias débiles .

Tal conjunto es útil para rastrear suscriptores en un escenario pub-sub . Cuando un suscriptor está fuera de alcance en otros lugares y, por lo tanto, se dirige a convertirse en un candidato para la recolección de basura, no es necesario que el suscriptor se moleste en darse de baja con gracia. La referencia débil permite al suscriptor completar su transición para ser candidato para la recolección de basura. Cuando finalmente se recolecta la basura, se elimina la entrada en el conjunto.

Si bien este conjunto no se proporciona directamente con las clases agrupadas, puede crear uno con algunas llamadas.

Primero, comenzamos haciendo una Setreferencia débil aprovechando la WeakHashMapclase. Esto se muestra en la documentación de la clase para Collections.newSetFromMap.

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

El valor del mapa Booleanes irrelevante aquí, ya que la clave del mapa constituye nuestro Set.

En un escenario como pub-sub, necesitamos seguridad de subprocesos si los suscriptores y editores están operando en subprocesos separados (muy probablemente el caso).

Vaya un paso más allá envolviéndolo como un conjunto sincronizado para que este conjunto sea seguro para subprocesos. Alimentar en una llamada a Collections.synchronizedSet.

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

Ahora podemos agregar y eliminar suscriptores de nuestro resultado Set. Y cualquier suscriptor "desaparecido" eventualmente será eliminado automáticamente después de que se ejecute la recolección de basura. Cuando ocurre esta ejecución depende de la implementación del recolector de basura de su JVM, y depende de la situación de tiempo de ejecución en este momento. Para una discusión y un ejemplo de cuándo y cómo el subyacente WeakHashMapborra las entradas caducadas, vea esta pregunta, * ¿WeakHashMap está en constante crecimiento o borra las claves de basura? * .