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

84

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

andandandand
источник

Ответы:

175

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

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

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

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

Тодд Гэмблин
источник
1
Это также полезно, если вы хотите эффективно отслеживать уникальные записи в многопоточной среде.
anataliocs 06
4

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

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

бесспорный
источник
2

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

Калеб Браси
источник
1

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

Патрик Раск
источник