CopyOnWriteArraySet 何时对实现线程安全的 HashSet 有用？

Question

在Java中，有线程安全版本HashMap named ConcurrentHashMap and thread-safe version TreeMap named ConcurrentSkipListMap, but there is no ConcurrentHashSet for 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() of ConcurrentHashMap 来同时实现 Set 和线程安全。

2使用synchronized方式，好像不推荐这种方式。

3基于ConcurrentSkipListMap，被广泛使用。

4 基于 CopyOnWriteArrayList, thus it shares the same basic properties of CopyOnWriteArrayList. Following is select from 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 操作，有人可以解释一下吗？

Answer 1

当你有一个线程安全集合的一小组元素时，它很有用。

一个示例是一组侦听器。您需要确保唯一性并有效地迭代它们。

顺便说一句，CopyOnWriteArraySet 在每个引用的基础上具有最低的开销。它可以小到其他集合大小的 1/6。如果您有很多，这将特别有用。

while Set data structure is for high performance contains operation, could anybody explain this?

COWAS 在内存方面更高效，并且 contains 对于小型集合比替代方案更快。什么是 "high performance" 取决于用例。

Answer 2

写时复制结构在功能上是不可变的。

Java 曾经有一个非常糟糕的故事，用于提供关于集合等可写结构的不可变视图。例如，如果您有一个集合成员，并且您 return 仅 public 编辑了它，调用者就可以转身编辑它，因此正在编辑您对象的内部状态！但是您还能做什么，从任何 public 函数复制 returning 之前的整个内容？那会毫无意义地慢。

这是 Java 历史上更早的故事。他们几乎完全依赖不可变对象（字符串就是一个例子）。集合是这种模式的一个例外，因此从封装的角度来看是有问题的。添加 CopyOnWriteArraySet 时， unmodifiableCollection 和 unmodifiableSet 还不存在（虽然 unmodifiableCollection 已经在很大程度上解决了问题，但我仍然觉得它比其他语言提供的解决方案更麻烦，尤其是在使用自定义数据结构时）。所以这可能首先解释了创建 CopyOnWriteArraySet 的最大动机。您可以 return 一个 CopyOnWriteArraySet 而不必担心其他人修改您的对象的内部状态，也不会浪费时间进行不必要的复制。

Copy-On-Write 是几年前的一种时尚，但它对于多线程编程来说是一个众所周知的效率低下的想法，并且效率低于其他模型。从您发布的文档中，他们通过创建线程本地快照来加速迭代它，这意味着他们正在花费内存来补偿。因此，只要您的数据很小，就完全可以 class 使用...因为内存快照加起来不会浪费太多内存。

Answer 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似乎并不好。

CopyOnWriteArraySet 何时对实现线程安全的 HashSet 有用？

When is CopyOnWriteArraySet useful to achieve thread-safe HashSet?

java

collections

concurrency

multithreading

java.util.concurrent