我想知道这里是否有人曾经使用过跳过列表。它看起来与平衡二叉树具有大致相同的优势，但实现起来更简单。如果有，您是自己编写的，还是使用预先编写的库（如果有，它的名称是什么）？
Head Geek
问问题
6689 次
7 回答
17
我的理解是，它们不是二叉树（例如红黑树）的有用替代品，而是用于数据库使用的B 树，因此您可以将级别的# 降低到可行的最小值并处理w/ base-K 日志而不是 base-2 日志以获得性能特征。概率跳过列表的算法（恕我直言）比相应的 B 树算法更容易正确。另外还有一些关于无锁跳过列表的文献。几个月前我考虑过使用它们，但后来放弃了发现HDF5库的努力。
有关该主题的文献：
比尔·普格的论文：
非学术论文/教程：
- Eternally Confuzzled（对几种数据结构进行了一些讨论）
- Thomas A. Anastasio 的“跳过列表”
于 2008-12-08T17:01:26.507 回答
9
实际上，对于我的一个项目，我正在实现自己的完整 STL。我使用了一个跳过列表来实现我的std::map. 我选择它的原因是它是一个简单的算法，它非常接近平衡树的性能，但具有更简单的迭代能力。
此外，Qt4 的 QMap也是一个跳过列表，这是我在std::map.
于 2008-10-24T19:31:45.230 回答
8
几年前，我为一个概率算法类实现了我自己的。我不知道任何库实现，但已经很长时间了。实现起来非常简单。我记得它们对于大型数据集有一些非常好的属性，并且避免了一些重新平衡的问题。我认为实现也比一般的二进制尝试更简单。这里有一个很好的讨论和一些示例 C++ 代码：
http://www.ddj.us/cpp/184403579?pgno=1
还有一个带有运行演示的小程序。可爱的 90 年代 Java 光泽在这里：
http://www.geocities.com/siliconvalley/network/1854/skiplist.html
于 2008-10-24T20:16:45.667 回答
7
Java 1.6 (Java SE 6) 将ConcurrentSkipListSet和ConcurrentSkipListMap引入了集合框架。所以，我推测那里有人真的在使用它们。
Skiplist 往往在多线程情况下提供的锁争用要少得多，并且（概率上）具有类似于树的性能特征。
请参阅William Pugh的原始论文[pdf]。
于 2008-12-05T05:17:53.827 回答
2
几年前，我实现了一个变体，我称之为规则引擎的反向跳过列表。大致相同，但参考链接从最后一个元素向后运行。
这是因为插入最有可能朝向集合后端的已排序项目会更快。
它是用 C# 编写的，经过几次迭代才能成功运行。
于 2008-10-24T19:29:55.200 回答
2
跳过列表具有与二分搜索算法相同的搜索对数时间界限，但它扩展了该性能以在插入或删除条目时更新方法。然而，跳跃列表的边界是预期的，而排序表的二进制搜索具有最坏情况的边界。
于 2020-05-12T14:06:05.497 回答
1
跳过列表很容易实现。但是，在插入和删除的情况下调整跳过列表上的指针，你必须小心。没有在真正的程序中使用它，但是做了一些运行时分析。跳过列表不同于搜索树。相似之处在于，它给出了一段时间字典操作的平均 log(n)，就像展开树一样。它比不平衡的搜索树好，但并不比平衡的树好。
每个跳过列表节点都有前向指针，代表当前->下一个（）连接到不同级别的跳过列表。通常，此级别的上限为 ln(N)。因此，如果 N = 100 万，则级别为 13。将有那么多指针，在 Java 中，这意味着用于实现引用数据类型的指针数量。作为平衡搜索树的地方更少，它提供相同的运行时间！！。
SkipList Vs Splay Tree Vs Hash正如为字典查找操作所描述的那样，锁剥离哈希表将在 0.010 ms 以下给出结果，其中 splay 树给出 ~ 1 ms 和跳过列表 ~ 720 ms。
于 2012-04-06T05:53:57.200 回答