¿Cuándo es útil un ConcurrentSkipListSet?

3 minutos de lectura

avatar de usuario
yyyyy

Acabo de ver esta estructura de datos en la API de Java 6 y tengo curiosidad acerca de cuándo sería un recurso útil. Estoy estudiando para el examen scjp y no lo veo cubierto en el libro de Kathy Sierra, aunque he visto preguntas de examen simuladas que lo mencionan.

avatar de usuario
Todd Gamblin

Conjunto de listas de saltos simultáneos y Mapa de lista de saltos simultáneos son útiles cuando necesita un contenedor ordenado al que accederán varios subprocesos. Estos son esencialmente los equivalentes de TreeMap y TreeSet para código concurrente.

La implementación de JDK 6 se basa en Conjuntos basados ​​en listas y tablas hash sin bloqueo dinámico de alto rendimiento por Maged Michael en IBM, que muestra que puede implementar muchas operaciones en listas salteadas de forma atómica usando comparar e intercambiar (CAS) operaciones. Estos no tienen bloqueo, por lo que no tiene que preocuparse por los gastos generales de synchronized (para la mayoría de las operaciones) cuando usa estas clases.

actualmente no hay Árbol rojo-negro Implementación concurrente basada en Map/Set en Java. Revisé un poco la literatura y encontré un pareja documentos que mostró árboles RB concurrentes superando las listas de omisión, pero muchas de estas pruebas se realizaron con memoria transaccionalque no es compatible con el hardware de ninguna de las principales arquitecturas en este momento.

Asumo que los muchachos de JDK se saltearon la lista aquí porque la implementación era bien conocida y porque hacerlo sin bloqueos era simple y portátil (usando CAS). Si a alguien le importa aclarar, por favor que lo haga. Soy curioso.

  • También es útil si desea realizar un seguimiento de los registros únicos en un entorno de subprocesos múltiples de manera eficaz.

    – anataliocs

    06/03/2017 a las 22:47

Las listas de omisión son listas ordenadas y eficientes para modificar con el rendimiento de log(n). en ese sentido es como TreeSet. sin embargo, no hay ConcurrentTreeSet. lo que escuché es que la lista de saltos es muy fácil de implementar, probablemente por eso.

De todos modos, cuando necesite un conjunto concurrente, ordenado y eficiente, puede usar ConcurrentSkipListSet

  • Respuesta concisa que es buena, pero probablemente podría haberla respaldado con enlaces en lugar de “Escuché” para mejorarla.

    – Christian Vielma

    17 de diciembre de 2021 a las 11:21

Estos son útiles cuando se necesita un conjunto al que se pueda acceder de forma segura mediante varios subprocesos simultáneamente. También proporciona un rendimiento decente al ser débilmente consistente: las inserciones se pueden hacer de manera segura mientras itera a través del Conjunto, pero no hay garantía de que su Iterador vea esa inserción.

ConcurrentSkipListMap fue un hallazgo fantástico cuando necesitaba implementar una capa de replicación para un caché local. Los aspectos de Mapa implementaron el caché, y los aspectos de Lista subyacentes me permitieron realizar un seguimiento del orden en que aparecían los objetos en el caché. El aspecto de “saltar” de esa lista hizo que fuera eficiente eliminar un objeto de un lugar en la lista y llevarlo hasta el final cuando se reemplazó en el caché.

¿Ha sido útil esta solución?