java - 为什么不存在 SkipList 的非并发版本

Question

我开始研究 ConcurrentSkipListSet。

从一开始我就试图了解 SkipList 是什么？

我是这样想的(可能的变体):

我有两个问题:

1. SkipList 与并发性有何关系？
2. 为什么不存在 此数据结构的并发变体？

Answer 1

你的跳过列表有点偏离，它看起来更像:

^{_{来自 http://en.wikipedia.org/wiki/File:Skip_list.svg}}

底部开始时像一个链接列表，您已经知道了……但更多地将它们视为每个级别都链接到的塔。这里的问题是，如果你想找到 7，你可以跳过从 1 -> 4 -> 6 -> 9(糟糕，不)到 7。这​​让你可以近似平衡二叉树链表。

对于红黑树或 AVL 树，当需要修改结构时，必须将其完全锁定，以便重新安排结构。另一方面，跳过列表可以在没有全局锁定的情况下“重新排列”。删除 7 只需要将指向它的链接更改为指向下一个元素，这只需要对 6 元素进行写锁定，而不是整个结构。

介绍跳跃列表的好书是 Skip Lists: A Probabilistic Alternative to Balanced Trees它展示了它是如何工作的以及各种算法。在这个是“表 2 - 不同算法的时间和实现”，它显示跳跃列表运行得更快，尽管其中一些是因为它们使用的特定数据。

在“关于跳过列表的其他工作”中

I have described a set of algorithms that allow multiple pro- cessors to concurrently update a skip list in shared memory [Pug89a]. This algorithms are much simpler than concurrent balanced tree algorithms. They allow an unlimited number of readers and n busy writers in a skip list of n elements with very little lock contention.

这导致另一篇文章标题为 Concurrent Maintenance of Skip Lists它专门研究了一个由多个读者和作者共同完成的结构。这涉及到编写器需要等待锁定多长时间以及整个结构的加速速度。

因此，由于这些属性，它允许结构中的多个读取器和写入器使用最少的锁定和结构平衡。

至于Java库中为什么没有非并发跳表？这意味着将代码复制到另一个包(这很糟糕)并且不会真正获得任何东西。没有人说你不能在不受并发问题限制的地方使用并发包。问题是他们需要两种类型的 Map 来进行并发工作，O(1) HashMap 和 O(log n) 树。由于 TreeMap 无法实现良好的并发实现，他们决定将其更改为 SkipList。

相关阅读:

• > How to implement lock-free skip list
• > lock-free skiplist with rank operation