跳跃表vs.二叉搜索树

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

Θ(n)操作，它迫使我们以升序访问每个节点(例如打印整个列表)，提供了以最佳方式执行跳过列表的级别结构的幕后去随机化的机会，使跳过列表的搜索时间达到O(log n)。[…] 一个跳跃表，我们还没有 最近执行的[任何此类]Θ(n)操作，没有 提供相同的绝对最坏情况 性能保证更多 传统平衡树数据 结构，因为它总是 有可能(尽管非常低 概率) 构建跳跃表将产生一个 结构不平衡

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

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

跳过列表更适合并发访问/修改。Herb Sutter写了一个关于并发环境中的数据结构的文章。它有更深入的信息。

二叉搜索树最常用的实现是红黑树。同时出现的问题是当树被修改时，它经常需要重新平衡。重新平衡操作可能会影响树的大部分，这将需要在许多树节点上使用互斥锁。在跳跃列表中插入一个节点要本地化得多，只有直接链接到受影响节点的节点才需要被锁定。

Jon Harrops的评论更新

我读了弗雷泽和哈里斯的最新论文。如果你对无锁数据结构感兴趣，这是很好的东西。本文主要研究事务内存和一个理论操作多词比较交换MCAS。这两种方法都是在软件中模拟的，因为目前还没有硬件支持它们。他们能够在软件中构建MCAS，这让我印象深刻。

我没有发现事务性内存的东西特别引人注目，因为它需要一个垃圾收集器。此外，软件事务存储器也存在性能问题。然而，如果硬件事务内存变得普遍起来，我会非常兴奋。最后，它仍然处于研究阶段，在未来十年左右的时间里不会用于生产代码。

在8.2节中，他们比较了几种并发树实现的性能。我将总结他们的发现。值得下载pdf，因为它在第50、53和54页有一些非常有用的图表。

• 锁定跳跃表是疯狂的快。它们在并发访问数量上的可伸缩性非常好。这就是跳跃表的特殊之处，其他基于锁的数据结构在压力下往往会崩溃。
• 无锁跳跃表始终比锁定跳跃表快，但仅仅快一点点。
• 事务性跳过列表始终比锁定和非锁定版本慢2-3倍。
• 在并发访问下锁定红黑树 croak。它们的性能随着每个新并发用户的增加而线性下降。在已知的两种锁定红黑树实现中，有一种在树再平衡过程中具有全局锁。另一种使用花哨的(复杂的)锁升级，但仍然没有明显优于全局锁版本。
• 无锁红黑树不存在(不再为真，请参见更新)。
• 事务性红黑树可与事务性跳过列表相比较。这非常令人惊讶，也非常有希望。事务性内存，虽然较慢，但更容易写入。它可以像在非并发版本上快速搜索和替换一样简单。

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

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

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

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

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

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

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

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

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

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

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

跳过列表Vs散列树Vs哈希表运行时在字典上查找op

首先，你不能公平地比较一个随机数据结构和一个给你最坏情况保证的数据结构。

跳跃表等价于随机平衡二叉搜索树(RBST)，在Dean和Jones的探索跳跃表和二叉搜索树之间的对偶性中有更详细的解释。

另一方面，你也可以有确定性跳跃表来保证最坏情况下的性能，参见门罗等人。

与上面的一些说法相反，您可以拥有在并发编程中工作良好的二叉搜索树(BST)实现。以并发为中心的bst的一个潜在问题是，您无法像从红黑树(RB)中那样轻松地获得相同的平衡保证。(但是“标准的”，即随机的跳跃列表也不能保证这些。)在始终保持平衡和良好(并且易于编程)并发访问之间存在权衡，因此放松 RB树通常在需要良好并发时使用。放松在于不立即重新平衡树。对于一个有点过时(1998)的调查，请参阅Hanke的“并发红黑树算法的性能”(ps.gz)。

其中一个最近的改进是所谓的彩色的树(基本上你有一些权重，这样黑色将是1，红色将是0，但你也允许介于两者之间的值)。半音树如何对抗跳跃表?让我们看看Brown等人无阻塞树的通用技术(2014)是怎么说的:

， 128线程，我们的算法优于Java的非阻塞skiplist Bronson等人的基于锁的AVL树增长了63%至224%，使用软件事务内存(STM)的RBT增长了13至134倍

编辑补充:Pugh的基于锁的跳跃表，在Fraser和Harris (2007) “无锁并发编程”中进行了基准测试，接近他们自己的无锁版本(在这里的顶部回答中充分强调了这一点)，也为良好的并发操作进行了调整，参考Pugh的跳跃表的并发维护，尽管是以相当温和的方式进行的。然而，一篇由Herlihy等人撰写的更新/2009年的论文一种简单的乐观跳表算法提出了一种据称比Pugh的更简单的基于锁的并发跳过表实现，批评Pugh没有提供足够令人信服的正确性证明。撇开这种(可能太迂迂的)不安不谈，Herlihy等人表明，他们更简单的基于锁的跳跃列表实现实际上无法像JDK的无锁实现那样进行扩展，但仅适用于高争用(50%插入，50%删除和0%查找)……弗雷泽和哈里斯根本没有测试;Fraser和Harris只测试了75%的查找，12.5%的插入和12.5%的删除(在有大约500K个元素的跳跃表上)。Herlihy等人的更简单的实现也接近于JDK在他们测试的低争用情况下的无锁解决方案(70%的查找，20%的插入，10%的删除);在这种情况下，他们实际上打败了无锁解决方案，当他们把跳跃表做得足够大时，即从200K到2M个元素，这样任何锁上的争用概率都可以忽略不计。如果Herlihy等人能够克服对Pugh的证明的困扰并测试他的实现，那就太好了，但遗憾的是他们没有这样做。

EDIT2:我找到了一个(2015年出版的)所有基准的母矿:Gramoli的“关于同步，比你想知道的还要多。同步工作台，测量同步对并发算法的影响:这里是一个与这个问题相关的摘录图像。