Ответ 1

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

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

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

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

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

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

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

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

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

Ответ 2

Можно объединить производительность contains() HashSet с concurrency -связанными свойствами 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;
            }
        }
    }

}

Ответ 3

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

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

Ответ 4

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

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

Такой набор удобен для отслеживания подписчиков в сценарии 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 постоянно растущим или он очищает ключи мусора? *