Когда CopyOnWriteArraySet полезен для создания потокобезопасного HashSet?

В Java существует поточно-безопасная версия HashMap с именем ConcurrentHashMap и потокобезопасная версия TreeMap с именем ConcurrentSkipListMap, но нет ConcurrentHashSet для HashSet.

Вместо этого обычно существует 4 способа использования поточно-безопасных Set:

Set<String> mySet = Collections.newSetFromMap(new ConcurrentHashMap<String, Boolean>());
Set<String> s = Collections.synchronizedSet(new HashSet<String>());
ConcurrentSkipListSet<E>
CopyOnWriteArraySet<E>

1 используйте keySet() для ConcurrentHashMap для достижения как Set, так и потокобезопасных.

2 используйте synchronized путь, кажется, что этот способ не рекомендуется.

3 основана на ConcurrentSkipListMap и широко используется.

4 основан на CopyOnWriteArrayList, поэтому он имеет те же основные свойства CopyOnWriteArrayList. Ниже показан выбор из CopyOnWriteArraySet doc: http://docs.oracle.com/javase/8/docs/api/java/util/concurrent/CopyOnWriteArraySet.html

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

Поскольку 1 и 3 обычно используются, почему существует CopyOnWriteArraySet? Когда CopyOnWriteArraySet полезно?

Добавлено: CopyOnWriteArraySet основано на CopyOnWriteArrayList, а операция contains в структуре List - O (n), а структура данных Set - для высокой производительности contains, может кто-нибудь объяснить это?

Ответ 1

Это полезно, если у вас есть небольшой набор элементов для потоковой безопасности.

Одним из примеров является набор слушателей. Вам необходимо обеспечить уникальность и эффективную обработку их.

BTW CopyOnWriteArraySet имеет самые низкие накладные расходы для каждой базовой базы. Это может быть всего лишь на 1/6 размера других коллекций. Это особенно полезно, если у вас их много.

в то время как структура данных для высокой производительности содержит операцию, может кто-нибудь объяснить это?

COWAS более эффективен с точки зрения памяти, а contains быстрее для небольших коллекций, чем альтернативы. Что такое "высокая производительность", зависит от варианта использования.

Ответ 2

Структуры копирования на запись функционально неизменяемы.

Java в один момент имела очень плохую историю для предоставления неизменных представлений о записываемых структурах, таких как множества. Например, если у вас есть член набора и вы публично его публиковали, вызывающий может просто развернуться и отредактировать его, и, следовательно, отредактировать внутреннее состояние вашего объекта! Но что еще вы можете сделать, скопируйте все, прежде чем вернуться из любой публичной функции? Это было бы бессмысленно медленно.

Это была история ранее в истории Java. Они полагались почти исключительно на неизменяемые объекты (пример строки). Коллекции были исключением из этого шаблона и поэтому были проблематичными с точки зрения инкапсуляции. Когда было добавлено CopyOnWriteArraySet, unmodifiableCollection и unmodifiableSet еще не существовало (хотя unmodifiableCollection в значительной степени решило проблему, я все же считаю это более громоздким решением, чем то, что предлагают другие языки, особенно при использовании настраиваемых структур данных), Таким образом, это объясняет, вероятно, самую большую мотивацию для создания CopyOnWriteArraySet в первую очередь. Вы можете вернуть CopyOnWriteArraySet, не опасаясь, что кто-то еще изменит ваше внутреннее состояние объекта, и не тратя время на ненужные копии.

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

Ответ 3

Тестовый код:

Set<String> a = new CopyOnWriteArraySet<String>();
    for(int i=0;i<10;i++) {
        a.add("str" + i);
    }
    boolean flag = true;
    long t1 = System.currentTimeMillis();
    for(int i=0;i<200000;i++) {
        flag = a.contains("str" + i);
    }
    System.out.println(System.currentTimeMillis() - t1);

    Set<String> b = Collections.newSetFromMap(new ConcurrentHashMap<String, Boolean>());
    for(int i=0;i<10;i++) {
        b.add("str" + i);
    }
    t1 = System.currentTimeMillis();
    for(int i=0;i<200000;i++) {
        flag = b.contains("str" + i);
    }
    System.out.println(System.currentTimeMillis() - t1);

Показывает, что CopyOnWriteArraySet работает медленнее, чем Collections.newSetFromMap. Поскольку тестовый пример является очень маленьким Set с операцией только для чтения, CopyOnWriteArraySet кажется не лучше.