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

Question

我开始研究ConcurrentSkipListSet.

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

我想象它(可能的变种):

我有两个问题:

1. SkipList如何与并发相关联？
2. 为什么exis不是这种数据结构的并发变体？

Answer 1

你的跳过列表有点偏,看起来更像是:

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

底部开始就像一个链接列表,你已经得到了......但更多地将它们看作是每个级别链接的塔.这里的问题是,如果你想找到7,你可以从1 - > 4 - > 6 - > 9(oops,nope)跳到 7.这使你可以用链表来近似平衡二叉树.

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

对跳过列表进行了详细介绍,其中介绍了跳过列表:平衡树的概率替代方案,它显示了它的工作原理和各种算法.其中包括"表2 - 不同算法的计时和实现",其中显示跳过列表的运行速度要快得多,尽管其中一些是由于它们使用的特定数据.

在"跳过列表的附加工作"中

我已经描述了一组算法,允许多个处理器同时更新共享内存中的跳过列表[Pug89a].这种算法比并发平衡树算法简单得多.它们允许无限数量的读者和n个繁忙的作者在n个元素的跳过列表中,几乎没有锁争用.

这导致了另一篇题为" 并发维护的跳过列表"的文章,该文章专门研究了一个由多个读者和作者组成的结构.这将考虑编写者需要等待锁定的时间以及整个结构的加速速度.

因此,由于这些属性,它允许结构中的多个读取器和编写器具有最小的锁定和结构平衡.

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

相关阅读:

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