Потокобезопасная структура данных для проверки существования и записи, если нет

Question

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

Я забыл, какая структура данных подходит для этого. Все, что есть в Java.util, прекрасно, как и высокопроизводительные сторонние библиотеки.

Answer 1

Классы коллекции в пакете java.util не являются поточно-ориентированными для обеспечения максимальной производительности в однопоточных приложениях.(Vector и Hashtable являются исключениями)

Существует несколько способов достижения безопасности потока, которую вы ищете.

Sychronized Wrapper Set<String> safeSet = Collections.synchronizedSet(new HashSet<>());

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

java.util.concurrent Package

Java 5 представила параллельные коллекции, которые обеспечивают намного лучшую производительность, чем синхронизированные оболочки.

Существуют различные варианты: копирование при записи, сравнение и замена и одновременные коллекции.

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

Так что для того, что вы делаете, HashSet, вероятно, будет хорошим совпадением, если он был однопоточным.В параллельном пакете вы можете использовать ConcurrentHashMap.

Это будет выглядеть так:

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

...

 private static final Object PRESENT = new Object();
 Map<String, Object> seenStrings = new ConcurrentHashMap<>();



for ( String aString : stringList ) {
    if ( seenStrings.containsKey(aString) ) {
        // Already there
    } else {
        // Not seen yet
        seenStrings.put(aString, PRESENT);
    }
}

Обновление Комментарий Энди хорош, я не был уверен, чтоВы хотели бы сделать, если вы уже видели элемент или если вы не видели.

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

if (seenStrings.put(aString, PRESENT) == null) {
       // Not seen yet
} 

Обновление В Java 8+ вы можете создать набор, поддерживаемый указанной картой,Эффективно ConcurrentHashSet.

Set<String> seenStrings = Collections.newSetFromMap(new ConcurrentHashMap<>());
for (String aString : stringList) {
    if (seenStrings.add(aString)) {               
            // Not seen yet
    }
}

Answer 2

Вы можете использовать CopyOnWriteArrayList или ConcurrentLinkedQueue для этой цели. Однако, если у вас много записей CopyOnWrite, подход будет дорогостоящим.

Если вы хотите удалить дубликаты, рассмотрите возможность использования CopyOnWriteArraySet