java - Java 中不同类型的线程安全集

Question

在 Java 中似乎有很多不同的实现和方法来生成线程安全集。 一些示例包括

1) CopyOnWriteArraySet

2) Collections.synchronizedSet(Set set)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap(new ConcurrentHashMap())

5)其他Set的生成方式与(4)类似

这些例子来自Concurrency Pattern: Concurrent Set implementations in Java 6

有人可以简单解释一下这些例子和其他例子的区别、优点和缺点吗？我无法理解并保持 Java 标准文档中的所有内容。

Answer 1

1. CopyOnWriteArraySet 是一个非常简单的实现 - 它基本上有一个数组中的元素列表，当更改列表时，它会复制该数组。此时正在运行的迭代和其他访问继续使用旧数组，避免了读取器和写入器之间同步的必要性(尽管写入本身需要同步)。通常快速的设置操作(尤其是 contains())在这里相当慢，因为将以线性时间搜索数组。

   仅将其用于非常小的集合，这些集合将被经常读取(迭代)并且很少更改。 (Swing 的监听器集是一个示例，但这些并不是真正的集，无论如何都应该仅在 EDT 中使用。)

2. Collections.synchronizedSet 将简单地将同步块(synchronized block)包装在原始集合的每个方法周围。您不应该直接访问原始集。这意味着该集合中的任何两个方法都不能同时执行(一个方法将阻塞，直到另一个方法完成)——这是线程安全的，但如果多个线程正在使用该集合，则不会有并发性。如果使用迭代器，通常仍然需要进行外部同步，以避免在迭代器调用之间修改集合时出现 ConcurrentModificationExceptions。性能将与原始集的性能类似(但有一些同步开销，如果并发使用会阻塞)。

   如果您只有低并发性，并且希望确保所有更改对其他线程立即可见，请使用此选项。

3. ConcurrentSkipListSet 是并发 SortedSet 实现，大多数基本操作的时间复杂度为 O(log n)。它允许并发添加/删除和读取/迭代，其中迭代可能会或可能不会告知自迭代器创建以来的更改。批量操作只是多个单一调用，并且不是原子完成的 - 其他线程可能只观察其中的一些操作。

   显然，只有当你的元素有一定的总顺序时，你才能使用它。 对于高并发情况、不太大的集合(因为 O(log n))，这看起来是一个理想的选择。

4. 对于 ConcurrentHashMap(以及从中派生的 Set):这里最基本的选项是(平均而言，如果您有一个良好且快速的 hashCode())，时间复杂度为 O(1)(但当许多键具有相同的哈希码时，可能会退化为 O(n))，例如 HashMap/HashSet。写入的并发性有限(表已分区，写入访问将在所需分区上同步)，而读取访问本身和写入线程完全并发(但可能尚未看到当前正在写入的更改的结果)。迭代器自创建以来可能会或可能不会看到更改，并且批量操作不是原子的。 调整大小很慢(对于 HashMap/HashSet)，因此您应该通过估计创建时所需的大小来尝试避免这种情况(并使用大约 1/3 以上的大小，因为它会在 3/4 满时调整大小)。

   当您有大型集合、良好(且快速)的哈希函数并且可以在创建映射之前估计集合大小和所需的并发性时，请使用此功能。

5. 这里还有其他可以使用的并发 map 实现吗？