线程安全的数据结构，检查是否存在，如果不存在则写入

Question

我想解析一长串包含重复项的字符串，并将每个唯一字符串恰好一次保存到数组中。在多线程方法中，线程将检查共享数据结构是否存在，如果不存在则写入。

我忘了什么数据结构适合这个。 Java.util 中的任何内容都可以，高性能第三方库也是如此。

Answer 1

您可以使用 CopyOnWriteArrayList 或 ConcurrentLinkedQueue 来达到此目的。但是，如果您有很多写入，CopyOnWrite 方法的成本会很高。

如果您想删除重复项，请考虑使用 CopyOnWriteArraySet

Answer 2

为了在单线程应用程序中提供最大性能，java.util 包中的集合类不是线程安全的。（Vector 和 Hashtable 除外）

有几种方法可以实现您正在寻找的线程安全。

同步包装器 Set<String> safeSet = Collections.synchronizedSet(new HashSet<>());

这会将所有对底层集合的调用包装在同步块中，锁定对象。然而，这意味着当一个线程迭代集合中的元素时，所有其他集合的方法都会阻塞，导致其他线程不得不等待。

java.util.并发包

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

更新 Andy 的评论很好，我不确定如果您已经看过或没有看过某个项目，您想做什么。

您可以这样做以确保自动执行检查和插入

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

线程安全的数据结构，检查是否存在，如果不存在则写入

Thread safe data structure to check for existence and write if not

java

concurrency

java.util.concurrent