问题标签 [skip-lists]

我开始研究 ConcurrentSkipListSet。

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

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

我有两个问题：

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

我被要求设计一个代表字典的数据结构。字典包含具有不同键号的项目。数据结构应在 O(1) 时间内支持以下操作：insert(x)、delete(x)、findMin()、findMax()、successor(x)、previous(x)。search(x) 操作也应该在 O(log n) 时间内进行。

作业是针对以下主题进行的：跳过列表、哈希表和堆。我想最好的结构将是一个跳过列表，但我找不到在 O(1) 中实现插入和删除的方法。有什么建议么？

我正在实施 STL 风格的跳过列表。内部节点类型如下：

内部节点中有 std::list 。当我想将 __skiplist_node 推回列表中时。在运行时构造跳过列表时。它遇到段故障。调试回溯显示：

我想知道的是如何为这个内部节点动态分配？</p>

以下是完整的代码：

根据其他地方关于堆栈溢出的建议，我查看了 John Shipman 关于跳过列表的优秀文章以及关于他的 python 实现的文档。代码都在那里，但为了解释的目的，它被分解成片段。这对网页来说很好，但我宁愿不必从那里提取文件。我找到的每个链接都指向同一页面。

pip install pyskip安装一些其他的实现。我不知道还能去哪里看。

给定 randomLevel() 函数：

这用于确定在插入节点时他将获得什么级别，根据 pugh 的文章，列表的最大级别 a 大于 k 的概率等于 1 - (1 - p^k )^n并且文章还说这个表达式最多为 np^k （因此对于那些知道这篇文章的人来说，预期的最大水平最多为 L(n) + 1/(1-p)..）。

我在理解这个数字的来源时遇到了严重的麻烦，因为我所能想到的就是 P(j 级的节点) = (p^j) (1-p) => P(大于 k 的节点) = 1 - sum(P(第 i 层中的节点), i=1 到 i=k) 这导致 P(最大级别 > k) = P( 级别 > k 中的节点之一) = n P(节点在大于 k 的级别) = ... = n*(1+p*(p^k-1))

帮助 ？？？谢谢 ：）

在 REDIS 文档中，它指出对排序集的插入和更新操作是 O(log(n))。

在这个问题上，他们指定了有关底层数据结构的更多细节，即跳过列表。

但是，有一些特殊情况取决于我不熟悉的 REDIS 实现。

• 在排序集的头部或尾部添加可能不是 O(log(n)) 操作，而是 O(1)，对吧？这个问题似乎同意保留意见。
• 即使排序没有改变，更新成员的分数仍然是 O(log(n)) 或者因为您取出元素并以稍微不同的分数再次插入它，或者因为您必须检查排序是否'不改变，因此差异仅在于插入或更新分数之间的持续操作。正确的？我真的希望我在这种情况下是错的。

任何见解都将受到欢迎。

Java 集合框架中的大多数类默认情况下是不同步的，但如果您需要它们是线程安全的，可以将它们制成同步的东西。同步有性能损失，所以如果你写的东西不需要是线程安全的，你最好使用非同步版本。

但ConcurrentSkipListMap不遵循这个方案。没有不同步的版本。为什么SkipListMap不需要线程安全的应用程序没有更快的非同步，与集合框架的其余部分一致？

我能想到的是，跳过列表的最简单实现已经是线程安全的，因此拥有同步版本不会有性能损失。这会有些道理，但是看一下源代码并不能完全证明这一点。尽管代码中没有synchronized块，但 Javadoc 确实以

此类实现 SkipLists 的并发变体...

这表明它正在不遗余力地修改算法以使其成为线程安全的。后来，我们读到

这些列表中的基本思想是在删除时标记已删除节点的“下一个”指针，以避免与并发插入冲突......

这听起来好像涉及某种开销。

仅仅是这个开销是如此之小以至于不值得拥有一个非线程安全的SkipListMap吗？

我正在尝试使用细粒度的锁定机制在 c 中实现基于锁定的跳过列表。在运行代码时，应用的锁定机制似乎是粗粒度的。我已经在前面的节点中放置了锁，用于插入，使用在节点结构中定义的 pthread_mutex_t 锁变量，并在使用后释放它们。整个列表没有被锁定，只有节点被锁定，它似乎仍然在实现粗粒度锁定机制。下面提供了完成锁定机制的代码片段。执行是否错误？

在skiplist编码中遵循的论文是

编辑：将节点插入到跳过列表的代码

所以我看到了这个关于概率跳过列表空间消耗的问题：（答案）

但我认为提问者不清楚他想要一种预期的方法还是最坏的方法。

所以我想再次将这个问题提出来辩论，我会解释我为什么感到困惑。

需要明确的是 - 我正在寻找最坏情况下概率跳过列表的空间复杂度。这就是我的想法：

一方面，我们假设最大级别数是 log(n)，很容易推断，在最坏的情况下，每个级别可能有 n 个节点，这会给我们 O(n logn)。另一方面，我假设可能有超过 log(n) 个级别（例如列表），我们将其设置为 n - 然后我们得到 n n => O(n^2)

但！我不明白为什么我们有权限制级别，如果新级别取决于抛硬币，我们假设在最坏的情况下我们将获得无限次正面（这意味着一个新级别）然后我们不同它甚至没有界限？！我很困惑。

我在跳过列表中插入时遇到问题。当我将元素插入跳过列表时，它只会将元素添加到较低级别，而不是较高级别。当我试图进入下层时，它会爆炸。感谢你的帮助。谢谢你。