最高效但线程安全的列表/集合

Question

Java有许多不同的集合类专为并发和线程安全而设计，但我不知道该选择哪一个适用于我的情况。

可能有多个线程同时调用.add()和.remove()方法，而我会经常使用类似List<T> newList = new ArrayList<T>(concurrentList)这样的语句复制此列表。我将永远不会遍历并发列表。

我考虑过像CopyOnWriteArrayList这样的东西，但我听说它可能非常低效，因为每次修改时都会复制自身。我希望能找到一个安全性和效率之间的好平衡点。

什么是最适合这种情况的列表（或集合）？

- Rogue

---

你确定需要一个列表吗？Map或Set是否能满足您的需求。与列表相比，同时访问Map或Set要容易得多。 - bhspencer

你可以使用以下代码创建一个基于ConcurrentHashMap的ConcurrentSet： Map<K, Boolean> map = new ConcurrentHashMap(); Set<K> set = Collections.newSetFromMap(map); - bhspencer

@Rogue 这真的取决于你的使用情况是否适合队列。 如果您可以始终从前面添加和删除，则可能更有效。请参见[ConcurrentLinkedQueue]（https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html） - augray

你在调用添加/删除操作的频率与复制操作相比如何？而且，你真的需要在不同的线程中从同一个列表中添加/删除元素，而不是每个线程编辑另一个副本吗？ - Tesseract

每秒50个元素？那你为什么担心性能呢？只有当你达到每秒百万个元素时才需要担心性能。 - Tesseract

Answer 1

正如@SpiderPig所说，最好的情况是使用不可变的单向链表来实现List。然而，根据@bhspencer的评论，这里使用List是不必要的。使用ConcurrentSkipListSet会更加高效（@augray）。请参考此相关帖子的采纳答案，了解不同并发集合的优缺点。

- Rogue

---

请注意，synchronizedSet也具有对象范围锁定（对它的所有调用都将被阻塞，因此一次只能有一个线程与其一起工作）。如果您可以找到一种使用并发对象而不是同步对象的方法，那么从性能上来说，您很可能会更好（假设该资源影响性能，这似乎是一个安全的假设，考虑到问题的情况）。 - augray

如果您愿意使用集合，ConcurrentSkipListSet 可能比 synchronizedSet 更高效。来自《Java并发编程实战》的说法是：“用并发集合替换同步集合可以在几乎没有风险的情况下提供显著的可扩展性改进。” - augray

Answer 2

你可能需要考虑使用 ctrie 是否适合你的用例 - 它具有线程安全的 add 和 remove 操作，并且“复制”（实际上是拍摄快照）数据结构的运行时间为 O(1)。我知道两个 JVM 实现该数据结构：实现一, 实现二。

- Zim-Zam O'Pootertoot

Answer 3

Collections.newSetFromMap(new ConcurrentHashMap<...>())

这通常是普通Set的实现方式（HashSet实际上是HashMap的修改包装器）。它既提供了ConcurrentHashMap的性能/并发优势，又没有像ConcurrentSkipListSet（排序）、COW列表（复制每个修改）或并发队列（FIFO/LIFO排序）等额外功能。

编辑：我没有看到@bhspencer在原帖中的评论，抱歉抢了风头。

- user2982130

Answer 4

基于哈希的Hashset比List更好。 使用LinkedList可以很好地添加最后一个元素和删除第一个元素。 由于ArrayList是基于数组索引的，因此搜索速度会更快。

谢谢。

- Shailendra Singh