多线程编程中有用的数据结构

Question

除了可以在多线程程序中使用的众所周知的数据结构，如并发堆栈、并发队列、并发列表、并发散列。是否还有其他鲜为人知但有用的数据结构可用于并行/多线程编程。

即使它们是经过一些优化的上述数据结构的一些不同版本，也请分享。

请务必包括一些参考资料。

编辑：将继续列出我发现的内容

1）ConcurrentCuckooHashing（ConcurrentHashing的优化版）

2) ConcurrentSkipList

Answer 1

如果您不介意，我将尝试用 JDK 中的示例来回答：

列表：

• CopyOnWriteArrayList 是一个列表，通过在每次修改列表时重新创建后备数组来实现线程安全使用；
• 返回的列表Collections.synchronizedList()是线程安全的，因为它们包括大多数操作的排他锁定（迭代是一个例外）；
• ArrayBlockingQueue. 队列大小固定，当没有任何东西可以拉出或没有空间可以推入时会阻塞；
• ConcurrentLinkedQueue 是一个基于Michael-Scott算法的无锁队列；
• 并发堆栈，基于 Treiber 算法。令人惊讶的是，我没有在 JDK 中找到它；

套：

• 套装，由工厂返还，Collections.newSetFromMap()并带有背衬ConcurrentHashMap。使用这些集合，您可以确定它的迭代器不会出现ConcurrentModificationException，并且它们使用条带化技术来锁定它 - 不需要锁定所有集合来执行某些操作。例如，当你要添加元素时，只会hashCode()锁定元素确定的集合中的部分；
• ConcurrentSkipListSet. 基于跳过列表数据结构的线程安全集；
• 集合，由 返回Collections.synchronizedSet()。关于类似列表的所有要点都适用于此。

地图：

• ConcurrentHashMap我已经提到并解释过了。条带化基于项目键；
• ConcurrentSkipListMap. 基于跳过列表的线程安全映射；
• 地图，由 返回Collections.synchronizedMap()。关于类似列表和地图的所有要点都适用于此。

这些或多或少是用于多线程使用的标准数据结构，对于大多数实际任务来说应该足够了。我还发现了一些您可能会觉得有用的链接：

• 免等待红黑树；
• 一篇关于并发数据结构的大文章；
• .NET 中使用的并发结构和同步原语；
• 关于事务性内存的文章- 不是真正的数据结构，但由于您的请求用于学术目的，值得一读；
• 另一篇关于事务性内存的文章- 易于阅读，但它是俄语的。如果你能读懂，绝对值得一读；