问题标签 [skip-lists]

我需要一个非常快速（插入、删除、包含）的高度并发列表，可以使用比较器/可比较器进行排序。

现有的 ConcurrentSkipListSet 将是理想的，如果它是一个列表而不是一个集合。我需要在数据结构中插入多个相等的项目。

如果找不到更好的东西，我目前正在考虑使用 LinkedDeque，但是这种结构比高争用的跳过列表要慢得多。

有什么建议么？

编辑：我真正需要的，最低限度，是使用 compareTo 排序的东西，可以同时插入并且可以使用对象标识删除/获取项目。评论中提到的所有其他并发要求仍然适用。

众所周知， skip list是一种非常迷人的数据结构，具有O(logn)插入/搜索功能，易于在复杂（AVL、红黑）树上实现，并且它已经在各种应用程序和框架中实现。

.NET 不知道这种数据结构（虽然 java 已经实现） ，他们有什么明显的原因吗？

我试图在数据库中找到相同的登录 id 用户。

首先，我将每个用户都放到跳过列表中，然后我想逐个比较。我的问题是如何获得 Skiplist 上的关键值。

我的一段代码在这里：

有人可以为此提供提示，我是这种语言的新手。提前致谢。

编辑：现在它正在工作

pragma runLim,0这一行是为了避免执行时间警告。

我在我正在实现的跳过列表的搜索方法中不断看到空指针异常。

例外的行是：

我几乎从这个页面复制了这个，所以我不确定它会有什么问题。

有没有办法找到一些使用特定集合的 Java 应用程序。我实现了自己的并发跳过列表，并希望将其“替换”到一个应用程序中，在该应用程序中ConcurrentSkipListSet使用 Java 集合来查看我的实现和ConcurrentSkipListSet.

我知道我可以对两个跳过列表实现（我的和 Java 的）进行基准测试，但我想看看在真实场景中有什么区别。

关于如何找到这样的应用程序的任何想法？（*我在 Java 标准库中搜索，但使用 找不到任何东西ConcurrentSkipList）。

在我见过的大多数跳过列表的实现中，它们使用随机算法来决定是否必须将元素复制到上层。

但我认为在每个级别使用奇数索引元素在上层都有副本会给我们带来对数搜索复杂性。为什么不用这个？

例如：数据：1 2 3 4 5 6 7 8 9

跳过列表：

1--------------------

1--------------------9

1--------5----------9

1----3---5----7----9

1-2-3-4-5-6-7-8-9

我正在阅读有关跳过列表和 MemSQL 的内容，想知道为什么跳过列表在数据库中没有得到更广泛的使用？使用跳过列表有什么主要缺点吗？

假设给我一个跳过列表，顺序为 3。

所以本质上它是一个1-2 skip-list.

如果我想50通过自上而下的插入算法插入，它会100在落入Headand150和 insert 50right before之间的间隙之前提高节点的级别100。现在将发生违规，因为 和 之间没有节点100，而在该间隙中150应该至少有一个高度为.h-1minlimit=1

我究竟做错了什么？

我在这个主题下浏览了java中的数据结构，Skip list我遇到了以下问题：

在 , 的跳过列表中n nodes，对于每个k和i满足1 ≤ k ≤lg n和1 ≤ i ≤ n/2k–1⎦ – 1，位置2k–1·i的节点指向位置2k–1· ( i + 1) 中的节点。这意味着每第二个节点指向前两个位置的节点，每四个节点指向前四个位置的节点，依此类推，如图 3.17a 所示。这是通过在列表中的节点中使用不同数量的参考字段来实现的：一半的节点只有一个参考字段，四分之一的节点有两个参考字段，八分之一的节点有三个参考字段，依此类推在。参考字段数表示每个节点的级别，级别数为maxLevel = ⎣lg n⎦ + 1。

图为： 一个具有 (a) 均匀分布和 (b) 不均匀分布的不同层级节点的跳过列表；(c) 清晰显示参考节点的跳过列表。

我不明白数学部分以及 sktip 列表甚至节点到底是什么？

寻找调试随机程序的一般原则，以及在 Python 中执行此操作的任何具体指南。

例如，考虑以下在跳过列表中的插入实现：

这insert取决于随机掷硬币。因此，该函数中的错误变得难以检测，因为它可能会或可能不会出现在每次运行中。在这种情况下，我们如何简化调试？