什么时候ConcurrentSkipListSet有用？

Question

我刚刚在Java 6 API上看到了这个数据结构，我很好奇它何时会成为一个有用的资源。我正在为scjp考试而学习，尽管我已经看过提及它的模拟考题，但我没有看到它在凯西塞拉利斯的书上。

Answer 1

ConcurrentSkipListSet和ConcurrentSkipListMap在您需要一个可以被多个线程访问的排序容器时非常有用。这些实质上是并发代码的TreeMap和TreeSet的等价物。

JDK 6的实现基于Maged Michael在IBM的High Performance Dynamic Lock-Free Hash Tables and List-Based Sets，它表明您可以使用compare and swap (CAS)操作以原子方式在跳过列表上执行大量操作。这些都是无锁的，因此当您使用这些类时，您不必担心​​（对于大多数操作）的开销。

目前没有基于Red-Black tree的基于Java的并发Map/Set实现。我仔细查看了一下文献，发现一个couplepapers表明并发RB树性能优于跳过列表，但是这些测试中有很多是用transactional memory完成的，目前在任何主要体系结构的硬件上都不支持这些测试。

我假设JDK家伙在这里使用了一个跳过列表，因为实现是众所周知的，因为它使得它无锁是简单和便携的（使用CAS）。如果有人关心澄清，请做。我很好奇。

Answer 2

跳过列表是排序列表，并有效地用log（n）性能进行修改。在这方面它就像TreeSet。但是没有ConcurrentTreeSet。我听到的是跳过列表很容易实现，这可能是为什么。

无论如何，当你需要一个并发的，分类高效的设置，你可以使用ConcurrentSkipListSet

Answer 3

这些，当你需要一组可以安全地被多个线程同时访问是有用的。它还通过弱一致性提供了良好的性能 - 在遍历Set时插入可以安全地进行，但不能保证您的Iterator将看到该插入。

Answer 4

ConcurrentSkipListMap是我需要为本地缓存实现复制层时的一个奇妙发现。 Map方面实现了缓存，而List方面让我跟踪对象在缓存中出现的顺序。该列表的“跳过”方面使得从列表中的一个位置移除一个对象并在缓存中替换它时将其对齐到最终效率。