我刚刚在Java6API上看到了这个数据结构,我很好奇它什么时候会是一个有用的资源。我正在为scjp考试做准备,但我没有看到凯西·塞拉的书中提到了这一点,尽管我见过提到这一点的模拟试题。
发布于 2009-12-15 08:56:09
当您需要一个将由多个线程访问的排序容器时,ConcurrentSkipListSet和ConcurrentSkipListMap非常有用。它们本质上是并发代码的TreeMap和TreeSet的等价物。
JDK6的实现是基于IBM的Maged的High Performance Dynamic Lock-Free Hash Tables and List-Based Sets的,这表明您可以使用compare and swap (CAS)操作自动实现跳过列表上的许多操作。这些类是无锁的,所以在使用这些类时,您不必担心synchronized
(对于大多数操作)的开销。
目前在Java语言中还没有基于Red-Black tree的并发Map/Set实现。我查阅了一些文献,发现了一个couple papers,它显示并发RB树的性能优于跳跃列表,但这些测试中的许多都是使用transactional memory完成的,目前任何主流架构的硬件都不支持它。
我猜想JDK的家伙之所以在这里使用跳过列表,是因为它的实现是众所周知的,而且使它无锁是简单和可移植的(使用CAS)。如果有人愿意澄清,请说。我很好奇。
发布于 2009-12-15 08:35:31
跳过列表是经过排序的列表,修改起来非常有效,性能为log(n)。在这一点上,它就像TreeSet。但是,没有ConcurrentTreeSet。我听说跳过列表很容易实现,这可能就是原因。
无论如何,当您需要一个并发的、有序的和有效的集合时,您可以使用ConcurrentSkipListSet
发布于 2009-12-15 08:36:36
当您需要一个可以由多个线程同时安全地访问的集合时,它们非常有用。它还通过弱一致性提供了不错的性能--在遍历集合时可以安全地进行插入,但不能保证迭代器将看到该插入。
https://stackoverflow.com/questions/1904439
复制相似问题