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

Question

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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