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

Question

我开始研究 ConcurrentSkipListSet。

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

我想是这样（可能的变体）：

我有两个问题：

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

Answer 1

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

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

底部开始像一个链接列表，你已经明白了......但更多地将它们视为连接到每个级别的塔。这里的问题是，如果你想找到 7，你可以从 1 -> 4 -> 6 -> 9 （哎呀，不）跳到7。这​​让你可以用链表近似平衡二叉树。

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

跳过列表的一个很好的读物是跳过列表：平衡树的概率替代方案，它展示了它的工作原理和各种算法。其中包含“表 2 - 不同算法的时序和实现”，它显示跳过列表运行得相当快，尽管其中一些是因为它们使用的特定数据。

在“跳过列表的附加工作”中

我已经描述了一组允许多个处理器同时更新共享内存中的跳过列表的算法[Pug89a]。这种算法比并发平衡树算法简单得多。它们允许在 n 个元素的跳过列表中无限数量的读取器和 n 个忙碌的写入器，并且锁争用非常少。

这导致了另一篇题为“跳过列表的并发维护”的文章，该文章专门研究了一个由多个读者和作者共同完成的结构。这涉及到编写器需要等待锁定多长时间以及整个结构的加速速度有多快。

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

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

相关阅读：

• 如何实现无锁跳过列表
• 具有等级操作的无锁跳过列表

Answer 2

1. 任何数据结构都与并发无关。请参阅 collections 包中的 Java List 实现。LinkedList 不是线程安全的，但您可以使用 Collections 类来实现。
2. 为 SkipList 编写实现的人决定将线程安全构建到类中。那是一个实施决定。