ConcurrentSkipListSet 在什么时候有用？

data-structures collections concurrency java

2022-08-31 10:54:45

我刚刚在Java 6 API上看到了这个数据结构，我很好奇它什么时候会成为有用的资源。我正在为scjp考试而学习，我没有看到Kathy Sierra的书上涵盖它，即使我看到过提到它的模拟考试问题。

答案 1

ConcurrentSkipListSet 和 ConcurrentSkipListMap 在您需要一个由多个线程访问的排序容器时非常有用。这些本质上是并发代码的 TreeMap 和 TreeSet 的等效项。

JDK 6 的实现基于 IBM 的 Maged Michael 的高性能动态无锁哈希表和基于列表的集合，这表明您可以使用比较和交换（CAS）操作以原子方式对跳过列表实现许多操作。这些是无锁的，因此在使用这些类时，您不必担心（对于大多数操作）的开销。synchronized

目前，Java 中没有基于红黑树的并发 Map/Set 实现。我浏览了一下文献，发现有几篇论文显示并发RB树的性能优于跳过列表，但很多这些测试都是用事务内存完成的，目前任何主要架构的硬件都不支持事务内存。

我假设JDK的人在这里有一个跳过列表，因为实现是众所周知的，因为让它无锁是简单和可移植的（使用CAS）。如果有人想澄清，请做。我很好奇。

答案 2

跳过列表是排序列表，并且使用 log（n）性能进行有效修改。在这方面，它就像TreeSet。但是没有并发树集。我听到的是跳过列表非常容易实现，这可能就是原因。

无论如何，当您需要一个并发，排序和高效的集时，您可以使用ConversateSkipListSet