跳过列表是使用列表实现的。

对于单链表和双链表存在无锁解决方案，但是对于任何O(logn)数据结构，没有直接只使用CAS的无锁解决方案。

但是，您可以使用基于CAS的列表来创建跳跃列表。

(请注意，使用CAS创建的MCAS允许任意数据结构，并且使用MCAS创建了概念证明红黑树)。

所以，尽管它们很奇怪，但它们却非常有用:-)

跳过列表确实具有锁剥离的优势。但是，最短时间取决于新节点的级别如何确定。这通常是使用Random()完成的。在56000个单词的字典上，跳跃表比展开树花费更多的时间，而树比哈希表花费更多的时间。前两个不能匹配哈希表的运行时。此外，哈希表的数组也可以以并发的方式进行锁剥离。

当需要引用的局部性时，使用跳过列表和类似的有序列表。例如:在应用程序中查找日期前后的航班。

内存中二叉搜索展开树非常好，使用频率也更高。

跳过列表Vs展开树Vs哈希表运行时的字典查找op

在实践中，我发现在我的项目中，b -树的性能比跳过列表要好。跳跃表似乎更容易理解，但实现b -树并不难。

我所知道的一个优点是，一些聪明的人已经想出了如何实现只使用原子操作的无锁并发跳过列表。例如，Java 6包含ConcurrentSkipListMap类，如果您不喜欢的话，可以读取它的源代码。

但是写一个并发b树的变体也不是很难——我看到别人做过——如果你在沿着树向下走的时候先发制人地拆分和合并节点，“以防万一”，那么你就不必担心死锁，而且一次只需要在树的两个层次上持有一个锁。同步开销会稍微高一些，但是b树可能更快。

从你引用的维基百科文章中:

Θ(n) operations, which force us to visit every node in ascending order (such as printing the entire list) provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to O(log n) search time. [...] A skip list, upon which we have not recently performed [any such] Θ(n) operations, does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure

编辑:所以这是一种权衡:跳过列表使用更少的内存，但风险是它们可能退化为不平衡的树。

此外，除了给出的答案(易于实现，与平衡树的性能相结合)。我发现实现顺序遍历(向前和向后)要简单得多，因为跳过列表在其实现中实际上有一个链表。

跳过列表是使用列表实现的。

对于单链表和双链表存在无锁解决方案，但是对于任何O(logn)数据结构，没有直接只使用CAS的无锁解决方案。

但是，您可以使用基于CAS的列表来创建跳跃列表。

(请注意，使用CAS创建的MCAS允许任意数据结构，并且使用MCAS创建了概念证明红黑树)。

所以，尽管它们很奇怪，但它们却非常有用:-)