最适合快速并发插入的Java数据结构

Question

我的使用场景如下：我有10个线程同时写入一个数据结构。数据结构中元素的顺序并不重要，所有元素都是唯一的。我只会在最后一次从这个数据结构中读取。

什么是最快的本地Java数据结构来适应这个目的？从我的阅读中，似乎 Collections.synchronizedList 可能是最好的选择？

- John Roberts

---

填充（filling）的意思是你只需要快速写入（fast write）还是快速读取（fast read）也要快速呢？ - SMA

Collections.synchronizedList 可以使用，但您仍需要选择支持列表（例如 ArrayList、LinkedList 等）。由于元素是唯一的，您也可以尝试使用诸如 ConcurrentSkipListSet 之类的集合，它将强制执行唯一性（也许对您有用？）。性能完全取决于您的读/写模式。最好的方法可能是自己测试。 - Stephen Rosenthal

另一个可能的方法：完全避免同步，将数据写入10个不同的集合（每个线程一个），只有在最后进行单次读取时才将它们合并。 - Stephen Rosenthal

线程需要“看到”其他线程写入的值吗？ - David Soroko

@SMA 在最开始。 - John Roberts

Answer 1

我有10个线程同时写入一个数据结构。

我认为最好使用每个线程单独的数据结构。这样就不需要在线程之间同步，而且对CPU缓存的友好度也更高。

最后它们可以合并。

至于底层结构：如果元素大小固定，数组/向量是最好的选择。合并它们只需要复制它们所占用的一段内存块，具体取决于实现方式——但列表始终会比较慢。

- Danny_ds

Answer 2

不需要在列表上同步，因为每个线程都可以在其本地副本上工作，并且最终可以将所有线程的结果合并成一个最终列表。

如果使用JDK7及以上版本，则可以使用fork和join来创建简单的列表，在每个分叉任务中，最后在join阶段将其连接到主列表中。

如果使用JDK6，则可以使用计数器锁（CountDownLatch），计数器初始值为10。每个线程在向其从主控制线程传递的各自列表中写入后，都会倒计时锁定，然后在主控制器中，一旦所有线程完成，就会将所有结果组合成一个结果。

- SMA