Кажется, есть много разных реализаций и способов генерирования потоковобезопасных наборов в Java. Некоторые примеры включают

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (Set set)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap (новый ConcurrentHashMap ())

5) Другие множества, сгенерированные способом, аналогичным (4)

Эти примеры взяты из шаблона параллелизма: реализации параллельного набора в Java 6

Может ли кто-нибудь просто объяснить различия, преимущества и недостатки этих и других примеров? У меня возникли проблемы с пониманием и сохранностью всего из документов Java Std.

1) Это CopyOnWriteArraySetдовольно простая реализация - она ​​в основном имеет список элементов в массиве и при изменении списка копирует массив. Итерации и другие обращения, которые выполняются в это время, продолжаются со старым массивом, избегая необходимости синхронизации между читателями и пишущими (хотя сама запись должна быть синхронизирована). Обычно операции быстрого набора (особенно contains()) довольно медленные, так как массивы будут искать в линейном времени.

Используйте это только для действительно небольших наборов, которые будут часто читаться (повторяться) и изменяться редко. (Наборы слушателей Swings были бы примером, но на самом деле это не наборы, и в любом случае их следует использовать только из EDT.)

2) Collections.synchronizedSetпросто обернет синхронизированный блок вокруг каждого метода исходного набора. Вы не должны получать доступ к оригинальному набору напрямую. Это означает, что никакие два метода набора не могут выполняться одновременно (один будет блокироваться, пока другой не завершится) - это потокобезопасно, но у вас не будет параллелизма, если множество потоков действительно использует набор. Если вы используете итератор, вам, как правило, по-прежнему необходимо выполнять внешнюю синхронизацию, чтобы избежать исключений ConcurrentModificationExceptions при изменении набора между вызовами итератора. Производительность будет аналогична производительности исходного набора (но с некоторыми накладными расходами синхронизации и блокировкой, если используется одновременно).

Используйте это, если у вас только низкий уровень параллелизма и вы хотите, чтобы все изменения были немедленно видны другим потокам.

3) ConcurrentSkipListSetявляется параллельной SortedSetреализацией, с большинством основных операций в O (log n). Это позволяет одновременное добавление / удаление и чтение / итерацию, когда итерация может или не может рассказать об изменениях с момента создания итератора. Массовые операции - это просто множественные одиночные вызовы, а не атомарно - другие потоки могут наблюдать только некоторые из них.

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

4) Для ConcurrentHashMap(и набора, полученного из него): здесь большинство основных опций (в среднем, если у вас хорошо и быстро hashCode()) в O (1) (но может выродиться в O (n)), как для HashMap / HashSet. Существует ограниченный параллелизм для записи (таблица разбита на разделы, и доступ на запись будет синхронизирован на нужном разделе), в то время как доступ на чтение полностью параллелен для самого себя и потоков записи (но может еще не увидеть результаты изменений, которые в данный момент находятся написано). Итератор может видеть или не видеть изменения, так как он был создан, и массовые операции не являются атомарными. Изменение размера происходит медленно (как для HashMap / HashSet), поэтому постарайтесь избежать этого, оценивая необходимый размер при создании (и используя примерно 1/3 от этого, поскольку он изменяет размер при заполнении 3/4).

Используйте это, когда у вас большие наборы, хорошая (и быстрая) хеш-функция, и вы можете оценить размер набора и необходимый параллелизм перед созданием карты.

5) Есть ли другие параллельные реализации карт, которые можно использовать здесь?

Можно комбинировать contains()производительность HashSetсо свойствами, связанными с параллелизмом CopyOnWriteArraySet, используя AtomicReference<Set>и заменяя весь набор в каждой модификации.

Эскиз реализации:

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;
            }
        }
    }

}

Если Javadocs не помогают, вы, вероятно, должны просто найти книгу или статью, чтобы прочитать о структурах данных. С одного взгляда:

• CopyOnWriteArraySet создает новую копию базового массива каждый раз, когда вы изменяете коллекцию, поэтому записи выполняются медленно, а итераторы - быстрыми и последовательными.
• Collections.synchronizedSet () использует вызовы синхронизированных методов старой школы для обеспечения безопасности потока Set. Это будет неэффективная версия.
• ConcurrentSkipListSet предлагает эффективные записи с несовместимыми пакетными операциями (addAll, removeAll и т. Д.) И итераторами.
• Collections.newSetFromMap (новый ConcurrentHashMap ()) имеет семантику ConcurrentHashMap, которая, я считаю, не обязательно оптимизирована для чтения или записи, но, как и ConcurrentSkipListSet, имеет несовместимые пакетные операции.

Параллельный набор слабых ссылок

Другой поворот - это потокобезопасный набор слабых ссылок .

Такой набор удобен для отслеживания подписчиков в сценарии pub-sub . Когда подписчик выходит из области действия в других местах и, следовательно, стремится стать кандидатом на сборку мусора, подписчику не нужно беспокоиться о изящной отписке. Слабая ссылка позволяет подписчику завершить переход к кандидату на сборку мусора. Когда мусор в конечном итоге собирается, запись в наборе удаляется.

Хотя в комплекте классов нет такого набора, вы можете создать его с помощью нескольких вызовов.

Сначала мы начнем со Setслабых ссылок, используя WeakHashMapкласс. Это показано в документации класса для Collections.newSetFromMap.

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

Значение карты, Booleanявляется здесь неуместно как ключ карты составляет наши Set.

В таком сценарии, как pub-sub, нам нужна безопасность потоков, если подписчики и издатели работают в отдельных потоках (вполне вероятно, что так и будет).

Сделайте еще один шаг, обернув его как синхронизированный набор, чтобы сделать этот набор потокобезопасным. Поток в призыв к Collections.synchronizedSet.

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

Теперь мы можем добавлять и удалять подписчиков из нашего результата Set. И любые «исчезающие» подписчики в конечном итоге будут автоматически удалены после выполнения сборки мусора. Когда это выполнение произойдет, зависит от реализации сборщика мусора в вашей JVM и зависит от ситуации времени выполнения в данный момент. Обсуждение и пример того, когда и как базовый инструментWeakHashMap очищает просроченные записи, см. В этом Вопросе: * Является ли WeakHashMap постоянно растущим или он очищает ключи мусора? * .