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

Question

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

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

Answer 1

java.util 包中的集合类不是线程安全的，以便在单线程应用程序中提供最大性能。 ( vector 和哈希表是异常(exception))

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

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

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

java.util.concurrent包

Java 5 引入了并发集合，它提供了比同步包装器更好的性能。

有不同的风格:写时复制、比较并交换和并发集合。

并发集合使用特殊的Lock，它比同步更灵活。

因此，对于您正在做的事情，如果 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
    }
}