Когда полезен ConcurrentSkipListSet?

Я только что видел эту структуру данных в API Java 6, и мне любопытно, когда это будет полезным ресурсом. Я готовлюсь к экзамену scjp, и я не вижу, чтобы он освещался в книге Кэти Сьерра, хотя я видел пробные экзаменационные вопросы, в которых это упоминается.

ConcurrentSkipListSet и ConcurrentSkipListMap полезны, когда вам нужен отсортированный контейнер, к которому будут обращаться несколько потоков. По сути, это эквиваленты TreeMap и TreeSet для параллельного кода.

Реализация для JDK 6 основана на высокопроизводительных динамических хэш-таблицах без блокировок и наборах на основе списков, разработанных Maged Michael из IBM, что показывает, что вы можете реализовать множество операций со списками пропуска атомарно, используя операции сравнения и обмена (CAS) . Они свободны от блокировок, поэтому вам не нужно беспокоиться о накладных расходах synchronized(для большинства операций) при использовании этих классов.

В настоящее время в Java не существует параллельной реализации Map / Set на основе красного и черного дерева . Я немного просмотрел литературу и нашел пару статей , в которых показано, что параллельные деревья RB превосходят списки пропусков, но многие из этих тестов проводились с транзакционной памятью , которая в настоящее время не поддерживается аппаратно ни на одной из основных архитектур.

Я предполагаю, что ребята из JDK пошли сюда с пропущенным списком, потому что реализация была хорошо известна и потому, что сделать ее без блокировки было просто и переносимо (с использованием CAS). Если кто-то хочет уточнить, пожалуйста. Мне любопытно.

списки пропуска - это отсортированные списки, которые можно эффективно изменять с помощью функции log (n). в этом отношении это похоже на TreeSet. однако нет ConcurrentTreeSet. я слышал, что список пропуска очень легко реализовать, наверное, поэтому.

В любом случае, когда вам нужен параллельный, отсортированный и эффективный набор, вы можете использовать ConcurrentSkipListSet

Они полезны, когда вам нужен набор, к которому могут безопасно обращаться одновременно несколько потоков. Он также обеспечивает достойную производительность за счет слабой согласованности - вставки можно безопасно выполнять, пока вы выполняете итерацию по Set, но нет гарантии, что ваш итератор увидит эту вставку.

ConcurrentSkipListMap был фантастической находкой, когда мне нужно было реализовать уровень репликации для собственного кеша. Аспекты Map реализовали кеш, а базовые аспекты List позволяют мне отслеживать порядок, в котором объекты появляются в кеше. Аспект «пропуска» этого списка позволял эффективно удалять объект из одного места в списке и перемещать его до конца, когда он был заменен в кеше.